logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

Asymptotics and Improvements of Sieving for Codes

Simona Etinski

( CWI )

salle 2

le 09 avril 2024 à 11:00

In this talk, I am going to present a joint work with Léo Ducas, Andre Esser, and Elena Kirshanova on sieving for codes. In this work, we provide an asymptotic analysis of the sieving for codes originally introduced in the paper by Guo, Johansson, and Nguyen (Eprint’23), after which we rely on a well-established lattice-based NNS machinery, known as Locality Sensitive Hashing and Filtering (LSH/F), to obtain a more systematic analysis of the sieving for codes. We thus introduce a baseline for the sieving approach for codes with a decoding complexity of 2^0.117n for the conventional worst parameters (full distance decoding, where complexity is 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. This approach outperforms the BJMM algorithm (Eurocrypt’12) but falls behind the most advanced conventional ISD approach by Both and May (PQCrypto’18). As in the case of lattices, we found that the Random-Spherical-Code-Product (RPC) gives the best asymptotic complexity. Moreover, we consider an alternative that seems specific to the Hamming Sphere, which we believe could be of practical interest as it plausibly hides less sub-exponential overheads than RPC. For more details, refer to the full version of the paper given at https://eprint.iacr.org/2023/1577.