Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis)

Question

I know that people may be yelling "of course!" at the title of the question, but my concern is not about how to construct quantum-resistant primitives, but rather how to use the power of quantum computers to develop secure and efficient cryptographic primitives and protocols.

For example, in post-quantum Cryptography people are concerned about the power of quantum computing as an adversarial situation, and the main use of such power is to solve problems like factoring or discrete logarithm (whereas the quantum-resilient primitives involve classical algorithms).

Are there primitives that use this power as an advantage (for instance, to improve efficiency)?

If quantum computers are going to become a reality then I agree we should prepare and deploy quantum-resistant schemes, but besides using the quantum power to perform cryptanalysis on certain classical cryptosystems, we could also use it to develop primitives involving quantum algorithms in their implementation (these may not be deployable before we live in a post-quantum world, but they could be used once scalable quantum computers exist).

Have this been studied? are there any proposals? In other words,does having quantum computers improve the Crypto world somehow?

Answer 1

As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography).

All the field was arguably started by Stephen Wiesner’s invention of Conjugate Coding in 1969, but which was rejected remained unpublished until 1983. He proposed a theoretical way to use quantum mechanics to construct unforgeable banknotes. This stayed a pedagogical example until (roughly) the last decade, which saw a renewed interest in quantum money schemes.

The main and best-known application is quantum key distribution (QKD), for which many protocols and have been studied since Charles Bennett and Gilles Brassard’s seminal paper in 1984. These protocols need the capacity to exchange attenuated light pulses (typically single photons or coherent states) between the partners, a capacity which has been recently demonstrated over 400 km. There is currently research going on to build quantum relay, some experimental networks using “trusted relay” are operational, and a satellite has been sent by China last year to serve as a quantum communication relay. Beyond this line of work optimizing the “practicality” of these protocols, theoreticians work to improve the security proofs, going in some cases until device-independent security (the protocol is secure even if the physical device you need has been built by the adversary).

Bit commitment (BC) schemes have been proposed since 1984, in the same paper as QKD, but attacks were always found. In 1997, Dominique Mayers, and, independently, Hoi-Kwong Lo and H.F. Chau showed that unconditionally secure quantum bit commitment was impossible. Since secure BC protocols have been found in specific scenarios:

• Protocols secure against adversaries with limited noisy quantum memories
• Non-composable secure protocols in a relativistic setting, where the fact that no information can propagate faster than light is a key part of the security proof.

Other relativistic quantum protocols have been studied for position verification since 2010, but security proofs remain hard to be found. We know that we will be limited to computational security, but the best generic attack is known is currently exponential, which leaves hope for security protocols.

Another line of research is blind quantum computing, the quantum analog of completely homomorphic encryption: it is possible to make a quantum computer (if you have one) perform a commutation on encrypted data in a completely blind way, at a small extra cost. The operator of the computer has no way to know anything about the computation (except its size), while the client, which only needs a small quantum apparatus (similar to the QKD one) gets the result of the said computation.

There are of course other avenues of research in quantum cryptography. If you want to have an idea of some of the subjects of this community, you can look on the web the program of the annual QCrypt conferences, where the slides of many talks are online.

Answer 2

Quantum Key Distribution as a concept dates back to the BB84 (Bennett, Brassard) protocol, and has been implemented for countering passive attacks, such as Man in the Middle. In theory it is impossible to eavesdrop without disturbing the wave function describing the state of the quantum photon channel. ID Quantique is one company in this domain and government implementations abound.

M. Wiener proposed an unforgeable quantum money system around the same time. The issue of quantum randomness and its use is also an area of research.

The focus has been not on efficiency but security for high value communication channels.

Answer 3

Quantum computers will help crypto especially in creating pure randomness. Given indefinite computational power it is always possible to derandomize any randomness that is generated classically. Most of the computers generate randomness by capturing the LSB of the clock or the time required to access hard-disk etc. These are considered random just because our measuring instruments are just inefficient. But if we had precise enough measurement devices then these are no longer random.

