Quantum computing is the area of computing that takes advantage of quantum physics, i.e., the behavior of subatomic particles like electrons or photons, for computing.
There are two principles that are exploited on quantum computing:
- Superposition. Quantum particles behave like a wave, and they are described by the Schrödinger equation. Then, there is incertitude and a probability that a particle has different positions.
- Entanglement. When a pair of particles are entangled, they remain connected even when separated by long distances.
The basic unit of quantum computer is the qubit. AQ stands for algorithmic cubic.
Classical bits have either the value 1 or 0. However, the qubit could have a probability to be 0 or to be 1 (i.e., they could have both values at the same time), because of the superposition principle.
A single qubit, holding the probability of being either 1 or 0 at a given level of probability, could store much more information that a single classical bit.
Qubits are represented graphically using the Bloch’s sphere. The north and south poles of the sphere represents the pure status 0 and 1. The equator represents the values. The other position within the spheres represents the amplitude and the relative phase between the states 0 and 1.
At the time the measure of a qubit is done, the qubit collapses and it has a single value (either 1 or 0).
Implementation of Quantum Computers
The implementation of quantum computers find these challenges:
- Quantum computers need to operate in temperatures near to absolute zero temperature (-273,15 ˚C).
- Qubits are stable only during a short period of time and lose easily the value it is storing.
Current quantum computers only have dozens of qubits, and qubits states does not last long.
Companies working on Quantum Computing
Some companies working on quantum computing:
- Google Quantum AI
- SandboxAQ
Quantum and Post-quantum Cryptography
Quantum cryptography (QC) is the field that exploits quantum properties for cryptography. It is based not in math, but in quantum hardware.
Quantum key distribution (QKD) is an example of quantum cryptography. It allows to use key encapsulation mechanism (KEM) using quantum technology. One of the properties of entanglement is that it is known when the qubit has been checked (it means, the secret has been already revealed).
Post-quantum cryptography (PQC) refers to the development of technologies that are secure enough against quantum computing attacks.
Quantum Computing Algorithms
The Shor algorithm is a quantum algorithm can be used to find the prime factors of an integer. It was discovered by Peter Shor in 1994.
Shor algorithm is effective only against asymmetric key algorithms like RSA or Diffie-Helman (DH). It is not effective against symmetric key algorithms.
The Grover algorithm is a quantum algorithm that is effective to attack symmetric key algorithms like AES or SHA-3. It was discovered by Lov Grover in 1996.
Challenging Pre-Quantum Cryptography
Classical or pre-quantum cryptography relies on 3 mathematical hard problems:
- Integer factorization problem
- Discrete logarithm problem
- Elliptic-curve discrete logarithm problem
All these problems can be solved easily using a quantum computer running Shor’s algorithm; this implies that the existence of a quantum computer would nullify pre-quantum cryptography.
The Q-day is referred as the day when traditional cryptography is vulnerable to quantum computing attacks.
Though as of 2023 the Q-day has not yet arrived (as far as it is publicly known), there is already an assumption that it will come eventually.
The “harvest now, decrypt later” strategy or store now, decrypt later (SNDL) consists of storing current pre-quantum encrypted data to be able to decode it once quantum computing is available.
Post-Quantum Cryptography Algorithms
Candidates for PQC:
- McEliece Algorithm (Code-Based Cryptography)
- Multivariate Algorithm
- Hash Cryptography
- Lattice-based Cryptography (LBC)
- Isogeny-based Cryptography (IBC)
How to protect against Post-quantum Cryptography
Symmetric keys can double the length of keys, and they will be protected against the Grover algorithm.
On the other hand, pre-quantum asymmetric algorithms should be replaced. Standard organizations are looking for candidates.
As of 2023, NIST is working on the following selection projects:
- NIST 1
- Key Exchange
- Crystals’ Kyber
- Crystals’ Dilithium
- Digital signature
- Falcon
- SPHINCS
- Key Exchange
- NIST Review of Finalists
- Key Exchange
- BIKE
- HQC
- Classical McEliece
- Key Exchange
- NIST Digital Signatures
- HAWK
- MAY
- SDitH
- PKP
Hybrid cryptography is the combination of pre-quantum and post-quantum cryptography.
NSA recommends go straight for post-quantum cryptography instead of using hybrid cryptography.
The idea of using hybrid cryptography instead of post-quantum cryptography is to have a fallback strategy in case PQC is not proven to be secure.
Post-Quantum Cryptography Organizations
Post-quantum cryptography organizations:
- Post-Quantum Cryptography Alliance
Post-Quantum Cryptography Alliance
Post-Quantum Cryptography Alliance (PQCA) was founded in 2024 within the Linux Foundation.
External References
- Wikipedia; “Quantum computing“; Wikipedia
- Wikipedia; “Quantum cryptography“; Wikipedia
- Wikipedia; “Post-quantum cryptography“; Wikipedia
- Marc Manzano & Sandra Guasch; “Overview of Post-quantum cryptography“; CriptoredCON 2023, YouTube