betaFeedback

WorksPhysics and Astronomy

Quantum Key Exchange from Public Quantum Money

Abstract

Two-message quantum key exchange (2QKE) cannot be realized in a statistically secure way, and therefore some computational assumptions are required. So far, the known weakest assumption for 2QKE is the existence of one-way functions (OWFs). Can we construct 2QKE from a weaker assumption than OWFs? In this paper, we give the first complete characterization of 2QKE. We show that the following four primitives are (existentially) equivalent: everlasting-secure 2QKE, standard 2QKE, efficiently-verifiable state puzzles (EV-StatePuzzs), and one-time secure digital signatures with quantum signatures and signing keys. Because EV-StatePuzzs are potentially weaker than OWFs [Kretschmer, Qian and Tal 2025], the equivalence implies that 2QKE are potentially weaker than OWFs. Moreover, our result shows the equivalence between standard 2QKE and everlasting-secure 2QKE, which means that everlasting security comes for free. Finally, one-shot signatures, quantum lightning, and public-key quantum money mini-schemes imply EV-StatePuzzs, and therefore, our result also gives a new lowerbound, namely everlasting-secure 2QKE, of these public-key unclonable primitives. We also show that one-shot signatures imply QPKE with quantum public keys. [Kitagawa, Morimae,Nishimaki and Yamakawa, 2024] constructed QPKE with quantum public keys from OWFs, and it was open whether QPKE with quantum public keys can be constructed from an assumption weaker than or incomparable to OWFs. Our result gives a potential answer to this question since one-shot signatures seem to be incomparable with OWFs. Moreover, QPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a publicly verifiable classical certificate that computationally binds the receiver to an upper bound on the total number of distinct valid ciphertexts under its verification key.

Introduction

Key exchange. Key exchange (KE), introduced in the seminal work of Diffie and Hellman [12], allows two parties, Alice and Bob, who share no secret information in advance, to agree on a common secret key by communicating over public authenticated channels. It is one of the most fundamental primitives in cryptography. In the classical world, however, KE is a “Cryptomania” object in Impagliazzo’s terminology [17]: all known constructions rely on structured, public-key-type hardness assumptions, such as the hardness of the discrete logarithm problem [12], factoring, and learning with errors [35]. This is believed to be inherent: Impagliazzo and Rudich [18] showed that KE cannot be constructed from one-way functions (OWFs) in a black-box way (see also [6]), and hence classical KE seems out of reach of Minicrypt assumptions.

The situation changes drastically once quantum communication is available. The celebrated BB84 protocol [4] allows Alice and Bob to agree on a shared key with information-theoretic security, assuming only authenticated classical channels; the quantum channel may be completely unauthenticated.1 This, however, comes at the cost of interaction: BB84 and its descendants require more than two messages, whereas classical KE can be achieved with only two messages, which is optimal. In fact, no two-message quantum key exchange (2QKE) protocol—where Alice sends a single (quantum and classical) message to Bob over an unauthenticated quantum channel and an authenticated classical channel, and Bob replies with a single message—can be secure against unbounded adversaries [31]. (See also [34, 14].) Computational assumptions are therefore necessary in the two-message setting, and it is natural to ask which computational assumptions suffice.

Malavolta and Walter [31] constructed a 2QKE (in fact, with everlasting security) assuming only OWFs, and Kitagawa, Morimae, Nishimaki, and Yamakawa [20] constructed quantum public-key encryption with quantum public keys from OWFs, which also yields 2QKE in the same setting. In summary, in the standard setting where only classical channels are authenticated, OWFs are currently the weakest assumption known to imply 2QKE. On the other hand, one of the most remarkable lessons of quantum cryptography in recent years is that OWFs need not be the minimal assumption [24, 32, 3]: many primitives, including secret-key encryptions, commitments, oblivious transfer, and multi-party computation, can be based on assumptions that are potentially weaker than OWFs, such as pseudorandom states [19], one-way puzzles [25], and EFI pairs [5], and many of these primitives can exist even if OWFs do not [24, 22, 23, 28]. However, no such “Microcrypt” primitive is known to imply 2QKE, and therefore the following question has remained open.

Can we construct 2QKE from an assumption weaker than OWFs?

