Paper 2023/1577

Asymptotics and Improvements of Sieving for Codes

Léo Ducas, Centrum Wiskunde & Informatica, Leiden University
Andre Esser, Technology Innovation Institute
Simona Etinski, Centrum Wiskunde & Informatica
Elena Kirshanova, Technology Innovation Institute, Immanuel Kant Baltic Federal University
Abstract

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 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 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 $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 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 it plausibly hides less sub-exponential overheads than RPC.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
sieving techniquesnear neighbor searchlocality sensitive hashinginformation set decodingcodes and lattices
Contact author(s)
leo ducas @ cwi nl
andre r esser @ gmail com
etinski simona @ gmail com
elenakirshanova @ gmail com
History
2023-10-13: revised
2023-10-12: received
See all versions
Short URL
https://ia.cr/2023/1577
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1577,
      author = {Léo Ducas and Andre Esser and Simona Etinski and Elena Kirshanova},
      title = {Asymptotics and Improvements of Sieving for Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1577},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1577}},
      url = {https://eprint.iacr.org/2023/1577}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.