Source-linked AI summary
The Impact of Quantum Computing on Present Cryptography
Vasileios Mavroeidis, Kamer Vishi, Mateusz D. Zych, Audun Jøsang
TL;DR
The paper examines how quantum computing threatens present cryptography, including public-key, symmetric, and hash-based schemes. It discusses quantum algorithms, quantum-computing challenges, quantum key distribution, and post-quantum cryptographic responses, emphasizing the vulnerability of current public-key algorithms and practical QKD limitations.
Problem
Quantum computing poses risks to conventional cryptographic schemes, especially public-key systems based on factoring and discrete logarithms, while symmetric schemes and hash functions are also affected.
Method
The paper surveys symmetric and asymmetric cryptosystems, quantum algorithms, quantum-computing challenges, quantum key-distribution protocols, and post-quantum cryptographic approaches.
Results
Present public-key algorithms such as RSA and elliptic-curve cryptography are described as vulnerable to quantum algorithms, while longer-output SHA-2 and SHA-3 remain quantum resistant.
Takeaways & Limitations
Cryptographic schemes resistant to quantum computing are presented as the response to the threat posed by Shor’s and Grover’s algorithms.
Takeaways & Limitations
Practical quantum key distribution is constrained by hardware weaknesses, noise, single-photon implementation difficulties, and attacks such as photon-number splitting.
Abstract
from arXiv · showhide
The aim of this paper is to elucidate the implications of quantum computing in present cryptography and to introduce the reader to basic post-quantum algorithms. In particular the reader can delve into the following subjects: present cryptographic schemes (symmetric and asymmetric), differences between quantum and classical computing, challenges in quantum computing, quantum algorithms (Shor's and Grover's), public key encryption schemes affected, symmetric schemes affected, the impact on hash functions, and post quantum cryptography. Specifically, the section of Post-Quantum Cryptography deals with different quantum key distribution methods and mathematicalbased solutions, such as the BB84 protocol, lattice-based cryptography, multivariate-based cryptography, hash-based signatures and code-based cryptography.
I. INTRODUCTION
The paper frames cryptography as essential for protecting data and distinguishes symmetric from asymmetric systems. It then motivates post-quantum cryptography by explaining that quantum algorithms threaten current schemes based on factorization and discrete logarithms.
- Cryptography protects data in transit and storage while supporting confidentiality, integrity, authenticity, and non-repudiation.
- Modern cryptosystems are divided into symmetric and asymmetric categories.
- The paper examines quantum computing, Shor’s and Grover’s algorithms, affected cryptographic schemes, hash functions, quantum key distribution, and post-quantum alternatives.
- Symmetric cryptography uses one shared secret key, creating a need for efficient key exchange over public networks.
- Asymmetric cryptography uses paired public and private keys for encryption, decryption, and digital signatures.
1) Factorization Problem - RSA Cryptosystem:
This section introduces RSA and discrete-logarithm-based cryptography alongside quantum computing concepts and the practical challenges that constrain quantum hardware. It emphasizes that quantum computing threatens present public-key systems while requiring reliable, coherent, and sufficiently error-corrected qubits.
- 1) Factorization Problem - RSA Cryptosystem:: RSA relies on the difficulty of factoring biprime numbers and is mainly used for key exchange alongside symmetric encryption such as AES.
- 2) Discrete Logarithm Problem (DLP):: Diffie-Hellman and ECC rely on the discrete logarithm problem, with ECC providing comparable security to RSA and DLP systems using shorter key operands.
- III. QUANTUM COMPUTING VS CLASSICAL COMPUTING: Quantum computers use qubits that can occupy superposition states, while entanglement links qubits into jointly described quantum states.
- III. QUANTUM COMPUTING VS CLASSICAL COMPUTING: Quantum-computing development includes universal and non-universal machines, which are designed respectively for general tasks and specific purposes.
- A. Challenges in Quantum Computing: Quantum algorithms are probabilistic, so measurement and verification can weaken their practical speed advantage.
- A. Challenges in Quantum Computing: Qubits experience bit-flip and phase errors from heat, environmental noise, and electromagnetic couplings.
- A. Challenges in Quantum Computing: Qubits retain quantum states only briefly, and longer coherence requires isolation and near-absolute-zero temperatures that complicate control.
- A. Challenges in Quantum Computing: Quantum Volume measures quantum-computer power using qubit count, error correction quality, and parallel operations rather than qubit count alone.
IV. CRYPTOSYSTEMS VULNERABLE TO QUANTUM ALGORITHMS
Quantum algorithms threaten present cryptography by exploiting the mathematical assumptions behind public-key systems, especially factorization and discrete logarithms. Shor’s algorithm illustrates this threat by deriving factors from periodicity in modular exponentiation.
- Shor’s algorithm makes cryptographic schemes based on integer factorization or discrete logarithms vulnerable to quantum computers.
- Quantum computers threaten secure communication because they can perform computations that conventional computers cannot.
- Shor’s algorithm: Shor’s factoring example uses a 4-qubit register to represent and process the number 15.
- Shor’s algorithm: For n = 15 and x = 2, modular exponentiation produces the repeating sequence 1, 2, 4, 8, yielding f = 4.
- Shor’s algorithm: The period f is used to calculate a possible factor, while non-prime results require repeating the calculation with different f values.
- Shor’s algorithm: Shor’s algorithm also addresses discrete logarithms through superposition and Fourier transformations that produce integers satisfying a usable equation.
B. Grover’s algorithm in Symmetric Cryptography
Grover’s algorithm accelerates searches of unsorted spaces, creating a reduced but significant threat to symmetric cryptography. Larger key spaces increase the work required for password and key cracking.
- Grover’s algorithm searches an unsorted database of N entries in √N searches, compared with N/2 searches for a conventional computer.
- For DES, Grover’s algorithm was reported to require only 185 searches to find a 56-bit key.
- Increasing the number of key bits makes password cracking require exponentially more searches.
- Grover’s algorithm has applications to symmetric cryptosystems but is not as fast as Shor’s algorithm.
C. Asymmetric Encryption Schemes Affected
Quantum computing affects public-key and symmetric cryptographic schemes differently: Shor’s algorithm rapidly breaks major public-key constructions, while Grover’s algorithm threatens selected symmetric schemes and hash functions.
- Asymmetric schemes: RSA, DSA, ElGamal, and elliptic-curve schemes rely on factorization or discrete logarithms and are vulnerable to Shor’s algorithm.
- Symmetric schemes: Grover’s algorithm threatens only some symmetric cryptographic schemes, while sufficiently large-key AES schemes are described as quantum resistant.
- Symmetric schemes: A 128-bit symmetric key provides a 64-bit security level under the stated square-root quantum speed-up.
- Symmetric schemes: AES is considered resilient to quantum computation when used with 192- or 256-bit keys.
- Hash functions: Quantum attacks on hash functions exploit fixed output lengths, but longer-output SHA-2 and SHA-3 remain quantum resistant.
V. POST-QUANTUM CRYPTOGRAPHY
Post-quantum cryptography seeks systems secure against both quantum and conventional computers while interoperating with existing networks. The paper presents QKD families and mathematical alternatives that avoid factorization and discrete-logarithm assumptions.
- Post-quantum cryptography aims to secure systems against quantum and conventional computers while interoperating with existing communication protocols and networks.
- NIST’s first-round call received 82 proposals: 59 encryption or key-exchange schemes and 23 signature schemes.
- The presented mathematical approaches avoid hidden-subgroup problems such as integer factorization and discrete logarithms.
- Quantum key distribution: QKD addresses key exchange over insecure channels using quantum-mechanical properties of light and transmission systems.
- Quantum key distribution: Prepare-and-measure protocols use measurement disturbance to reveal eavesdropping, allowing corrupted information to be discarded and intercepted information estimated.
- QKD families: QKD protocols are organized into discrete-variable, continuous-variable, and distributed-phase-reference families distinguished by detection systems.
- QKD families: Discrete-variable protocols are most widely implemented, whereas continuous-variable and distributed-phase-reference protocols mainly address experimental limitations.
1) BB84 protocol:
BB84 generates shared key bits by transmitting randomly polarized photons and comparing measurement bases. Although the protocol is provably secure under stated channel conditions, implemented detector hardware has been shown vulnerable to blinding attacks, including after proposed mitigation.
- BB84 protocol: BB84 uses photon polarization to create a random sequence of qubits transmitted through a quantum channel.A secure key sequence can be generated when the channel bit error rate is less than about 7%.
- BB84 protocol: Alice randomly chooses a bit and one of two polarization bases, while Bob measures each photon using a randomly selected basis.They continue until enough bits are generated, then publicly compare bases without revealing measured values.
- Security limitation: BB84 is provably secure when the channel bit error rate is below about 7%, but its implemented avalanche-photodiode detector was compromised by blinding.The attack allowed inspection of the secret key without the receiver noticing.
- Security limitation: Lydersen et al. again revealed the secret key after photocurrent monitoring was proposed to mitigate detector-blinding attacks.The result shows that the proposed hardware improvement did not prevent the demonstrated attack.
2) Photon Number Splitting Attack:
Photon Number Splitting attacks exploit the use of laser pulses containing multiple photons in practical quantum key distribution. Decoy states are presented as a proposed mitigation, while alternative post-quantum mathematical schemes are also surveyed.
- Photon Number Splitting Attack: Practical QKD uses laser pulses because producing and detecting individual photons is impractical, creating exposure to Photon Number Splitting attacks.An attacker can split off and store a photon while allowing the remaining photons to reach Bob.
- Photon Number Splitting Attack: In a PNS attack, Eve waits for Alice to reveal the encoding bases and measures stored photons using the correct bases.This lets Eve obtain information about secret-key bits from multiphoton signals without being noticed.
- Mitigation: Decoy states mitigate PNS attacks by randomly sending pulses with lower average photon numbers that Eve cannot distinguish from ordinary signals.The method is described as working for both single- and multiphoton pulses.
- Mathematical-based solutions: Alternative public-key schemes based on lattices, multivariate polynomials, hashes, and error-correcting codes are investigated because the Hidden Subgroup Problem does not apply to them.The paper notes that these alternatives do not necessarily satisfy all characteristics of an ideal scheme.
1) Lattice-based Cryptography:
Lattice-based cryptography replaces factorization-based constructions with schemes founded on the presumed hardness of lattice problems. The surveyed candidates vary substantially in security evidence, efficiency, key size, and known weaknesses, with NTRU identified as the most promising among those discussed.
- Lattice-based Cryptography: Lattice-based encryption avoids RSA’s factorization basis and relies on hard lattice problems such as the Shortest Vector Problem.The input is a lattice represented by an arbitrary basis, and the goal is to find its shortest nonzero vector.
- Lattice-based Cryptography: Ajtai-Dwork connects worst-case and average-case SVP complexity, but its security claim was later refuted and its large public key causes message expansion.These properties make AD an unrealistic post-quantum public-key candidate.
- Lattice-based Cryptography: GGH uses the NP-hard Closest Vector Problem but has a flaw allowing partial plaintext recovery from CVP instances.The flaw was proved by Nguyen in 1999.
- Lattice-based Cryptography: NTRU supports encryption and digital signatures, relies on difficult polynomial factorization, and has no known attack reported in the paper.For 128-bit post-quantum security, it requires 12881-bit keys.
- Lattice-based Cryptography: NTRU Prime addresses weaknesses of several lattice cryptosystems, including NTRU, by using different ring structures.The paper concludes that NTRU is the most efficient and secure candidate among the lattice-based schemes discussed.
2) Multivariate-based Cryptography:
The paper discusses multivariate cryptography, hash-based signatures, and their constructions as post-quantum alternatives. It describes multivariate schemes as difficult to develop, while hash-based signatures include stateful and stateless candidates under standardization evaluation.
- Multivariate-based Cryptography: Multivariate cryptography relies on the difficulty of solving systems of multivariate polynomials over finite fields.The paper states that developing encryption algorithms based on multivariate equations is difficult.
- Hash-based signatures: Lamport signatures use a security parameter b and require a secure hash function for a 128-bit security level.The supplied passage introduces the scheme but does not specify the required hash-function construction.
- Hash-based signatures: One-time signatures are unsuitable for large-scale use because each key can be used only once.WOTS is described as more efficient than Lamport’s scheme, with smaller signatures and keys.
- Hash-based signatures: Merkle signatures combine one-time signatures with binary trees, using the root hash as the public key that verifies signatures stored in leaf nodes.Each internal node represents the hash of its child-node concatenation.
- Hash-based signatures: XMSS and SPHINCS are the two hash-based signature schemes identified as under evaluation for standardization.XMSS is stateful, whereas SPHINCS is stateless.
4) Code-based Cryptography:
Code-based cryptography relies on the difficulty of decoding linear codes and is considered robust to quantum attacks when key sizes increase. Its practical trade-off is strong efficiency and security at the cost of very large public keys.
- Code-based cryptosystems use error-correcting codes and rely on the difficulty of decoding linear codes.
- Increasing key sizes by a factor of 4 is presented as making code-based algorithms robust to quantum attacks.
- Large-dimensional Low-Weight-Code-World Problems are considered infeasible, supporting the security basis of these systems.
- In the described system, messages contain exactly t bits set to 1 and are encrypted by multiplying the message m by the receiver’s public matrix K.
- McEliece encryption and decryption are fast with very low complexity, but its public keys range from 100 kilobytes to several megabytes.