There is a very good example on randomness related to coin tosses:

youtube.com/watch?v=AYnJv68T3MM

This isn't the case in quantum computers. When it comes to quantum computers we generate the randomness by determining the spin of the electron of a phosphorous atom. But this electron is in the superposition state of +0.5 and -0.5 spin. The moment we measure the spin of the electron it will collapse to either one of the definite state. Which is equally likely. There is no way that one might end up determining the randomness. In other words if anyone who is able to determine the randomness in the spin would end up breaking the Heisenberg's uncertainty principle.

Answer 4

While some think a quantum computer will give a stronger basis for random numbers, you don't need a quantum computer for quantum randomness. Given that some answers have already mentioned QKD, I'll focus instead on the complexity classes of quantum computing, and how they might be used to build cryptographic primitives.

Complexity Classes

Cryptography in general bases security claims on costs associated with cryptanalysis. For example, the Learning with Errors concept reduces a worst-case approximation to an average case for being able to solve lattice problems. It's understood that solving a lattice problem is "hard," meaning it is computationally infeasible to solve the problem in practice.

The most commonly referenced complexity classes are some form of $P$ and $NP$. These denote the time it takes to solve a respective problem, either in polynomial time or non-polynomial time.

$BQP$ is one of a few quantum complexity classes, which stands for bounded-error quantum polynomial time. While it is understood that:

$P \subseteq BPP \subseteq BQP \subseteq AWPP \subseteq PP \subseteq PSPACE$

The relationship between $BQP$ and $NP$ isn't fully understood yet. Shor's algorithm, which is one of the more famous instances of a quantum algorithm, is known to be in $BQP$ but believed to be outside $P$.

Impact on Cryptography

If the majority of cryptographic schemes make use, in some way, of the hardness of problems then it makes sense to assume that the $BQP$ class will also impact the security proofs and reductions in cryptography. A simple argument for this is as follows. Shor's algorithm is in $BQP$ and believed to be outside $P$. We know Shor's algorithm jeopardizes cryptography based on factorization. Thus, there are potentially many more algorithms in $BQP$ but not in $P$ that will jeopardize cryptographic schemes. That said, we also know that quantum computing is not universally better than a classical computer, there are certain problems where performance is equal.

Thus, it could be argued that with a new understanding of $BQP$, we may find different security reductions are possible based on problems in $BQP$. If it's discovered that $BQP$ intersects $NP$, I think this would support reductions of such $NP$ problems for use in cryptography.

The Upshot

we could also use it to develop primitives involving quantum algorithms in their implementation

Yes, we can use knowledge of quantum complexity to inform decisions on constructing new cryptographic primitives.

Have this been studied? are there any proposals?

The closest example of this I am aware of is a proposal that uses the Riemann sphere for the $l_1$-ball and $l_\infty$-ball. This method was proposed given the potential correspondence between the Bloch sphere and Riemann sphere. You can find a brief overview here.

does having quantum computers improve the Crypto world somehow?

Yes. The complexity associated with quantum computing will have additional impacts beyond quantum algorithms known to threaten some classical cryptography. The potential impact outside of cryptanalysis may come in the form of novel reductions in security proofs for cryptography that relies on $BQP$ problems. Further impacts may also come in the form of cryptography using the Riemann sphere as a foundation for primitives, allowing similar models between cryptography and quantum computing.

Answer 5

The one great advantage of quantum computer is generating pure randomness. It is actually not necessary that the randomness generated be uniform but may be biased based on the superposition state. But nevertheless it is not predictable by any of the measuring instruments (even theoretically).

The pure randomness created by quantum computer is not just helping the quantum cryptography but also classical Cryptography (modern). For example a quantum one time pad is far more secure than a classical one just because the randomness generated is pure. When it comes to RSA, for every 200 RSA public keys there are atleast two moduli with common primes( yes this means the security of those two keys is broken). This is just because the randomness generated while generating the primes are not truly random. This has nothing to do with the RSA security but the randomness generated while generating the primes!! A quantum computer would solve this problem easily.