CryptoDB
Syndrome Decoding Estimator
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | PKC 2022 |
| Abstract: | The selection of secure parameter sets requires an estimation of the attack cost to break the respective cryptographic scheme instantiated under these parameters. The current NIST standardization process for post-quantum schemes makes this an urgent task, especially considering the announcement to select final candidates by the end of 2021. For code-based schemes, recent estimates seemed to contradict the claimed security of most proposals, leading to a certain doubt about the correctness of those estimates. Furthermore, none of the available estimates includes most recent algorithmic improvements on decoding linear codes, which are based on information set decoding (ISD) in combination with nearest neighbor search. In this work we observe that \emph{all} major ISD improvements are build on nearest neighbor search, explicitly or implicitly. This allows us to derive a framework from which we obtain \emph{practical} variants of all relevant ISD algorithms including the most recent improvements. We derive formulas for the practical attack costs and make those online available in an easy to use estimator tool written in python and C. Eventually, we provide classical and quantum estimates for the bit security of all parameter sets of current code-based NIST proposals. |
Video from PKC 2022
BibTeX
@inproceedings{pkc-2022-31701,
title={Syndrome Decoding Estimator},
publisher={Springer-Verlag},
author={Andre Esser and Emanuele Bellini},
year=2022
}