Paper 2023/1940

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

Sreyosi Bhattacharyya, Indian Statistical Institute
Palash Sarkar, Indian Statistical Institute

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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. Indocrypt 2023
information set decodingcode based cryptographyClassic McEliece cryptosystemtime/memory trade-off
Contact author(s)
bhattacharyya sreyosi @ gmail com
palash @ isical ac in
2023-12-22: approved
2023-12-21: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.