After attending a talk by Psi Vessely on Quantum Key Distribution (in particular on BB84), the UCSD crypto group discussed some of the alleged benefits of QKD. We mentioned the “standard list”:

1. No-cloning theorem provides protection against evesdroppers that “standard” crypto cannot achieve ¹

2. The protocol itself only requires authenticated channels, so can be viewed as “key exchange within Minicrypt”

In our discussion, Adam Suhl pointed out that we don’t strictly need to be within Minicrypt, as (using previously-shared randomness) you could use a one-time MAC to authenticate messages. This leads to a natural question:

If you run QKD using a one-time MAC to authenticate communications, can you “gain” on the amount of shared random bits you have?

If you could do the above, it gives a construction of information-theoretic secure cryptography which both doesn’t assume that you’re in minicrypt, and doesn’t have a limit on the amount of communication you can do.

The Heuristic Answer

Even without describing the BB84 protocol, it should be clear that the answer depends on the (classical) round complexity of the protocol. In particular, all classical communication must be MAC’d, and therefore expends ² some constant amount of the key material both parties have. This means that a protocol which is \(O(f(n))\) classical rounds must also have \(O(f(n))\) bits of preshared randomness to execute, where \(n\) is the amount of quantum bits communicated.

Provided the algorithm can agree on \(\omega(f(n))\) random bits, we would therefore have a strict “gain” in the number of shared bits upon a single execution of the protocol. We could then “bootstrap” this procedure to get an arbitrary number of pre-shared bits, which we can use with things like the one-time pad to discard all computational assumptions!

The Actual Answer

At this point, I would normally do some computations. For better or worse, while searching for the round complexity of parts ³ of the BB84 protocol, I found this paper. Section 4 in particular describes a relatively simple protocol which seems to achieve “OTP-like” encryption by using QKD with one-time MACs to generate enough key material. Note that I haven’t read the full paper (and do not work in this area), but the plausible idea we had seems to have been fleshed out by this paper, and they claim it works.

Issues with full QKD without Minicrypt

The aforementioned scheme seems to provide a construction that allows you to exchange enough key material to do the one-time pad on arbitrarily large messages with no computational assumptions. This is what I was hoping for, and we found it!

Unfortunately, there’s the following dumb attack an evesdropper can always do to thwart this plan — measure every quantum message! This measurement can lead to the key exchange protocol failing, and a reduction in the jointly shared randomness of Alice and Bob, which will eventually force them to fallback on using techniques that do not deplete their jointly shared randomness (such as computationally secure MACs to authenticate the channel).

So the answer to “Can you do QKD without Authenticated Channels”? seems to be yes, but no. Still, the possibility of “bootstrapping” QKD is something I haven’t seen in casual discussions of it, and was quite interesting to learn about.