Paper 2023/1924

Analyzing the complexity of reference post-quantum software: the case of lattice-based KEMs

Daniel J. Bernstein
Abstract

Software for various post-quantum KEMs has been submitted by the KEM design teams to the SUPERCOP testing framework. The ref/*.c and ref/*.h files together occupy, e.g., 848 lines for ntruhps4096821, 928 lines for ntruhrss701, 1316 lines for sntrup1277, and 2633 lines for kyber1024. It is easy to see that these numbers overestimate the inherent complexity of software for these KEMs. It is more difficult to systematically measure this complexity. This paper takes these KEMs as case studies and applies consistent rules to streamline the ref software for the KEMs, while still passing SUPERCOP's tests and preserving the decomposition of specified KEM operations into functions. The resulting software occupies 381 lines for ntruhps4096821, 385 lines for ntruhrss701, 472 lines for kyber1024, and 478 lines for sntrup1277. This paper also identifies the external subroutines used in each case, identifies the extent to which code is shared across different parameter sets, quantifies various software complications specific to each KEM, and traces how differences in KEM design goals produced different software complications. As a spinoff, this paper presents a kyber512 key-recovery demo exploiting variations in timings of the Kyber reference code.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
post-quantum cryptographylattice-based cryptographysoftware metrics
Contact author(s)
authorcontact-pqcomplexity @ box cr yp to
History
2024-04-19: last of 2 revisions
2023-12-17: received
See all versions
Short URL
https://ia.cr/2023/1924
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1924,
      author = {Daniel J. Bernstein},
      title = {Analyzing the complexity of reference post-quantum software: the case of lattice-based {KEMs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1924},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1924}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.