Public-key encryption. Public-key encryption (PKE) [12, 36, 13] is a strengthening of KE: Alice publishes a single public key, and anyone holding it can encrypt a message that only Alice can decrypt. Thus, whereas KE lets two designated parties agree on a secret, PKE lets Alice receive secret messages from arbitrarily many senders without any prior contact with them. In the classical world, PKE is again a Cryptomania object [17]: PKE trivially implies KE, and hence the black-box separation of Impagliazzo and Rudich [18] rules out constructions of PKE from OWFs as well. Once quantum communication is available, however, the picture changes as it does for KE. Kitagawa, Morimae, Nishimaki, and Yamakawa [20] showed that, if public keys are allowed to be quantum states, quantum PKE (QPKE) can be constructed from OWFs alone, even when unbounded polynomially many copies of quantum public keys are transmitted over unauthenticated quantum channels. In other words, quantum physics can move PKE from Cryptomania down to Minicrypt. It is then natural to ask whether it can descend even further, into Microcrypt, and hence, in parallel with 2QKE, we have the following open problem.

Can we construct QPKE with quantum public keys from an assumption weaker than or incomparable to OWFs?

Public-key quantum money and its variants. Quantum physics enables entirely new primitives that are classically impossible, based on the no-cloning theorem. Public-key quantum money [AC12] is a scheme where quantum states, called banknotes, are issued together with classical serial numbers: anyone can publicly verify a banknote with its serial number, but no one can duplicate it. Aaronson and Christiano [AC12] abstracted its core as a mini-scheme, which consists of a minting algorithm that outputs a pair of a classical serial number and a banknote, and a verification algorithm; the security requires that no QPT adversary, given a single banknote, can output a (possibly entangled) state that passes the verification on both of two registers with respect to the same serial number. Quantum lightning [Zha21] is a strengthening of public-key quantum money mini-schemes: no QPT adversary can output two states that pass the verification with respect to the same serial number, even though the adversary prepares the states by itself. One-shot signatures (OSS) [2] further strengthen quantum lightning into a signature-type primitive: given a classical common reference string, anyone can generate a classical verification key together with a quantum signing key, and the signing key can sign an arbitrary message, but only once; no QPT adversary can output a verification key of its own choice together with valid signatures on two distinct messages under it. OSS imply quantum lightning, and quantum lightning implies public-key quantum money mini-schemes [2 Zha21]. OSS have recently been constructed relative to a classical oracle, and also in the plain model assuming sub-exponentially-secure indistinguishability obfuscation and LWE [37, 16].

These public-key unclonable primitives easily imply efficiently-verifiable state puzzles (EV-StatePuzzs). An EV-StatePuzz is a pair (Samp, Ver) of QPT algorithms with the following syntax: Samp(1λ1^\lambda) outputs a classical bit string ss, called the puzzle, and a quantum state ψs\psi_s, called the answer, and Ver(1λ,s,ρ1^\lambda, s, \rho) accepts or rejects a candidate answer ρ\rho. Correctness requires that the honest answer ψs\psi_s is accepted with overwhelming probability, and security requires that no QPT adversary, given only the puzzle ss, can output a state that is accepted by Ver(1λ,s,⋅1^\lambda, s, \cdot). EV-StatePuzzs are considered as “zero-copy-secure” public-key quantum money mini schemes: in public-key quantum money mini schemes, a single copy of a quantum bank note is given to the adversary, and the adversary has to generate another copy, while in EV-StatePuzzs, zero copy of a quantum bank note is given to the adversary.

Despite the intensive study of the constructions of public-key quantum money and its variants, surprisingly little is known about their cryptographic consequences: the known lower bounds of these unclonable primitives (and of EV-StatePuzzs) are only one-way puzzles (OWPuzzs) and commitments [25, 26]. It is therefore natural to ask the following question.

Are there any other useful cryptographic primitives that can be constructed from one-shot signatures, quantum lightning, public-key quantum money, or EV-StatePuzzs, beyond commitment schemes?

Our results

In this paper, we show the following:

Theorem 1.1. The following four primitives are existentially equivalent:

  1. Everlasting-secure 2QKE.

  1. Standard 2QKE.

  1. Efficiently-verifiable state puzzles (EV-StatePuzzs).

  1. One-time secure digital signatures with quantum signatures and quantum signing keys.

