Quantum computers are based on physical principles that are fundamentally different from those underlying today’s classical computing. At a large scale, they would be capable of performing certain tasks much faster than today’s computers. While prototypes of small quantum computers, often designated by NISQ (Noisy Intermediate Scale Quantum computers), already exist, building large-scale reprogrammable ones is still at a very upstream research stage. There are many lines of research in quantum physics for the creation of such quantum computers but none of them is certain to succeed. Though their potential benefits are not fully known, they could obviously be high. Thus, the industry, governments, and academia around the world are devoting significant resources to research in quantum computing. For example, in 2021, the French government announced an investment of more than 1 billion euros in quantum technologies, including quantum computing [8]. A complete survey on the status of quantum computer development has been detailed by the BSI, the German counterpart of ANSSI [7]. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

The security of the majority of digital infrastructures relies on public key cryptography (PKC), a technology that enables secure communications between entities, typically users or servers, that do not share any pre-established secret. More precisely, PKC serves two main functionalities: protected channel establishment (key establishment) and authentication of digital information (including authentication of parties inside a communication protocol by the use of digital signatures). Today, these techniques are essentially based on two mathematical problems: the factorization of large numbers and the discrete logarithm computation. Both are dimensioned to be virtually impossible to solve with our current computing resources and mathematical knowledge. For example, the well-known RSA public key algorithm relies on the factorization of large numbers. These two fundamental problems will no longer be unsolvable if a large-scale quantum computer is built; thus, the security of currently deployed public key cryptography could collapse. Indeed, in 1994, P. Shor introduced a quantum algorithm [15]) able to solve these problems. This algorithm cannot be performed on classical computers, but it could be performed on large-scale ones. To avoid any confusion with the existing prototypes of small-scale quantum computers, the NCSC, the British counterpart of ANSSI, introduced the name of Cryptographically Relevant Quantum Computers, CRQCs (see the NCSC’s whitepaper on quantum-safe cryptography [12]). In other words, a CRQC is a quantum computer that is able to execute relevant instances of Shor’s algorithm, thus threatening today’s public-key cryptography. The prototypes of quantum computers that exist are presently far from the required scale and stability of CRQCs, and therefore, they are currently not a threat to public key cryptography. Many research challenges in physics, engineering, and computer science must be overcome before scaling up to large quantum computers that can solve the factorization and discrete logarithm problems on which the current PKC is based. However, the threat of retroactive attacks cannot be ruled out. A family of attacks, called “store now, decrypt later attacks”, constist in storing today the data exchange corresponding to a secure channel establishment and the encrypted messages over such a channel, with the purpose of eventually decrypting these messages once a CRQC becomes available. This threat could be relevant in certain scenarios involving very sensitive information, e.g., classified information. Furthermore, the quantum threat could also impact digital signatures. Indeed, a CRQC could be used to forge signatures and allow impersonation attacks. Unlike the threat of retroactive “store now, decrypt later attacks,” this threat would only be effective if the signatures are generated at a time when a CRQC exists. Thus, the signatures that are verified on the y, like in authenticated channels, cannot be directly impacted before the existence of a CRQC. However, in the context of document signing, long-term validity is sometimes required in certain specific use cases, and these signatures can be compromised by the existence of a CRQC. The transition from pre-quantum signatures to post-quantum ones should be tackled before the existence of any CRQC to avoid any a posteriori impersonation attack. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition  

Symmetric cryptography, a different and complementary branch of cryptographic algorithms, could also be targeted by potential large-scale quantum computers. A generic quantum algorithm introduced by Grover in 1998 [11] quadratically speeds up the exhaustive search of secret keys in symmetric algorithms. Grover’s algorithm can also speed up certain attacks on hash functions called collision-finding attacks. These attacks also require the use of CRQCs, but for numerous algorithms, one can reasonably assume that they could be mitigated by adjusting the sizes of the hash outputs and keys (using 256 bits keys instead of 128 for the AES symmetric encryption mechanism and using 384 bits hash outputs for SHA-2 and SHA-3 for instance). Thus, the generic impact of Grover’s algorithm on symmetric cryptography is far more limited than the impact of Shor’s algorithm on PKC. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

Because of the “store now, decrypt later” attack, the quantum threat should be taken into account before the question of whether the development of a CRQC will ever become achievable in the future is cleared up. Thus, a profound change in today’s public key cryptography towards quantum-resistant algorithms should be globally initiated to anticipate a possible collapse of our current cryptographic infrastructure. Even though protecting our current public key cryptography against this distant threat has a cost, researching alternative cryptographic solutions can be beneficial from another perspective. Indeed, beyond the quantum threat, cryptography is never infallible; weaknesses are found from time to time, even in cryptographic mechanisms implemented in classical computers. Thus, it is not possible to totally rule out a discovery of a potential weakness impacting the security of hardware and/or software and requiring the replacement of algorithms. Nowadays, the public key cryptography used worldwide is close to a monoculture and would strongly benefit from the introduction of new alternative algorithms. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

Quantum Key Distribution (QKD), sometimes called quantum cryptography, is a way of enabling secure communications without being vulnerable to classical and quantum computers by using quantum channels. Nevertheless, this technique does not provide a complete functional equivalent to public key cryptography and has limited applications due to the need for a dedicated communication infrastructure and without real routing capabilities. More information on the ANSSI position can be found under reference [5]. As such, except for niche applications where QKD provides some extra physical security on top of algorithmic cryptography (and not as a replacement), ANSSI does not consider it a suitable countermeasure to mitigate the quantum threat. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

