Carl Alexander Miller

The National Institute of Standards and Technology is selecting public-key cryptographic algorithms through a public, competition-like process. The new public-key cryptography standards will specify additional digital signatures, public-key encryption, and key-establishment algorithms to supplement Federal Information Processing Standard (FIPS) 186-5, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers. After three rounds of evaluation and analysis, NIST announced the selection of the first algorithms to be standardized \cite {NISTIR8413}. The public-key encapsulation mechanism (KEM) selected for standardization was CRYSTALS-Kyber (ML-KEM). The digital signatures selected were CRYSTALS-Di lithium (ML-DSA), Falcon (FN-DSA), and SPHINCS+ (SLH-DSA). In August 2024, NIST published the first three post-quantum cryptography standards based on these algorithms \cite {FIPS203, FIPS204, FIPS205}. Four candidate algorithms for key establishment have continued to be studied in a fourth round of analysis: BIKE, Classic McEliece, HQC, and SIKE. This report describes the evaluation and selection process of these fourth-round candidates based on public feedback and internal review. The report summarizes each of the candidate algorithms and identifies those selected for standardization. The only key-establishment algorithm that will be standardized is HQC. NIST will develop a standard based on HQC to augment and diversify its key-establishment portfolio.

NIST is in the process of evaluating public-key digital signature algorithms for potential standardization to protect sensitive information into the foreseeable future, including after the advent of quantum computers. Any signature scheme that is eventually selected would augment FIPS 204, Module-Lattice-Based Digital Signature Standard; FIPS 205, Stateless Hash-Based Digital Signature Standard; FIPS 186-5, Digital Signature Standard (DSS); and SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes. This report describes the evaluation criteria and selection process of the First Round of the Additional Digital Signatures for the NIST Post-Quantum Cryptography (PQC) Standardization Process. Based on public feedback and internal reviews of the first-round candidates, NIST selected14 candidate algorithms to move forward to the second round of evaluation: CROSS, FAEST, HAWK, LESS, MAYO, Mirath (merger of MIRA/MiRitH), MQOM, PERK, QR-UOV, RYDE, SDitH, SNOVA, SQIsign, and UOV.

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the previous work by Kiltz, Lyubashevsky, and Schaffner (EUROCRYPT 2018) that gave the only other rigorous security proof for a variant of Dilithium, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key size and signature size are about 2.9 times and 1.3 times larger, respectively, than those proposed by Kiltz et al. at the same security level.

Quantum cryptography bases its security proofs on physical assumptions. A longstanding observation in the field is that we may be able to do more cryptographic tasks when we assume not only the laws of quantum mechanics but also the impossibility of superluminal signaling (i.e., that information cannot travel faster than the speed of light). Relativistic quantum cryptography takes into account the spatial locations of the parties involved and uses the impossibility of superluminal signaling as a basis for security. Previous efforts in this field have been fruitful, both theoretically and experimentally.

When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is a quantum correlation? These questions are central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations -- that is, correlations for which the number of measurements and number of measurement outcomes are fixed -- such that solving the quantum membership problem for this family is computationally impossible. Thus, the undecidability that arises in understanding Bell experiments is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.