Concrete Time/Memory Trade-Offs in Generalised Stern’s ISD Algorithm

Sreyosi Bhattacharyya; Palash Sarkar

Paper 2023/1940

Concrete Time/Memory Trade-Offs in Generalised Stern’s ISD Algorithm

Sreyosi Bhattacharyya, Indian Statistical Institute

Palash Sarkar

, Indian Statistical Institute

Abstract

The first contribution of this work is a generalisation of Stern's information set decoding (ISD) algorithm. Stern's algorithm, a variant of Stern's algorithm due to Dumer, as well as a recent generalisation of Stern's algorithm due to Bernstein and Chou are obtained as special cases of our generalisation. Our second contribution is to introduce the notion of a set of effective time/memory trade-off (TMTO) points for any ISD algorithm for given ranges of values of parameters of the algorithm. Such a set succinctly and uniquely captures the entire landscape of TMTO points with only a minor loss in precision. We further describe a method to compute a set of effective TMTO points. As an application, we compute sets of effective TMTO points for the five variants of the Classic McEliece cryptosystem corresponding to the new algorithm as well as for Stern's, Dumer's and Bernstein and Chou's algorithms. The results show that while Dumer's and Bernstein and Chou's algorithms do not provide any interesting TMTO points beyond what is achieved by Stern's algorithm, the new generalisation that we propose provide about twice the number of effective TMTO points that is obtained from Stern's algorithm. Consequences of the obtained TMTO points to the classification of the variants of Classic McEliece in appropriate NIST categories are discussed.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. Indocrypt 2023
Keywords: information set decoding code based cryptography Classic McEliece cryptosystem time/memory trade-off
Contact author(s): bhattacharyya sreyosi @ gmail com
palash @ isical ac in
History: 2023-12-22: approved; 2023-12-21: received; See all versions
Short URL: https://ia.cr/2023/1940
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1940,
      author = {Sreyosi Bhattacharyya and Palash Sarkar},
      title = {Concrete Time/Memory Trade-Offs in Generalised Stern’s ISD Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1940},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1940}},
      url = {https://eprint.iacr.org/2023/1940}
}