CryptoDB
Asymptotics and Improvements of Sieving for Codes
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2024 |
| Abstract: | A recent work of Guo, Johansson and Nguyen (Eprint'23) proposes a promising adaptation of Sieving techniques from lattices to codes, in particular claiming concrete cryptanalytic improvements on various schemes. The core of their algorithm reduces to a Near-Neighbor Search (NNS) problem, for which they devise an ad-hoc approach. In this work we aim for a better theoretical understanding of this approach. First by providing an asymptotic analysis which is not present in the original paper. Second, we propose a more systematic use of known NNS machinery, namely Locality Sensitive Hashing and Filtering (LSH/F), an approach that has been applied very successfully in the case of sieving over lattices. We establish the first baseline for the sieving approach with a decoding complexity of $2^{0.117n}$ for the conventional worst parameters (full distance decoding, complexity maximized over all code rates). Our cumulative improvements, eventually enable us to lower the hardest parameter decoding complexity for SievingISD algorithms to $2^{0.101n}$. While this outperforms the BJMM algorithm (Eurocrypt'12) it falls yet behind the most advanced conventional ISD approach by Both and May (PQCrypto'18). As for lattices, we found the Random-Spherical-Code-Product (RPC) to give the best asymptotic complexity. Moreover, we also consider an alternative that seems specific to the Hamming Sphere, which we believe could be of practical interest, as they plausibly hide less sub-exponential overheads than RPC. |
BibTeX
@inproceedings{eurocrypt-2024-33959,
title={Asymptotics and Improvements of Sieving for Codes},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-58754-2_6},
author={Leo Ducas and Simona Etinski and Andre Esser and Elena Kirshanova},
year=2024
}