Asymptotics and improvements of Sieving for codes

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 we provide 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 20.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 20.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) gives 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.

• View at Publisher

Free Full Text ( Final Version , 647kb )