The 2QKE that we construct has the following syntax: Alice and Bob are QPT. Alice sends a classical bit string to Bob over an authenticated classical channel, and a quantum state over an unauthenticated quantum channel. Bob returns a quantum state to Alice over an unauthenticated quantum channel. Alice outputs a bit α\alpha and Bob outputs a bit β\beta. Correctness requires that the probability that α=β\alpha= \beta is at least 1−negl⁡1 - \operatorname{negl}. The standard security requires that for any QPT Eve, who can freely read the classical message and can freely modify the quantum messages, the probability that e=βe = \beta is at most 12+negl⁡\frac{1}{2} + \operatorname{negl}, where ee is Eve’s output. Everlasting security considers the setup where Eve is QPT during the protocol, but after that Eve can do any unbounded operation on her state to output ee. Everlasting-secure 2QKE implies 2QKE with the standard security.

Theorem 1.1 shows, in particular, that 2QKE are equivalent to EV-StatePuzzs. This gives the first complete characterization of 2QKE. Moreover, EV-StatePuzzs can be trivially constructed from OWFs, but can exist even if P=NP\mathrm{P} = \mathrm{NP} relative to a classical oracle [23]. Hence

Corollary 1.2. Relative to a classical oracle, P=NP\mathrm{P} = \mathrm{NP} but everlasting-secure 2QKE exist.

This means, in particular, that 2QKE are potentially weaker than OWFs. Note that [14] constructed a unitary oracle relative to which BQP=QCMA\mathrm{BQP} = \mathrm{QCMA} but quantum multiparty non-interactive key exchange over classical channel exist. Their KE is stronger than our 2QKE, but their oracle is a quantum one.

Theorem 1.1 also shows the equivalence between standard 2QKE and everlasting 2QKE. This means that everlasting security comes for free:

Corollary 1.3. If 2QKE exist, then everlasting-secure 2QKE exists.

In the proof of Theorem 1.1, we construct everlasting-secure 2QKE from one-time secure digital signatures with quantum signatures. Everlasting 2QKE thus constructed actually satisfies the special property: Alice does not need any quantum memory. In other words, the internal state that Alice keeps between her first and second phases is classical. Hence we have the following corollary:

Corollary 1.4. If 2QKE exist, then everlasting-secure 2QKE in which Alice does not need quantum memory exists.

EV-OWPuzzs imply EV-StatePuzzs. Moreover, planted QCMA [21] is equivalent to EV-OWPuzzs. Therefore

Corollary 1.5. If EV-OWPuzzs (or planted QCMA) exist, then everlasting-secure 2QKE exists.

One-shot signatures [2], quantum lightning [Zha21], and public-key quantum money mini-schemes [AC12] imply EV-StatePuzzs. Hence we also have the following corollary.

Corollary 1.6. If one-shot signatures, quantum lightning, or public-key quantum money mini-schemes exist, then everlasting-secure 2QKE exists.

This gives a non-trivial lowerbound of these public-key unclonable primitives. Whether the lowerbound is tight or not is open. In particular, showing that 2QKE2QKE imply public-key quantum money mini-schemes will be very hard, because it also shows that OWFs imply public-key quantum money mini-schemes.

[14] constructed a unitary oracle relative to which BQP=QMABQP = QMA but quantum lightning exists. Since quantum lightning implies 2QKE2QKE from Corollary 1.6, we have the following corollary.

Corollary 1.7. Relative to a unitary oracle, BQP=QMABQP = QMA but everlasting-secure 2QKE2QKE exist.

Finally, we also show the following:

Theorem 1.8. If one-shot signatures exist, then everlasting-secure QPKEQPKE with quantum public keys exist.

Because one-shot signatures seem to be incomparable to OWFs, this result seems to imply that (even everlasting-secure) QPKEQPKE with quantum public keys can be constructed from assumptions incomparable to OWFs.

Moreover, QPKEQPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a classical certificate with which anyone can verify that the receiver has relinquished the ability of issuing new public keys.

Corollary 1.9. If one-shot signatures exist, then everlasting-secure QPKEQPKE with quantum public keys that satisfies certified freeze exist.

