Beyond QKD

I. Introduction

Quantum networks are being deployed across the world, especially in Europe and China. However, all of these deployments are application-specific Quantum Key Distribution (QKD) networks. Despite the expectation that most of the disruptive potential of quantum networks lies in networks based on entanglement-distribution with quantum memories (to which we will from now refer to as "next-generation quantum networks") QKD is the only application that is commercially available, and has been since the early 2000s.

There is much work in the R&D domain on next-generation networks and applications but much of it is focused on working towards the quantum memory network stage and beyond despite there being two stages, the prepare-and-measure and entanglement generation network stages, between them and today's QKD networks, i.e., trusted repeater network stage. This jump is understandable given that the most promising applications with the most significant quantum advantage lie in the later stages but the reality is that there are still many years of research and experimental development needed to reach the quantum memory network stage. We will have to wait even longer if we want to consider practical large-scale deployments. It would be unproductive if we do not devote at least some effort to exploring the intermediate two stages, the prepare and measure and entanglement distribution network stages, given that many applications in these stages are feasible with hardware that is commercially available.

To address this gap an inventory of quantum network applications would be useful. A few such inventories are already available such as the Quantum Network Protocol Zoo, this review of quantum cryptography beyond QKD, or this other about unclonable cryptography. Such inventories are incredibly useful and a valuable treasure trove of information but can be difficult to use for the purposes of application development for two reasons. First, these inventories often dive deep into the technical, mathematical, and theoretical background which is important, but difficult to use when trying to figure out the value it might provide to the user. Secondly, they generally include applications from all stages of quantum network development which can be distracting as the most attractive applications tend to also have the most difficult hardware requirements.

This document sets out to identify use cases in which quantum networks can provide practical benefits over classical methods today. The focus of this document is thus on the value each application brings to the user and on its feasibility with today's technology. The aim is thus not to replace the other inventories but rather to build upon them but with a user-centric and feasibility focus. In fact, previous inventories served as a starting point for this one. In particular, the goal is to provide insight into where the does the quantum advantage of different applications sufficiently exceed the classical state of the art that it is worthwhile for vendors and users to invest their resources into.

Finally, we also hope that this inventory provide a bridge that will help connect the work put into the deployment of QKD networks with next-generation quantum network development by slowly eliminating the dichotomy between the two types of network. After all, they are both quantum networks that need to transmit single photons on a fiber with many similarities at the network control and management level.

II. Applications and primitives

In this section we inventorise the actual applications and primitives; where a primitive is a building block of a more complex application. However, we don't try to distinguish which item is an application or primitive leaving that to the reader.

For each item, we include the following:

1. Description: Brief, simple description that is easy to understand by anybody who might benefit from its use. Applications/primitives with a more technical benefit can be explained with more complex language, but applications/primitives for general use should be explained in simple English.
2. Reference: A reference to a more technical/detailed description such as an academic journal or technical reference.
3. Classical state of the art: Most of the application/primitives can be implemented without any quantum technology whatsoever. It is important to be aware of what the classical state of the art is to make a more reasoned judgement of what value there is in its quantum advantage.
4. Quantum advantage: The benefit over the classical state of the art that is possible with commercially available hardware. Additional assumptions can be made as long as they are stated, e.g., adversary has bounded storage.
5. Hardware requirements: We make a distinction between BB84 nodes that generate and measure single-qubit states, MDI-QKD nodes that post-select entanglement by interfering two single-qubit states, and entanglement-generation sources. Note that although single-qubit generators and detectors are available, scalable implementations will still require weak coherent pulses. We will mention if lab implementations use off-the-shelf QKD-type hardware (of either type) or require modifications.
6. Implementations: Links to known implementations outside of the lab, if any. These should be links to source code repositories, vendor brochures, news releases from vendors, but not to academic literature or press releases about scientific accomplishments.

2.1 Unforgeable tokens

An unclonable primitive, sometimes also called private-key quantum money in the literature, refers to tokens distributed by a central authority that are inherently impossible to counterfeit (quantum states), while the verification is only possible by a central authority holding a secret key (to ensure security, this will be the same authority generating the tokens). In principle, flexible spending is limited by the lack of quantum memories to store the tokens, and hence applications must be sought in settings where instantaneous spending is an advantage.

Reference: https://www.nature.com/articles/s41534-022-00524-4

Classical state of the art: Although classical information can always be copied, we can construct validation techniques such that each bitstring can only be validated once (its unforgeable), for example by forcing a central authority to perform validation. A prototypical application of unforgeable tokens is of credit card transactions with a central verifying body. However, classically, the central authority would refresh both the token and the secret key after each transaction.

