Academia and businesses are therefore intensely researching new cryptographic algorithms (usually public-key algorithms) which are expected to be efficiently secured against an attack using a quantum computer.
Various internet and industry standards use asymmetric cryptography based on RSA or elliptic curve cryptography (ECC) to protect data communication between smart cards, smart phones, computers, servers, or industrial control systems. As an example, with the RSA algorithm a public-key encryption (PKE) scheme can be realized that allows it to send an encrypted email (e.g., with PGP/ GPG or S/MIME) to a recipient without the need to first exchange a symmetric key on a secured channel – the public key of the recipient is sufficient to achieve confidentiality. Other applications of asymmetric cryptography are digital signatures, also based on RSA or ECC. They can be used to sign and verify data where the public key is used to check the validity of a signature. If a digitally signed contract or long term archives is modified after signing, even by one bit, a digital signature check will fail.
Together, PKE and digital signatures are both crucial in the Transport Layer Security (TLS) protocol which is the backbone of secured communication in the Internet and used by browsers, smart phones and increasingly also Internet of Things (IoT) devices.
However, since the seminal work of Peter Shor in 1994 it is known that RSA and ECC are susceptible to attacks by quantum computers. A quantum computer powerful enough to implement Shor’s algorithm would allow the factoring of the public key of the RSA cryptosystem in polynomial time. Additionally, the algorithm can also be adapted to break ECC-based public keys. Another quantum algorithm has been proposed by Grover that can be used to accelerate brute-force attacks on symmetric block ciphers like AES. However, it does not lead to a complete break but roughly halves the bit-security level of symmetric algorithms. As a consequence, the key length of algorithms with a 128-bit key and thus 128-bit security has to be doubled (moving to AES-256).
Post-Quantum versus Quantum Cryptography
Post-quantum cryptography (PQC) refers to new cryptographic algorithms executed on classical computers that are expected to be efficiently secured against attackers using quantum computers. In contrast, quantum cryptography (QC) or more specifically quantum key distribution (QKD) uses properties of quantum mechanics to establish a secret key between two parties. This secret key can then be used to encrypt bulk data using classic symmetric ciphers like AES. The security of QKD is not based on a computational assumption that a measurement of a quantum state (e.g., of the spin of a photon) destroys the state and that quantum states would be protected from being copied. As a consequence, if a passive attacker performs a measurement to obtain the key, this attack could be detected by the receiver. However, QKD is not a universal replacement of RSA and ECC.
In contrast, post-quantum cryptosystems are executed on classical computers and have the same high-level behavior as currently available ciphers so that they act as a drop-in replacement. Currently, the main concern of researchers in PQC is asymmetric cryptography (i.e., replacing RSA and ECC) as the threat of Grover’s algorithm to symmetric schemes can be mitigated by moving to already available 256-bit secured algorithms.