The known results and our results are summarized in Figure 1.

Summary of known results and our results

Figure 1. Summary of known results and our results. Note that the constructions of QPKE from OWFs and one-shot signatures achieve slightly different properties. (For the difference, see § 1.4.) In this figure, for simplicity, we do not distinguish them.

Technical Overview

In this subsection, we provide high-level overview of our proofs.

From EV-StatePuzzs to one-time signatures. This is simple. The construction is a quantum analogue of Lamport signatures. KeyGen runs (sb,ψb)←Samp⁡(1λ)(s_b, \psi_b) \leftarrow\operatorname{Samp}(1^\lambda) for each b∈{0,1}b \in\{0,1\}, and outputs vk⁡:=(s0,s1)\operatorname{vk} := (s_0, s_1) and sigk⁡:=(ψ0,ψ1)\operatorname{sigk} := (\psi_0, \psi_1). The signature of m∈{0,1}m \in\{0,1\} is ψm\psi_m, and the verification of (m,σ)(m,\sigma) runs Ver⁡(1λ,sm,σ)\operatorname{Ver}(1^\lambda,s_m,\sigma). For one-time security, the reduction embeds its challenge puzzle s∗s^* at a random position b∗←{0,1}b^* \leftarrow\{0,1\} of vk⁡\operatorname{vk} and samples the other puzzle–answer pair by itself. With probability 1/21/2, the adversary queries the signature of m=1−b∗m = 1 - b^*, which the reduction can answer with its self-sampled state, and the forged signature for 1−m=b∗1-m = b^* is a state accepted by Ver⁡(1λ,s∗,⋅)\operatorname{Ver}(1^\lambda,s^*,\cdot), i.e., an answer to the challenge puzzle.

From one-time signatures to everlasting-secure 2QKE. Before explaining our construction, we recall the construction of [31, 20] where digital signatures with classical signatures are used.

Let (KeyGen⁡,Sign⁡,Vrfy⁡)(\operatorname{KeyGen},\operatorname{Sign},\operatorname{Vrfy}) be a one-time secure digital signature scheme with classical signatures. Alice runs (vk⁡,sigk⁡)←KeyGen⁡(1λ)(\operatorname{vk},\operatorname{sigk}) \leftarrow\operatorname{KeyGen}(1^\lambda) and generates the signatures σ(0)\sigma(0) and σ(1)\sigma(1) of both messages. She prepares the state

∣0⟩A∣σ(0)⟩B+(−1)a∣1⟩A∣σ(1)⟩B,(1)\lvert0\rangle_A\lvert\sigma(0)\rangle_B + (-1)^a\lvert1\rangle_A\lvert\sigma(1)\rangle_B, \tag*{(1)}

where a←{0,1}a \leftarrow\{0,1\} is a uniformly random bit. She sends the registers (A,B)(A,B) to Bob over the unauthenticated quantum channel, and sends vkv_k over the authenticated classical channel. Bob coherently checks that the register BB contains a valid signature of the message stored in the register AA. If the check rejects, Bob outputs a uniformly random bit β\beta and returns the maximally mixed state to Alice. If the check accepts, the state is only negligibly disturbed, and Bob samples b←{0,1}b \leftarrow\{0,1\}, applies ZbZ^b on the register AA, returns the state to Alice, and outputs β:=b\beta:= b. Alice’s state is now

∣0⟩A∣σ(0)⟩B+(−1)a⊕b∣1⟩A∣σ(1)⟩B,(2)\lvert0\rangle_A\lvert\sigma(0)\rangle_B + (-1)^{a\oplus b}\lvert1\rangle_A\lvert\sigma(1)\rangle_B, \tag*{(2)}

from which she can easily learn a⊕ba \oplus b, because she knows both σ(0)\sigma(0) and σ(1)\sigma(1). She can therefore learn bb.