Quantum advantage: Since quantum data cannot be copied, the tokens can change holder without the central authority needing to update their database of private keys nor the tokens. Therefore, they allow for simultaneously achieving unforgeability, instant validation and user privacy, while only two out of these three properties are achievable with classical tokens.

Hardware requirements: In principle, memories are necessary to ensure flexible spending (the tokens are quantum states). However, this can be replaced by a network of trusted agents in verifiable locations (through possibly primitive 2.6 Quantum Position Verification). Noise-robust experiments have been performed with single-photon sources generating BB84 states, but there is yet no complete security proof for weak coherent pulses.

Implementations: https://cdn.prod.website-files.com/669960f53cd73aedb80c8eea/6737abcb0d737d15feea6d4d_Quantinuum_Quantum-Tokens-Whitepaper.pdf

2.2 Quantum digital signatures

The idea is to create two algorithms: one for signing and one for verifying, such that the sender associates a signature to a verification key (quantum state), after which any classical message can be signed and anyone holding a verifying key can prove the authenticity of a message. If we had access to public key infrastructure, we could publicly broadcast verification keys, but quantum communication allows for a certain number of trusted participants to still be able to check the validity of a signature by establishing a private verification key securely by means of quantum communication. In this case, the digital signature is an unclonable primitive, referring to the fact that verification is associated with a single signature, and is hence unforgeable. By definition, any digital signature scheme should be: correct, unforgeable, non-repudiable and transferable.

Reference: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.93.032325

Classical state of the art: Classically digital signatures require trapdoor OWF (they are a type of asymmetric cryptography): although RSA and discrete-log are broken by Shor’s algorithms, there are lattice/code/isoginy… post-quantum secure proposals being accepted by standardization bodies.

Quantum advantage: Can be made information-theoretically secure (assuming classical authenticated channels), as opposed to being computationally secure even assuming authenticated channels in the classical case. There are two type of protocols proposed in the theory (1) are quantum protocols assuming classical authenticated channels and (2) classical communication rounds on top of QKD, but the latter ones are less efficient. However, note that these type of enhanced digital signatures cannot be reused if the security guarantees are to be maintained.

Hardware requirements: The verification key can be measured immediately in the first phase of the protocol, such that no memory is needed. Digital signatures have similar implementation challenges as QKD, with security proofs for imperfect BB84 sources present; the main problem being that the setting up stage requires n-to-n quantum communication.

Implementations: Not known.

2.3 Private-key tokenized signatures

An unclonable primitive, sometimes also called tokenized MACs in the literature, refers to a signature scheme where the signing key (quantum state) cannot be used to sign more than a fixed number of messages, but can still be verified by verifiers holding a pre-shared verification key. Think of scenarios where you might want to delegate the signing of a message.

Reference: https://arxiv.org/pdf/2105.05016

Classical state of the art: This primitive does not really have a classical counterpart, as classically even if you share the classical signing key privately, this would allow unlimited signing capacity.

Quantum advantage: Cryptographically limit the number of copies that can be signed with a given signing key.

Hardware requirements: A number of BB84 states must be measured according to the desired signing, hence without memories it only allows for immediate signing (just a proof of concept is possible with current hardware). There is no much noise analysis done, but some protocols are resistant for up to 14% depolarizing noise.

Implementations: Not known.

2.4 Unclonable encryption

A good encryption method today does not mean that the encryption keys cannot be leaked or learner in the future, meaning that very sensitive information can suffer from harvesting attacks, that is, classically there is no way of stopping an adversary from copying encrypted information and waiting long enough to obtain the decryption keys. On the other hand, quantum communication allows us to develop unclonable primitives such as encrypting a message (plaintext) in a ciphertext (quantum state) in a way that the ciphertext cannot be copied, i.e. an encrypted message cannot be copied in transmission.

Reference: two important variants (1) assuming only pre-shared private key https://arxiv.org/pdf/1903.00130, and (2) assuming public-key infrastructure https://arxiv.org/pdf/2103.15009.

Classical state of the art: Classically you can always copy a ciphertext without the sender/receiver knowing, and possibly wait until you obtain the secret-key at a later point “harvest-now decrypt-later” attack.

Quantum advantage: Cryptographically prevent ciphertext copying (thus if you limit the number of copies of the ciphertext, you can also limit the harvest-now decrypt-later possibility). Note however that the outcome of the decryption is classical.

