What authentication protocol to use for BB84 and other QKD protocols?

Question

Just like other classical and quantum key distribution protocols, BB84 is vulnerable to "man"-in-the-middle attacks, where Eve pretends to be Bob to Alice, and Eve pretends to be Alice to Bob. The countermeasure against this potential "man"-in-the-middle attack is to implement authentication and data integrity checks on the Alice-Bob classical channel. ^{[1] [2] [4] [5]}

My question is: what authentication protocol should we use for BB84 and other QKD protocols?

I can think of the following candidates:

1. We could use pre-shared keys as suggested in [1]. But that feels problematic to me for two reasons.

   1.1. The whole point of having a key distribution protocol is to avoid the need for pre-shared keys. If the pre-shared key is ever leaked, authentication and hence the QKD protocol itself is compromised.

   1.2. A client can only connect to a server if the client and server already have agreed on a pre-shared key. In many use cases (e.g. web browser connecting to a web server) this is a very unreasonable requirement.

2. Start with a pre-shared key for the first key agreement. But during that first key agreement, generate some extra key bits that are used for authentication during the next key agreement, etc. This is suggested in [3] and [6]. However, if one of the devices loses its state (e.g. due to a power cycle or field replacement after a failure) we have to revert back to the first pre-shared key. Thus, the first pre-shared key will always be a vector of attack. And, it still suffers from the problem described in 1.2 above.

3. In classical key distribution protocols problem, both 1.1 and 1.2 are solved by using authentication protocols such as RSA or DSA that rely on PKI and on the use of certificates and trusted CAs. However, we cannot use RSA or DSA for QKD authentication because both RSA and DSA are quantum-unsafe (they assume discrete logs are hard).

4. Use post quantum crypto (PQC) algorithms to authenticate the QKD session. But if you trust PQC, then why not use it for everything (i.e. not only authentication but also the actual key agreement) instead of using QKD; PQC is easier to deploy since it not require any quantum photon sources or quantum photon detectors.

So, to reiterate my question in another way, is there an authentication protocol that achieves both of the following goals?

A. It allows a client to authenticate any server without assuming that the client and server have a pre-shared key.

B. It is quantum-safe.

---

^References:

^{[1] [Is quantum key distribution safe against MITM attacks too?](https://crypto.stackexchange.com/questions/2719/is-quantum-key-distribution-safe-against-mitm-attacks-too#2721)}

^{[2] Van Meter, Rodney. Quantum Networking (Networks and Telecommunications). Wiley. Kindle Edition. Section 5.2: "A true man-in-the-middle attack is foiled by (and explains the need for) authentication and data integrity checks on the classical channel."}

^{[3] Reis, André. Quantum Key Distribution Post Processing - A study on the Information Reconciliation Cascade Protocol. Section 1.1 footnote: "Specially important, those [extra key] bits can be used to generate Message Authentication Codes for future QKD executions to extend the length of the shared key"}

^{[4] Reis, André. Quantum Key Distribution Post Processing - A study on the Information Reconciliation Cascade Protocol. Section 2.2: "the classical phase uses a public classical authenticated channel (using Digital Signatures or Message Authentication Codes)"}

^{[5] ETSI GS QKD 002 V1.1.1 "Quantum Key Distribution; Use Cases". Section 4.1.2: "Quantum key distribution, too, requires authentication of the parties to rule out man-in-the-middle attacks. This is done by public discussion on the classical channel which uses a message authentication primitive to guarantee message integrity."}

^{[6] ETSI GS QKD 002 V1.1.1 "Quantum Key Distribution; Use Cases". Section 4.1.3: "In QKD, a small fraction of the continuously generated key can be used for information theoretically secure message authentication, but when a link is taken into operation, a pre-distributed initial secret is necessary to authenticate the public channel before the first quantum keys become available. This is comparable to digital signature schemes, where the public key (mostly in the form of identity certificates) of the sender, or the public key of a trusted third party, when transitive trust relations are applied, must be pre-distributed (e.g. with the web browser). Insofar the necessity of a pre-distributed secret constitutes no principal disadvantage of information theoretically secure authentication schemes, as opposed to signature based or MAC based authentication systems, as this is claimed e.g. in [i.21]."}

Answer 1

In classical cryptography, the Diffie-Hellman key exchange is also susceptible to a man-in-the-middle attack, and to get around that, we use a digital signature algorithm, like RSA or ECDSA.

You can take a similar approach in quantum cryptography, such as with the Gottesman-Chuang algorithm or something similar. It is a pretty simple algorithm, if Alice places qubits into a random state of $|0\rangle$, $|+\rangle$, or $|1\rangle$, then another person measuring it can't know what superposition it is in just from a single copy, and thus you have a one-way function that could used to verify Alice's identity.

Alice's "public key" could be a database of consumable public keys stored by a trusted third party where only Alice knows the state of those qubits (that information is stored classically). Those qubits could be stored in the database in pairs, so if Bob wants Alice to sign a specific message, he can grab the qubits from those pairs associated with the specific 0s and 1s and ask Alice to verify those.

When Bob wants Alice to verify her identity with the qubits he grabbed associated with his message, he sends Alice the message and Alice would know in private the states associated with those qubits so she could respond with their respective states.

Bob can verify Alice's identity then by recreating the qubits with the states provided by Alice and then doing the swap test to check if they're equal. The message being signed/verified should be rather lengthy to make sure there's a high probability that if they are talking to an imposter, they won't get lucky and guess the states.

There is a bit of a problem with quantum cryptography in that the only quantum-safe one-way function is creating a qubit in a superposition state, but the No Cloning Theorem only prevents reversing this function if you make one copy. If you make money copies, you can reverse it due to Holevo's theorem.

This means any digital signature algorithm will have to use consumable keys with limited copies of them. However, if that limitation does not bother you, it is a quantum-safe algorithm, especially if you have only one database of consumable public keys. If you have multiple copies of the same key, you can compute exactly how much it undermines the security, and you can offset it by using longer messages.

An attacker who makes measurements on copies of the same key only increases their confidence that they know what it is but never gets to 100% certainty. So if you increase the length of the messages signed, then the higher probability of them making a mistake will counteract their greater confidence in what the key is, making it more likely they make bad guesses which would be caught by the swap test.

There is also the obvious problem that digital signature algorithms using quantum mechanics as the one-way function imply long-term storage of qubits without decoherence, which is not practical. One way around it may be to establish a trusted connection with a trusted third-party in person which you could then send the public keys to the moment someone else tries to make a connection to your server, and then you can direct them to go to the third-party for the public key.

Both the former problem with limited copies of signatures and the latter problem of potentially needing a trusted third-party established through other means implies a functional quantum network with high security would probably have to be rather centralized around a small number of nodes that can verify connections.