The security is intuitively understood in the following way: Because the relative phase aa is unknown to Eve, Alice’s first phase is indistinguishable from the following one to Eve: Alice chooses c←{0,1}c \leftarrow\{0,1\} and sends ∣c⟩∣σ(c)⟩\lvert c\rangle\lvert\sigma(c)\rangle to Bob. By using ∣c⟩∣σ(c)⟩\lvert c\rangle\lvert\sigma(c)\rangle, Eve generates a state ρ\rho and sends it to Bob. Bob performs the test on ρ\rho. Assume that the test passes, and let ρ′\rho' be the state after the test. Assuming the strong existential unforgeability2, we can show that ρ′\rho' is statistically close to ∣c⟩∣σ(c)⟩\lvert c\rangle\lvert\sigma(c)\rangle. This is because, if ρ′\rho' contains a valid-message-signature-pair state ∣d⟩∣τ(d)⟩\lvert d\rangle\lvert\tau(d)\rangle such that d=1−cd=1-c or d=c∧τ(c)≠σ(c)d=c \land\tau(c)\ne\sigma(c), then ρ′\rho' also contains it, which contradicts the strong existential unforgeability. Then, even if Bob applies ZbZ^b on ρ′\rho', no information about bb is encoded on ρ′\rho', and therefore even unbounded Eve cannot learn bb from the state sent from Bob.

This idea, however, does not work if the signatures are quantum states. In general, the signing algorithm for quantum signatures works as follows: it applies a unitary UU on ∣0…0⟩\lvert0\ldots0\rangle to generate the state ∑iCi∣i⟩∣ϕi⟩\sum_i C_i\lvert i\rangle\lvert\phi_i\rangle, and measure the first register in the computational basis. If the result is ii, the second register collapses to ∣ϕi⟩\lvert\phi_i\rangle. Some qubits of ∣ϕi⟩\lvert\phi_i\rangle are output as the quantum signature. Without loss of generality, we can assume that quantum signatures are pure, because we can redefine (I⊗P)∣ϕi⟩(I\otimes P)\lvert\phi_i\rangle as the signature, where PP is a random Pauli operator whose description is stored in the signing key.

For such a signing algorithm, the idea of [31, 20] that we have explained above does not work. First, even if Alice generates two quantum signatures, ∣σ(0)⟩,∣σ(1)⟩\lvert\sigma(0)\rangle,\lvert\sigma(1)\rangle, by running the signing algorithm twice, she cannot generate the superposition

∣0⟩∣σ(0)⟩+∣1⟩∣σ(1)⟩(3)\lvert0\rangle\lvert\sigma(0)\rangle+\lvert1\rangle\lvert\sigma(1)\rangle \tag*{(3)}

from ∣σ(0)⟩⊗∣σ(1)⟩\lvert\sigma(0)\rangle\otimes\lvert\sigma(1)\rangle. Second, the signing algorithm is not necessarily deterministic, and therefore Alice cannot learn a⊕ba\oplus b from ∣0⟩∣σ(0)⟩+(−1)a⊕b∣1⟩∣σ(1)⟩\lvert0\rangle\lvert\sigma(0)\rangle+(-1)^{a\oplus b}\lvert1\rangle\lvert\sigma(1)\rangle. Third, we cannot assume the strong existential unforgeability, because in the first place it is not well defined for quantum signatures.

The first two issues are resolved by modifying Alice’s first phase as follows:

  1. Generate ∣+⟩∣σ(0)⟩∣σ(1)⟩\lvert+\rangle\lvert\sigma(0)\rangle\lvert\sigma(1)\rangle.

  2. Apply the controlled-SWAP to get ∣0⟩∣σ(0)⟩∣σ(1)⟩+∣1⟩∣σ(1)⟩∣σ(0)⟩\lvert0\rangle\lvert\sigma(0)\rangle\lvert\sigma(1)\rangle+\lvert1\rangle\lvert\sigma(1)\rangle\lvert\sigma(0)\rangle.

  3. Apply a random Pauli PP to the third register to get ∣0⟩∣σ(0)⟩P∣σ(1)⟩+∣1⟩∣σ(1)⟩P∣σ(0)⟩\lvert0\rangle\lvert\sigma(0)\rangle P\lvert\sigma(1)\rangle+\lvert1\rangle\lvert\sigma(1)\rangle P\lvert\sigma(0)\rangle.