Hardware requirements: There are no noise analyses in the literature, but in theory the possibility to generate BB84 states is enough for both private and public key unclonable encryption.

Implementations: Not known.

2.5 Encryption with certified deletion

Given the huge amount of data that we produce, storage solutions exist for saving our (hopefully) encrypted data. However, there is no guarantee that these storage centers actually delete the data once requested. Actually, by only using classical technology, it is not possible to certify the deletion of information. When using quantum communication the paradigm changes and we can construct the following unclonable primitive: we can encrypt the plaintext in a ciphertext (quantum state) such that the recipient of the state can produce a classical string proving that any chance of recovering the plaintext is vanished.

Reference: two important variants (1) providing only private key encryption https://arxiv.org/pdf/1910.03551, and (2) lifting the previous scheme to a public key one by only adding classical communication rounds https://arxiv.org/pdf/2105.05393.

Classical state of the art: Classically you cannot prove that a ciphertext has been deleted.

Quantum advantage: Cryptographically prevent ciphertext storage without permission, by being able to certify the deletion of encrypted data.

Hardware requirements: No noise analyses in the literature, but in theory the possibility to generate BB84 states is enough. However, the BB84 states must be measured in the Hadamard basis to give a proof of deletion, hence without quantum memories it only allows for proving immediate deletion of received messages (just a proof-of-concept).

Implementations: Not known.

2.6 Quantum position verification

For some applications the geographic position of a party might be enough for identification of a party (you might be interested in storing your data in a data-center of your country, where it’s not the identity what matters but the location). While Global Positioning Systems are a way of locating yourself, for these type of tasks we want to verify that a message originates from a specific geographic location. Fortunately, the interference of two quantum states in combination with the principle that communication cannot occur faster than the speed of light, can be used to construct cryptographic protocols certifying the location of a third party.

Reference: For a compilation of existing QPV protocols see github.com/rellaner/awesome-position-based-quantum-cryptography

Classical state of the art: You can send radio wave signals and measure the time they take to return, but these are not resilient to collusion attacks.

Quantum advantage: Cryptographically ensure that the target is at the claim location, which is possible as long as the adversaries have access only to limited (linear instead of exponential) entanglement in the security parameter.

Hardware requirements: Noise-robust and multi-photon resistant protocols are present in the literature for different type of QKD hardware (DV, CV…).

Implementations: Not known.

2.7 Quantum fingerprinting

The idea of fingerprinting is for two parties compare if their respective bit strings are equal with as little communication as possible, by sending a function of their strings f(x) instead of the strings directly x. As an application, think of password-based identification where you want to authenticate yourself without revealing the actual password. Quantum fingerprinting consider the scenario where two parties try to compare their classical strings x,y by sending quantum states that depend on the strings x,y instead.

Reference: For a comparison between classical and quantum fingerprinting protocols see https://ieeexplore.ieee.org/abstract/document/1423153

Classical state of the art: Classically the best known algorithm requires O(sqrt(n)) bits of communication without any set-up assumptions, but if we assume the existence of a Common Reference String (which is quite a standard assumption in classical cryptography), then it’s possible with O(log(n)) bits of communication, that is, very efficiently.

Quantum advantage: By considering qubits to be communicated instead of bits, O(log(n)) qubits of communication are enough in the plain model, are a constant number of them in the CRS model.

Hardware requirements: There are noise-robust protocol in the plain model using weak coherent modes present. Although such technology exists in QKD hardware, it would require some modifications.

Implementations: Although there are no implementations with fully commercial hardware, the following article did one with plug-and-play IDQuantique hardware https://www.nature.com/articles/ncomms9735.pdf.

2.8 Bit commitment

The sender transfers a hidden bit to the receiver, postponing the moment when the receiver will discover its actual value, but the sender cannot change the value after they’ve committed to it. It’s a very important primitive to build more complex cryptosystems, but both classical and quantum bit commitment require of computational assumptions to prove its security.

Reference: Given that unconditional bit commitment is not possible neither classical nor quantumly, there are proposals for multiple models (1) assuming that the parties are allowed finite-bias, which is not composable but enough for using it as a subroutine in cheat-sensitive strong coin flipping https://sci-hub.st/https://journals.aps.org/pra/pdf/10.1103/PhysRevA.78.022316, (2) assuming a bounded/noisy quantum storage https://arxiv.org/abs/0911.2302 and (3) in a relativistic model https://arxiv.org/pdf/1504.00944.

Classical state of the art: They can be built from computational assumptions like one-way functions (symmetric cryptography) in the plain model.

