Impact case study database

Our research has influenced understanding, policies and practices of the information security industry, when constructing and assessing postquantum cryptosystems. This impact is evidenced by the NIST postquantum standardisation process. We describe: (4a) the NIST process itself; (4b) the ways in which our research was used to inform and influence the process; (4c) quotes from a sample of beneficiaries to document the reach and significance of the process.

4a Influencing the NIST Postquantum Standardisation Process:

Secure encryption is of critical importance to the economy and society: The Economic Impacts of the Advanced Encryption Standard, 1996-2017 [Chen et al, E2] commissioned by NIST (part of the U.S. Department of Commerce, responsible for standardisation across many areas in order to promote U.S. industrial competitiveness) estimated that the economic benefits of the NIST AES standardisation alone were over USD250,000,000,000 (2017).

All public key algorithms commonly standardised, such as RSA, Diffie-Hellman, ElGamal and Elliptic Curve variants, are based on problems that become tractable (using Shor’s algorithm) if an adversary has access to a quantum computer: “ a sufficiently powerful quantum computer will put many forms of modern communication – from key exchange to encryption to digital authentication – in peril” [Chen et al, E2]. Many applications, such as the digital signing of long-term contracts or encryption of sensitive medical information, require underlying cryptographic algorithms to remain secure for 15-25 years or more. And yet “ researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars. This is a serious long-term threat to the cryptosystems currently standardized by NIST” [Chen et al, E2]. This situation resulted in a global demand for post-quantum cryptosystems: designed to operate on today’s hardware but remaining secure if an adversary has access to a quantum computer.

In 2016 the NIST Post-Quantum Cryptography standardisation process [E2] was initiated with the aim to define best practice for practical cryptographic algorithms that the international community would regard as secure for wide deployment in the post-quantum world. The process is a policy debate, taking the form of an international public competition split into rounds. Teams of cryptographic experts submit algorithms; these are scrutinised by the community; unsuitable submissions are removed, and others are merged; the scrutiny repeated until a trusted portfolio of ciphers emerges. There have been three rounds in total, with the most highly recommended submissions forming a group of finalists, identified on 22 July 2020. This process has influence beyond NIST to other arenas: For example, the Head of International Standards at the UK National Cyber Security Centre chairs the ETSI TC CYBER QSC Working Group, which was established in 2015 with the aim to assess and recommend quantum-safe cryptographic primitives and protocols for the European standardisation organisation ETSI, writes that the Group has been following the NIST post-quantum standardisation process closely [E3]. Royal Holloway research has been integral to this policy debate.

4b How our work was used in the NIST process:

The work of RHUL researchers has been a major influence on the NIST Post-quantum standardisation process, ensuring that the final portfolio of algorithms is accepted by the international community and giving companies the confidence to deploy products with a clear expectation of what the future post-quantum standard will be. 39% of all submissions and 73% of the finalists used the RHUL team’s research, either citing their research in their specification document in support of their design decisions, or making use of the researchers’ expertise directly as a contributor to the proposal. (Cipher specifications and submission documents are available via the NIST Postquantum website [E2].) A total of 19 outputs written by team members have been cited by algorithm designers as part of the NIST process [E4]. These publications are a mix of theoretical outputs such as those above, and applied outputs written specifically to address issues relevant to the process. Moreover:

RHUL support for successful Round 3 finalists: Albrecht and Cid are part of the submission team of Classic McEliece, one of the four finalists for Key Encapsulation Mechanisms (KEMs). The submission is the result of the merger with the 2^nd round submission NTS-KEM, of which they were also part of the design team. NTS-KEM was joint work with industry partner PQ Solutions, who “ invited RHUL to be part of the submission team because of the contribution made by RHUL in the evolution and refinement of NTS-KEM from the original NTS scheme […and] because of their very high reputation both internationally as well as nationally and the quality of their recent outstanding publications” [E5].