Because PP is unknown to Eve, the third register is “masked” and Alice’s state “looks like” ∣0⟩∣σ(0)⟩+∣1⟩∣σ(1)⟩\lvert0\rangle\lvert\sigma(0)\rangle+\lvert1\rangle\lvert\sigma(1)\rangle. Moreover, Alice can map ∣0⟩∣σ(0)⟩P∣σ(1)⟩+(−1)a⊕b∣1⟩∣σ(1)⟩P∣σ(0)⟩\lvert0\rangle\lvert\sigma(0)\rangle P\lvert\sigma(1)\rangle+(-1)^{a\oplus b}\lvert1\rangle\lvert\sigma(1)\rangle P\lvert\sigma(0)\rangle to (∣0⟩+(−1)a⊕b∣1⟩)∣σ(0)⟩∣σ(1)⟩(\lvert0\rangle+(-1)^{a\oplus b}\lvert1\rangle)\lvert\sigma(0)\rangle\lvert\sigma(1)\rangle by applying PP and the controlled-SWAP again, and from the latter state she can learn a⊕ba\oplus b.

To resolve the third issue, we had to construct a different proof than those of [20, 31]. Because we cannot assume strong existential unforgeability, we cannot say that the state ρ′\rho' after Bob’s test is ∣c⟩∣σ(c)⟩\lvert c\rangle\lvert\sigma(c)\rangle. However, still we can say that ρ′\rho' is spanned by valid-message-signature-pair states {∣d⟩∣τ(d)⟩}\{\lvert d\rangle\lvert\tau(d)\rangle\}. In order for Eve to get the information about bb, ρ′\rho' (and therefore the state ρ\rho Eve sends to Bob) must contain high weight on both ∣0⟩∣τ(0)⟩\lvert0\rangle\lvert\tau(0)\rangle and ∣1⟩∣τ(1)⟩\lvert1\rangle\lvert\tau(1)\rangle. However, this means Eve has the ability to forge a signature for the message 1−c1-c, which contradicts the security of the signature scheme.

From 2QKE to EV-StatePuzzs. Finally, we explain the converse direction. [34] and [14] already showed that 2QKE imply StatePuzzs, but we observe that we can actually construct EV-StatePuzzs.