Quantum advantage: General commitments can be made non-interactive using quantum communication, but if we want to build more complex primitives from them the advantages are not so clear. For example, for OT we need extractable commitments (which are necessarily interactive).

Hardware requirements: Experimental demonstrations vary for the type of model considered: relativistic, noisy/bounded storage… but in principle QKD-type hardware should suffice.

Implementations: Not known.

2.9 Oblivious transfer

A two-party primitive where the sender holds n messages, and the receiver chooses to get only one of them, in a way that it does not reveal to the sender which one was chosen. Interestingly, OT is complete for multi-party computing, meaning that any multi-party computation can be build from compiling multiple OTs. However, this compilation requires the OT to be composable, meaning that only OT protocols with a strong security proof are actually useful as building block for MPC.

Reference: Given that unconditional oblivious transfer is not possible neither classical nor quantumly, there are proposals for multiple models (1) in the noisy storage model https://arxiv.org/pdf/0807.1333, (2) in the relativistic model https://arxiv.org/pdf/1512.05649 and finally (3) with computational assumptions, that is, assuming the existence of OWF https://arxiv.org/abs/2406.09110 and (4) with computational assumptions (OWF) in the quantum-random oracle model (QROM) https://arxiv.org/abs/2209.04520. Note that only the protocols with computational assumptions are proven composable.

Classical state of the art: Classically OT requires trapdoor-OWF (asymmetric cryptography or public-key infrastrcture): RSA and discrete-log broken by Shor’s algorithms, but there are lattice/code/isoginy… PQC proposals at NIST.

Quantum advantage: Can be constructed from extractable and equivocal commitments, thus only requires OWF (as opposed to trapdoor-OWF classically). In practice, this means that it can be built from symmetric cryptography’s tools, whose security hasn’t been challenges by quantum computers.

Hardware requirements: Noise-robust experiments have been performed with single-photon sources generating BB84 states, but there are no complete security proofs for weak coherent pulses.

Implementations: Not known.

2.10 Multi-party computing

Distrusting parties can compute a function jointly on their private inputs, without having to reveal anything other than the outcome, that is, without having to share their data. In principle such protocol would be possible if we encrypted all our data in a way that we could compute homomorphically on it (the computations commute with the encryption), and in fact Homomorphic Encryption is a subset of Multi-Party Computing. However, the idea is that by relaxing the requirement of no communication between the parties we could obtain more efficient protocols. In practice, known quantum-enhanced constructions of MPC rely of quantum Oblivious Transfer, such that on a first stage oblivious keys are pre-processed using quantum communication, and can be later used when the function to compute is chosen, such that the second stage can consist only of classical communication.

Reference: The typical construction of MPC from OT consists of first obtaining 2-party computing as shown by https://dl.acm.org/doi/pdf/10.1145/62212.62215 (OT → 2PC) and https://mmp.cs.illinois.edu/pub/mpc-ot.pdf (2PC → MPC), these constructions where proven to be quantum-secure by Unruh https://arxiv.org/abs/0910.2912. If we instead assume the QROM, we can construct MPC from OT directly https://arxiv.org/abs/2304.10480.

Classical state of the art: Classically there are multiple constructions based on: secret sharing, FHE, OT… but they all rely on classical authenticated channels (thus trapdoor-OWF or public-key cryptography).

Quantum advantage: Since quantumly OT can be constructed just from extractable and equivocal commitments, quantum-enhanced MPC only requires the existence of OWF (as opposed to trapdoor-OWF classically). In practice, this means that it can be built from symmetric cryptography’s tools, whose security hasn’t been challenges by quantum computers.

Hardware requirements: The construction on top of OT is information-theoretically secure with an addition of constant rounds of classical communication, thus the same hardware requirements apply. That is, the ability to generate BB84 states suffices (although there are no complete security proofs for weak coherent pulses).

Implementations: Not known.

2.11 Strong coin flipping

Two remote and mutually distrustful parties agree on an uniformly random bitstring, with the guarantee that neither party can bias the result toward their preferred outcome. Coin flipping not only is useful on its own as a dispute-resolution mechanism, but also a building-block for many other cryptographic primitives (if composability of the protocol is properly ensured). An ideal SCF protocol should be: fair, secure and balanced. In practice, quantum SCF can be built from classical post-processing of single-qubit measurement outcomes as a consequence of the uncertainty principle.

Reference: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.84.052305

