Asymptotics and improvements of Sieving for codes

A recent work by Guo, Johansson, and Nguyen (Eprint’23) proposes a promising adaptation of Sieving techniques from lattices to codes, in particular, by claiming concrete cryptanalytic improvements on various schemes. The core of their algorithm reduces to a Near Neigh- bor Search (NNS) problem, for which they devise an ad-hoc approach. In this work, we aim for a better theoretical understanding of this ap- proach. First, we provide an asymptotic analysis which is not present in the original paper. Second, we propose a more systematic use of well- established NNS machinery, known as Locality Sensitive Hashing and Filtering (LSH/F). LSH/F is an approach that has been applied very successfully in the case of sieving over lattices. We thus establish the first baseline for the sieving approach with a decoding complexity of 20.117n for the conventional worst parameters (full distance decoding, where complexity is maximized over all code rates). Our cumulative im- provements eventually enable us to lower the hardest parameter decoding complexity for SievingISD algorithms to 20.101n. This approach outper- forms the BJMM algorithm (Eurocrypt’12) but falls 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 al- ternative 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.