References

  1. [2]Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd ACM STOC, pages 255–268. ACM Press, June 2020. (Cited on page 4, 5, 7, 9, 15, 16.)
  2. [3][AQY22] Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 208–236. Springer, Cham, August 2022. (Cited on page 3.)arxiv.org/abs/2112.10020
  3. [4][BB84] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In IEEE International Conference on Computers Systems and Signal Processing, pages 175–179. IEEE, 1984. (Cited on page 3.)
  4. [5][BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. ITCS 2023, 2023. (Cited on page 3.)arxiv.org/abs/2209.04101
  5. [6][BM09] Boaz Barak and Mohammad Mahmoodv-Ghidary. Merkle puzzles are optimal - an O(n²)-query attack on any key exchange from a random oracle. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 374–390. Springer, Berlin, Heidelberg, August 2009. (Cited on page 3.)DOI
  6. [7][BQSY24] John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen. An efficient quantum parallel repetition theorem and applications. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 1478–1487. ACM Press, June 2024. (Cited on page 9, 22.)DOI
  7. [8][CDF+08] Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 471–488. Springer, Berlin, Heidelberg, April 2008. (Cited on page 34.)
  8. [11][CPS02] Sergio Cabello, Carles Padró, and Germán Sáez. Secret sharing schemes with detection of cheaters for a general access structure. DCC, 25(2):175–188, 2002. (Cited on page 34.)
  9. [12][DH76] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. (Cited on page 3.)
  10. [13][GM82] Shafi Goldwasser and Silvio Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In 14th ACM STOC, pages 365–377. ACM Press, May 1982. (Cited on page 3.)
  11. [14][GMMY24] Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. CountCrypt: Quantum cryptography between QCMA and PP. Cryptology ePrint Archive, Paper 2024/1707, 2024. (Cited on page 3, 5, 6, 7, 9, 12.)arxiv.org/abs/2410.14792
  12. [15][GMR88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, 1988. (Cited on page 10.)DOI
  13. [16]Andrew Huang and Vinod Vaikuntanathan. A simple and efficient one-shot signature scheme. Cryptology ePrint Archive, Report 2025/1906, 2025. (Cited on page 4, 16, 30.)arxiv.org/abs/2510.10899
  14. [17]Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 134–147. IEEE Computer Society, 1995. (Cited on page 3.)
  15. [18]Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In 21st ACM STOC, pages 44–61. ACM Press, May 1989. (Cited on page 3.)
  16. [19]Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Cham, August 2018. (Cited on page 3.)DOI
  17. [20]Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum public-key encryption with tamper-resilient public keys from one-way functions. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 93–125. Springer, Cham, August 2024. (Cited on page 3, 7, 8, 9, 10, 11, 12, 17.)arxiv.org/abs/2304.01800
  18. [21]Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Publicly verifiable deletion from minimal assumptions. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023, Part IV, volume 14372 of LNCS, pages 228–245. Springer, Cham, November / December 2023. (Cited on page 5.)arxiv.org/abs/2304.07062
  19. [22]William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 1589–1602. ACM Press, June 2023. (Cited on page 3.)DOI
  20. [23]William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions. In Michal Koucký and Nikhil Bansal, editors, 57th ACM STOC, pages 189–200. ACM Press, June 2025. (Cited on page 3, 5, 7.)DOI
  21. [24]William Kretschmer. Quantum pseudorandomness and classical complexity. TQC 2021, 2021. (Cited on page 3.)DOI
  22. [25]Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 968–978. ACM Press, June 2024. (Cited on page 3, 4.)arxiv.org/abs/2310.11526
  23. [26]Dakshita Khurana and Kabir Tomer. Founding quantum cryptography on quantum advantage, or, towards cryptography from #p hardness. In Michal Koucký and Nikhil Bansal, editors, 57th ACM STOC, pages 178–188. ACM Press, June 2025. (Cited on page 4, 7, 12.)
  24. [27]Leslie Lamport. Constructing digital signatures from a one-way function. Technical Report SRI-CSL-98, 1979., 1979. (Cited on page 14.)
  25. [28]Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 979–990. ACM Press, June 2024. (Cited on page 3.)arxiv.org/abs/2310.08870
  26. [29]Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, CRYPTO ’87, volume 293 of LNCS, pages 369–378. Springer, Berlin, Heidelberg, August 1988. (Cited on page 10.)DOI
  27. [30]Ralph C. Merkle. A certified digital signature. In Gilles Brassard, editor, CRYPTO ’89, volume 435 of LNCS, pages 218–238. Springer, New York, August 1990. (Cited on page 10.)
  28. [31]Giulio Malavolta and Michael Walter. Robust quantum public-key encryption with applications to quantum key distribution. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 126–151. Springer, Cham, August 2024. (Cited on page 3, 7, 8, 9, 10, 11, 12, 15.)arxiv.org/abs/2304.02999
  29. [32]Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 269–295. Springer, Cham, August 2022. (Cited on page 3.)DOI
  30. [33]Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In 21st ACM STOC, pages 33–43. ACM Press, May 1989. (Cited on page 10.)DOI
  31. [34]Luowen Qian, Justin Raizes, and Mark Zhandry. Hard quantum extrapolations in quantum cryptography. In Serge Fehr and Pierre-Alain Fouque, editors, EUROCRYPT 2025, Part VII, volume 15607 of LNCS, pages 53–81. Springer, Cham, May 2025. (Cited on page 3, 9, 12.)arxiv.org/abs/2409.16516
  32. [35]Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. ACM Press, May 2005. (Cited on page 3.)
  33. [36]Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the Association for Computing Machinery, 21(2):120–126, February 1978. (Cited on page 3.)
  34. [37]Omri Shmueli and Mark Zhandry. On one-shot signatures, quantum vs. classical binding, and obfuscating permutations. In Yael Tauman Kalai and Seny F. Kamara, editors, CRYPTO 2025, Part II, volume 16001 of LNCS, pages 350–383. Springer, Cham, August 2025. (Cited on page 4, 16, 30.)arxiv.org/abs/2507.12456
  35. [38]Dominique Unruh. Everlasting multi-party computation. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 380–397. Springer, Berlin, Heidelberg, August 2013. (Cited on page 15.)

Paper details

vlnc:W_u2x8cfru
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude Fable 5.1 (bare), ChatGPT-6 Astra

View statement
Looking for related papers…
Contents