Sensational articles like this about quantum computers even in 2016, create uncertainties for data security in the case that quantum computers of sufficient power are constructed. This article will attempt to shed some light on the situation.
What is Quantum Computing?
Quantum computing is the application of quantum mechanics principles to perform computations. Specifically, quantum computing exploits quantum states of sub-atomic particles like superposition and entanglement to create quantum computers. When applied to quantum computers with sufficient power, specific algorithms can perform computations much faster than classical computers and even solve problems out of reach of the current computing technology. As a result, there is an increased interest from governments and industries worldwide to develop quantum computers. The field is still in its infancy, but the development is gaining traction, and there are already working quantum computers, albeit very weak at this point.
SSL.com provides a wide variety of SSL/TLS server certificates for HTTPS websites.
Classical and Quantum Computing
How can quantum computing influence cryptography?
“In 1994, Peter Shor of Bell Laboratories showed that quantum computers, a new technology leveraging the physical properties of matter and energy to perform calculations can efficiently solve each of these problems, thereby rendering all public-key cryptosystems based on such assumptions impotent. Thus a sufficiently powerful quantum computer will put many forms of modern communication—from key exchange to encryption to digital authentication—in peril.”
Will quantum computing come soon?
What can we do?
When widespread quantum computing technology arrives, we will need to be ready with a quantum-resistant PKI. There are many undergoing projects towards this goal and many proposed technologies that could provide a solution. Below, we will try to summarize the most promising technologies and give a brief review of the collective projects underway to establish post-quantum cryptography, along with the challenges that lay ahead.
Families of post-quantum algorithms
Research in the last 15-20 years has proven the existence of algorithms resistant to quantum attacks. Below we provide a brief description of the most promising algorithm families that could provide a solution for security in a post-quantum world.
Code-based Cryptography
Code-based cryptography uses error-correcting codes to build public-key cryptography. It was first proposed by Robert McEliece in 1978 and is one of the oldest and most researched asymmetric encryption algorithms. A signature scheme can be constructed based on the Niederreiter scheme, the dual variant of the McEliece scheme. The McEliece cryptosystem has resisted cryptanalysis so far. The main problem with the original system is the large private and public key size.
Hash-based cryptography
Hash-based cryptography represents a promising post-quantum cryptography approach for digital signatures. Hash functions are functions that map strings of arbitrary length to strings of fixed length. They are one of the older public-key cryptography schemes, and their security assessments against classical and quantum-based attacks are well understood. Hash functions are already one of the most widely used cryptographic tools. It was known that they could be used as the sole tool for building public-key cryptography for a long time. In addition, hash-based cryptography is flexible and can meet different performance expectations. On the downside, hash-based signature schemes are mainly stateful, meaning that the private key needs to be updated after every use; otherwise, security is not guaranteed. There are hash-based schemes that are stateless, but they come at the cost of longer signatures, more significant processing times, and the signer’s need to keep track of some information, like how many times a key was used to create a signature.
Lattice-based cryptography
Lattice-based cryptography is a particular case of the sub-set sum problem-based cryptography and was first introduced in 1996 by Ajtai. It is the generic term for cryptographic primitives constructed with the use of lattices. Some of these constructions appear to be resistant to both quantum and classical computers attacks. Additionally, they have other attractive features, like worst-case hardness difficulty. Also, they present simplicity and parallelism and are versatile enough to construct robust cryptographic schemes. Finally, they are the only family of algorithms containing all three kinds of primitives required to build a post-quantum Public Key Infrastructure: public-key encryption, key exchange, and digital signature.
Multivariate cryptography
Multivariate cryptography refers to public-key cryptography whose public keys represent a multivariate and nonlinear (usually quadratic) polynomial map. Solving these systems is proven to be NP-complete, thus making this family of algorithms good candidates for post-quantum cryptography. Currently, multi-variate encryption schemes have proven less efficient than other schemes since they require substantial public keys and long decryption times. On the other hand, they turned out to be more suitable for building signature schemes, as they provide the shortest signature sizes among post-quantum algorithms, although they incur rather large public keys.
Isogeny-based cryptography
Isogeny-based cryptography uses maps between elliptic curves to build public-key cryptography. The algorithm that is a candidate for post-quantum cryptography is the Supersingular isogeny Diffie-Hellman key exchange (SIDH) introduced in 2011, making this scheme the most recent among the candidates. SIDH requires one of the smallest keys among the proposed key exchange schemes and supports perfect forward secrecy. However, its relatively young age means that there are not many schemes based on this concept, and there has not been much for inspecting their possible vulnerabilities.
Projects for post-quantum cryptography
There are various working groups for post-quantum cryptography schemes, like the Open Quantum Safe (OQS) project and ENISA. Still, the most coherent initiative is the NIST Post-Quantum Cryptography Standardization Project that has been underway since 2017. As the name implies, the project aims at choosing a suitable cryptography scheme that will be the industry standard in the post-quantum era. The process began with 69 candidate algorithms, of which 26 advanced to the second round of evaluation. In July 2020, round 3 candidates were announced, as shown in the table below. There are seven finalists and eight alternative candidates overall. On the table is noted if they are considered for encryption or signature schemes, the algorithm family and the hard problem upon which they are based.
| Scheme | Enc/SIg | Family | Hard Problem |
| Round 3 Finalists | |||
| Classic McEliece | Enc | Code-Based | Decoding random binary Goppa codes |
| Crytals-Kyber | Enc | Lattice-Based | Cyclotomic Module-LWE |
| NTRU | Enc | Lattice-Based | Cyclotomic NTRU Problem |
| Saber | Enc | Lattice-Based | Cyclotomic Module-LWR |
| Crystals-Dilithium | Sig | Lattice-Based | Cyclotomic Module-LWE and Module-SIS |
| Falcon | Sig | Lattice-Based | Cyclotomic Ring-SIS |
| Rainbow | Sig | Multivariate-Based | Oil-and-Vinegar Trapdoor |
| Round 3 Alternate Candidates | |||
| BIKE | Enc | Code-Based | Decoding quasi-cyclic codes |
| HQC | Enc | Code-Based | Coding variant of Ring-LWE |
| Frodo-KEM | Enc | Lattice-Based | LWE |
| NTRU-Prime | Enc | Lattice-Based | Non-cyclotomic NTRU Problem or Ring-LWE |
| SIKE | Enc | Isogeny-Based | Isogeny problem with extra points |
| GeMSS | Sig | Multivariate-Based | ‘Big-Field’ trapdoor |
| Picnic | Sig | Symmetric Crypto | Preimage resistance of a block cipher |
| SPHINCS+ | Sig | Hash-Based | Preimage resistance of a hash function |
The algorithm evaluation was based on the three criteria shown below.
- Security: This is the most crucial criterion. NIST has established several factors to consider for evaluating the security provided by each candidate algorithm. Apart from the quantum resistance of algorithms, NIST has also defined additional security parameters that are not part of the current cybersecurity ecosystem. These are perfect forward secrecy, resistance to side-channel attacks, and resistance to multi-key attacks.
- Cost and performance: The algorithms are evaluated based upon their performance metrics like key sizes, the computational efficiency of public and private key operations and generation, and decryption failures.
- Algorithm and implementation characteristics: Assuming the algorithms provide good overall security and performance, they are evaluated based on their flexibility, simplicity, and adoption ease (like the existence or not of intellectual property covering the algorithm).
Cryptographic agility
Conclusion