Classical state of the art: Since an perfect SCF is not possible unconditionally, we need to consider either (1) a trusted third party, or (2) 1/2-sqrt(x/2) bias and x probability of abort, or (3) computational assumptions such as the existence of OWF.

Quantum advantage: Perfect SCF with information theoretic security is possible against entanglement-limited adversaries, but if no assumption is made on the adversaries one can still obtain better bias than in the classical case.

Hardware requirements: Noise-robust protocols in the plain model using weak coherent modes are present in the literature https://www.nature.com/articles/ncomms4717. Although such technology exists in QKD hardware, using commercial hardware would actually require some modifications.

Implementations: Not known.

2.12 Weak coin flipping

Two remote and mutually distrustful parties agree on a winner/loser — in principle this is a weaker functionality than strong coin flipping, and classically WCF with small bias can be build from SCF with small bias. However, quantumly QCF can be built with arbitrary small bias, as opposite to SCF. As in the case of SCF, an ideal WCF protocol should be: fair, secure and balanced. Since WCF is a building block for leader election protocols, it is important to ensure that it is either composable or fits the security scheme of the particular leader-election protocol.

Reference: for analytical results see https://arxiv.org/abs/1911.13283, for a linear-optics implementation see https://journals.aps.org/pra/abstract/10.1103/PhysRevA.102.022414

Classical state of the art: Classically information-theoretically secure WCF is only possible if we allow for finite bias.

Quantum advantage: Although it is also impossible to do information-theoretically secure, there are protocols that achieve bias arbitrarily close to zero (as opposed to finite bias in the classical case).

Hardware requirements: In theory can be performed with linear optics, but the protocols do not scale well with number of rounds and it is not known how compatible it is with existing QKD hardware.

Implementations: Not known.

2.13 Randomized leader election

A distributed consensus protocol where parties must agree on a honest random unbiased leader, while some of the participants might be dishonest. Alternatively, it can be seen as a dice rolling, where each number corresponds to a participant, and the outcome is either a number assigned to an honest participant or an abort. Although the original idea was to have an entanglement-generation source distributed among all the participants, such that classical communication of measurement outcomes can be used to agree on a random honest number, its practical implementation can take the form of a tree-structure leaderboard formed by two-party elections (by adding constant rounds of communication to weak coin flipping protocols).

Reference: https://arxiv.org/abs/0909.4186

Classical state of the art: Can be either (1) information-theoretically secure with an honest majority or (2) requires computational assumptions.

Quantum advantage: If we allow arbitrary small probability of bias, it can be made information-theoretically secure (assuming a classical authenticated channel) even with a dishonest majority, as opposed to needing to assume an honest majority classically.

Hardware requirements: The construction on top of WCF may require classical authenticated channels and extra rounds of classical communication, but the same hardware requirements apply, thus can be done with QKD-type hardware.

Implementations: Not known.

2.14 One-time programs

An unclonable primitive, quantum states can be used to encode functions that can only be evaluated once before self-destructing (which is ensured by measuring them). These can be used to enforce licensing restrictions or preventing unauthorized software copies. However, note that without access to quantum memories the function (quantum state) must be evaluated immediately, thus applications have to be sought in this domain.

Reference: https://www.nature.com/articles/s41534-021-00435-w

Classical state of the art: Classically you cannot prove the destruction of a program.

Quantum advantage: Cryptographically ensure that the program can only be evaluated once, if we allow non-zero error of incorrect evaluation, which cannot be done simply with classical resources.

Hardware requirements: Experiments have been performed with entanglement-generation sources, but no complete noise-robust security proof has been given.

Implementations: Not known.

2.15 Secret sharing

A central authority splits a message (called shares) between n parties such that the original message can only be reconstructed if at least k parties collaborate. In particular, no individual share should reveal any information about the original message. The idea is to have an entanglement-generation source that creates stronger-than-classical correlations, and the sharing of secrets can be obtained by classically communicating the measurement outcomes of the shared quantum states.

Reference: If parties only have access to 2-party entanglement, most protocols can only perform 2-party secret sharing https://opg.optica.org/oe/fulltext.cfm?uri=oe-29-20-32244#g001.

Classical state of the art: Classically information-theoretic secret sharing is possible but requires the length of the shares to be as long as the message.

Quantum advantage: Both the length of the secret can be larger than the shares, and any eavesdropping attempt can be detected.

Hardware requirements: Since general secret-sharing protocols require GHZ state distribution (thus n-partyte entanglement), only 2-party protocols are implementable with entanglement-generation hardware, although there is no noise-robust security proof. However, the Qline architecture promises to do secret sharing only with BB84 sources and middle nodes that only perform rotations.

