This article was originally published on the Red Hat Customer Portal. The information may no longer be current.
Traditional computers are binary digital electronic devices based on transistors. They store information encoded in the form of binary digits each of which could be either 0 or 1. Quantum computers, in contrast, use quantum bits or qubits to store information either as 0, 1 or even both at the same time. Quantum mechanical phenomenons such as entanglement and tunnelling allow these quantum computers to handle a large number of states at the same time.
Quantum computers are probabilistic rather than deterministic. Large-scale quantum computers would theoretically be able to solve certain problems much quicker than any classical computers that use even the best currently known algorithms. Quantum computers may be able to efficiently solve problems which are not practically feasible to solve on classical computers. Practical quantum computers will have serious implications on existing cryptographic primitives.
Most cryptographic protocols are made of two main parts, the key negotiation algorithm which is used to establish a secure channel and the symmetric or bulk encryption cipher, which is used to do the actual protection of the channel via encryption/decryption between the client and the server.
The SSL/TLS protocol uses RSA, Diffie-Hellman (DH) or Elliptic Curve Diffie-Hellman (ECDH) primitives for the key exchange algorithm. These primitives are based on hard mathematical problems which are easy to solve when the private key is known, but computationally intensive without it. For example, RSA is based on the fact that when given a product of two large prime numbers, factorizing the product (which is the public key) is computationally intensive. By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find the public key factors. This ability could allow a quantum computer to decrypt many of the cryptographic systems in use today. Similarly, DH and ECDH key exchanges could all be broken very easily using sufficiently large quantum computers.
For symmetric ciphers, the story is slightly different. It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm with key length of n bits by brute force requires time equal to roughly 2^(n/2) invocations of the underlying cryptographic algorithm, compared with roughly 2^n in the classical case, meaning that the strength of symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search. Therefore the situation with symmetric ciphers is stronger than the one with public key crypto systems.
Hashes are also affected in the same way symmetric algorithms are: Grover's algorithm requires twice the hash size (as compared to the current safe values) for the same cryptographic security.
Therefore, we need new algorithms which are resistant to quantum computations. Currently there are 5 proposals, which are under study:
Lattice-based cryptography
A lattice is the symmetry group of discrete translational symmetry in n directions. This approach includes cryptographic systems such as Learning with Errors, Ring-Learning with Errors (Ring-LWE), the Ring Learning with Errors Key Exchange and the Ring Learning with Errors Signature. Some of these schemes (like NTRU encryption) have been studied for many years without any known feasible attack vectors and hold great promise. On the other hand, there is no supporting proof of security for NTRU against quantum computers.
Lattice is interesting because it allows the use of traditional short key sizes to provide the same level of security. No short key system has a proof of hardness (long key versions do). The possibility exists that a quantum algorithm could solve the lattice problem, and the short key systems may be the most vulnerable.
Multivariate cryptography
Multivariate cryptography includes cryptographic systems such as the Rainbow scheme which is based on the difficulty of solving systems of multivariate equations. Multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature, though various attempts to build secure multivariate equation encryption schemes have failed.
Several practical key size versions have been proposed and broken. EU has standardized on a few; unfortunately those have all been broken (classically).
Hash-based cryptography
Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number theoretic digital signatures like RSA and DSA. The primary drawback for any Hash based public key is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact reduced interest in these signatures until interest was revived due to the desire for cryptography to resist attack by quantum computers. Schemes that allow an unlimited number of signatures (called 'stateless') have now been proposed.
Hash based systems are provably secure as long as hashes are not invertible. The primary issue with hash based systems is the signature sizes (quite large). They also only provide signatures, not key exchange.
Code-based cryptography
Code-based cryptography includes cryptographic systems which rely on error-correcting codes. The original McEliece signature using random Goppa codes has withstood scrutiny for over 30 years. The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the McEliece public key encryption system as a candidate for long term protection against attacks by quantum computers. The downside, however, is that code based cryptography has large key sizes.
Supersingular elliptic curve isogeny cryptography
This cryptographic system relies on the properties of supersingular elliptic curves to create a Diffie-Hellman replacement with forward secrecy. Because it works much like existing Diffie-Hellman implementations, it offers forward secrecy which is viewed as important both to prevent mass surveillance by governments but also to protect against the compromise of long term keys through failures.
Implementations
Since this is a dynamic field with cycles of algorithms being defined and broken, there are no standardized solutions. NIST's crypto competition provides a good chance to develop new primitives to power software for the next decades. However it is important to mention here that Google Chrome, for some time, has implemented the NewHope algorithm which is a part of Ring Learning-with-Errors (RLWE) family. This experiment has currently concluded.
Update: the Libreswan IPsec VPN subsystem added support for Post-Quantum Pre-shared Keys for IKEv2 (soon to be a full RFC) as a part of version 3.23.
Lastly, the use of pre-shared keys is a good work-around for quantum threats, but is not the ultimate solution. Red Hat's current strategy for quantum threats is available in this article.
In conclusion, which Post-Quantum cryptographic scheme will be accepted will ultimately depend on how fast quantum computers become viable and made available at minimum to state agencies if not the general public.
Sull'autore
Huzaifa Sidhpurwala is a Senior Principal Product Security Engineer - AI security, safety and trustworthiness, working for Red Hat Product Security Team.
Altri risultati simili a questo
Ricerca per canale
Automazione
Novità sull'automazione IT di tecnologie, team e ambienti
Intelligenza artificiale
Aggiornamenti sulle piattaforme che consentono alle aziende di eseguire carichi di lavoro IA ovunque
Hybrid cloud open source
Scopri come affrontare il futuro in modo più agile grazie al cloud ibrido
Sicurezza
Le ultime novità sulle nostre soluzioni per ridurre i rischi nelle tecnologie e negli ambienti
Edge computing
Aggiornamenti sulle piattaforme che semplificano l'operatività edge
Infrastruttura
Le ultime novità sulla piattaforma Linux aziendale leader a livello mondiale
Applicazioni
Approfondimenti sulle nostre soluzioni alle sfide applicative più difficili
Serie originali
Raccontiamo le interessanti storie di leader e creatori di tecnologie pensate per le aziende
Prodotti
- Red Hat Enterprise Linux
- Red Hat OpenShift
- Red Hat Ansible Automation Platform
- Servizi cloud
- Scopri tutti i prodotti
Strumenti
- Formazione e certificazioni
- Il mio account
- Supporto clienti
- Risorse per sviluppatori
- Trova un partner
- Red Hat Ecosystem Catalog
- Calcola il valore delle soluzioni Red Hat
- Documentazione
Prova, acquista, vendi
Comunica
- Contatta l'ufficio vendite
- Contatta l'assistenza clienti
- Contatta un esperto della formazione
- Social media
Informazioni su Red Hat
Red Hat è leader mondiale nella fornitura di soluzioni open source per le aziende, tra cui Linux, Kubernetes, container e soluzioni cloud. Le nostre soluzioni open source, rese sicure per un uso aziendale, consentono di operare su più piattaforme e ambienti, dal datacenter centrale all'edge della rete.
Seleziona la tua lingua
Red Hat legal and privacy links
- Informazioni su Red Hat
- Opportunità di lavoro
- Eventi
- Sedi
- Contattaci
- Blog di Red Hat
- Diversità, equità e inclusione
- Cool Stuff Store
- Red Hat Summit