Post-quantum cryptography (PQC) is a family of cryptographic algorithms, including key establishment and digital signatures, that ensures a conjectured (note: 1) security even against an attacker equipped with quantum computers. Post-quantum algorithms can be executed on classical computers with classical communication channels and thus can be deployed in existing infrastructures, unlike QKD. Besides, these algorithms are not only for use after a CRQC is built; they can also be deployed in anticipation. For ANSSI, PQC represents the most promising avenue to thwart the quantum threat. The international research effort on post-quantum cryptography accelerated in 2015 after NSA’s release advising to “shift to quantum-resistant cryptography in the near future [9]. In 2017, the National Institute of Standards and Technologies (NIST) started a standardization campaign to define standard post-quantum public key algorithms (key establishments and signatures). At the time of writing, this process is still ongoing [13] and is currently in its third round. Standards are expected to be published within the next one to four years. Contrary to other standardization campaigns where there was only one finalist, the post-quantum campaign will end up with several standards for different applications. This standardization process has acted as a catalyst, allowing a strong involvement of the international cryptography research community and focusing the analysis efforts on a restricted number of candidate algorithms while preserving the diversity of the underlying problems. This process has also broadened the analysis to various implementation use cases like embedded components. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

The different families of post-quantum public key candidate algorithms are defined by the mathematical structure on which they are built. Nowadays, post-quantum public key algorithms are mostly based upon Structured or unstructured Euclidean lattices, Error-correcting codes, Isogenies between elliptic curves, Multivariate systems, and Hash trees. While the mathematical problems were introduced in the last century, the PQC algorithms are relatively recent. They offer various compromises between key size, signatures or ciphertext size, computational complexity, and security assurance. A technical survey of the algorithms and the underlying mathematical problems can be found in [10]. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

Beyond the NIST objective to derive standards, the past three rounds of the NIST standardization campaign provide a variety of algorithms along with security analysis. Although this new post-quantum toolbox may seem handy for developers, the maturity level of the post-quantum algorithms presented to the NIST process should not be overestimated. Many aspects lack cryptanalytical hindsight or are still research topics, e.g., analysis of the difficulty of the underlying problem in the classical and quantum computation models, dimensioning, integration of schemes in protocols, and, more importantly, the design of secure implementations. This situation will probably last sometime after the publication of NIST standards. Acknowledging the immaturity of PQC is important: ANSSI will not endorse any direct drop-in replacement of currently used algorithms in the short/medium term. However, this immaturity should not serve as an argument for postponing the deployments. ANSSI encourages all industries to initiate in the next months a gradual overlap transition in order to progressively increase trust in the post-quantum algorithms and their implementations while ensuring no security regression as far as classical (pre-quantum) security is concerned. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

A hybrid mechanism (key establishment or signature) combines the computations of a recognized pre-quantum public key algorithm and an additional algorithm conjectured post-quantum secure. This makes the mechanism benefit both from the strong assurance of the resistance of the first algorithm against classical attackers and from the conjectured resistance of the second algorithm against quantum attackers. Certain hybrid protocols are in standardization processes, like [17] for TLS 1:3 or [18] for IKEv2. More generally, for key establishment, one can perform both a pre-quantum and a post-quantum key establishment and then combine both results, e.g., using a Key Derivation Function (KDF). Alternatively, one may use for some specific applications a KDF on a pre-shared key and a shared key obtained from a pre-quantum scheme. For signature schemes, hybrid signatures can be achieved with the concatenation of signatures issued by a pre-quantum and a post-quantum scheme and the requirement that both signatures be valid in order for the hybrid signature to be valid. Even though hybridization is a relatively simple construction, ANSSI emphasizes that the role of hybridization in cryptographic security is crucial and will be mandatory for phases 1 and 2 presented in the sequel. In addition, the implementation security of the hybridization technique should also be taken into consideration. Given that most post-quantum algorithms involve message sizes much larger than the current pre-quantum schemes, the extra performance cost of a hybrid scheme remains low in comparison with the cost of the underlying post-quantum scheme. ANSSI believes that this is a reasonable price to pay for guaranteeing an additional pre-quantum security, at least equivalent to the one provided by current pre-quantum standardized algorithms. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition

As detailed in the sequel, the deployment of hybrid PQC is not a mandatory feature as of today. However, ANSSI will encourage the initiation of progress towards cryptoagility as much as possible for future products. More precisely, a product is said to be crypto-agile if it includes the possibility to update its cryptographic algorithms without recalling it or substituting it with a new one. The quantum threat makes cryptoagility particularly relevant, and beyond this threat, classical attacks may also evolve and make cryptographic mechanisms or key lengths obsolete. In practice, cryptoagility also means that in addition to the possibility of patching, products could include an extra surface for allowing potential updates in order to react to upcoming cryptographic recommendations and standard updates. Even though updates of the cryptographic algorithms should be much less frequent than patches, the cryptoagility feature is non-trivial to implement due to the need for retro-compatibility and the potential requirement for additional security visas if the product is certified. However, as the motivation for cryptoagility is very relevant nowadays, ANSSI believes that cryptoagility features should be taken into account during the benefit/risk analysis of future products. Source: https://cyber.gouv.fr/en/publications/anssi-views-post-quantum-cryptography-transition