Implementations: there is no experiment, but commercial hardware providers have mentioned the possibility to perform it in the Qline https://veriqloud.com/security-of-a-secret-sharing-protocol-on-the-qline/.

2.16 Detectable Byzantine agreement

Sometimes called broadcast, refers to a distributed consensus protocol where multiple parties wish to agree on a common value proposed by a honest party (or abort), even when some of them are dishonest. Although we can obtain the highest form of security (information-theoretical security) only when at most one third of the parties is dishonest, even with quantum communication, computational security is achievable even when the majority of participants are dishonest. In other words, if we allow the participants to have access to public-key infrastructure, all the honest parties participating in the protocol have the guarantee that either they reach to a value proposed by another honest party, or the protocol will abort.

Reference: We can either build it directly using quantum communication from classical authenticated channels https://dl.acm.org/doi/pdf/10.1145/571825.571841 or by adding constant rounds of communication on top of QKD https://www.mdpi.com/1099-4300/22/10/1152.

Classical state of the art: Computationally secure cheat-sensitive broadcast is achievable assuming classical authenticated channels and signature schemes (thus public-key infrastructure).

Quantum advantage: Quantumly only classical authenticated are necessary, as opposed to signature schemes classically.

Hardware requirements: There are constant-rounds classical communication protocols that achieve broadcast when parties share QKD communication lines (see above), thus the hardware requirements are the same. However, we can build broadcast directly, in particular a 4-round protocol, if parties have access to entanglement generation sources https://www.mdpi.com/2076-3417/13/14/8405.

Implementations: Not known.

2.17 Anonymous transmission

We can build our networks such that messages are routed through multiple intermediaries, in a way that no single intermediary can correlate the sender with the recipient. We denote the class of protocols that ensure the confidentiality of the identity of the sender anonymous transmission protocols. If we further ensure the privacy of the message, we call it fully anonymous transmission. Since quantum devices allow to generate stronger-than-classical correlations, the idea is to use measurement outcomes to generate and distribute information from anonymous participants with higher security guarantees.

Reference: There are two types of protocols either (1) adding rounds of communication on top of QKD https://www.nature.com/articles/s41534-022-00535-1 or (2) directly https://arxiv.org/abs/quant-ph/0210194. A generalization of QKD to the multi-party setting with anonymity is called anonymous conference agreement https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.3.040306.

Classical state of the art: For anonymous transmission, information-theoretic security is possible only by assuming authenticated classical channels and broadcast channels (thus trusted third parties). If we moreover ask for privacy of the message, then we need to require either (1) a majority of honest parties, or (2) allow a single cheating party to cause the protocol to abort.

Quantum advantage: Information-theoretic security can be achieved assuming only authenticated classical channels, as opposed to broadcast channels or cheat-abort classically.

Hardware requirements: Since general anonymous transmission protocols require GHZ state distribution (thus n-partyte entanglement), only not-so-efficient protocols are implementable using QKD-type hardware. However, there is no noise-robust security proof yet.

Implementations: Not known.

III. Summary

N	Functionality	Description	Classical counterpart	Quantum advantage	Hardware requirements
1	Unforgeable tokens / Private-key money	A central authority distributes tokens that are inherently impossible to counterfeit (quantum states) and can only be validated once, but the verification is only possible by an authority holding the secret key.	Credit cards with a central verifying body.	Since quantum data cannot be copied, the tokens can change holder without the central authority needing to update their database of private keys nor the tokens. Can simultaneously achieve unforgeability, instant validation and user privacy.	In principle, memories are necessary to ensure flexible spending (the tokens are quantum states). However, this can be replaced by a network of trusted agents in verifiable locations (through possibly QPV). Noise-robust experiments performed with single-photon sources generating BB84 states, but no complete security proof for weak coherent pulses.
2	Quantum digital signatures	Associating a signature to a verification key (quantum state) such that any classical message can be signed and anyone holding a verifying key can prove the authenticity of a message. A QDS should be: correct, unforgeable, non-repudiable and transferable.	Requires trapdoor OWF: RSA and discrete-log broken by Shor’s algorithms, but there are lattice/code/isoginy… PQC proposals at NIST.	ITS (assuming a classical authenticated channels), as opposed to computational in the classical case. Note that a phase of QKD and further classical communication is also enough for ITS DS, but “direct” signing using quantum communication has better key rates. However, only one-time signatures are possible.	The verification key can be measured immediately in the first phase of the protocol, such that no memory is needed. Similar implementation challenges as QKD but security for imperfect BB84 sources present; the main problem is that the setting up stage requires n-to-n quantum communication.
3	Private-key tokenized signatures / tokenized MACs	A signature scheme where the signing key (quantum state) cannot be used to sign more than a fixed number of messages, but can still be verified by verifiers holding a pre-shared verification key. Think of scenarios where you might want to delegate the signing of a message.	Sharing the classical signing key privately, but this would allow unlimited signing capacity.	Cryptographically limit the number of copies that can be signed with a given signing key.	A number of BB84 states must be measured according to the desired signing, hence without memories it only allows for immediate signing (just a PoC). Not much noise analysis, but resistant for up to 14% depolarizing noise.
4	Unclonable encryption	Encrypt the plaintext in a ciphertext (quantum state) such that the ciphertext cannot be copied, i.e. an encrypted message cannot be copied in transmission.	Classically you can always copy a ciphertext without the sender/receiver knowing, and possibly wait until you obtain the secret-key at a later point “harvest-now decrypt-later” attack.	Cryptographically prevent ciphertext copying (thus if you limit the number of copies of the ciphertext, you can also limit the harvest-now decrypt-later possibility). Note however that the outcome of the decryption is classical.	No noise analysis, but in theory BB84 states are enough for both private or public key UE.
5	Encryption with certified deletion	Encrypt the plaintext in a ciphertext (quantum state) such that the recipient of the state can produce a classical string proving that any chance of recovering the plaintext is vanished.	Classically you cannot prove that a ciphertext has been deleted.	Cryptographically verify that a state has been deleted (thus the plaintext cannot be recovered).	No noise analysis. A number of BB84 states must be measured in the Hadamard basis to give a proof of deletion, hence without memories it only allows for proving immediate deletion of received messages (just a PoC).
6	Position verification	Verify that a message originates from a specific geographical position.	Send radio wave signals and measure the time they take, not resilient to collusion attacks.	Cryptographically secure against entanglement-limited adversaries.	Noise-robust and multi-photon resistant protocols present (DV, CV…).
7	Quantum fingerprinting	Two parties compare if their respective bit strings are equal with as little communication as possible.	Used for password-based identification (you want to authenticate yourself without revealing the actual password): classically requires O(sqrt(n)) bits in the CRS model and O(log(n)) in the plain. Note that in the CRS model this is already efficient.	Need to compare less bits: O(log(n)) if the parties share a trusted entanglement source and O(1) in the plain model.	Noise-robust protocol in the plain model using weak coherent modes present. Although such technology exists in QKD hardware, it would require some modifications.
8	Bit commitment	The sender transfers a hidden bit to the receiver, postponing the moment when the receiver will discover its actual value. The sender cannot change the value after they’ve committed to it.	Can be built from OWF in the plain model, and are a building block for many other primitives: coin flipping, ZK, signatures, verifiable secret sharing…	General commitments can be made non-interactive using quantum communication, but if we want to build OT we need extractable ones (which are necessarily interactive). There might still be specific applications where QBC can provide advantages, but it’s not clear.	Experimental demonstrations vary for the type of model considered: relativistic, noisy storage, bounded storage…
9	Oblivious transfer	The receiver chooses which one (only one) our of n messages of the sender to receive, without the sender knowing the choice. It’s complete for 2 party computation.	Requires trapdoor-OWF: RSA and discrete-log broken by Shor’s algorithms, but there are lattice/code/isoginy… PQC proposals at NIST.	Can be constructed from extractable and equivocal commitments, thus only requires OWF (as opposed to trapdoor-OWF classically). In practice, this means that it can be built from symmetric cryptography’s tools, whose security hasn’t been challenges by quantum computers. Instead of computational, we can also make physical assumptions: then ITS-QOT is possible, but it’s not clear if its composable.	Noise-robust experiments performed with single-photon sources generating BB84 states, but no complete security proof for weak coherent pulses.
10	Multi-Party Computing	Distrusting parties can compute a function jointly on their private inputs, without having to reveal anything other than the outcome.	There are multiple constructions based on: secret sharing, FHE, OT… but they all rely on classical authenticated channels (thus trapdoor-OWF).	Can be constructed from oblivious transfer, which in turn can be constructed from extractable and equivocal commitments, thus only require OWF (as opposed to trapdoor-OWF classically). In practice, this means that it can be built from symmetric cryptography’s tools, whose security hasn’t been challenges by quantum computers.	The construction on top of OT is ITS with an addition of constant rounds of classical communication, thus the same hardware requirements apply.
11	Strong coin flipping	Two remote parties agree on an unbiased uniformly random bitstring. Ideally should be: fair, secure and balanced.	Can be ITS with either (1) a trusted third party or (2) 1/2-sqrt(x/2) bias and x probability of abort. We can also build it from OWF.	ITS security achievable against unentangled adversaries, or better than classical bias.	Noise-robust protocol in the plain model using weak coherent modes present. Although such technology exists in QKD hardware, it would require some modifications.
12	Weak coin flipping	Two remote parties agree on a winner/loser. Ideally should be: fair, secure and balanced. Building block for leader election protocols.	Can be ITS with finite bias.	Can achieve bias arbitrarily close to zero (as opposed to finite bias in the classical case).	In theory can be performed with linear optics, but does not scale well with number of rounds and its not clear if commercial QKD hardware allows for an implementation.
13	Randomized leader election	A distributed consensus protocol where parties must agree on a honest random unbiased leader.	Can be either (1) ITS with honest majority or (2) requires computational assumptions.	If we allow arbitrary small eps-prob of bias, ITS (assuming a classical authenticated channel) even with a dishonest majority, as opposed to honest majority classically.	The construction on top of WCF may require classical authenticated channels and extra rounds of classical communication, but the same hardware requirements apply.
14	One-Time Programs	Functions that can only be evaluated once before self-destructing.	Classically you cannot prove that a program has been destroyed, but possible application is software protection, for which other solutions exist.	Cryptographically (ITS) ensure that the program can only be evaluated once, if we allow non-zero error of incorrect evaluation.	Experiments performed with entanglement-generation sources, but no complete noise-robust security proof.
15	Secret sharing	A central authority splits a message between n parties (called shares) such that the original message can only be reconstructed if at least k parties collaborate.	It’s ITS possible but requires the length of the shares key to be as long as the message.	The length of the secret message can be larger than the length of the shares (assuming classical authenticated channels) and eavesdropping can be detected.	2-party protocols proposed for different sources (entanglement-generation, post-selected entanglement, CV…), but no complete noise-robust security proof. A multi-party secret sharing is possible either with single-qubits in a line or if GHZ states are possible to generate.
16	Detectable Byzantine agreement / Broadcast	A distributed consensus protocol where multiple parties wish to agree on a common value proposed by a honest party (or have the security that the protocol will abort), even when some of the participants in the protocol are dishonest.	Computational security possible for dishonest parties assuming classical authenticated channels and signature schemes.	ITS possible (assuming classical authenticated channels).	There are multiple memoryless constructions with either (1) ITS from QKD with addition constant rounds of classical communication, thus the same hardware requirements apply or (2) with entanglement-generation can be made just in 4 rounds of communication, but very precise timing requirements are necessary and there are no noise analyses.
17	Anonymous transmission	Ensures the privacy of the message as well as the confidentiality of identity of the sender.	ITS security possible assuming authenticated classical channels and broadcast channels (thus a trusted third party).	ITS security assuming only authenticated channels, as opposed to broadcast channels classically.	There are multiple memoryless constructions with either (1) ITS from QKD with addition constant rounds of classical communication, thus the same hardware requirements apply or (2) with entanglement-generation, but (3) the best performance is achieved when participants can share GHZ states. There are no complete noise-robust security proofs.

IV. Diagram

The following diagraman classifies the beyond-qkd primitives (without the need of memories) in terms of their hardware requirements.

Each arrow represents a dependency, if a primitive can be built with different hardware, albeit obtaining substantially different properties, this is represented by more than one arrow. In particular, no primitives requires more than one type of quantum hardware.

V. Challenges

There are multiple challenges when trying to find which quantum cryptographic protocols can be done in a near-term stage of networks. First of all, most theoretical literature does not provide enough noise analysis to justify security with current hardware, nor does it make a distinction between the different types of hardware available (BB84, MDI-QKD, entanglement-generation…). Even if an analytical protocol mentions that BB84 state generation and measurement is enough, it is not clear what characteristics (detector rates, coincidence events etc.) would be enough for an acceptable implementation. Moreover, many of the primitives described where first presented with more complex hardware requirements (such as memories of entanglement-generation), which where later simplified to earlier stages of hardware (such as bi-partite entanglement), thus the classification of “beyond QKD with near-term hardware” is not static.

On the side of the hardware providers, it would be helpful to have access to semi-processed data before the QKD keys are distilled, to actually be able to see which of the applications are doable and accelerate the discovery of use cases.