Welcome to the resource topic for 2023/1924
Title:
Analyzing the complexity of reference post-quantum software
Authors: Daniel J. Bernstein
Abstract:Constant-time C 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 2613 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 inherent 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 finds secret-dependent timings in kyber*/ref.
ePrint: https://eprint.iacr.org/2023/1924
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .