I’m not sure if this makes sense, but I know that there is quantum and post-quantum encryption, and I’m curious whether quantum computing can break a quantum encryption.
1
-
$\begingroup$ perhaps you mean ECC type cryptography? See security.stackexchange.com/a/261196/8618 $\endgroup$– akostadinovApr 14, 2022 at 12:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is a good question that highlights the unfortunately broad use of the term "quantum cryptography". Either way, the TL/DR of it is that, although quantum computers break many currently used classical public key distribution protocols, we also have:
- Provably, no, quantum computers will not be able to break encryption with keys exchanged with various quantum key distribution (QKD) protocols; and
- Conjecturally, no, quantum computers should not be able to break public-key encryption based on various post-quantum cryptography schemes.
In more detail, in many of the quantum key distribution schemes, such as the BB84 protocol and the E91 protocol, qubits are exchanged between parties that wish to communicate. These protocols are based on the no-cloning theorem, and are information-theoretically secure. This implies that no amount of computational power would be sufficient to crack ciphers based on these protocols. However, practical implementations of such schemes might indeed have other serious vulnerabilities - the machine that sent photons in the very first implementation of BB84 made different sounds, depending on whether it was sending qubits in the $\{|0\rangle,|1\rangle\}$ basis or the $\{|+\rangle,|-\rangle\}$ basis!
Compare the information-theoretical security of QKD protocols to the many protocols currently used for secure public-key communication, such as RSA and Diffie-Hellman, along with elliptic-curve based schemes. For example, these cryptographic schemes were thought to be computationally secure, in the sense that the resources used to crack these schemes were thought to grow exponentially with key sizes. Of course, the big break-through of Shor is that no, these schemes are not secure in the presence of powerful-enough quantum computers.
Accordingly, partly because we do not yet have a "quantum internet" powerful enough to securely implement QKD protocols to trade qubits around the world, and we only have the "classical internet", the race is on to find public-key cryptosystems that don't involve trading qubits between Alice and Bob but are nonetheless conjectured to be computationally secure even in a world of quantum computers. This is the meaning of "post" in post-quantum cryptography. These are classical protocols that are conjectured to be computationally secure against even a quantum computer.
Post-quantum cryptography began as a field, after the development of both quantum key distribution schemes and Shor's algorithm. The last line of Jennifer and Peter Shor's lovely limerick on the cat-and-mouse games of using a quantum computer to read e-mails could probably also be changed to "Till we've crypto that's -post- quantum, and daunt 'em." But that might not scan as nicely.
