Paper 2023/1924
Analyzing the complexity of reference post-quantum software: the case of lattice-based KEMs
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
-
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}
}