Research in establishing concrete costs for solving the Learning with Errors (LWE) problem [E3], which underlies post-quantum cryptosystem security, served as foundation for the parameter choices of round 3 finalists CRYSTALS-KYBER, Frodo, NTRU, NTRU Prime, qTESLA, and SABER. RHUL research concerned with the asymptotic difficulty of solving hard problems on general and algebraic lattices [E4] is cited by both Falcon and NTRU Prime.

The U.S. National Security Agency (NSA) states that they “ are confident in those lattice-based schemes with strong dependence on well-studied mathematical problems” [E9]. This public statement illustrates the importance of the underpinning role of the study of these underlying problems; four of the five lattice-based finalists cite the RHUL team’s work.

RHUL influence on the selection process: Critical for confidence in the NIST process is the efficient scrutiny of submissions. Both optimising the choices and rejecting weak submissions are essential in the process. RHUL research showing that two post-quantum underpinning problems (Ring-LWE and Module-LWE) are equivalent in difficulty [E3] led NIST to advance Module-LWE-based schemes Kyber, Saber and Dilithium into the 3^rd round over Ring-LWE counterparts [E2, Apon]. Research by Blackburn [E3] was instrumental in the elimination of WalnutDSA, which depends on a problem in the representation theory of braid groups.

The Chief Scientist Thales UK writes: “ *We recognise the significant contribution of the researchers at Royal Holloway to the NIST PQC process: their work has had a widespread and positive influence. Martin Albrecht and Rachel Player’s parameter selection tool and related underpinning theoretical work has informed many of the lattice-based algorithm designs in the NIST process, and we have made direct use of this work in our evaluations. We also very much appreciate Simon Blackburn’s role in removing weak candidates (in particular WalnutDSA) from consideration... All this work is fundamental to our confidence in the process.*” [E6]

4c Defining best practice, developing understanding, implementation and deployment:

The NIST Post-Quantum Standardization Process is the first major initiative in this area and is highly influential in defining best practice. Beneficiaries of the process include agencies and companies needing to understand, develop or implement public-key cryptosystems, and the wider information security industry aiming to advise clients on quantum-safe options. Amazon Web Services, Philips, PQ Solutions Ltd, Thales UK are exemplars of interested parties [E5-8]. Round 3 finalists are already recommended by agencies in areas where long term security is critical. For example, both the NSA [E9] and its German counterpart BSI have already expressed opinions on candidates and primitives. BSI writes “ *From the BSI’s point of view, security is our top priority. The lattice-based algorithm FrodoKEM and the classic McEliece code-based method are the most conservative choices. [… These] two algorithms mentioned are recommended if a manufacturer or user already wants to use a quantum computer-resistant procedure for key update’ (translated from [E10]).

Matt Ball, Chief Scientist of Thales UK, writes: “ The NIST PQC standardisation process is the most significant international development over the last few years, performing a vital role in establishing best-practice, deepening our understanding of PQC, and in suggesting candidate PQC algorithms whose security and performance have been rigorously tested” [E6].

The Senior Standardisation Officer at Philips states “[W] *e felt it was essential to invest in developing secure and performant quantum-safe alternatives. We saw the NIST process as the most important worldwide initiative towards this goal” [E7].

RHUL independent security analysis has supported PQ Solutions deployment of novel post-quantum products. CSO and Chairman of PQ Solutions Ltd writes “[W]e are already developing PQ products based on the emerging NIST PQ standards including Classic McEliece. Being part of the NIST process gives the company a commercial advantage in assuring potential customers of rigorous and secure implementations. For example, we already sell a popular hybrid PQ VPN, a VPN using a combination of existing encryption standards plus expected PQ standards” [E5].

Leading cloud computing provider Amazon Web Services (AWS), Senior Principal Engineer writes " The NIST post-quantum standardization process is extremely important to us at AWS. […] The NIST process has extremely high visibility in industry and is defining the best practice for postquantum systems. […] We are implementing hybrid-post-quantum solutions today based on NIST submissions to understand their impact to cloud computing” [E8].