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 1 λ ) outputs a classical bit string s s s , called the puzzle, and a quantum state ψ s \psi_s ψ s , called the answer, and Ver(1 λ , s , ρ 1^\lambda, s, \rho 1 λ , s , ρ ) accepts or rejects a candidate answer ρ \rho ρ . Correctness requires that the honest answer ψ s \psi_s ψ s is accepted with overwhelming probability, and security requires that no QPT adversary, given only the puzzle s s s , can output a state that is accepted by Ver(1 λ , s , ⋅ 1^\lambda, s, \cdot 1 λ , s , ⋅ ). 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:
Everlasting-secure 2QKE.
Standard 2QKE.
Efficiently-verifiable state puzzles (EV-StatePuzzs).
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} 1 − 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 e = β is at most 1 2 + negl \frac{1}{2} + \operatorname{negl} 2 1 + negl , where e e e 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 e e e . 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 = N P \mathrm{P} = \mathrm{NP} P = NP relative to a classical oracle [23 ] . Hence
Corollary 1.2. Relative to a classical oracle, P = N P \mathrm{P} = \mathrm{NP} P = 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 B Q P = Q C M A \mathrm{BQP} = \mathrm{QCMA} BQP = 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 2 Q K E 2QKE 2 Q K E 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 B Q P = Q M A BQP = QMA B QP = QM A but quantum lightning exists. Since quantum lightning implies 2 Q K E 2QKE 2 Q K E from Corollary 1.6, we have the following corollary.
Corollary 1.7. Relative to a unitary oracle, B Q P = Q M A BQP = QMA B QP = QM A but everlasting-secure 2 Q K E 2QKE 2 Q K E exist.
Finally, we also show the following:
Theorem 1.8. If one-shot signatures exist, then everlasting-secure Q P K E QPKE QP K E with quantum public keys exist.
Because one-shot signatures seem to be incomparable to OWFs, this result seems to imply that (even everlasting-secure) Q P K E QPKE QP K E with quantum public keys can be constructed from assumptions incomparable to OWFs.
Moreover, Q P K E QPKE QP K E 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 Q P K E QPKE QP K E with quantum public keys that satisfies certified freeze exist.
The known results and our results are summarized in Figure 1 .
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 ( s b , ψ b ) ← Samp ( 1 λ ) (s_b, \psi_b) \leftarrow\operatorname{Samp}(1^\lambda) ( s b , ψ b ) ← Samp ( 1 λ ) for each b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } , and outputs vk : = ( s 0 , s 1 ) \operatorname{vk} := (s_0, s_1) vk := ( s 0 , s 1 ) and sigk : = ( ψ 0 , ψ 1 ) \operatorname{sigk} := (\psi_0, \psi_1) sigk := ( ψ 0 , ψ 1 ) . The signature of m ∈ { 0 , 1 } m \in\{0,1\} m ∈ { 0 , 1 } is ψ m \psi_m ψ m , and the verification of ( m , σ ) (m,\sigma) ( m , σ ) runs Ver ( 1 λ , s m , σ ) \operatorname{Ver}(1^\lambda,s_m,\sigma) Ver ( 1 λ , s m , σ ) . For one-time security, the reduction embeds its challenge puzzle s ∗ s^* s ∗ at a random position b ∗ ← { 0 , 1 } b^* \leftarrow\{0,1\} b ∗ ← { 0 , 1 } of vk \operatorname{vk} vk and samples the other puzzle–answer pair by itself. With probability 1 / 2 1/2 1/2 , the adversary queries the signature of m = 1 − b ∗ 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^* 1 − m = b ∗ is a state accepted by Ver ( 1 λ , s ∗ , ⋅ ) \operatorname{Ver}(1^\lambda,s^*,\cdot) Ver ( 1 λ , s ∗ , ⋅ ) , 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}) ( KeyGen , Sign , 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) ( vk , sigk ) ← KeyGen ( 1 λ ) and generates the signatures σ ( 0 ) \sigma(0) σ ( 0 ) and σ ( 1 ) \sigma(1) σ ( 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)} ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B + ( − 1 ) a ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B , (1)
where a ← { 0 , 1 } a \leftarrow\{0,1\} a ← { 0 , 1 } is a uniformly random bit. She sends the registers ( A , B ) (A,B) ( A , B ) to Bob over the unauthenticated quantum channel, and sends v k v_k v k over the authenticated classical channel. Bob coherently checks that the register B B B contains a valid signature of the message stored in the register A A A . 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\} b ← { 0 , 1 } , applies Z b Z^b Z b on the register A A A , returns the state to Alice, and outputs β : = b \beta:= b β := 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)} ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B + ( − 1 ) a ⊕ b ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B , (2)
from which she can easily learn a ⊕ b a \oplus b a ⊕ b , because she knows both σ ( 0 ) \sigma(0) σ ( 0 ) and σ ( 1 ) \sigma(1) σ ( 1 ) . She can therefore learn b b b .
The security is intuitively understood in the following way: Because the relative phase a a a 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\} c ← { 0 , 1 } and sends ∣ c ⟩ ∣ σ ( c ) ⟩ \lvert c\rangle\lvert\sigma(c)\rangle ∣ c ⟩ ∣ σ ( c )⟩ to Bob. By using ∣ c ⟩ ∣ σ ( c ) ⟩ \lvert c\rangle\lvert\sigma(c)\rangle ∣ c ⟩ ∣ σ ( c )⟩ , 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 ∣ c ⟩ ∣ σ ( c )⟩ . This is because, if ρ ′ \rho' ρ ′ contains a valid-message-signature-pair state ∣ d ⟩ ∣ τ ( d ) ⟩ \lvert d\rangle\lvert\tau(d)\rangle ∣ d ⟩ ∣ τ ( d )⟩ such that d = 1 − c d=1-c d = 1 − c or d = c ∧ τ ( c ) ≠ σ ( c ) d=c \land\tau(c)\ne\sigma(c) d = c ∧ τ ( c ) = σ ( c ) , then ρ ′ \rho' ρ ′ also contains it, which contradicts the strong existential unforgeability. Then, even if Bob applies Z b Z^b Z b on ρ ′ \rho' ρ ′ , no information about b b b is encoded on ρ ′ \rho' ρ ′ , and therefore even unbounded Eve cannot learn b b b 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 U U U on ∣ 0 … 0 ⟩ \lvert0\ldots0\rangle ∣ 0 … 0 ⟩ to generate the state ∑ i C i ∣ i ⟩ ∣ ϕ i ⟩ \sum_i C_i\lvert i\rangle\lvert\phi_i\rangle ∑ i C i ∣ i ⟩ ∣ ϕ i ⟩ , and measure the first register in the computational basis. If the result is i i i , the second register collapses to ∣ ϕ i ⟩ \lvert\phi_i\rangle ∣ ϕ i ⟩ . Some qubits of ∣ ϕ i ⟩ \lvert\phi_i\rangle ∣ ϕ i ⟩ 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 ( I ⊗ P ) ∣ ϕ i ⟩ as the signature, where P P P 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 ∣ σ ( 0 )⟩ , ∣ σ ( 1 )⟩ , 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)} ∣ 0 ⟩ ∣ σ ( 0 )⟩ + ∣ 1 ⟩ ∣ σ ( 1 )⟩ (3)
from ∣ σ ( 0 ) ⟩ ⊗ ∣ σ ( 1 ) ⟩ \lvert\sigma(0)\rangle\otimes\lvert\sigma(1)\rangle ∣ σ ( 0 )⟩ ⊗ ∣ σ ( 1 )⟩ . Second, the signing algorithm is not necessarily deterministic, and therefore Alice cannot learn a ⊕ b a\oplus b a ⊕ 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 ∣ 0 ⟩ ∣ σ ( 0 )⟩ + ( − 1 ) a ⊕ b ∣ 1 ⟩ ∣ σ ( 1 )⟩ . 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:
Generate ∣ + ⟩ ∣ σ ( 0 ) ⟩ ∣ σ ( 1 ) ⟩ \lvert+\rangle\lvert\sigma(0)\rangle\lvert\sigma(1)\rangle ∣ + ⟩ ∣ σ ( 0 )⟩ ∣ σ ( 1 )⟩ .
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 ∣ 0 ⟩ ∣ σ ( 0 )⟩ ∣ σ ( 1 )⟩ + ∣ 1 ⟩ ∣ σ ( 1 )⟩ ∣ σ ( 0 )⟩ .
Apply a random Pauli P P P 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 ∣ 0 ⟩ ∣ σ ( 0 )⟩ P ∣ σ ( 1 )⟩ + ∣ 1 ⟩ ∣ σ ( 1 )⟩ P ∣ σ ( 0 )⟩ .
Because P P P 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 ∣ 0 ⟩ ∣ σ ( 0 )⟩ + ∣ 1 ⟩ ∣ σ ( 1 )⟩ . 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 ∣ 0 ⟩ ∣ σ ( 0 )⟩ P ∣ σ ( 1 )⟩ + ( − 1 ) a ⊕ b ∣ 1 ⟩ ∣ σ ( 1 )⟩ P ∣ σ ( 0 )⟩ to ( ∣ 0 ⟩ + ( − 1 ) a ⊕ b ∣ 1 ⟩ ) ∣ σ ( 0 ) ⟩ ∣ σ ( 1 ) ⟩ (\lvert0\rangle+(-1)^{a\oplus b}\lvert1\rangle)\lvert\sigma(0)\rangle\lvert\sigma(1)\rangle (∣ 0 ⟩ + ( − 1 ) a ⊕ b ∣ 1 ⟩) ∣ σ ( 0 )⟩ ∣ σ ( 1 )⟩ by applying P P P and the controlled-SWAP again, and from the latter state she can learn a ⊕ b a\oplus b a ⊕ 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 ∣ c ⟩ ∣ σ ( c )⟩ . However, still we can say that ρ ′ \rho' ρ ′ is spanned by valid-message-signature-pair states { ∣ d ⟩ ∣ τ ( d ) ⟩ } \{\lvert d\rangle\lvert\tau(d)\rangle\} {∣ d ⟩ ∣ τ ( d )⟩} . In order for Eve to get the information about b b b , ρ ′ \rho' ρ ′ (and therefore the state ρ \rho ρ Eve sends to Bob) must contain high weight on both ∣ 0 ⟩ ∣ τ ( 0 ) ⟩ \lvert0\rangle\lvert\tau(0)\rangle ∣ 0 ⟩ ∣ τ ( 0 )⟩ and ∣ 1 ⟩ ∣ τ ( 1 ) ⟩ \lvert1\rangle\lvert\tau(1)\rangle ∣ 1 ⟩ ∣ τ ( 1 )⟩ . However, this means Eve has the ability to forge a signature for the message 1 − c 1-c 1 − 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.
By the principle of deferred measurement, we can assume without loss of generality that Alice’s first phase has the following form: she applies a unitary U U U on ∣ 0 … 0 ⟩ \lvert0\ldots0\rangle ∣ 0 … 0 ⟩ over three registers (S, M, W) to generate the state
U ∣ 0 … 0 ⟩ = ∑ s C s ∣ s ⟩ S ∣ Φ s ⟩ M , W , (4) U\lvert0\ldots0\rangle=\sum_s C_s\lvert s\rangle_{\mathrm{S}}\lvert\Phi_s\rangle_{\mathrm{M,W}}, \tag*{(4)} U ∣ 0 … 0 ⟩ = s ∑ C s ∣ s ⟩ S ∣ Φ s ⟩ M , W , (4)
measures S in the computational basis to obtain s s s , sends s s s over the authenticated classical channel and the register M over the unauthenticated quantum channel, and keeps the register W.
We first construct a 1 / 2 1/2 1/2 -sound EV-StatePuzz from a 2QKE. Here, a δ \delta δ -sound EV-StatePuzz is an EV-StatePuzz where any QPT adversary can make the verification algorithm accept with probability at most δ + n e g l \delta+\mathrm{negl} δ + negl . The construction is as follows. Samp(1 λ 1^\lambda 1 λ ) runs Alice’s first phase, and outputs the puzzle s s s and the answer ψ s : = ∣ Φ s ⟩ \psi_s:=\lvert\Phi_s\rangle ψ s := ∣ Φ s ⟩ , which is the state of the registers (M, W). Ver(1 λ , s , ρ 1^\lambda,s,\rho 1 λ , s , ρ ) runs Bob’s honest algorithm on s s s and the register M of ρ \rho ρ , which outputs a bit β \beta β and a returned quantum state, then runs Alice’s second phase on s s s , the register W of ρ \rho ρ , and the returned state, which outputs a bit α \alpha α , and finally accepts if and only if α = β \alpha=\beta α = β . The correctness of the EV-StatePuzz is exactly the correctness of the 2QKE. For the security, let us consider a QPT adversary A \mathcal{A} A , given s s s , outputs a state that is accepted by Ver(1 λ , s , ⋅ 1^\lambda,s,\cdot 1 λ , s , ⋅ ) with probability at least 1 / 2 + 1 / poly 1/2+1/\operatorname{poly} 1/2 + 1/ poly . Then Eve can run A \mathcal{A} A on input s s s , and send the M register of the output state to Bob. Eve then simulates Alice’s second phase on her state and the state returned from Bob. Conditioned on each s s s , the experiment of Ver(1 λ , s , A ( 1 λ , s ) 1^\lambda,s,\mathcal{A}(1^\lambda,s) 1 λ , s , A ( 1 λ , s ) ) is identical to the attacked execution of the 2QKE, where the acceptance condition α = β \alpha=\beta α = β corresponds to the event that Eve’s output e e e agrees with Bob’s output β \beta β . Hence Eve breaks the security of the 2QKE.
The 1 / 2 1/2 1/2 -security of the EV-StatePuzz can be amplified by parallel repetition [BOSY24], and finally we obtain an EV-StatePuzz with negligible security.
QPKΕ from one-shot signatures. Finally, we explain our construction of everlasting-secure QPKΕ with quantum public keys from one-shot signatures (OSS) [2 ] . An OSS scheme has a classical common reference string c r s \mathsf{crs} crs , a classical verification key, a quantum signing key, classical signatures, and a classical deterministic verification algorithm. Its security requires that no QPT adversary, given c r s \mathsf{crs} crs , can output a verification key of its own choice together with valid signatures on two distinct messages under it. In particular, a signing key can be used only once, even by its honest holder.
Recall the 2QKE schemes of [31 , 20 ] explained above. Alice’s message, namely a classical vk and the state ∣ 0 ⟩ ∣ σ ( 0 ) ⟩ + ( − 1 ) a ∣ 1 ⟩ ∣ σ ( 1 ) ⟩ \lvert0\rangle\lvert\sigma(0)\rangle+(-1)^a\lvert1\rangle\lvert\sigma(1)\rangle ∣ 0 ⟩ ∣ σ ( 0 )⟩ + ( − 1 ) a ∣ 1 ⟩ ∣ σ ( 1 )⟩ , can be regarded as a quantum public key. In the QPKE setting, however, the receiver has to distribute unbounded polynomially many public keys, all of which must be verifiable under the single authenticated vk, and this is why [31 , 20 ] need many-time secure digital signatures, which are available from OWFs. Our 2QKE from EV-StatePuzzs does not directly extend to QPKE for the same reason. OSS is also a “one-time” object, but its signatures are classical. This allows us to apply the certificate-chain technique, which is a classical folklore technique to convert one-time signatures into stateful many-time signatures [29 , 30 , 33 , 15 ] : the t t t -th one-time key signs the t t t -th message together with a freshly generated ( t + 1 ) (t+1) ( t + 1 ) -th verification key, and the t t t -th signature consists of the resulting chain of certificates. Because the certificates are classical, they can be freely copied into every subsequent public key.
Our construction of QPKE from OSS is as follows. KeyGen runs c r s ← S e t u p ( 1 λ ) \mathrm{crs} \leftarrow\mathrm{Setup}(1^\lambda) crs ← Setup ( 1 λ ) and ( w 1 , s i g k 1 ) ← G e n ( c r s ) (w_1,\mathrm{sigk}_1) \leftarrow\mathrm{Gen}(\mathrm{crs}) ( w 1 , sigk 1 ) ← Gen ( crs ) , outputs v k : = ( c r s , w 1 ) \mathrm{vk} := (\mathrm{crs}, w_1) vk := ( crs , w 1 ) , and keeps s i g k 1 \mathrm{sigk}_1 sigk 1 as the initial secret key. On the t t t -th invocation, PKGen generates three fresh key pairs ( u t 0 , s i g k t 0 ) (u_t^0,\mathrm{sigk}_t^0) ( u t 0 , sigk t 0 ) , ( u t 1 , s i g k t 1 ) (u_t^1,\mathrm{sigk}_t^1) ( u t 1 , sigk t 1 ) , and ( w t + 1 , s i g k t + 1 ) (w_{t+1},\mathrm{sigk}_{t+1}) ( w t + 1 , sigk t + 1 ) , signs μ t : = u t 0 ∥ u t 1 ∥ w t + 1 \mu_t := u_t^0 \mathbin\Vert u_t^1 \mathbin\Vert w_{t+1} μ t := u t 0 ∥ u t 1 ∥ w t + 1 with the chain key s i g k t \mathrm{sigk}_t sigk t to obtain the signature τ t \tau_t τ t , and, for each α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } , signs the message α \alpha α with the key s i g k t α \mathrm{sigk}_t^\alpha sigk t α to obtain a classical signature σ t ( α ) \sigma_t(\alpha) σ t ( α ) . It then samples a t ← { 0 , 1 } a_t \leftarrow\{0,1\} a t ← { 0 , 1 } , prepares
1 2 ( ∣ 0 ⟩ A ∣ σ t ( 0 ) ⟩ B + ( − 1 ) a t ∣ 1 ⟩ A ∣ σ t ( 1 ) ⟩ B ) , (5) \frac{1}{\sqrt{2}}\left(|0\rangle_A |\sigma_t(0)\rangle_B + (-1)^{a_t}|1\rangle_A |\sigma_t(1)\rangle_B\right), \tag*{(5)} 2 1 ( ∣0 ⟩ A ∣ σ t ( 0 ) ⟩ B + ( − 1 ) a t ∣1 ⟩ A ∣ σ t ( 1 ) ⟩ B ) , (5)
and outputs the public key p k t \mathrm{pk}_t pk t consisting of t t t , the chain ( μ s , τ s ) s ≤ t (\mu_s,\tau_s)_{s\leq t} ( μ s , τ s ) s ≤ t , and this state. It stores ( a t , σ t ( 0 ) , σ t ( 1 ) ) (a_t,\sigma_t(0),\sigma_t(1)) ( a t , σ t ( 0 ) , σ t ( 1 )) classically and keeps s i g k t + 1 \mathrm{sigk}_{t+1} sigk t + 1 for the next invocation. E n c ( v k , p k t , m ) \mathrm{Enc}(\mathrm{vk},\mathrm{pk}_t,m) Enc ( vk , pk t , m ) verifies the chain starting from w 1 w_1 w 1 , coherently checks that the register B contains a valid signature under u t α u_t^\alpha u t α of the message α \alpha α stored in the register A, applies Z m Z^m Z m on A, measures (A, B) in the Hadamard basis to obtain ( c , d ) (c,d) ( c , d ) , and outputs the classical ciphertext ( t , c , d ) (t,c,d) ( t , c , d ) . Because the receiver knows a t a_t a t , σ t ( 0 ) \sigma_t(0) σ t ( 0 ) , and σ t ( 1 ) \sigma_t(1) σ t ( 1 ) , it recovers m = c ⊕ a t ⊕ d ⋅ ( σ t ( 0 ) ⊕ σ t ( 1 ) ) m = c \oplus a_t \oplus d \cdot(\sigma_t(0) \oplus\sigma_t(1)) m = c ⊕ a t ⊕ d ⋅ ( σ t ( 0 ) ⊕ σ t ( 1 )) .
Note that, because OSS signatures are classical, the receiver can directly prepare the superposition of the two signatures and knows both of them, and the sender can send the classical Hadamard-basis measurement outcome as in [31 , 20 ] ; the controlled-SWAP and the random Pauli used in our 2QKE are not needed, and ciphertexts are classical. On the other hand, unlike [31 , 20 ] , a single OSS key cannot sign both 0 and 1, and this is why each public key has two verification keys u t 0 , u t 1 u_t^0,u_t^1 u t 0 , u t 1 , which are signed together with the next chain key.
Although the chain itself is the classical one, both its role and its analysis differ from the classical setting. First, in the classical setting the chain is used to sign messages, whereas here it is used only to certify the keys, and the “payload” of each public key is a quantum state, namely a superposition of two classical signatures whose relative phase a t a_t a t is a secret of the receiver. Second, in the classical setting the security of the chain is reduced to one-time unforgeability under a challenge verification key given by the challenger, and the reduction has to guess the position at which the adversary deviates from the honest chain. In our setting the OSS adversary chooses the verification key by itself and has no signing oracle, and therefore our reductions simply run the entire security game by themselves, keep all honest keys, and output two colliding signatures; no guessing is involved. Third, only the weak form of unforgeability, in which the two forged messages must be distinct, is needed. This is in contrast to [31 , 20 ] , whose proofs rely on strong unforgeability to argue that the state after the coherent verification is exactly ∣ c ⟩ ∣ σ ( c ) ⟩ |c\rangle|\sigma(c)\rangle ∣ c ⟩ ∣ σ ( c )⟩ ; instead, we reuse the “cross-term” argument of our 2QKE proof explained above.
The security proof goes as follows. Since Dec is never run in the security game, averaging over the pad a t a_t a t dephases A, and hence the adversary’s view is unchanged if the challenger samples α t ← { 0 , 1 } \alpha_t \leftarrow\{0,1\} α t ← { 0 , 1 } and sends ∣ α t ⟩ ∣ σ t ( α t ) ⟩ |\alpha_t\rangle|\sigma_t(\alpha_t)\rangle ∣ α t ⟩ ∣ σ t ( α t )⟩ instead, without ever signing with s i g k t 1 − α t \mathrm{sigk}_t^{1-\alpha_t} sigk t 1 − α t ; the key s i g k t 1 − α t \mathrm{sigk}_t^{1-\alpha_t} sigk t 1 − α t thus remains unconsumed in the challenger’s hand. This replacement is an equality of states, and is therefore valid even against the unbounded phase of the adversary. Suppose that the adversary has made q ′ q' q ′ public-key queries before the challenge, so that the challenger has issued the honest chain ( μ 1 , τ 1 ) , … , ( μ q ′ , τ q ′ ) (\mu_1,\tau_1),\ldots,(\mu_{q'},\tau_{q'}) ( μ 1 , τ 1 ) , … , ( μ q ′ , τ q ′ ) and holds the next chain signing key s i g k q ′ + 1 \mathrm{sigk}_{q'+1} sigk q ′ + 1 , corresponding to the verification key w q ′ + 1 w_{q'+1} w q ′ + 1 contained in μ q ′ \mu_{q'} μ q ′ (for q ′ = 0 q'=0 q ′ = 0 , this is w 1 w_1 w 1 ), which has not signed anything yet. The adversary then submits a public key, whose classical part is measured to obtain a chain ( μ 1 ′ , τ 1 ′ ) , … , ( μ t ′ ′ , τ t ′ ′ ) (\mu'_1,\tau'_1),\ldots,(\mu'_{t'},\tau'_{t'}) ( μ 1 ′ , τ 1 ′ ) , … , ( μ t ′ ′ , τ t ′ ′ ) of some length t ′ t' t ′ . If this chain does not verify under w 1 w_1 w 1 , the challenge ciphertext is ⊥ \perp ⊥ , and there is nothing to prove. Otherwise, we distinguish two cases according to whether the submitted chain is a prefix of the honest chain, i.e., whether t ′ ≤ q ′ t' \le q' t ′ ≤ q ′ and μ s ′ = μ s \mu'_s=\mu_s μ s ′ = μ s for all s ≤ t ′ s \le t' s ≤ t ′ .
If the submitted chain is not a prefix of the honest chain, then the adversary has forged a certificate under an honestly generated chain key. Indeed, let r r r be the first position where μ r ′ ≠ μ r \mu'_r \ne\mu_r μ r ′ = μ r . If r ≤ q ′ r \le q' r ≤ q ′ , then τ r ′ \tau'_r τ r ′ is a valid signature of μ r ′ \mu'_r μ r ′ under w r w_r w r , and the challenger already holds another valid signature τ r \tau_r τ r of the different message μ r \mu_r μ r under the same key w r w_r w r . If no such r ≤ q ′ r \le q' r ≤ q ′ exists, then t ′ > q ′ t' > q' t ′ > q ′ and τ q ′ + 1 ′ \tau'_{q'+1} τ q ′ + 1 ′ is a valid signature of μ q ′ + 1 ′ \mu'_{q'+1} μ q ′ + 1 ′ under w q ′ + 1 w_{q'+1} w q ′ + 1 ; since s i g k q ′ + 1 \mathsf{sigk}_{q'+1} sigk q ′ + 1 is unconsumed, the challenger can sign a different message with it. In both cases, a reduction that simulates the challenger obtains two valid signatures on distinct messages under an honestly generated verification key, which contradicts the security of OSS. Hence this case occurs only with negligible probability.
If the submitted chain is a prefix of the honest chain, then the keys used by Enc are the honest ones, ( u j 0 , u j 1 ) (u^0_j,u^1_j) ( u j 0 , u j 1 ) with j : = t ′ j := t' j := t ′ . Recall that, in the modified security game, the challenger sent ∣ α j ⟩ ∣ σ j ( α j ) ⟩ |\alpha_j\rangle|\sigma_j(\alpha_j)\rangle ∣ α j ⟩ ∣ σ j ( α j )⟩ and still holds the unconsumed leaf key s i g k j 1 − α j \mathsf{sigk}^{1-\alpha_j}_j sigk j 1 − α j . As in the proof of our 2QKE, after the coherent check the submitted state on the registers ( A , B ) (\mathrm{A},\mathrm{B}) ( A , B ) is spanned by valid pairs ∣ α ⟩ ∣ β ⟩ |\alpha\rangle|\beta\rangle ∣ α ⟩ ∣ β ⟩ with ⊤ = Ver ( c r s , u j α , α , β ) \top=\operatorname{Ver}(\mathrm{crs},u^\alpha_j,\alpha,\beta) ⊤ = Ver ( crs , u j α , α , β ) , and applying Z b Z^b Z b on A can encode b b b only in the cross term between the ∣ 0 ⟩ |0\rangle ∣0 ⟩ -branch and the ∣ 1 ⟩ |1\rangle ∣1 ⟩ -branch. The weight of this cross term is bounded by the weight of the branch ∣ 1 − α j ⟩ ∣ β ⟩ |1-\alpha_j\rangle|\beta\rangle ∣1 − α j ⟩ ∣ β ⟩ with β \beta β a valid signature of 1 − α j 1-\alpha_j 1 − α j under u j 1 − α j u^{1-\alpha_j}_j u j 1 − α j , and such a β \beta β is a forgery: measuring ( A , B ) (\mathrm{A},\mathrm{B}) ( A , B ) in the computational basis to obtain it and signing the other message α j \alpha_j α j with the unconsumed s i g k j 1 − α j \mathsf{sigk}^{1-\alpha_j}_j sigk j 1 − α j yields two valid signatures on distinct messages under u j 1 − α j u^{1-\alpha_j}_j u j 1 − α j , which again contradicts the security of OSS. Hence the cross term has negligible weight, and the trace distance between the adversary’s states for b = 0 b=0 b = 0 and b = 1 b=1 b = 1 is negligible.
Remarks on Our 2QKE
Here we provide several remarks on our 2QKE.
First, the 2QKE scheme constructed from EV-StatePuzzs in this paper is a special version of 2QKE where Bob can choose his own key. In general 2QKE, Bob’s key is randomly generated and he cannot choose his key. However, in our 2QKE scheme, Bob can choose his own key. (This is clear from our construction of 2QKE.) The 2QKE schemes constructed in [31 , 20 ] from OWFs also satisfy this property. On the other hand, our lowerbound, 2QKE ⇒ \Rightarrow ⇒ EV-StatePuzzs, holds for general 2QKE where Bob cannot choose his key. (This is also clear from the construction of EV-StatePuzzs.)
Second, in the 2QKE schemes of [31 , 20 ] , Bob’s message can be classical. Because they use digital signatures with classical signatures, the B register of the state ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B + ( − 1 ) a ⊕ b ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B |0\rangle_{\mathrm{A}}|\sigma(0)\rangle_{\mathrm{B}}+(-1)^{a\oplus b}|1\rangle_{\mathrm{A}}|\sigma(1)\rangle_{\mathrm{B}} ∣0 ⟩ A ∣ σ ( 0 ) ⟩ B + ( − 1 ) a ⊕ b ∣1 ⟩ A ∣ σ ( 1 ) ⟩ B is in the computational basis state. Hence, instead of sending the state, Bob can send the Hadamard-basis measurement result on the state from which Alice can recover a ⊕ b a\oplus b a ⊕ b . Because we use digital signatures with quantum signatures, the state of the B register is not necessarily in the computational-basis state, and therefore we cannot use the same technique. It is an open problem whether we can construct 2QKE with classical Bob’s message from EV-StatePuzzs or other assumptions weaker than OWFs.
Third, in our 2QKE, we require security only for Bob; we require that Eve cannot learn Bob’s key. On the other hand, we do not require security for Alice, and therefore Eve could learn Alice’s key. In fact, it is unavoidable with the current syntax, because Eve can impersonate Bob: Eve can take Alice’s message and run Bob’s algorithm, and return the message to Alice. Then due to the correctness, Eve’s key agrees with Alice’s key. The 2QKE schemes of [31 , 20 ] do not have this issue because Bob’s message is classical, and therefore it can be authenticated: Eve cannot impersonate Bob. Because Bob’s message is quantum in our 2QKE scheme, we cannot use the same idea. However, actually, there is a solution if Bob additionally sends a short classical bit string over the authenticated classical channel. (For details, see § 7 .)
Fourth, in our 2QKE, Eve can make Alice accept a key that is different from Bob’s key in the following way: Eve does not touch Alice’s message to Bob, but Eve applies Z d Z^{d} Z d with random d ← { 0 , 1 } d \leftarrow\{0,1\} d ← { 0 , 1 } on the A register of the state sent from Bob to Alice so that Alice outputs her key b ⊕ d b \oplus d b ⊕ d . Again, the 2QKE schemes of [31 , 20 ] do not have this issue because Bob’s message is classical and authenticated. However, we can again address the issue in a similar way. (For details, see § 7 .)
Finally, [20 ] constructed quantum PKE with quantum public keys that are secure even if unbounded polynomially-many public keys are distributed. This is possible because they use OWFs, which allow many-time secure digital signatures. On the other hand, we do not know how to obtain many-time secure digital signatures from EV-StatePuzzs. Constructing quantum PKE (even with quantum public keys) from a weaker assumption than OWFs remains open.
Remarks on Our QPKE
Unlike [20 ] , PKGen of our QPKE constructed from OSS is stateful, and the size of the classical part of the public key grows with the number of uses. Moreover, the secret key is quantum. The size of the classical part of the secret key grows with the number of uses. On the other hand, our QPKE achieves everlasting security.
The length of p k t \mathrm{pkt} pkt grows linearly in t t t because the chain has length t t t . A standard Merkle-tree variant, in which the t t t -th leaf is certified by a path of length λ \lambda λ in a lazily generated binary tree, reduces it to O ( λ ) O(\lambda) O ( λ ) times the length of a verification key and a signature, at the cost of storing O ( λ ) O(\lambda) O ( λ ) chain signing keys in the secret key and a slightly more involved case analysis in the proof.
Related Works
StatePuzzs from public-key quantum money was shown in [34 , 26 ] . StatePuzzs from 2QKE was shown in [34 , 14 ] . In this paper, we observed that actually EV-StatePuzzs are implied.
Preliminaries
Public-Key Quantum Money
Definition 2.1 (Public-key quantum money mini-scheme [AC12]). A public-key quantum money mini-scheme consists of two QPT algorithms (Mint, Vrfy) with the following syntax .
Mint( 1 λ ) → ( s , ρ s ) (1^{\lambda}) \to(s, \rho_s) ( 1 λ ) → ( s , ρ s ) : The minting algorithm takes the security parameter 1 λ 1^{\lambda} 1 λ as input, and outputs a classical serial number s s s and a quantum state ρ s \rho_s ρ s .
Vrfy( 1 λ , s , ρ ) → ⊤ / ⊥ (1^{\lambda}, s, \rho) \to\top/\bot ( 1 λ , s , ρ ) → ⊤/⊥ : The verification algorithm takes the security parameter 1 λ 1^{\lambda} 1 λ , a serial number s s s , and a quantum state ρ \rho ρ as input, and outputs ⊤ \top ⊤ or ⊥ \bot ⊥ .
We require the following two properties.
Correctness. For all λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
Pr [ ⊤ ← Vrfy ( 1 λ , s , ρ s ) : ( s , ρ s ) ← Mint ( 1 λ ) ] ≥ 1 − negl ( λ ) . (6) \Pr\left[\top\leftarrow\operatorname{Vrfy}(1^{\lambda},s,\rho_s) : (s,\rho_s) \leftarrow\operatorname{Mint}(1^{\lambda})\right] \ge1-\operatorname{negl}(\lambda). \tag*{(6)} Pr [ ⊤ ← Vrfy ( 1 λ , s , ρ s ) : ( s , ρ s ) ← Mint ( 1 λ ) ] ≥ 1 − negl ( λ ) . (6)
Security. Define the algorithm Vrfy2 as follows: Vrfy2 ( 1 λ , s , σ ) _2(1^\lambda,s,\sigma) 2 ( 1 λ , s , σ ) takes as input a serial number s s s and a (possibly entangled) quantum state σ \sigma σ over two registers, applies Vrfy( 1 λ , s , ⋅ ) (1^\lambda,s,\cdot) ( 1 λ , s , ⋅ ) to each register, and outputs ⊤ \top ⊤ if and only if both invocations output ⊤ \top ⊤ . Then, for any QPT adversary A \mathcal{A} A ,
Pr [ ⊤ ← Vrfy 2 ( 1 λ , s , σ ) : ( s , ρ s ) ← Mint ( 1 λ ) σ ← A ( 1 λ , s , ρ s ) ] ≤ negl ( λ ) . (7) \Pr\left[\top\leftarrow\operatorname{Vrfy}_2(1^\lambda,s,\sigma) : \begin{array}{l}(s,\rho_s) \leftarrow\operatorname{Mint}(1^\lambda)\\ \sigma\leftarrow\mathcal{A}(1^\lambda,s,\rho_s)\end{array}\right] \leq\operatorname{negl}(\lambda). \tag*{(7)} Pr [ ⊤ ← Vrfy 2 ( 1 λ , s , σ ) : ( s , ρ s ) ← Mint ( 1 λ ) σ ← A ( 1 λ , s , ρ s ) ] ≤ negl ( λ ) . (7)
EV-StatePuzzs
Definition 2.2 (Efficiently verifiable state puzzles (EV-StatePuzzs)). Let δ : N → [ 0 , 1 ] \delta:\mathbb{N}\to[0,1] δ : N → [ 0 , 1 ] . A δ \delta δ -sound efficiently verifiable state puzzle (EV-StatePuzz) is a pair (Samp, Ver) of QPT algorithms with the following syntax:
Samp( 1 λ ) → ( s , ψ s ) (1^\lambda)\to(s,\psi_s) ( 1 λ ) → ( s , ψ s ) : It is a QPT algorithm that, on input the security parameter λ \lambda λ , outputs a classical bit string s s s and a quantum state ψ s \psi_s ψ s . s s s is called the puzzle and ψ s \psi_s ψ s is called answer.
Ver( 1 λ , s , ρ ) → ⊤ / ⊥ (1^\lambda,s,\rho)\to\top/\bot ( 1 λ , s , ρ ) → ⊤/⊥ : It is a QPT algorithm that, on input 1 λ 1^\lambda 1 λ , s s s and a quantum state ρ \rho ρ , outputs ⊤ \top ⊤ or ⊥ \bot ⊥ .
We require the following two properties.
Pr [ ⊤ ← Ver ( 1 λ , s , ψ s ) : ( s , ψ s ) ← Samp ( 1 λ ) ] ≥ 1 − negl ( λ ) . (8) \Pr[\top\leftarrow\operatorname{Ver}(1^\lambda,s,\psi_s):(s,\psi_s)\leftarrow\operatorname{Samp}(1^\lambda)]\geq1-\operatorname{negl}(\lambda). \tag*{(8)} Pr [ ⊤ ← Ver ( 1 λ , s , ψ s ) : ( s , ψ s ) ← Samp ( 1 λ )] ≥ 1 − negl ( λ ) . (8) Pr [ ⊤ ← Ver ( 1 λ , s , A ( 1 λ , s ) ) : ( s , ψ s ) ← Samp ( 1 λ ) ] ≤ δ ( λ ) + negl ( λ ) . (9) \Pr[\top\leftarrow\operatorname{Ver}(1^\lambda,s,\mathcal{A}(1^\lambda,s)):(s,\psi_s)\leftarrow\operatorname{Samp}(1^\lambda)]\leq\delta(\lambda)+\operatorname{negl}(\lambda). \tag*{(9)} Pr [ ⊤ ← Ver ( 1 λ , s , A ( 1 λ , s )) : ( s , ψ s ) ← Samp ( 1 λ )] ≤ δ ( λ ) + negl ( λ ) . (9) We call a δ \delta δ -sound EV-StatePuzz just EV-StatePuzz if δ = 0 \delta=0 δ = 0 .
Digital Signatures
Definition 2.3 (One-time digital signatures with quantum signatures). A one-time digital signature scheme consists of three QPT algorithms (KeyGen, Sign, Ver) with the following syntax.
KeyGen( 1 λ ) → ( v k , s i g k ) (1^\lambda)\to(\mathrm{vk},\mathrm{sigk}) ( 1 λ ) → ( vk , sigk ) : The key generation algorithm takes the security parameter 1 λ 1^\lambda 1 λ as input, and outputs a classical verification key v k \mathrm{vk} vk and a quantum signing key s i g k \mathrm{sigk} sigk .
Sign( s i g k , m ) → σ (\mathrm{sigk},m)\to\sigma ( sigk , m ) → σ : The signing algorithm takes the signing key s i g k \mathrm{sigk} sigk and a message m ∈ { 0 , 1 } m\in\{0,1\} m ∈ { 0 , 1 } as input, and outputs a quantum signature σ \sigma σ .
Ver( v k , m , σ ) → ⊤ / ⊥ (\mathrm{vk},m,\sigma)\to\top/\bot ( vk , m , σ ) → ⊤/⊥ : The verification algorithm takes the verification key v k \mathrm{vk} vk , a message m ∈ { 0 , 1 } m\in\{0,1\} m ∈ { 0 , 1 } , and a quantum state σ \sigma σ as input, and outputs ⊤ \top ⊤ or ⊥ \bot ⊥ .
We require the following two properties.
Correctness. For all m ∈ { 0 , 1 } m\in\{0,1\} m ∈ { 0 , 1 } ,
Pr [ ⊤ ← Ver ( v k , m , σ ) : ( v k , s i g k ) ← KeyGen ( 1 λ ) σ ← Sign ( s i g k , m ) ] ≥ 1 − negl ( λ ) . (10) \Pr\left[\top\leftarrow\operatorname{Ver}(\mathrm{vk},m,\sigma): \begin{array}{l}(\mathrm{vk},\mathrm{sigk})\leftarrow\operatorname{KeyGen}(1^\lambda)\\ \sigma\leftarrow\operatorname{Sign}(\mathrm{sigk},m)\end{array}\right]\geq1-\operatorname{negl}(\lambda). \tag*{(10)} Pr [ ⊤ ← Ver ( vk , m , σ ) : ( vk , sigk ) ← KeyGen ( 1 λ ) σ ← Sign ( sigk , m ) ] ≥ 1 − negl ( λ ) . (10)
One-time security. For any QPT adversary A = ( A 1 , A 2 ) \mathcal{A} = (\mathcal{A}_1,\mathcal{A}_2) A = ( A 1 , A 2 ) ,
Pr [ ⊤ ← Ver ( v k , 1 − m , σ ′ ) : ( v k , s i g k ) ← KeyGen ( 1 λ ) ( m , s t ) ← A 1 ( v k ) σ ← Sign ( s i g k , m ) σ ′ ← A 2 ( σ , s t ) ] ≤ negl ( λ ) (11) \Pr\left[
\begin{aligned}
\top&\leftarrow\operatorname{Ver}(\mathrm{vk},1-m,\sigma') :\\
(\mathrm{vk},\mathrm{sigk}) &\leftarrow\operatorname{KeyGen}(1^\lambda)\\
(m,\mathrm{st}) &\leftarrow\mathcal{A}_1(\mathrm{vk})\\
\sigma&\leftarrow\operatorname{Sign}(\mathrm{sigk},m)\\
\sigma' &\leftarrow\mathcal{A}_2(\sigma,\mathrm{st})
\end{aligned}
\right]
\leq\operatorname{negl}(\lambda) \tag*{(11)} Pr ⊤ ( vk , sigk ) ( m , st ) σ σ ′ ← Ver ( vk , 1 − m , σ ′ ) : ← KeyGen ( 1 λ ) ← A 1 ( vk ) ← Sign ( sigk , m ) ← A 2 ( σ , st ) ≤ negl ( λ ) (11)
where s t \mathrm{st} st is a (possibly quantum) internal state of A 1 \mathcal{A}_1 A 1 .
Remark 2.4. Without loss of generality, we will assume that the signature σ \sigma σ is a pure state determined exclusively by the signing key and the message. In particular, we can include the description of a random Pauli in the signing key, and then have the signature of a message m m m be a purification of the mixed signature with the random Pauli applied to the purification register.
Constructing Digital Signatures
We make the following observations, with a formal proof included in Appendix § 9 . The first result follows from the observation that when looking at the construction of state puzzles from public-key quantum money mini-schemes, the verification algorithm of the mini-scheme gives a verification algorithm for the resulting puzzle. The second result follows from generalizing Lamport’s construction of one-time signatures from one-way functions [27 ] .
Lemma 2.5. The following hold.
If there exist public-key quantum money mini-schemes, then there exist EV-StatePuzzs.
If there exist EV-StatePuzzs, then there exist one-time secure digital signatures.
2QKE
Definition 2.6 (Two-message quantum key exchange (2QKE)). A two-message quantum key exchange (2QKE) is the following interactive protocol between QPT Alice and QPT Bob. Alice and Bob share a quantum channel, which is not authenticated, and a classical channel, which is authenticated.
Alice and Bob take 1 λ 1^\lambda 1 λ as input.
Alice sends a quantum state and a classical bit string to Bob.
Bob returns a quantum state to Alice.
Alice outputs a bit α \alpha α and Bob outputs a bit β \beta β .
We require the following two properties.
Correctness. The probability that α = β \alpha= \beta α = β is at least 1 − negl ( λ ) 1 - \operatorname{negl}(\lambda) 1 − negl ( λ ) . Security. For any QPT Eve who outputs a bit e e e , the probability that e = β e = \beta e = β is at most 1 2 + negl ( λ ) \frac{1}{2} + \operatorname{negl}(\lambda) 2 1 + negl ( λ ) . Here, Eve can freely read the classical messages and can freely modify the quantum messages.
Definition 2.7 (Everlasting security of 2QKE [38 , 31 ] ). A 2QKE satisfies everlasting security if the following holds for any Eve of the following form: during the execution of the protocol, Eve can freely read the classical messages and can freely modify the quantum messages, but all of her operations are QPT; after the protocol terminates, Eve applies computationally-unbounded operations on all the registers that she keeps, and outputs a bit e e e . The requirement is that the probability that e e e is equal to Bob’s output β \beta β is at most 1 2 + negl ( λ ) \frac{1}{2} + \operatorname{negl}(\lambda) 2 1 + negl ( λ ) .
Remark 2.8. Everlasting security implies the security of 2QKE, because a QPT Eve is a special case of the Eve of Definition 2.7.
One-Shot Signatures
Definition 2.9 (One-shot signatures [2 ] ). A one-shot signature scheme consists of four algorithms (Setup, Gen, Sign, Ver) with the following syntax.
Setup ( 1 λ ) → c r s \operatorname{Setup}(1^\lambda) \to\mathsf{crs} Setup ( 1 λ ) → crs : The setup algorithm is a QPT algorithm that takes the security parameter 1 λ 1^\lambda 1 λ as input, and outputs a classical common reference string c r s \mathsf{crs} crs .
Gen ( c r s ) → ( v k , s i g k ) \operatorname{Gen}(\mathsf{crs}) \to(\mathsf{vk},\mathsf{sigk}) Gen ( crs ) → ( vk , sigk ) : The key generation algorithm is a QPT algorithm that takes c r s \mathsf{crs} crs as input, and outputs a classical verification key v k \mathsf{vk} vk and a quantum signing key s i g k \mathsf{sigk} sigk .
Sign ( c r s , s i g k , m ) → σ \operatorname{Sign}(\mathsf{crs},\mathsf{sigk},m) \to\sigma Sign ( crs , sigk , m ) → σ : The signing algorithm is a QPT algorithm that takes c r s \mathsf{crs} crs , the signing key s i g k \mathsf{sigk} sigk , and a message m ∈ { 0 , 1 } ∗ m \in\{0,1\}^{*} m ∈ { 0 , 1 } ∗ as input, and outputs a classical signature σ \sigma σ .
Ver ( c r s , v k , m , σ ) → ⊤ / ⊥ \operatorname{Ver}(\mathsf{crs},\mathsf{vk},m,\sigma) \to\top/\bot Ver ( crs , vk , m , σ ) → ⊤/⊥ : The verification algorithm is a classical deterministic polynomial-time algorithm that takes c r s \mathsf{crs} crs , the verification key v k \mathsf{vk} vk , a message m ∈ { 0 , 1 } ∗ m \in\{0,1\}^{*} m ∈ { 0 , 1 } ∗ , and a signature σ \sigma σ as input, and outputs ⊤ \top ⊤ or ⊥ \bot ⊥ .
We require the following two properties.
Correctness. For any quantum algorithm M M M that outputs a classical message m ∈ { 0 , 1 } ∗ m \in\{0,1\}^{*} m ∈ { 0 , 1 } ∗ , which may be computationally unbounded,
Pr [ ⊤ ← Ver ( c r s , v k , m , σ ) : c r s ← Setup ( 1 λ ) ( v k , s i g k ) ← Gen ( c r s ) m ← M ( c r s , v k ) σ ← Sign ( c r s , s i g k , m ) ] ≥ 1 − negl ( λ ) . (12) \Pr\left[
\begin{array}{c}
\top\leftarrow\operatorname{Ver}(\mathsf{crs},\mathsf{vk},m,\sigma) : \\
\mathsf{crs} \leftarrow\operatorname{Setup}(1^\lambda) \\
(\mathsf{vk},\mathsf{sigk}) \leftarrow\operatorname{Gen}(\mathsf{crs}) \\
m \leftarrow M(\mathsf{crs},\mathsf{vk}) \\
\sigma\leftarrow\operatorname{Sign}(\mathsf{crs},\mathsf{sigk},m)
\end{array}
\right] \ge1-\operatorname{negl}(\lambda). \tag*{(12)} Pr ⊤ ← Ver ( crs , vk , m , σ ) : crs ← Setup ( 1 λ ) ( vk , sigk ) ← Gen ( crs ) m ← M ( crs , vk ) σ ← Sign ( crs , sigk , m ) ≥ 1 − negl ( λ ) . (12)
Security. For any QPT adversary A \mathcal{A} A ,
Pr [ ⊤ ← Ver ( c r s , v k , m 0 , σ 0 ) ∧ ⊤ ← Ver ( c r s , v k , m 1 , σ 1 ) ∧ m 0 ≠ m 1 : c r s ← Setup ( 1 λ ) ( v k , m 0 , σ 0 , m 1 , σ 1 ) ← A ( 1 λ , c r s ) ] ≤ negl ( λ ) . (13) \Pr\left[
\begin{array}{c}
\top\leftarrow\operatorname{Ver}(\mathsf{crs},\mathsf{vk},m_0,\sigma_0) \\
\land\ \top\leftarrow\operatorname{Ver}(\mathsf{crs},\mathsf{vk},m_1,\sigma_1) \\
\land\ m_0 \ne m_1 : \\
\mathsf{crs} \leftarrow\operatorname{Setup}(1^\lambda) \\
(\mathsf{vk},m_0,\sigma_0,m_1,\sigma_1) \leftarrow\mathcal{A}(1^\lambda,\mathsf{crs})
\end{array}
\right] \le\operatorname{negl}(\lambda). \tag*{(13)} Pr ⊤ ← Ver ( crs , vk , m 0 , σ 0 ) ∧ ⊤ ← Ver ( crs , vk , m 1 , σ 1 ) ∧ m 0 = m 1 : crs ← Setup ( 1 λ ) ( vk , m 0 , σ 0 , m 1 , σ 1 ) ← A ( 1 λ , crs ) ≤ negl ( λ ) . (13)
QPKE
Definition 2.11 (QPKE with quantum public keys). A quantum public-key encryption (QPKE) scheme with quantum public keys consists of four QPT algorithms (KeyGen, PKGen, Enc, Dec) with the following syntax.
KeyGen ( 1 λ ) → ( v k , s k 0 ) \operatorname{KeyGen}(1^\lambda) \to(\mathrm{vk},\mathrm{sk}_0) KeyGen ( 1 λ ) → ( vk , sk 0 ) : The key generation algorithm takes the security parameter 1 λ 1^\lambda 1 λ as input, and outputs a classical verification key vk and an initial secret key s k 0 \mathrm{sk}_0 sk 0 , which may be a quantum state.
PKGen ( s k ) → ( p k , s k ′ ) \operatorname{PKGen}(\mathrm{sk}) \to(\mathrm{pk},\mathrm{sk}') PKGen ( sk ) → ( pk , sk ′ ) : The public key generation algorithm takes a secret key sk as input, and outputs a quantum public key pk and an updated secret key s k ′ \mathrm{sk}' sk ′ , which may be a quantum state.
Enc ( v k , p k , m ) → c t \operatorname{Enc}(\mathrm{vk}, \mathrm{pk}, m) \to\mathrm{ct} Enc ( vk , pk , m ) → ct : The encryption algorithm takes the verification key vk, a quantum public key pk, and a message m ∈ { 0 , 1 } m \in\{0,1\} m ∈ { 0 , 1 } as input, and outputs a classical ciphertext ct.
Dec ( s k , c t ) → m ′ \operatorname{Dec}(\mathrm{sk}, \mathrm{ct}) \to m' Dec ( sk , ct ) → m ′ : The decryption algorithm takes the classical part of a secret key sk and a classical ciphertext ct as input, and outputs m ′ ∈ { 0 , 1 } m' \in\{0,1\} m ′ ∈ { 0 , 1 } .
Here, a secret key consists of a classical part and a quantum part (the latter may be empty), and Dec acts only on the classical part. In particular, secret keys are not consumed by decryption, and polynomially many ciphertexts can be decrypted with the same secret key.
We require the following correctness and security.
Correctness. For any polynomial k k k and any ( m 1 , … , m k ( λ ) ) ∈ { 0 , 1 } k ( λ ) (m_1,\ldots,m_{k(\lambda)}) \in\{0,1\}^{k(\lambda)} ( m 1 , … , m k ( λ ) ) ∈ { 0 , 1 } k ( λ ) ,
Pr [ ∀ i ∈ [ k ( λ ) ] ( v k , s k 0 ) ← KeyGen ( 1 λ ) ( p k j , s k j ) ← PKGen ( s k j − 1 ) ( j = 1 , … , k ( λ ) ) m i ← Dec ( s k k ( λ ) , c t i ) c t i ← Enc ( v k , p k i , m i ) ( i = 1 , … , k ( λ ) ) ] ≥ 1 − negl ( λ ) . (14) \Pr\left[
\begin{array}{c}
\forall i \in[k(\lambda)] \qquad(\mathrm{vk},\mathrm{sk}_0) \leftarrow\operatorname{KeyGen}(1^\lambda)\\
(\mathrm{pk}_j,\mathrm{sk}_j) \leftarrow\operatorname{PKGen}(\mathrm{sk}_{j-1})\ (j=1,\ldots,k(\lambda))\\
m_i \leftarrow\operatorname{Dec}(\mathrm{sk}_{k(\lambda)},\mathrm{ct}_i) \qquad\mathrm{ct}_i \leftarrow\operatorname{Enc}(\mathrm{vk},\mathrm{pk}_i,m_i)\ (i=1,\ldots,k(\lambda))
\end{array}
\right] \ge1-\operatorname{negl}(\lambda). \tag*{(14)} Pr ∀ i ∈ [ k ( λ )] ( vk , sk 0 ) ← KeyGen ( 1 λ ) ( pk j , sk j ) ← PKGen ( sk j − 1 ) ( j = 1 , … , k ( λ )) m i ← Dec ( sk k ( λ ) , ct i ) ct i ← Enc ( vk , pk i , m i ) ( i = 1 , … , k ( λ )) ≥ 1 − negl ( λ ) . (14)
where the k ( λ ) k(\lambda) k ( λ ) executions of Dec take the classical part of s k k ( λ ) \mathrm{sk}_{k(\lambda)} sk k ( λ ) as input, and are therefore well defined.
Security. A Q P K E QPKE QP K E scheme (KeyGen, PKGen, Enc, Dec) is secure if for any Q P T QPT QP T adversary A A A ,
Pr [ b ′ = b ] ≤ 1 2 + negl ( λ ) (15) \Pr[b' = b] \le\frac{1}{2} + \operatorname{negl}(\lambda) \tag*{(15)} Pr [ b ′ = b ] ≤ 2 1 + negl ( λ ) (15)
in the following security game.
The challenger runs ( v k , s k 0 ) ← KeyGen ( 1 λ ) (\mathrm{vk},\mathrm{sk}_0) \leftarrow\operatorname{KeyGen}(1^\lambda) ( vk , sk 0 ) ← KeyGen ( 1 λ ) and sends v k \mathrm{vk} vk to A A A .
A A A can make public-key queries: on the j j j -th query, the challenger runs ( p k j , s k j ) ← PKGen ( s k j − 1 ) (\mathrm{pk}_j,\mathrm{sk}_j) \leftarrow\operatorname{PKGen}(\mathrm{sk}_{j-1}) ( pk j , sk j ) ← PKGen ( sk j − 1 ) and sends p k j \mathrm{pk}_j pk j to A A A .
A A A generates a quantum state over two registers ( P , E ) (\mathbf{P},\mathbf{E}) ( P , E ) , sends the register P \mathbf{P} P to the challenger, and keeps the register E \mathbf{E} E .
The challenger samples b ← { 0 , 1 } b \leftarrow\{0,1\} b ← { 0 , 1 } , runs c t ← Enc ( v k , P , b ) \mathrm{ct} \leftarrow\operatorname{Enc}(\mathrm{vk},\mathbf{P},b) ct ← Enc ( vk , P , b ) , where the state of the register P \mathbf{P} P is used as the public key, and sends c t \mathrm{ct} ct to A A A .
A A A further makes public-key queries.
A A A outputs b ′ ∈ { 0 , 1 } b' \in\{0,1\} b ′ ∈ { 0 , 1 } .
Definition 2.12 (Everlasting security). A Q P K E QPKE QP K E scheme satisfies everlasting security if the following holds for any adversary A A A of the following form: during the security game of Definition 2.11, all operations of A A A are Q P T QPT QP T ; after the interaction with the challenger terminates, A A A applies computationally-unbounded operations on all the registers that it keeps, and outputs a bit b ′ b' b ′ . The requirement is that
Pr [ b ′ = b ] ≤ 1 2 + negl ( λ ) . (16) \Pr[b' = b] \le\frac{1}{2} + \operatorname{negl}(\lambda). \tag*{(16)} Pr [ b ′ = b ] ≤ 2 1 + negl ( λ ) . (16)
Remark 2.13. The security game of Definition 2.11 corresponds to the setting where v k \mathrm{vk} vk is distributed over an authenticated classical channel while quantum public keys are distributed over unauthenticated quantum channels: the register P \mathbf{P} P models the (possibly tampered) quantum public key that the sender actually uses, whereas v k \mathrm{vk} vk is guaranteed to be authentic.
Remark 2.14. Unlike the Q P K E QPKE QP K E of [20 ] , our syntax allows PKGen to be stateful (the secret key is updated and carried over across invocations), and secret keys may be quantum, while v k \mathrm{vk} vk and ciphertexts remain classical. In our construction, the quantum part of the secret key is a single one-shot signing key, and its size does not grow with the number of issued public keys; all other components of the secret key are classical, and Dec takes only the classical part as input. A quantum public key is consumed by a single execution of Enc, and therefore each p k i \mathrm{pk}_i pk i is used to encrypt a single message; multi-bit messages can be encrypted bit by bit under independently generated public keys.
2QKE from Digital Signatures
Theorem 3.1. If one-time secure digital signatures with quantum signatures exist, then 2QKE with everlasting security exist.
Proof. Let ( KeyGen , Sign , Vrfy ) (\operatorname{KeyGen}, \operatorname{Sign}, \operatorname{Vrfy}) ( KeyGen , Sign , Vrfy ) be a one-time secure digital signature scheme with quantum signatures. By Remark 2.4, we assume that signatures ∣ σ ( 0 ) ⟩ \lvert\sigma(0)\rangle ∣ σ ( 0 )⟩ and ∣ σ ( 1 ) ⟩ \lvert\sigma(1)\rangle ∣ σ ( 1 )⟩ are pure states. We assume without loss of generality that sig k \operatorname{sig}_{k} sig k consists of two registers ( sig k 0 , sig k 1 ) (\operatorname{sig}_{k_0},\operatorname{sig}_{k_1}) ( sig k 0 , sig k 1 ) such that Sign ( sig k , m ) \operatorname{Sign}(\operatorname{sig}_{k},m) Sign ( sig k , m ) acts only on sig k m \operatorname{sig}_{k_m} sig k m , so that Alice can generate both ∣ σ ( 0 ) ⟩ \lvert\sigma(0)\rangle ∣ σ ( 0 )⟩ and ∣ σ ( 1 ) ⟩ \lvert\sigma(1)\rangle ∣ σ ( 1 )⟩ . Note that this can be satisfied by running any signature algorithm twice, and using the first signing key to generate ∣ σ ( 0 ) ⟩ \lvert\sigma(0)\rangle ∣ σ ( 0 )⟩ and the second to generate ∣ σ ( 1 ) ⟩ \lvert\sigma(1)\rangle ∣ σ ( 1 )⟩ .
Write the verification algorithm in the standard form: Vrfy ( vk , m , ⋅ ) \operatorname{Vrfy}(\operatorname{vk},m,\cdot) Vrfy ( vk , m , ⋅ ) appends an ancilla register B ′ \mathrm{B}' B ′ initialized to ∣ 0 … 0 ⟩ \lvert0\ldots0\rangle ∣ 0 … 0 ⟩ , applies a unitary U vk , m U_{\operatorname{vk},m} U vk , m , and measures a flag qubit in the computational basis, accepting if and only if the outcome is ⊤ \top ⊤ . Define the projection Π vk , m \Pi_{\operatorname{vk},m} Π vk , m on the registers ( B , B ′ ) (\mathrm{B},\mathrm{B}') ( B , B ′ ) and the POVM element Λ vk , m \Lambda_{\operatorname{vk},m} Λ vk , m on the register B \mathrm{B} B by
Π vk , m : = U vk , m † ( ∣ ⊤ ⟩ ⟨ ⊤ ∣ ⊗ I ) U vk , m , Λ vk , m : = ⟨ 0 … 0 ∣ B ′ Π vk , m ∣ 0 … 0 ⟩ B ′ , (17) \Pi_{\operatorname{vk},m}:=U_{\operatorname{vk},m}^{\dagger}(\lvert\top\rangle\langle\top\rvert\otimes I)U_{\operatorname{vk},m},\qquad\Lambda_{\operatorname{vk},m}:=\langle0\ldots0\rvert_{\mathrm{B}'}\Pi_{\operatorname{vk},m}\lvert0\ldots0\rangle_{\mathrm{B}'}, \tag*{(17)} Π vk , m := U vk , m † (∣ ⊤ ⟩ ⟨ ⊤ ∣ ⊗ I ) U vk , m , Λ vk , m := ⟨ 0 … 0 ∣ B ′ Π vk , m ∣ 0 … 0 ⟩ B ′ , (17)
so that Pr [ ⊤ ← Vrfy ( vk , m , σ ) ] = Tr [ Λ vk , m σ ] \Pr[\top\leftarrow\operatorname{Vrfy}(\operatorname{vk},m,\sigma)]=\operatorname{Tr}[\Lambda_{\operatorname{vk},m}\sigma] Pr [ ⊤ ← Vrfy ( vk , m , σ )] = Tr [ Λ vk , m σ ] for every state σ \sigma σ of the register B \mathrm{B} B .
We construct a 2QKE as follows.
Alice runs ( vk , sig k ) ← KeyGen ( 1 λ ) (\operatorname{vk},\operatorname{sig}_{k})\leftarrow\operatorname{KeyGen}(1^{\lambda}) ( vk , sig k ) ← KeyGen ( 1 λ ) .
Alice runs ∣ σ ( 0 ) ⟩ ← Sign ( sig k , 0 ) \lvert\sigma(0)\rangle\leftarrow\operatorname{Sign}(\operatorname{sig}_{k},0) ∣ σ ( 0 )⟩ ← Sign ( sig k , 0 ) and ∣ σ ( 1 ) ⟩ ← Sign ( sig k , 1 ) \lvert\sigma(1)\rangle\leftarrow\operatorname{Sign}(\operatorname{sig}_{k},1) ∣ σ ( 1 )⟩ ← Sign ( sig k , 1 ) .
By using the controlled-SWAP gate, Alice generates
∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B ∣ σ ( 1 ) ⟩ C + ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B ∣ σ ( 0 ) ⟩ C . (18) \lvert0\rangle_{\mathrm{A}}\lvert\sigma(0)\rangle_{\mathrm{B}}\lvert\sigma(1)\rangle_{\mathrm{C}}+\lvert1\rangle_{\mathrm{A}}\lvert\sigma(1)\rangle_{\mathrm{B}}\lvert\sigma(0)\rangle_{\mathrm{C}}. \tag*{(18)} ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B ∣ σ ( 1 ) ⟩ C + ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B ∣ σ ( 0 ) ⟩ C . (18)
Alice applies a random Pauli P P P on C \mathrm{C} C to get
∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C . (19) \lvert0\rangle_{\mathrm{A}}\lvert\sigma(0)\rangle_{\mathrm{B}}P\lvert\sigma(1)\rangle_{\mathrm{C}}+\lvert1\rangle_{\mathrm{A}}\lvert\sigma(1)\rangle_{\mathrm{B}}P\lvert\sigma(0)\rangle_{\mathrm{C}}. \tag*{(19)} ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C . (19)
Alice samples a ← { 0 , 1 } a\leftarrow\{0,1\} a ← { 0 , 1 } and applies Z a Z^{a} Z a on A \mathrm{A} A to get
∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ( − 1 ) a ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C . (20) \lvert0\rangle_{\mathrm{A}}\lvert\sigma(0)\rangle_{\mathrm{B}}P\lvert\sigma(1)\rangle_{\mathrm{C}}+(-1)^{a}\lvert1\rangle_{\mathrm{A}}\lvert\sigma(1)\rangle_{\mathrm{B}}P\lvert\sigma(0)\rangle_{\mathrm{C}}. \tag*{(20)} ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ( − 1 ) a ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C . (20)
Alice sends the state to Bob. Alice also sends vk \operatorname{vk} vk to Bob.
Bob appends ∣ 0 … 0 ⟩ B ′ \lvert0\ldots0\rangle_{\mathrm{B}'} ∣ 0 … 0 ⟩ B ′ and measures A B B ′ \mathrm{ABB}' ABB ′ with { Π vk , I − Π vk } \{\Pi^{\operatorname{vk}},I-\Pi^{\operatorname{vk}}\} { Π vk , I − Π vk } , where
Π vk : = ∑ m ∈ { 0 , 1 } ∣ m ⟩ ⟨ m ∣ A ⊗ Π vk , m . (21) \Pi^{\operatorname{vk}}:=\sum_{m\in\{0,1\}}\lvert m\rangle\langle m\rvert_{\mathrm{A}}\otimes\Pi_{\operatorname{vk},m}. \tag*{(21)} Π vk := m ∈ { 0 , 1 } ∑ ∣ m ⟩ ⟨ m ∣ A ⊗ Π vk , m . (21)
If the result is I − Π vk I-\Pi^{\operatorname{vk}} I − Π vk , he outputs a random bit, and sends the maximally-mixed state to Alice. If the result is Π vk \Pi^{\operatorname{vk}} Π vk , the post-measurement state is, due to the gentle measurement lemma, negligibly close to
( ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ( − 1 ) a ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C ) ⊗ ∣ 0 … 0 ⟩ B ′ . (22) \left(\lvert0\rangle_{\mathrm{A}}\lvert\sigma(0)\rangle_{\mathrm{B}}P\lvert\sigma(1)\rangle_{\mathrm{C}}+(-1)^{a}\lvert1\rangle_{\mathrm{A}}\lvert\sigma(1)\rangle_{\mathrm{B}}P\lvert\sigma(0)\rangle_{\mathrm{C}}\right)\otimes\lvert0\ldots0\rangle_{\mathrm{B}'}. \tag*{(22)} ( ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ( − 1 ) a ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C ) ⊗ ∣ 0 … 0 ⟩ B ′ . (22)
Bob discards B ′ \mathrm{B}' B ′ . Bob samples b ← { 0 , 1 } b\leftarrow\{0,1\} b ← { 0 , 1 } and applies Z b Z^{b} Z b on A \mathrm{A} A to get
∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ( − 1 ) a ⊕ b ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C , (23) \lvert0\rangle_{\mathrm{A}}\lvert\sigma(0)\rangle_{\mathrm{B}}P\lvert\sigma(1)\rangle_{\mathrm{C}}+(-1)^{a\oplus b}\lvert1\rangle_{\mathrm{A}}\lvert\sigma(1)\rangle_{\mathrm{B}}P\lvert\sigma(0)\rangle_{\mathrm{C}}, \tag*{(23)} ∣ 0 ⟩ A ∣ σ ( 0 ) ⟩ B P ∣ σ ( 1 ) ⟩ C + ( − 1 ) a ⊕ b ∣ 1 ⟩ A ∣ σ ( 1 ) ⟩ B P ∣ σ ( 0 ) ⟩ C , (23)
and sends it to Alice. Bob outputs b b b .
Alice applies P † P^\dagger P † and the controlled-SWAP to get ( ∣ 0 ⟩ + ( − 1 ) a ⊕ b ∣ 1 ⟩ ) ∣ σ ( 0 ) ⟩ ∣ σ ( 1 ) ⟩ (|0\rangle+ (-1)^{a\oplus b}|1\rangle)|\sigma(0)\rangle|\sigma(1)\rangle ( ∣0 ⟩ + ( − 1 ) a ⊕ b ∣1 ⟩) ∣ σ ( 0 )⟩ ∣ σ ( 1 )⟩ . She measures the first qubit in the Hadamard basis, and outputs the measurement result plus a a a .
Correctness is clear. Let us show everlasting security. Without loss of generality, Eve works as follows: she reads vk, prepares her register E \mathbf{E} E initialized to ∣ 0 … 0 ⟩ |0\ldots0\rangle ∣0 … 0 ⟩ , applies a QPT unitary V 1 v k V_1^{\mathrm{vk}} V 1 vk on the registers ( A , B , C , E ) (\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{E}) ( A , B , C , E ) , and forwards ( A , B , C ) (\mathbf{A},\mathbf{B},\mathbf{C}) ( A , B , C ) to Bob; when Bob’s message is transmitted, she keeps all the registers ( A , B , C , E ) (\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{E}) ( A , B , C , E ) , applies a two-outcome POVM { D , I − D } \{D,I-D\} { D , I − D } on them, which can be computationally unbounded, and outputs the outcome as e e e .
Because a a a and P P P are used only in step 8, we can average Alice’s message over them: averaging over a a a dephases the register A \mathbf{A} A , and averaging over P P P makes the register C \mathbf{C} C maximally mixed, and therefore Alice’s first phase is identical, from Eve’s viewpoint, to the following one.
Alice runs ( v k , s i g k ) ← KeyGen ( 1 λ ) (\mathrm{vk},\mathrm{sig}_{\mathrm{k}}) \leftarrow\operatorname{KeyGen}(1^\lambda) ( vk , sig k ) ← KeyGen ( 1 λ ) .
Alice chooses α ← { 0 , 1 } \alpha\leftarrow\{0,1\} α ← { 0 , 1 } .
Alice runs ∣ σ ( α ) ⟩ ← Sign ( s i g k , α ) |\sigma(\alpha)\rangle\leftarrow\operatorname{Sign}(\mathrm{sig}_{\mathrm{k}},\alpha) ∣ σ ( α )⟩ ← Sign ( sig k , α ) .
Alice samples x ← { 0 , 1 } n x \leftarrow\{0,1\}^n x ← { 0 , 1 } n .
Alice sends the state ∣ α ⟩ A ∣ σ ( α ) ⟩ B ∣ x ⟩ C |\alpha\rangle_{\mathbf{A}}|\sigma(\alpha)\rangle_{\mathbf{B}}|x\rangle_{\mathbf{C}} ∣ α ⟩ A ∣ σ ( α ) ⟩ B ∣ x ⟩ C to Bob. Alice also sends vk to Bob.
Hence hereafter we consider this Alice’s first phase.
By the principle of deferred measurement, we can also assume without loss of generality that KeyGen has the following form: a unitary is applied to ∣ 0 … 0 ⟩ |0\ldots0\rangle ∣0 … 0 ⟩ , some registers are measured in the computational basis to get vk, and the quantum sigk is a state of some unmeasured registers. Similarly, we can assume without loss of generality that Sign has the following form: a unitary is applied to ∣ 0 … 0 ⟩ |0\ldots0\rangle ∣0 … 0 ⟩ , some registers are measured in the computational basis to get a result i i i , and the pure quantum signature is a state of some unmeasured registers. Let t : = ( v k , i , x ) t := (\mathrm{vk},i,x) t := ( vk , i , x ) . For the notational simplicity, hereafter we omit vk of Π v k , m \Pi_{\mathrm{vk},m} Π vk , m , Π v k \Pi_{\mathrm{vk}} Π vk , Λ v k , m \Lambda_{\mathrm{vk},m} Λ vk , m and V 1 v k V_1^{\mathrm{vk}} V 1 vk . For each α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } and t t t , define the normalized pure state
∣ ξ α ( t ) ⟩ : = V 1 ( ∣ α ⟩ A ∣ σ ( α ) ⟩ B ∣ x ⟩ C ∣ 0 … 0 ⟩ E ) , (24) |\xi_\alpha(t)\rangle:= V_1(|\alpha\rangle_{\mathbf{A}}|\sigma(\alpha)\rangle_{\mathbf{B}}|x\rangle_{\mathbf{C}}|0\ldots0\rangle_{\mathbf{E}}), \tag*{(24)} ∣ ξ α ( t )⟩ := V 1 ( ∣ α ⟩ A ∣ σ ( α ) ⟩ B ∣ x ⟩ C ∣0 … 0 ⟩ E ) , (24)
and the unnormalized state
∣ φ m , α ( t ) ⟩ : = ( ⟨ m ∣ A ⊗ Π m ⊗ I C , E ) ( ∣ ξ α ( t ) ⟩ ⊗ ∣ 0 … 0 ⟩ B ′ ) (25) |\varphi_{m,\alpha}(t)\rangle:= (\langle m|_{\mathbf{A}} \otimes\Pi_m \otimes I_{\mathbf{C},\mathbf{E}})(|\xi_\alpha(t)\rangle\otimes|0\ldots0\rangle_{\mathbf{B}'}) \tag*{(25)} ∣ φ m , α ( t )⟩ := (⟨ m ∣ A ⊗ Π m ⊗ I C , E ) ( ∣ ξ α ( t )⟩ ⊗ ∣0 … 0 ⟩ B ′ ) (25)
for m ∈ { 0 , 1 } m \in\{0,1\} m ∈ { 0 , 1 } . We can easily show
( Π ⊗ I C , E ) ( ∣ ξ α ( t ) ⟩ ∣ 0 … 0 ⟩ B ′ ) = ∑ m ∈ { 0 , 1 } ∣ m ⟩ A ⊗ ∣ φ m , α ( t ) ⟩ . (26) (\Pi\otimes I_{\mathbf{C},\mathbf{E}})(|\xi_\alpha(t)\rangle|0\ldots0\rangle_{\mathbf{B}'}) = \sum_{m\in\{0,1\}} |m\rangle_{\mathbf{A}} \otimes|\varphi_{m,\alpha}(t)\rangle. \tag*{(26)} ( Π ⊗ I C , E ) ( ∣ ξ α ( t )⟩ ∣0 … 0 ⟩ B ′ ) = m ∈ { 0 , 1 } ∑ ∣ m ⟩ A ⊗ ∣ φ m , α ( t )⟩ . (26)
For β ∈ { 0 , 1 } \beta\in\{0,1\} β ∈ { 0 , 1 } , let σ β \sigma_\beta σ β denote the state of all the registers that Eve keeps at the end of the protocol, conditioned on that Bob’s output is β \beta β . Because Bob’s output is a uniformly random bit both when Bob’s test outputs ⊤ \top ⊤ and when it outputs ⊥ \bot ⊥ , Bob’s output is independent of t t t , α \alpha α , and the outcome of Bob’s test, and hence
σ β = E t , α [ ( 1 − p α ( t ) ) ρ r e j ( t , α ) ] (27) \sigma_\beta= \mathbb{E}_{t,\alpha}\left[(1-p_\alpha(t))\rho_{\mathrm{rej}}(t,\alpha)\right] \tag*{(27)} σ β = E t , α [ ( 1 − p α ( t )) ρ rej ( t , α ) ] (27)
+ E t , α [ Tr B ′ ( Z A β ⊗ I ) ( Π ⊗ I C , E ) ( ∣ ξ α ( t ) ⟩ ⟨ ξ α ( t ) ∣ ⊗ ∣ 0 … 0 ⟩ ⟨ 0 … 0 ∣ B ′ ) ( Π ⊗ I C , E ) ( Z A β ⊗ I ) ] , (28) + \mathbb{E}_{t,\alpha}\left[\operatorname{Tr}_{\mathbf{B}'}(Z_{\mathbf{A}}^\beta\otimes I)(\Pi\otimes I_{\mathbf{C},\mathbf{E}})(|\xi_\alpha(t)\rangle\langle\xi_\alpha(t)| \otimes|0\ldots0\rangle\langle0\ldots0|_{\mathbf{B}'}) (\Pi\otimes I_{\mathbf{C},\mathbf{E}})(Z_{\mathbf{A}}^\beta\otimes I)\right], \tag*{(28)} + E t , α [ Tr B ′ ( Z A β ⊗ I ) ( Π ⊗ I C , E ) ( ∣ ξ α ( t )⟩ ⟨ ξ α ( t ) ∣ ⊗ ∣0 … 0 ⟩ ⟨ 0 … 0 ∣ B ′ ) ( Π ⊗ I C , E ) ( Z A β ⊗ I ) ] , (28)
where p α ( t ) p_{\alpha}(t) p α ( t ) is the probability that Bob’s test outputs ⊤ \top ⊤ , and ρ r e j ( t , α ) \rho_{\mathrm{rej}}(t,\alpha) ρ rej ( t , α ) is the state of the registers that Eve keeps conditioned on ( t , α ) (t,\alpha) ( t , α ) and on Bob’s test outputting ⊥ \bot ⊥ , which is independent of β \beta β . Substituting Equation (26) into Equation (28) , we obtain
σ 1 − σ 0 = − ∑ α ∈ { 0 , 1 } E t [ Tr B ′ [ ∣ 0 ⟩ ⟨ 1 ∣ A ⊗ ∣ φ 0 , α ( t ) ⟩ ⟨ φ 1 , α ( t ) ∣ + ∣ 1 ⟩ ⟨ 0 ∣ A ⊗ ∣ φ 1 , α ( t ) ⟩ ⟨ φ 0 , α ( t ) ∣ ] ] . (29) \sigma_1-\sigma_0=-\sum_{\alpha\in\{0,1\}}\mathbb{E}_t\left[\operatorname{Tr}_{B'}\left[|0\rangle\langle1|_A\otimes|\varphi_{0,\alpha}(t)\rangle\langle\varphi_{1,\alpha}(t)|+|1\rangle\langle0|_A\otimes|\varphi_{1,\alpha}(t)\rangle\langle\varphi_{0,\alpha}(t)|\right]\right]. \tag*{(29)} σ 1 − σ 0 = − α ∈ { 0 , 1 } ∑ E t [ Tr B ′ [ ∣0 ⟩ ⟨ 1 ∣ A ⊗ ∣ φ 0 , α ( t )⟩ ⟨ φ 1 , α ( t ) ∣ + ∣1 ⟩ ⟨ 0 ∣ A ⊗ ∣ φ 1 , α ( t )⟩ ⟨ φ 0 , α ( t ) ∣ ] ] . (29)
For any POVM element 0 ⪯ D ⪯ I 0\preceq D\preceq I 0 ⪯ D ⪯ I ,
Pr [ e = β ] = 1 2 Tr [ ( I − D ) σ 0 ] + 1 2 Tr [ D σ 1 ] = 1 2 + 1 2 Tr [ D ( σ 1 − σ 0 ) ] ≤ 1 2 + 1 4 ∥ σ 1 − σ 0 ∥ 1 . (30) \Pr[e=\beta]=\frac{1}{2}\operatorname{Tr}[(I-D)\sigma_0]+\frac{1}{2}\operatorname{Tr}[D\sigma_1]=\frac{1}{2}+\frac{1}{2}\operatorname{Tr}[D(\sigma_1-\sigma_0)]\leq\frac{1}{2}+\frac{1}{4}\|\sigma_1-\sigma_0\|_1. \tag*{(30)} Pr [ e = β ] = 2 1 Tr [( I − D ) σ 0 ] + 2 1 Tr [ D σ 1 ] = 2 1 + 2 1 Tr [ D ( σ 1 − σ 0 )] ≤ 2 1 + 4 1 ∥ σ 1 − σ 0 ∥ 1 . (30)
By Equation (29) , the triangle inequality, ∥ ∣ 0 ⟩ ⟨ 1 ∣ A ⊗ M ∥ 1 = ∥ M ∥ 1 \||0\rangle\langle1|_A\otimes M\|_1=\|M\|_1 ∥∣0 ⟩ ⟨ 1 ∣ A ⊗ M ∥ 1 = ∥ M ∥ 1 , and ∥ M ∗ ∥ 1 = ∥ M ∥ 1 \|M^{*}\|_1=\|M\|_1 ∥ M ∗ ∥ 1 = ∥ M ∥ 1 ,
∥ σ 1 − σ 0 ∥ 1 ≤ 2 ∑ α ∈ { 0 , 1 } ∥ E t [ ∣ φ 0 , α ( t ) ⟩ ⟨ φ 1 , α ( t ) ∣ ] ∥ 1 . (31) \|\sigma_1-\sigma_0\|_1\leq2\sum_{\alpha\in\{0,1\}}\left\|\mathbb{E}_t\left[|\varphi_{0,\alpha}(t)\rangle\langle\varphi_{1,\alpha}(t)|\right]\right\|_1. \tag*{(31)} ∥ σ 1 − σ 0 ∥ 1 ≤ 2 α ∈ { 0 , 1 } ∑ ∥ E t [ ∣ φ 0 , α ( t )⟩ ⟨ φ 1 , α ( t ) ∣ ] ∥ 1 . (31)
It therefore suffices to show, for each α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } ,
∥ E t [ ∣ φ 0 , α ( t ) ⟩ ⟨ φ 1 , α ( t ) ∣ ] ∥ 1 ≤ negl ( λ ) . (32) \left\|\mathbb{E}_t\left[|\varphi_{0,\alpha}(t)\rangle\langle\varphi_{1,\alpha}(t)|\right]\right\|_1\leq\operatorname{negl}(\lambda). \tag*{(32)} ∥ E t [ ∣ φ 0 , α ( t )⟩ ⟨ φ 1 , α ( t ) ∣ ] ∥ 1 ≤ negl ( λ ) . (32)
Define
η α : = E t [ ∥ ∣ φ 1 − α , α ( t ) ⟩ ∥ 2 ] . (33) \eta_{\alpha}:=\mathbb{E}_t\left[\left\|\left|\varphi_{1-\alpha,\alpha}(t)\right\rangle\right\|^2\right]. \tag*{(33)} η α := E t [ ∥ ∣ φ 1 − α , α ( t ) ⟩ ∥ 2 ] . (33)
Hence, by the triangle inequality, ∥ ∣ u ⟩ ⟨ v ∣ ∥ 1 = ∥ ∣ u ⟩ ∥ ⋅ ∥ ∣ v ⟩ ∥ \||u\rangle\langle v|\|_1=\||u\rangle\|\cdot\||v\rangle\| ∥∣ u ⟩ ⟨ v ∣ ∥ 1 = ∥∣ u ⟩ ∥ ⋅ ∥∣ v ⟩ ∥ , ∥ ∣ φ α , α ⟩ ∥ ≤ 1 \||\varphi_{\alpha,\alpha}\rangle\|\leq1 ∥∣ φ α , α ⟩ ∥ ≤ 1 , and Jensen’s inequality,
∥ E t [ ∣ φ 0 , α ( t ) ⟩ ⟨ φ 1 , α ( t ) ∣ ] ∥ 1 ≤ E t [ ∥ ∣ φ 0 , α ( t ) ⟩ ∥ ⋅ ∥ ∣ φ 1 , α ( t ) ⟩ ∥ ] ≤ E t [ ∥ ∣ φ 1 − α , α ( t ) ⟩ ∥ ] ≤ η α . (34) \left\|\mathbb{E}_t\left[|\varphi_{0,\alpha}(t)\rangle\langle\varphi_{1,\alpha}(t)|\right]\right\|_1\leq\mathbb{E}_t\left[\left\|\left|\varphi_{0,\alpha}(t)\right\rangle\right\|\cdot\left\|\left|\varphi_{1,\alpha}(t)\right\rangle\right\|\right]\leq\mathbb{E}_t\left[\left\|\left|\varphi_{1-\alpha,\alpha}(t)\right\rangle\right\|\right]\leq\sqrt{\eta_{\alpha}}. \tag*{(34)} ∥ E t [ ∣ φ 0 , α ( t )⟩ ⟨ φ 1 , α ( t ) ∣ ] ∥ 1 ≤ E t [ ∥ ∣ φ 0 , α ( t ) ⟩ ∥ ⋅ ∥ ∣ φ 1 , α ( t ) ⟩ ∥ ] ≤ E t [ ∥ ∣ φ 1 − α , α ( t ) ⟩ ∥ ] ≤ η α . (34)
Equation (32) then follows from the following claim.
Claim 3.2. For each α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } , η α ≤ negl ( λ ) \eta_{\alpha}\leq\operatorname{negl}(\lambda) η α ≤ negl ( λ ) .
Proof. Fix α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } . Because ∣ m ⟩ ⟨ m ∣ A ⊗ Π m ⊗ I C , E |m\rangle\langle m|_A\otimes\Pi_m\otimes I_{C,E} ∣ m ⟩ ⟨ m ∣ A ⊗ Π m ⊗ I C , E is a projection, and because ⟨ 0 … 0 ∣ B ′ Π m ∣ 0 … 0 ⟩ B ′ = Λ m \langle0\ldots0|_{B'}\Pi_m|0\ldots0\rangle_{B'}=\Lambda_m ⟨ 0 … 0 ∣ B ′ Π m ∣0 … 0 ⟩ B ′ = Λ m by Equation (17) , we have, for each m ∈ { 0 , 1 } m\in\{0,1\} m ∈ { 0 , 1 } and conditioned on any fixed t t t ,
∥ ∣ φ m , α ( t ) ⟩ ∥ 2 = ( ⟨ ξ α ( t ) ∣ ⊗ ⟨ 0 … 0 ∣ B ′ ) ( ∣ m ⟩ ⟨ m ∣ A ⊗ Π m ⊗ I C , E ) ( ∣ ξ α ( t ) ⟩ ⊗ ∣ 0 … 0 ⟩ B ′ ) (35) \left\|\left|\varphi_{m,\alpha}(t)\right\rangle\right\|^2=\left(\langle\xi_{\alpha}(t)|\otimes\langle0\ldots0|_{B'}\right)\left(|m\rangle\langle m|_A\otimes\Pi_m\otimes I_{C,E}\right)\left(|\xi_{\alpha}(t)\rangle\otimes|0\ldots0\rangle_{B'}\right) \tag*{(35)} ∥ ∣ φ m , α ( t ) ⟩ ∥ 2 = ( ⟨ ξ α ( t ) ∣ ⊗ ⟨ 0 … 0 ∣ B ′ ) ( ∣ m ⟩ ⟨ m ∣ A ⊗ Π m ⊗ I C , E ) ( ∣ ξ α ( t )⟩ ⊗ ∣0 … 0 ⟩ B ′ ) (35)
= ⟨ ξ α ( t ) ∣ ( ∣ m ⟩ ⟨ m ∣ A ⊗ Λ m ⊗ I C , E ) ∣ ξ α ( t ) ⟩ , (36) =\langle\xi_{\alpha}(t)|\left(|m\rangle\langle m|_A\otimes\Lambda_m\otimes I_{C,E}\right)|\xi_{\alpha}(t)\rangle, \tag*{(36)} = ⟨ ξ α ( t ) ∣ ( ∣ m ⟩ ⟨ m ∣ A ⊗ Λ m ⊗ I C , E ) ∣ ξ α ( t )⟩ , (36)
where Λ m \Lambda_m Λ m acts on the register B. In particular,
η α = E t [ ⟨ ξ α ( t ) ∣ ( ∣ 1 − α ⟩ ⟨ 1 − α ∣ A ⊗ Λ 1 − α ⊗ I C , E ) ∣ ξ α ( t ) ⟩ ] . (37) \eta_{\alpha}=\mathbb{E}_t\left[\langle\xi_{\alpha}(t)|\left(|1-\alpha\rangle\langle1-\alpha|_A\otimes\Lambda_{1-\alpha}\otimes I_{C,E}\right)|\xi_{\alpha}(t)\rangle\right]. \tag*{(37)} η α = E t [ ⟨ ξ α ( t ) ∣ ( ∣1 − α ⟩ ⟨ 1 − α ∣ A ⊗ Λ 1 − α ⊗ I C , E ) ∣ ξ α ( t )⟩ ] . (37)
For each α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } , consider the following QPT adversary G α = ( G 1 α , G 2 α ) G^{\alpha}=(G^{\alpha}_1,G^{\alpha}_2) G α = ( G 1 α , G 2 α ) against the one-time security of the digital signature scheme.
G 2 α ( σ , s t ) G_{2}^{\alpha}(\sigma,st) G 2 α ( σ , s t ) : Sample x ← { 0 , 1 } n x \leftarrow\{0,1\}^{n} x ← { 0 , 1 } n and prepare ∣ α ⟩ A ⊗ σ B ⊗ ∣ x ⟩ C ⊗ ∣ 0 … 0 ⟩ E |\alpha\rangle_{A} \otimes\sigma_{B} \otimes|x\rangle_{C} \otimes|0\ldots0\rangle_{E} ∣ α ⟩ A ⊗ σ B ⊗ ∣ x ⟩ C ⊗ ∣0 … 0 ⟩ E , where σ \sigma σ is the signature given by the challenger. Apply V 1 V_{1} V 1 on ( A , B , C , E ) (A,B,C,E) ( A , B , C , E ) , and measure the register A A A in the computational basis. If the outcome is not 1 − α 1-\alpha 1 − α , abort. Otherwise, output the state of the register B B B as σ ′ \sigma' σ ′ .
We show that the probability that G 2 α G_{2}^{\alpha} G 2 α does not abort and the challenger’s verification accepts is exactly η α \eta_{\alpha} η α . In the one-time security experiment against G 2 α G_{2}^{\alpha} G 2 α , the challenger runs ( v k , s i g k ) ← KeyGen ( 1 λ ) (\mathrm{vk},\mathrm{sigk}) \leftarrow\operatorname{KeyGen}(1^{\lambda}) ( vk , sigk ) ← KeyGen ( 1 λ ) and σ ← Sign ( s i g k , α ) \sigma\leftarrow\operatorname{Sign}(\mathrm{sigk},\alpha) σ ← Sign ( sigk , α ) . By the normal form of Sign \operatorname{Sign} Sign and Remark 2.4, conditioned on v k \mathrm{vk} vk and the result i i i of the internal measurement of this signing, σ \sigma σ is the pure state ∣ σ ( α ) ⟩ |\sigma(\alpha)\rangle ∣ σ ( α )⟩ . Condition on t = ( v k , i , x ) t=(\mathrm{vk},i,x) t = ( vk , i , x ) . After G 2 α G_{2}^{\alpha} G 2 α applies V 1 V_{1} V 1 , the state of the registers ( A , B , C , E ) (A,B,C,E) ( A , B , C , E ) is ∣ ξ α ( t ) ⟩ |\xi_{\alpha}(t)\rangle ∣ ξ α ( t )⟩ . Define
∣ χ ⟩ : = ( ⟨ 1 − α ∣ A ⊗ I B , C , E ) ∣ ξ α ( t ) ⟩ . (38) |\chi\rangle:= \left(\langle1-\alpha|_{A} \otimes I_{B,C,E}\right)|\xi_{\alpha}(t)\rangle. \tag*{(38)} ∣ χ ⟩ := ( ⟨ 1 − α ∣ A ⊗ I B , C , E ) ∣ ξ α ( t )⟩ . (38)
The probability that the measurement of A A A yields 1 − α 1-\alpha 1 − α is ∥ ∣ χ ⟩ ∥ 2 \lVert|\chi\rangle\rVert^{2} ∥ ∣ χ ⟩ ∥ 2 , and, conditioned on this outcome, the challenger’s verification Vrfy ( v k , 1 − m , ⋅ ) = Vrfy ( v k , 1 − α , ⋅ ) \operatorname{Vrfy}(\mathrm{vk},1-m,\cdot)=\operatorname{Vrfy}(\mathrm{vk},1-\alpha,\cdot) Vrfy ( vk , 1 − m , ⋅ ) = Vrfy ( vk , 1 − α , ⋅ ) accepts with probability ⟨ χ ∣ ( Λ 1 − α ⊗ I C , E ) ∣ χ ⟩ / ∥ ∣ χ ⟩ ∥ 2 \langle\chi|(\Lambda_{1-\alpha}\otimes I_{C,E})|\chi\rangle/\lVert|\chi\rangle\rVert^{2} ⟨ χ ∣ ( Λ 1 − α ⊗ I C , E ) ∣ χ ⟩ / ∥ ∣ χ ⟩ ∥ 2 , because its acceptance probability is the expectation of Λ 1 − α \Lambda_{1-\alpha} Λ 1 − α in the reduced state of the register B B B . The probability that G 2 α G_{2}^{\alpha} G 2 α does not abort and the challenger accepts is therefore
⟨ χ ∣ ( Λ 1 − α ⊗ I C , E ) ∣ χ ⟩ = ⟨ ξ α ( t ) ∣ ( ∣ 1 − α ⟩ ⟨ 1 − α ∣ A ⊗ Λ 1 − α ⊗ I C , E ) ∣ ξ α ( t ) ⟩ = ∥ ∣ φ 1 − α , α ( t ) ⟩ ∥ 2 , (39) \langle\chi|(\Lambda_{1-\alpha}\otimes I_{C,E})|\chi\rangle
= \langle\xi_{\alpha}(t)|(|1-\alpha\rangle\langle1-\alpha|_{A}\otimes\Lambda_{1-\alpha}\otimes I_{C,E})|\xi_{\alpha}(t)\rangle
= \lVert|\varphi_{1-\alpha,\alpha}(t)\rangle\rVert^{2}, \tag*{(39)} ⟨ χ ∣ ( Λ 1 − α ⊗ I C , E ) ∣ χ ⟩ = ⟨ ξ α ( t ) ∣ ( ∣1 − α ⟩ ⟨ 1 − α ∣ A ⊗ Λ 1 − α ⊗ I C , E ) ∣ ξ α ( t )⟩ = ∥ ∣ φ 1 − α , α ( t )⟩ ∥ 2 , (39)
where the last equality is Equation (36) . Averaging over t = ( v k , i , x ) t=(\mathrm{vk},i,x) t = ( vk , i , x ) , G 2 α G_{2}^{\alpha} G 2 α wins the one-time security experiment with probability η α \eta_{\alpha} η α by Equation (33) , where aborting counts as losing. The one-time security of the digital signature scheme therefore gives η α ≤ negl ( λ ) \eta_{\alpha}\leq\operatorname{negl}(\lambda) η α ≤ negl ( λ ) .
EV-StatePuzzs from 2QKE
Theorem 4.1. If 2QKE exists, then 1 2 \frac{1}{2} 2 1 -sound EV-StatePuzzs exist.
Proof. Assume that a 2QKE exists. We can assume without loss of generality that Alice’s first phase has the following form: she applies a unitary U U U on ∣ 0 … 0 ⟩ |0\ldots0\rangle ∣0 … 0 ⟩ over three registers ( S , M , W ) (S,M,W) ( S , M , W ) to generate the state
U ∣ 0 … 0 ⟩ = ∑ s C s ∣ s ⟩ S ∣ Φ s ⟩ M , W , (40) U|0\ldots0\rangle= \sum_{s} C_{s}|s\rangle_{S}|\Phi_{s}\rangle_{M,W}, \tag*{(40)} U ∣0 … 0 ⟩ = s ∑ C s ∣ s ⟩ S ∣ Φ s ⟩ M , W , (40) where each C s ≥ 0 C_{s}\geq0 C s ≥ 0 , ∑ s C s 2 = 1 \sum_{s}C_{s}^{2}=1 ∑ s C s 2 = 1 , and each ∣ Φ s ⟩ |\Phi_{s}\rangle ∣ Φ s ⟩ is a normalized pure state; she measures S S S in the computational basis to obtain s s s ; she sends s s s over the classical channel and the register M M M over the quantum channel to Bob, and keeps the register W W W . Alice’s second phase is a quantum algorithm that takes s s s , the register W W W , and the quantum state returned from Bob as input, and outputs the bit α \alpha α .
We construct an EV-StatePuzz ( Samp , Ver ) (\operatorname{Samp},\operatorname{Ver}) ( Samp , Ver ) as follows.
Samp ( 1 λ ) \operatorname{Samp}(1^{\lambda}) Samp ( 1 λ ) : Apply U U U on ∣ 0 … 0 ⟩ |0\ldots0\rangle ∣0 … 0 ⟩ and measure S S S in the computational basis to obtain s s s . Output the puzzle s s s and the answer ψ s : = ∣ Φ s ⟩ \psi_{s}:=|\Phi_{s}\rangle ψ s := ∣ Φ s ⟩ , i.e., the state of the registers ( M , W ) (M,W) ( M , W ) .
Ver ( 1 λ , s , ρ ) \operatorname{Ver}(1^{\lambda},s,\rho) Ver ( 1 λ , s , ρ ) : The input ρ \rho ρ is a state of the registers ( M , W ) (M,W) ( M , W ) . Run Bob’s honest algorithm on s s s and the register M M M ; it outputs a bit β \beta β and returns a quantum state. Run Alice’s second phase on s s s , the register W W W , and the returned state; it outputs a bit α \alpha α . Output ⊤ \top ⊤ if and only if α = β \alpha=\beta α = β .
Both algorithms are QPT.
Correctness is clear. Let us show security. Let A \mathcal{A} A be a QPT adversary and write
p ( λ ) : = Pr [ ⊤ ← Ver ( 1 λ , s , A ( 1 λ , s ) ) : ( s , ψ s ) ← Samp ( 1 λ ) ] . (41) p(\lambda) := \Pr[\top\leftarrow\operatorname{Ver}(1^\lambda, s, \mathcal{A}(1^\lambda,s)) : (s,\psi_s) \leftarrow\operatorname{Samp}(1^\lambda)]. \tag*{(41)} p ( λ ) := Pr [ ⊤ ← Ver ( 1 λ , s , A ( 1 λ , s )) : ( s , ψ s ) ← Samp ( 1 λ )] . (41)
We construct the following QPT Eve:
Eve intercepts and discards the quantum message on the register M. She reads s s s from the classical channel without modifying it.
She runs A ( 1 λ , s ) \mathcal{A}(1^\lambda,s) A ( 1 λ , s ) to obtain a state of fresh registers ( M ′ , W ′ ) (\mathrm{M}',\mathrm{W}') ( M ′ , W ′ ) . She sends the register M ′ \mathrm{M}' M ′ to Bob over the quantum channel, and keeps the register W ′ \mathrm{W}' W ′ .
Bob runs his honest algorithm on s s s and the received register M ′ \mathrm{M}' M ′ , outputs β \beta β , and returns a quantum state to Alice. Eve intercepts the returned state. (She sends nothing to Alice.)
Eve runs Alice’s second phase on s s s , the register W ′ \mathrm{W}' W ′ , and the intercepted state, and outputs its output as e e e .
Conditioned on any fixed s s s , the state of the registers ( M ′ , W ′ ) (\mathrm{M}',\mathrm{W}') ( M ′ , W ′ ) and the process applied to it are identical in the attacked execution and in the experiment of Ver ( 1 λ , s , A ( 1 λ , s ) ) \operatorname{Ver}(1^\lambda,s,\mathcal{A}(1^\lambda,s)) Ver ( 1 λ , s , A ( 1 λ , s )) , where the roles of ( β , α ) (\beta,\alpha) ( β , α ) in the latter are played by ( β , e ) (\beta,e) ( β , e ) in the former; moreover, the distribution of s s s is the same in the two experiments. Therefore
Pr [ e = β ] = p ( λ ) . (42) \Pr[e=\beta]=p(\lambda). \tag*{(42)} Pr [ e = β ] = p ( λ ) . (42)
The security of the 2QKE gives p ( λ ) ≤ 1 2 + negl ( λ ) p(\lambda) \le\frac{1}{2}+\operatorname{negl}(\lambda) p ( λ ) ≤ 2 1 + negl ( λ ) , which is the claimed soundness. □
Lemma 4.2. Let p p p be a polynomial and let δ : N → [ 0 , 1 ] \delta:\mathbb{N}\to[0,1] δ : N → [ 0 , 1 ] satisfying δ ( λ ) ≤ 1 − 1 / p ( λ ) \delta(\lambda)\le1-1/p(\lambda) δ ( λ ) ≤ 1 − 1/ p ( λ ) . If δ \delta δ -sound EV-StatePuzzs exist, then EV-StatePuzzs exist.
Proof. Let ( Samp , Ver ) (\operatorname{Samp},\operatorname{Ver}) ( Samp , Ver ) be a δ \delta δ -sound EV-StatePuzz, and let ( Samp ′ , Ver ′ ) (\operatorname{Samp}',\operatorname{Ver}') ( Samp ′ , Ver ′ ) be its k k k -fold parallel repetition with k : = λ p ( λ ) k:=\lambda p(\lambda) k := λ p ( λ ) : Samp ′ \operatorname{Samp}' Samp ′ runs Samp ( 1 λ ) \operatorname{Samp}(1^\lambda) Samp ( 1 λ ) independently k k k times, and Ver ′ \operatorname{Ver}' Ver ′ accepts if and only if all k k k answer registers are accepted. Correctness follows from the union bound. The security experiment of ( Samp , Ver ) (\operatorname{Samp},\operatorname{Ver}) ( Samp , Ver ) is a two-message quantum interactive protocol between a QPT challenger and the adversary, and that of ( Samp ′ , Ver ′ ) (\operatorname{Samp}',\operatorname{Ver}') ( Samp ′ , Ver ′ ) is exactly its k k k -fold parallel repetition. Hence, by the parallel repetition theorem for three-message computationally-secure quantum interactive protocols with efficient challengers [7 ] , any QPT adversary wins the latter with probability at most ( δ ( λ ) + negl ( λ ) ) k + negl ( λ ) ≤ ( 1 − 1 2 p ( λ ) ) λ p ( λ ) + negl ( λ ) ≤ e − λ / 2 + negl ( λ ) ≤ negl ( λ ) (\delta(\lambda)+\operatorname{negl}(\lambda))^k+\operatorname{negl}(\lambda)\le(1-\frac{1}{2p(\lambda)})^{\lambda p(\lambda)}+\operatorname{negl}(\lambda)\le e^{-\lambda/2}+\operatorname{negl}(\lambda)\le\operatorname{negl}(\lambda) ( δ ( λ ) + negl ( λ ) ) k + negl ( λ ) ≤ ( 1 − 2 p ( λ ) 1 ) λ p ( λ ) + negl ( λ ) ≤ e − λ /2 + negl ( λ ) ≤ negl ( λ ) . □
QPKE from One-Shot Signatures
Theorem 5.1. If one-shot signatures exist, then everlasting-secure QPKE with quantum public keys exist.
Proof. Let ( Setup , Gen , Sign , Ver ) (\operatorname{Setup},\operatorname{Gen},\operatorname{Sign},\operatorname{Ver}) ( Setup , Gen , Sign , Ver ) be a one-shot signature scheme. Without loss of generality, we assume that verification keys have a fixed polynomial length and that all signatures are ℓ \ell ℓ -bit strings for a polynomial ℓ \ell ℓ , by padding. For x , y ∈ { 0 , 1 } ℓ x,y\in\{0,1\}^{\ell} x , y ∈ { 0 , 1 } ℓ , we write x ⋅ y : = ⨁ i = 1 ℓ x i y i x\cdot y:=\bigoplus_{i=1}^{\ell}x_i y_i x ⋅ y := ⨁ i = 1 ℓ x i y i . We use two registers A and B, consisting of one qubit and ℓ \ell ℓ qubits, respectively. For a pair u = ( u 0 , u 1 ) u=(u^0,u^1) u = ( u 0 , u 1 ) of verification keys, define the projection
Π u : = ∑ α ∈ { 0 , 1 } ∣ α ⟩ ⟨ α ∣ A ⊗ ∑ β ∈ { 0 , 1 } ℓ : ⊤ = Ver ( crs , u α , α , β ) ∣ β ⟩ ⟨ β ∣ B . (43) \Pi^u := \sum_{\alpha\in\{0,1\}}|\alpha\rangle\langle\alpha|_{\mathrm{A}}\otimes\sum_{\substack{\beta\in\{0,1\}^{\ell}:\\ \top=\operatorname{Ver}(\operatorname{crs},u^\alpha,\alpha,\beta)}}|\beta\rangle\langle\beta|_{\mathrm{B}}. \tag*{(43)} Π u := α ∈ { 0 , 1 } ∑ ∣ α ⟩ ⟨ α ∣ A ⊗ β ∈ { 0 , 1 } ℓ : ⊤ = Ver ( crs , u α , α , β ) ∑ ∣ β ⟩ ⟨ β ∣ B . (43)
Because Ver \operatorname{Ver} Ver is classical and deterministic, Π u \Pi^{u} Π u is diagonal in the computational basis, and the projective measurement { Π u , I − Π u } \{\Pi^{u}, I-\Pi^{u}\} { Π u , I − Π u } can be implemented in QPT by computing Ver \operatorname{Ver} Ver coherently into a flag qubit and measuring the flag.
We construct a QPKE scheme as follows.
KeyGen ( 1 λ ) (1^\lambda) ( 1 λ ) : Run c r s ← S e t u p ( 1 λ ) \mathsf{crs} \leftarrow\mathsf{Setup}(1^\lambda) crs ← Setup ( 1 λ ) and ( w 1 , s i g k 1 ) ← G e n ( c r s ) (w_1,\mathsf{sigk}_1) \leftarrow\mathsf{Gen}(\mathsf{crs}) ( w 1 , sigk 1 ) ← Gen ( crs ) . Output v k : = ( c r s , w 1 ) \mathsf{vk} := (\mathsf{crs}, w_1) vk := ( crs , w 1 ) and s k 0 : = ( c r s , w 1 , s i g k 1 ) \mathsf{sk}_0 := (\mathsf{crs}, w_1,\mathsf{sigk}_1) sk 0 := ( crs , w 1 , sigk 1 ) together with a counter initialized to 0 0 0 and an empty table. Only s i g k 1 \mathsf{sigk}_1 sigk 1 is quantum.
PKGen ( s k t − 1 ) (\mathsf{sk}_{t-1}) ( sk t − 1 ) (the t t t -th invocation; s k t − 1 \mathsf{sk}_{t-1} sk t − 1 contains c r s \mathsf{crs} crs , the classical data ( μ s , τ s , a s , σ s ( 0 ) , σ s ( 1 ) ) s ≤ t − 1 (\mu_s,\tau_s,a_s,\sigma_s(0),\sigma_s(1))_{s\leq t-1} ( μ s , τ s , a s , σ s ( 0 ) , σ s ( 1 ) ) s ≤ t − 1 defined below, and the signing key s i g k t \mathsf{sigk}_t sigk t ):
Run ( u t 0 , s i g k t 0 ) ← G e n ( c r s ) (u_t^0,\mathsf{sigk}_t^0) \leftarrow\mathsf{Gen}(\mathsf{crs}) ( u t 0 , sigk t 0 ) ← Gen ( crs ) , ( u t 1 , s i g k t 1 ) ← G e n ( c r s ) (u_t^1,\mathsf{sigk}_t^1) \leftarrow\mathsf{Gen}(\mathsf{crs}) ( u t 1 , sigk t 1 ) ← Gen ( crs ) , and ( w t + 1 , s i g k t + 1 ) ← G e n ( c r s ) (w_{t+1},\mathsf{sigk}_{t+1}) \leftarrow\mathsf{Gen}(\mathsf{crs}) ( w t + 1 , sigk t + 1 ) ← Gen ( crs ) . We call ( u t 0 , u t 1 ) (u_t^0,u_t^1) ( u t 0 , u t 1 ) the t t t -th leaf keys.
Set μ t : = u t 0 ∥ u t 1 ∥ w t + 1 \mu_t := u_t^0 \mathbin\Vert u_t^1 \mathbin\Vert w_{t+1} μ t := u t 0 ∥ u t 1 ∥ w t + 1 and run τ t ← S i g n ( c r s , s i g k t , μ t ) \tau_t \leftarrow\mathsf{Sign}(\mathsf{crs},\mathsf{sigk}_t,\mu_t) τ t ← Sign ( crs , sigk t , μ t ) . This consumes s i g k t \mathsf{sigk}_t sigk t .
For each α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } , run σ t ( α ) ← S i g n ( c r s , s i g k t α , α ) \sigma_t(\alpha) \leftarrow\mathsf{Sign}(\mathsf{crs},\mathsf{sigk}_t^\alpha,\alpha) σ t ( α ) ← Sign ( crs , sigk t α , α ) . This consumes s i g k t 0 \mathsf{sigk}_t^0 sigk t 0 and s i g k t 1 \mathsf{sigk}_t^1 sigk t 1 .
Sample a t ← { 0 , 1 } a_t \leftarrow\{0,1\} a t ← { 0 , 1 } and prepare the state
1 2 ( ∣ 0 ⟩ A ∣ σ t ( 0 ) ⟩ B + ( − 1 ) a t ∣ 1 ⟩ A ∣ σ t ( 1 ) ⟩ B ) . (44) \frac{1}{\sqrt{2}}\left(|0\rangle_A|\sigma_t(0)\rangle_B+(-1)^{a_t}|1\rangle_A|\sigma_t(1)\rangle_B\right). \tag*{(44)} 2 1 ( ∣0 ⟩ A ∣ σ t ( 0 ) ⟩ B + ( − 1 ) a t ∣1 ⟩ A ∣ σ t ( 1 ) ⟩ B ) . (44) Output p k t : = ( t , ( μ s , τ s ) s ≤ t , the state of ( A , B ) ) \mathsf{pk}_t := (t,(\mu_s,\tau_s)_{s\leq t},\text{ the state of }(A,B)) pk t := ( t , ( μ s , τ s ) s ≤ t , the state of ( A , B )) and s k t \mathsf{sk}_t sk t , which is s k t − 1 \mathsf{sk}_{t-1} sk t − 1 with s i g k t \mathsf{sigk}_t sigk t removed and s i g k t + 1 \mathsf{sigk}_{t+1} sigk t + 1 and ( μ t , τ t , a t , σ t ( 0 ) , σ t ( 1 ) ) (\mu_t,\tau_t,a_t,\sigma_t(0),\sigma_t(1)) ( μ t , τ t , a t , σ t ( 0 ) , σ t ( 1 )) appended.
Enc ( v k , p k , m ) (\mathsf{vk},\mathsf{pk},m) ( vk , pk , m ) : Parse v k = ( c r s , w 1 ) \mathsf{vk}=(\mathsf{crs},w_1) vk = ( crs , w 1 ) . Measure the classical part of p k \mathsf{pk} pk in the computational basis (this does nothing for honestly generated public keys), and parse the outcome as ( t , ( μ s ′ , τ s ′ ) s ≤ t ) (t,(\mu'_s,\tau'_s)_{s\leq t}) ( t , ( μ s ′ , τ s ′ ) s ≤ t ) and each μ s ′ \mu'_s μ s ′ as u s ′ 0 ∥ u s ′ 1 ∥ w s + 1 ′ u_s^{\prime0}\mathbin\Vert u_s^{\prime1}\mathbin\Vert w'_{s+1} u s ′0 ∥ u s ′1 ∥ w s + 1 ′ . If the parsing fails or t = 0 t=0 t = 0 , output c t : = ⊥ \mathsf{ct}:=\perp ct :=⊥ .
(Chain check.) Set w 1 ′ : = w 1 w'_1:=w_1 w 1 ′ := w 1 and check ⊤ = Ver ( c r s , w s ′ , μ s ′ , τ s ′ ) \top=\operatorname{Ver}(\mathsf{crs},w'_s,\mu'_s,\tau'_s) ⊤ = Ver ( crs , w s ′ , μ s ′ , τ s ′ ) for all s ∈ { 1 , … , t } s\in\{1,\ldots,t\} s ∈ { 1 , … , t } . If any check fails, output c t : = ⊥ \mathsf{ct}:=\perp ct :=⊥ .
(Leaf check.) Set u ′ : = ( u t ′ 0 , u t ′ 1 ) u':=(u_t^{\prime0},u_t^{\prime1}) u ′ := ( u t ′0 , u t ′1 ) and measure the registers ( A , B ) (A,B) ( A , B ) of p k \mathsf{pk} pk with { Π u ′ , I − Π u ′ } \{\Pi^{u'},I-\Pi^{u'}\} { Π u ′ , I − Π u ′ } . If the outcome is I − Π u ′ I-\Pi^{u'} I − Π u ′ , output c t : = ⊥ \mathsf{ct}:=\perp ct :=⊥ .
Apply Z m Z^m Z m on A A A , measure ( A , B ) (A,B) ( A , B ) in the Hadamard basis to obtain ( c , d ) ∈ { 0 , 1 } × { 0 , 1 } ℓ (c,d)\in\{0,1\}\times\{0,1\}^{\ell} ( c , d ) ∈ { 0 , 1 } × { 0 , 1 } ℓ , and output c t : = ( t , c , d ) \mathsf{ct}:=(t,c,d) ct := ( t , c , d ) .
Dec ( s k , c t ) (\mathsf{sk},\mathsf{ct}) ( sk , ct ) : If c t = ⊥ \mathsf{ct}=\perp ct =⊥ , output a uniformly random bit. Otherwise, parse c t = ( t , c , d ) \mathsf{ct}=(t,c,d) ct = ( t , c , d ) , retrieve ( a t , σ t ( 0 ) , σ t ( 1 ) ) (a_t,\sigma_t(0),\sigma_t(1)) ( a t , σ t ( 0 ) , σ t ( 1 )) from s k \mathsf{sk} sk , and output m ′ : = c ⊕ a t ⊕ d ⋅ ( σ t ( 0 ) ⊕ σ t ( 1 ) ) m':=c\oplus a_t\oplus d\cdot(\sigma_t(0)\oplus\sigma_t(1)) m ′ := c ⊕ a t ⊕ d ⋅ ( σ t ( 0 ) ⊕ σ t ( 1 )) .
All algorithms are QPT. Ciphertexts are classical, and Dec uses only the classical part of the secret key. The quantum part of s k t \mathsf{sk}_t sk t is the single unconsumed signing key s i g k t + 1 \mathsf{sigk}_{t+1} sigk t + 1 , and hence its size does not grow with the number t t t of issued public keys; the leaf signing keys s i g k t 0 , s i g k t 1 \mathsf{sigk}_t^0,\mathsf{sigk}_t^1 sigk t 0 , sigk t 1 are consumed within the t t t -th invocation of PKGen, and all other components of s k t \mathsf{sk}_t sk t are classical.
Correctness. Consider an honest execution with the i i i -th public key. By the correctness of the one-shot signature scheme and the union bound, with probability 1 − negl ( λ ) 1-\operatorname{negl}(\lambda) 1 − negl ( λ ) , all the pairs ( μ s , τ s ) (\mu_s,\tau_s) ( μ s , τ s ) for s ≤ i s\leq i s ≤ i pass the verification under w s w_s w s , and ⊤ = Ver ( c r s , u i α , α , σ i ( α ) ) \top=\operatorname{Ver}(\mathsf{crs},u_i^\alpha,\alpha,\sigma_i(\alpha)) ⊤ = Ver ( crs , u i α , α , σ i ( α )) for both α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } . Condition on this event. Then the chain check passes, and the state Equation (44) lies in the image of Π u i \Pi^{u_i} Π u i , so that the leaf check accepts with certainty without changing the state. After Z m Z^{m} Z m is applied on A, the state is 1 2 ( ∣ 0 ⟩ A ∣ σ i ( 0 ) ⟩ B + ( − 1 ) a i ⊕ m ∣ 1 ⟩ A ∣ σ i ( 1 ) ⟩ B ) \frac{1}{\sqrt{2}}(|0\rangle_{\mathrm{A}}|\sigma_i(0)\rangle_{\mathrm{B}}+(-1)^{a_i\oplus m}|1\rangle_{\mathrm{A}}|\sigma_i(1)\rangle_{\mathrm{B}}) 2 1 ( ∣0 ⟩ A ∣ σ i ( 0 ) ⟩ B + ( − 1 ) a i ⊕ m ∣1 ⟩ A ∣ σ i ( 1 ) ⟩ B ) , and the Hadamard-basis measurement returns ( c , d ) (c,d) ( c , d ) with probability
1 2 ℓ + 2 ∣ 1 + ( − 1 ) a i ⊕ m ⊕ c ⊕ d ⋅ ( σ i ( 0 ) ⊕ σ i ( 1 ) ) ∣ 2 , (45) \frac{1}{2^{\ell+2}}\left|1+(-1)^{a_i\oplus m\oplus c\oplus d\cdot(\sigma_i(0)\oplus\sigma_i(1))}\right|^2, \tag*{(45)} 2 ℓ + 2 1 1 + ( − 1 ) a i ⊕ m ⊕ c ⊕ d ⋅ ( σ i ( 0 ) ⊕ σ i ( 1 )) 2 , (45)
which vanishes unless c ⊕ a i ⊕ d ⋅ ( σ i ( 0 ) ⊕ σ i ( 1 ) ) = m c\oplus a_i\oplus d\cdot(\sigma_i(0)\oplus\sigma_i(1))=m c ⊕ a i ⊕ d ⋅ ( σ i ( 0 ) ⊕ σ i ( 1 )) = m . Hence Dec outputs m m m . Because ( a i , σ i ( 0 ) , σ i ( 1 ) ) (a_i,\sigma_i(0),\sigma_i(1)) ( a i , σ i ( 0 ) , σ i ( 1 )) is retained in the classical part of the secret key, this holds for Dec ( s k k , ⋅ ) \operatorname{Dec}(\mathrm{sk}_k,\cdot) Dec ( sk k , ⋅ ) for any i ≤ k i\leq k i ≤ k , and the correctness follows from the union bound over the k k k ciphertexts.
Everlasting security. Let A \mathcal{A} A be an adversary as in Definition 2.12 : all operations of A \mathcal{A} A are QPT during the interaction with the challenger, and A \mathcal{A} A applies computationally-unbounded operations afterwards. Let q ′ q' q ′ be the number of public-key queries made before the challenge. Without loss of generality, A \mathcal{A} A is unitary during the QPT phase, and we write E \mathbf{E} E for the register of A \mathcal{A} A .
Removing the pads. For any state ρ \rho ρ of ( A , B ) (\mathrm{A},\mathrm{B}) ( A , B ) ,
1 2 ∑ a ∈ { 0 , 1 } ( Z A a ⊗ I B ) ρ ( Z A a ⊗ I B ) = ∑ α ∈ { 0 , 1 } ( ∣ α ⟩ ⟨ α ∣ A ⊗ I B ) ρ ( ∣ α ⟩ ⟨ α ∣ A ⊗ I B ) , (46) \frac{1}{2}\sum_{a\in\{0,1\}}(Z_{\mathrm{A}}^{a}\otimes I_{\mathrm{B}})\rho(Z_{\mathrm{A}}^{a}\otimes I_{\mathrm{B}})=\sum_{\alpha\in\{0,1\}}(|\alpha\rangle\langle\alpha|_{\mathrm{A}}\otimes I_{\mathrm{B}})\rho(|\alpha\rangle\langle\alpha|_{\mathrm{A}}\otimes I_{\mathrm{B}}), \tag*{(46)} 2 1 a ∈ { 0 , 1 } ∑ ( Z A a ⊗ I B ) ρ ( Z A a ⊗ I B ) = α ∈ { 0 , 1 } ∑ ( ∣ α ⟩ ⟨ α ∣ A ⊗ I B ) ρ ( ∣ α ⟩ ⟨ α ∣ A ⊗ I B ) , (46)
i.e., averaging over the pad is the completely dephasing channel on A. Applied to the state Equation (44) , it gives 1 2 ∑ α ∈ { 0 , 1 } ∣ α ⟩ ⟨ α ∣ A ⊗ ∣ σ t ( α ) ⟩ ⟨ σ t ( α ) ∣ B \frac{1}{2}\sum_{\alpha\in\{0,1\}}|\alpha\rangle\langle\alpha|_{\mathrm{A}}\otimes|\sigma_t(\alpha)\rangle\langle\sigma_t(\alpha)|_{\mathrm{B}} 2 1 ∑ α ∈ { 0 , 1 } ∣ α ⟩ ⟨ α ∣ A ⊗ ∣ σ t ( α )⟩ ⟨ σ t ( α ) ∣ B . The pad a t a_t a t is used nowhere else in the security game, because Dec is never executed in the security game of Definition 2.11. Therefore, the state of all registers ever given to A \mathcal{A} A is unchanged if step 4 of PKGen is replaced with the following: sample α t ← { 0 , 1 } \alpha_t\leftarrow\{0,1\} α t ← { 0 , 1 } and set the state of ( A , B ) (\mathrm{A},\mathrm{B}) ( A , B ) to ∣ α t ⟩ A ∣ σ t ( α t ) ⟩ B |\alpha_t\rangle_{\mathrm{A}}|\sigma_t(\alpha_t)\rangle_{\mathrm{B}} ∣ α t ⟩ A ∣ σ t ( α t ) ⟩ B . In this game, σ t ( 1 − α t ) \sigma_t(1-\alpha_t) σ t ( 1 − α t ) is never used. Since the signing σ t ( 1 − α t ) ← Sign ( c r s , s i g k t 1 − α t , 1 − α t ) \sigma_t(1-\alpha_t)\leftarrow\operatorname{Sign}(\mathrm{crs},\mathrm{sigk}_t^{1-\alpha_t},1-\alpha_t) σ t ( 1 − α t ) ← Sign ( crs , sigk t 1 − α t , 1 − α t ) acts only on registers held by the challenger and its output is never sent to A \mathcal{A} A , the state of all registers ever given to A \mathcal{A} A is further unchanged if the challenger omits this signing and keeps s i g k t 1 − α t \mathrm{sigk}_t^{1-\alpha_t} sigk t 1 − α t unconsumed. Hence the security game is statistically identical to the following modified security game: on the t t t -th public-key query, the challenger runs steps 1 and 2 of PKGen, samples α t ← { 0 , 1 } \alpha_t\leftarrow\{0,1\} α t ← { 0 , 1 } , runs σ t ← Sign ( c r s , s i g k t α t , α t ) \sigma_t\leftarrow\operatorname{Sign}(\mathrm{crs},\mathrm{sigk}_t^{\alpha_t},\alpha_t) σ t ← Sign ( crs , sigk t α t , α t ) , keeps s i g k t 1 − α t \mathrm{sigk}_t^{1-\alpha_t} sigk t 1 − α t unconsumed, and sends
p k t : = ( t , ( μ s , τ s ) s ≤ t , ∣ α t ⟩ A ∣ σ t ⟩ B ) . (47) \mathrm{pk}_t := (t,(\mu_s,\tau_s)_{s\leq t},|\alpha_t\rangle_{\mathrm{A}}|\sigma_t\rangle_{\mathrm{B}}). \tag*{(47)} pk t := ( t , ( μ s , τ s ) s ≤ t , ∣ α t ⟩ A ∣ σ t ⟩ B ) . (47)
We stress that this replacement is an equality of the state of the registers of A \mathcal{A} A , and is therefore valid even against the unbounded phase of A \mathcal{A} A . Hereafter we consider the modified security game.
The challenge. Let T T T denote the entire classical transcript of the modified security game up to and including the measurement of the classical part of the public key performed by Enc at the challenge, namely c r s \mathrm{crs} crs , w 1 w_1 w 1 , ( μ s , τ s , α s , σ s ) s ≤ q ′ (\mu_s,\tau_s,\alpha_s,\sigma_s)_{s\leq q'} ( μ s , τ s , α s , σ s ) s ≤ q ′ , and the outcome ( t ′ , ( μ s ′ , τ s ′ ) s ≤ t ′ ) (t',(\mu'_{s},\tau'_{s})_{s\leq t'}) ( t ′ , ( μ s ′ , τ s ′ ) s ≤ t ′ ) of the measurement. The distribution of T T T does not depend on b b b . Every input to A \mathcal{A} A before the challenge is a classical string contained in T T T , and A \mathcal{A} A is unitary. Hence, conditioned on T T T , the joint state of the registers ( A , B ) (\mathrm{A},\mathrm{B}) ( A , B ) of the submitted public key and E is a normalized pure state, which we denote by ∣ ξ ( T ) ⟩ |\xi(T)\rangle ∣ ξ ( T )⟩ , and the registers held by the challenger, namely the unconsumed signing keys, are in a state that is in tensor product with ∣ ξ ( T ) ⟩ |\xi(T)\rangle ∣ ξ ( T )⟩ and does not depend on b b b .
Let σ b ( T ) \sigma_b(T) σ b ( T ) be the state of ( A , B , E ) (\mathrm{A},\mathrm{B},\mathrm{E}) ( A , B , E ) immediately after Enc has performed the leaf check and, on acceptance, applied Z b Z^b Z b on A, conditioned on T T T and on the challenge bit being b b b ; if t ′ = 0 t'=0 t ′ = 0 or the chain check fails, we set σ b ( T ) : = ∣ ξ ( T ) ⟩ ⟨ ξ ( T ) ∣ \sigma_b(T):=|\xi(T)\rangle\langle\xi(T)| σ b ( T ) := ∣ ξ ( T )⟩ ⟨ ξ ( T ) ∣ . Everything that happens afterwards, namely the Hadamard-basis measurement of ( A , B ) (A,B) ( A , B ) , the delivery of c t \mathsf{ct} ct , the answers to further public-key queries, and the QPT operations of A \mathcal{A} A , is a quantum channel that may depend on T T T but not on b b b , applied to σ b ( T ) \sigma_b(T) σ b ( T ) and to the registers of the challenger. Let ω b \omega_b ω b be the state of the registers of A \mathcal{A} A at the end of the QPT phase conditioned on b b b . By the above, ω b = ∑ T Pr [ T ] Φ T ( σ b ( T ) ) \omega_b = \sum_T \Pr[T] \Phi_T(\sigma_b(T)) ω b = ∑ T Pr [ T ] Φ T ( σ b ( T )) for some quantum channels Φ T \Phi_T Φ T that do not depend on b b b , and hence, by the monotonicity of the trace distance,
∥ ω 1 − ω 0 ∥ 1 ≤ ∑ T Pr [ T ] ∥ σ 1 ( T ) − σ 0 ( T ) ∥ 1 . (48) \lVert\omega_1-\omega_0\rVert_1 \le\sum_T \Pr[T]\lVert\sigma_1(T)-\sigma_0(T)\rVert_1. \tag*{(48)} ∥ ω 1 − ω 0 ∥ 1 ≤ T ∑ Pr [ T ] ∥ σ 1 ( T ) − σ 0 ( T ) ∥ 1 . (48)
The unbounded phase of A \mathcal{A} A is a two-outcome POVM { D , I − D } \{D,I-D\} { D , I − D } on ω b \omega_b ω b , and therefore
Pr [ b ′ = b ] = 1 2 Tr [ ( I − D ) ω 0 ] + 1 2 Tr [ D ω 1 ] = 1 2 + 1 2 Tr [ D ( ω 1 − ω 0 ) ] ≤ 1 2 + 1 4 ∥ ω 1 − ω 0 ∥ 1 . (49) \Pr[b'=b]=\frac{1}{2}\operatorname{Tr}[(I-D)\omega_0]+\frac{1}{2}\operatorname{Tr}[D\omega_1]=\frac{1}{2}+\frac{1}{2}\operatorname{Tr}[D(\omega_1-\omega_0)]\le\frac{1}{2}+\frac{1}{4}\lVert\omega_1-\omega_0\rVert_1. \tag*{(49)} Pr [ b ′ = b ] = 2 1 Tr [( I − D ) ω 0 ] + 2 1 Tr [ D ω 1 ] = 2 1 + 2 1 Tr [ D ( ω 1 − ω 0 )] ≤ 2 1 + 4 1 ∥ ω 1 − ω 0 ∥ 1 . (49)
It thus suffices to bound the right-hand side of Equation (48) .
Fix T T T such that t ′ ≥ 1 t'\ge1 t ′ ≥ 1 and the chain check passes, and write u ′ : = ( u t ′ ′ , u t ′ + 1 ′ ) u' := (u'_{t'},u'_{t'+1}) u ′ := ( u t ′ ′ , u t ′ + 1 ′ ) . For α ∈ { 0 , 1 } \alpha\in\{0,1\} α ∈ { 0 , 1 } , define the unnormalized vector on ( B , E ) (B,E) ( B , E )
∣ φ α ( T ) ⟩ : = ( ⟨ α ∣ A ⊗ I B , E ) ( Π u ′ ⊗ I E ) ∣ ξ ( T ) ⟩ , (50) \lvert\varphi_\alpha(T)\rangle:= (\langle\alpha\rvert_A \otimes I_{B,E})(\Pi^{u'}\otimes I_E)\lvert\xi(T)\rangle, \tag*{(50)} ∣ φ α ( T )⟩ := (⟨ α ∣ A ⊗ I B , E ) ( Π u ′ ⊗ I E ) ∣ ξ ( T )⟩ , (50)
so that ( Π u ′ ⊗ I E ) ∣ ξ ( T ) ⟩ = ∑ α ∈ { 0 , 1 } ∣ α ⟩ A ⊗ ∣ φ α ( T ) ⟩ (\Pi^{u'}\otimes I_E)\lvert\xi(T)\rangle= \sum_{\alpha\in\{0,1\}}\lvert\alpha\rangle_A\otimes\lvert\varphi_\alpha(T)\rangle ( Π u ′ ⊗ I E ) ∣ ξ ( T )⟩ = ∑ α ∈ { 0 , 1 } ∣ α ⟩ A ⊗ ∣ φ α ( T )⟩ and ∥ ∣ φ α ( T ) ⟩ ∥ ≤ 1 \lVert\lvert\varphi_\alpha(T)\rangle\rVert\le1 ∥∣ φ α ( T )⟩∥ ≤ 1 . The branch on which the leaf check rejects does not depend on b b b , and the unnormalized state on the accepting branch after Z b Z^b Z b is applied is ∑ α ∈ { 0 , 1 } ( − 1 ) b α ∣ α ⟩ A ⊗ ∣ φ α ( T ) ⟩ \sum_{\alpha\in\{0,1\}}(-1)^{b\alpha}\lvert\alpha\rangle_A\otimes\lvert\varphi_\alpha(T)\rangle ∑ α ∈ { 0 , 1 } ( − 1 ) b α ∣ α ⟩ A ⊗ ∣ φ α ( T )⟩ . Hence
σ 1 ( T ) − σ 0 ( T ) = − 2 ( ∣ 0 ⟩ ⟨ 1 ∣ A ⊗ ∣ φ 0 ( T ) ⟩ ⟨ φ 1 ( T ) ∣ + ∣ 1 ⟩ ⟨ 0 ∣ A ⊗ ∣ φ 1 ( T ) ⟩ ⟨ φ 0 ( T ) ∣ ) , (51) \sigma_1(T)-\sigma_0(T)=-2\left(\lvert0\rangle\langle1\rvert_A\otimes\lvert\varphi_0(T)\rangle\langle\varphi_1(T)\rvert+\lvert1\rangle\langle0\rvert_A\otimes\lvert\varphi_1(T)\rangle\langle\varphi_0(T)\rvert\right), \tag*{(51)} σ 1 ( T ) − σ 0 ( T ) = − 2 ( ∣ 0 ⟩ ⟨ 1 ∣ A ⊗ ∣ φ 0 ( T )⟩ ⟨ φ 1 ( T )∣ + ∣ 1 ⟩ ⟨ 0 ∣ A ⊗ ∣ φ 1 ( T )⟩ ⟨ φ 0 ( T )∣ ) , (51)
and, by the triangle inequality and ∥ ∣ u ⟩ ⟨ v ∣ ∥ 1 = ∥ ∣ u ⟩ ∥ ⋅ ∥ ∣ v ⟩ ∥ \lVert\lvert u\rangle\langle v\rvert\rVert_1=\lVert\lvert u\rangle\rVert\cdot\lVert\lvert v\rangle\rVert ∥∣ u ⟩ ⟨ v ∣ ∥ 1 = ∥∣ u ⟩∥ ⋅ ∥∣ v ⟩∥ ,
∥ σ 1 ( T ) − σ 0 ( T ) ∥ 1 ≤ 4 ∥ ∣ φ 0 ( T ) ⟩ ∥ ⋅ ∥ ∣ φ 1 ( T ) ⟩ ∥ . (52) \lVert\sigma_1(T)-\sigma_0(T)\rVert_1\le4\lVert\lvert\varphi_0(T)\rangle\rVert\cdot\lVert\lvert\varphi_1(T)\rangle\rVert. \tag*{(52)} ∥ σ 1 ( T ) − σ 0 ( T ) ∥ 1 ≤ 4 ∥∣ φ 0 ( T )⟩∥ ⋅ ∥∣ φ 1 ( T )⟩∥ . (52)
We call T T T good if 1 ≤ t ′ ≤ q ′ 1\le t'\le q' 1 ≤ t ′ ≤ q ′ , the chain check passes, and μ s ′ = μ s \mu_s'=\mu_s μ s ′ = μ s for all s ≤ t ′ s\le t' s ≤ t ′ , i.e., the submitted chain is a prefix of the honest chain. For good T T T , we have u ′ = ( u t ′ ′ , u t ′ + 1 ′ ) u'=(u'_{t'},u'_{t'+1}) u ′ = ( u t ′ ′ , u t ′ + 1 ′ ) : the leaf keys of the submitted public key are the honest t ′ t' t ′ -th leaf keys. We call T T T bad if t ′ ≥ 1 t'\ge1 t ′ ≥ 1 and the chain check passes but T T T is not good, and let Bad be the event that T T T is bad. Since σ 1 ( T ) = σ 0 ( T ) \sigma_1(T)=\sigma_0(T) σ 1 ( T ) = σ 0 ( T ) unless T T T is good or bad, Equation (52) and ∥ ∣ φ α ( T ) ⟩ ∥ ≤ 1 \lVert\lvert\varphi_\alpha(T)\rangle\rVert\le1 ∥∣ φ α ( T )⟩∥ ≤ 1 give
∑ T Pr [ T ] ∥ σ 1 ( T ) − σ 0 ( T ) ∥ 1 ≤ 4 Pr [ B a d ] + 4 ∑ T : g o o d Pr [ T ] ∥ ∣ φ 1 − α t ′ ( T ) ⟩ ∥ ≤ 4 Pr [ B a d ] + 4 η , (53) \sum_T \Pr[T]\lVert\sigma_1(T)-\sigma_0(T)\rVert_1\le4\Pr[\mathrm{Bad}]+4\sum_{T:\,\mathrm{good}}\Pr[T]\lVert\lvert\varphi_{1-\alpha_{t'}}(T)\rangle\rVert\le4\Pr[\mathrm{Bad}]+4\sqrt{\eta}, \tag*{(53)} T ∑ Pr [ T ] ∥ σ 1 ( T ) − σ 0 ( T ) ∥ 1 ≤ 4 Pr [ Bad ] + 4 T : good ∑ Pr [ T ] ∥∣ φ 1 − α t ′ ( T )⟩∥ ≤ 4 Pr [ Bad ] + 4 η , (53)
where
η : = ∑ T : g o o d Pr [ T ] ∥ ∣ φ 1 − α t ′ ( T ) ⟩ ∥ 2 , (54) \eta:=\sum_{T:\,\mathrm{good}}\Pr[T]\lVert\lvert\varphi_{1-\alpha_{t'}}(T)\rangle\rVert^2, \tag*{(54)} η := T : good ∑ Pr [ T ] ∥∣ φ 1 − α t ′ ( T )⟩ ∥ 2 , (54)
and the last inequality of Equation (53) is the Cauchy–Schwarz inequality. The theorem follows from the following two claims.
Claim 5.2. Pr [ B a d ] ≤ negl ( λ ) \Pr[\mathrm{Bad}]\le\operatorname{negl}(\lambda) Pr [ Bad ] ≤ negl ( λ ) .
Pr [ B a d ] ≤ negl ( λ ) . (55) \Pr[\mathrm{Bad}]\le\operatorname{negl}(\lambda). \tag*{(55)} Pr [ Bad ] ≤ negl ( λ ) . (55)
Proof. We construct a QPT adversary B 1 B_1 B 1 against the security of the one-shot signature scheme. Recall that in the security game of Definition 2.9 there is no signing oracle, and the adversary outputs a verification key of its own choice together with valid signatures on two distinct messages under it. The verification key output by B 1 B_1 B 1 will be one of the chain keys w 1 , … , w q ′ + 1 w_1,\ldots,w_{q'+1} w 1 , … , w q ′ + 1 generated by B 1 B_1 B 1 itself in the simulation below; in particular, B 1 B_1 B 1 does not have to fix a target key in advance.
B 1 ( 1 λ , c r s ) B_1(1^\lambda,\mathsf{crs}) B 1 ( 1 λ , crs ) runs the modified security game by itself, playing the role of the challenger against A A A , which is run as a subroutine: it runs ( w 1 , s i g k 1 ) ← Gen ( c r s ) (w_1,\mathsf{sigk}_1)\gets\operatorname{Gen}(\mathsf{crs}) ( w 1 , sigk 1 ) ← Gen ( crs ) , using the given c r s \mathsf{crs} crs in place of running Setup, sends v k : = ( c r s , w 1 ) \mathsf{vk}:=(\mathsf{crs},w_1) vk := ( crs , w 1 ) to A A A , and answers each public-key query of A A A as the challenger of the modified security game does. The simulation is exact, because every operation of the challenger is an invocation of Gen, Sign, or Ver under c r s \mathsf{crs} crs , or a public operation, and involves no secret unknown to B 1 B_1 B 1 . As a by-product, when A A A submits its public key at the challenge, B 1 B_1 B 1 holds the honest chain data ( μ s , τ s ) s ≤ q ′ (\mu_s,\tau_s)_{s\le q'} ( μ s , τ s ) s ≤ q ′ and the unconsumed signing key s i g k q ′ + 1 \mathsf{sigk}_{q'+1} sigk q ′ + 1 corresponding to w q ′ + 1 w_{q'+1} w q ′ + 1 . B 1 B_1 B 1 then measures the classical part of the submitted public key, obtaining ( t ′ , ( μ s ′ , τ s ′ ) s ≤ t ′ ) (t',(\mu'_s,\tau'_s)_{s\le t'}) ( t ′ , ( μ s ′ , τ s ′ ) s ≤ t ′ ) , and halts the simulation.
Suppose that Bad occurs. Then t ′ ≥ 1 t'\ge1 t ′ ≥ 1 and, setting w 1 ′ : = w 1 w'_1:=w_1 w 1 ′ := w 1 , all the certificates verify, i.e., ⊤ = Ver ( c r s , w s ′ , μ s ′ , τ s ′ ) \top=\operatorname{Ver}(\mathsf{crs},w'_s,\mu'_s,\tau'_s) ⊤ = Ver ( crs , w s ′ , μ s ′ , τ s ′ ) for all s ≤ t ′ s\le t' s ≤ t ′ . Note that the message at each position determines the verification key of the next position, because w s + 1 w_{s+1} w s + 1 is a component of μ s \mu_s μ s and verification keys have a fixed length. Exactly one of the following two cases occurs.
Case 1: there exists s ≤ min ( t ′ , q ′ ) s\le\min(t',q') s ≤ min ( t ′ , q ′ ) with μ s ′ ≠ μ s \mu'_s\ne\mu_s μ s ′ = μ s . Let r r r be the smallest such index. Since μ s ′ = μ s \mu'_s=\mu_s μ s ′ = μ s for all s < r s<r s < r , we have w r ′ = w r w'_r=w_r w r ′ = w r (for r = 1 r=1 r = 1 this is w 1 ′ = w 1 w'_1=w_1 w 1 ′ = w 1 ). Hence ( μ r ′ , τ r ′ ) (\mu'_r,\tau'_r) ( μ r ′ , τ r ′ ) verifies under the honest key w r w_r w r , the honest pair ( μ r , τ r ) (\mu_r,\tau_r) ( μ r , τ r ) is held by B 1 B_1 B 1 because r ≤ q ′ r\le q' r ≤ q ′ , and μ r ≠ μ r ′ \mu_r\ne\mu'_r μ r = μ r ′ . B 1 B_1 B 1 outputs ( w r , μ r , τ r , μ r ′ , τ r ′ ) (w_r,\mu_r,\tau_r,\mu'_r,\tau'_r) ( w r , μ r , τ r , μ r ′ , τ r ′ ) .
Case 2: μ s ′ = μ s \mu'_s=\mu_s μ s ′ = μ s for all s ≤ min ( t ′ , q ′ ) s\le\min(t',q') s ≤ min ( t ′ , q ′ ) . Since T T T is not good, we must have t ′ > q ′ t'>q' t ′ > q ′ . In particular, the position q ′ + 1 q'+1 q ′ + 1 exists, and its verification key is the honest one, w q ′ + 1 ′ = w q ′ + 1 w'_{q'+1}=w_{q'+1} w q ′ + 1 ′ = w q ′ + 1 (for q ′ = 0 q'=0 q ′ = 0 this is w 1 ′ = w 1 w'_1=w_1 w 1 ′ = w 1 ). Hence ( μ q ′ + 1 ′ , τ q ′ + 1 ′ ) (\mu'_{q'+1},\tau'_{q'+1}) ( μ q ′ + 1 ′ , τ q ′ + 1 ′ ) is a valid message-signature pair under w q ′ + 1 w_{q'+1} w q ′ + 1 , whose signing key s i g k q ′ + 1 \mathsf{sigk}_{q'+1} sigk q ′ + 1 has never signed and is held by B 1 B_1 B 1 . B 1 B_1 B 1 picks an arbitrary μ ′ ′ ≠ μ q ′ + 1 ′ \mu''\ne\mu'_{q'+1} μ ′′ = μ q ′ + 1 ′ , runs τ ′ ′ ← Sign ( c r s , s i g k q ′ + 1 , μ ′ ′ ) \tau''\gets\operatorname{Sign}(\mathsf{crs},\mathsf{sigk}_{q'+1},\mu'') τ ′′ ← Sign ( crs , sigk q ′ + 1 , μ ′′ ) , and outputs ( w q ′ + 1 , μ q ′ + 1 ′ , τ q ′ + 1 ′ , μ ′ ′ , τ ′ ′ ) (w_{q'+1},\mu'_{q'+1},\tau'_{q'+1},\mu'',\tau'') ( w q ′ + 1 , μ q ′ + 1 ′ , τ q ′ + 1 ′ , μ ′′ , τ ′′ ) .
In both cases, conditioned on Bad, the output of B 1 B_1 B 1 consists of a verification key and signatures on two distinct messages under it, and the pair coming from the submitted chain verifies because the chain check passed. The other pair, ( μ r , τ r ) (\mu_r,\tau_r) ( μ r , τ r ) in Case 1 and ( μ ′ ′ , τ ′ ′ ) (\mu'',\tau'') ( μ ′′ , τ ′′ ) in Case 2, verifies with probability 1 − negl ( λ ) 1-\operatorname{negl}(\lambda) 1 − negl ( λ ) by the correctness of the one-shot signature scheme and the union bound over the at most q ′ + 1 q'+1 q ′ + 1 pairs involved; here we use the correctness for adversarially chosen messages, because these messages are correlated with c r s \mathsf{crs} crs and the verification key. Hence B 1 B_1 B 1 wins the security game of Definition 2.9 with probability at least Pr [ B a d ] − negl ( λ ) \Pr[\mathrm{Bad}]-\operatorname{negl}(\lambda) Pr [ Bad ] − negl ( λ ) , and the security of the one-shot signature scheme gives Pr [ B a d ] ≤ negl ( λ ) \Pr[\mathrm{Bad}]\le\operatorname{negl}(\lambda) Pr [ Bad ] ≤ negl ( λ ) . □
Claim 5.3.
η ≤ negl ( λ ) . (56) \eta\le\operatorname{negl}(\lambda). \tag*{(56)} η ≤ negl ( λ ) . (56)
Proof. We construct a QPT adversary B 2 B_2 B 2 against the security of the one-shot signature scheme. The verification key output by B 2 B_2 B 2 will be one of the leaf keys generated by B 2 B_2 B 2 itself in the simulation below.
B 2 ( 1 λ , c r s ) B_2(1^\lambda,\mathsf{crs}) B 2 ( 1 λ , crs ) runs the modified security game by itself, playing the role of the challenger against A A A , which is run as a subroutine, exactly as B 1 B_1 B 1 does. As a by-product, when A A A submits its public key at the challenge, B 2 B_2 B 2 holds, for each t ≤ q ′ t\le q' t ≤ q ′ , the bit α t \alpha_t α t and the unconsumed signing key s i g k t 1 − α t \mathsf{sigk}_t^{1-\alpha_t} sigk t 1 − α t corresponding to the leaf key u t 1 − α t u_t^{1-\alpha_t} u t 1 − α t . Here we crucially use the modified security game, in which the challenger signs only with s i g k t α t \mathsf{sigk}_t^{\alpha_t} sigk t α t . B 2 B_2 B 2 measures the classical part of the submitted public key, obtaining ( t ′ , ( μ s ′ , τ s ′ ) s ≤ t ′ ) (t',(\mu'_s,\tau'_s)_{s\le t'}) ( t ′ , ( μ s ′ , τ s ′ ) s ≤ t ′ ) , and checks whether T T T is good; this is possible because the chain check is a public computation and B 2 B_2 B 2 has generated $(\mu_s)_{s\le q'} itself. If T T T is not good, B 2 \mathcal{B}_2 B 2 aborts; this loses nothing, because η \eta η is a sum over good transcripts. Otherwise, let j : = t ′ j := t' j := t ′ , so that u ′ = ( u j 0 , u j 1 ) u' = (u_j^0,u_j^1) u ′ = ( u j 0 , u j 1 ) ; note that j j j is read off the measured chain, and no guessing is involved. Then, instead of performing the leaf check and the subsequent steps of Enc, B 2 \mathcal{B}_2 B 2 measures the registers ( A , B ) (A,B) ( A , B ) in the computational basis to obtain ( α ∗ , β ∗ ) (\alpha^*,\beta^*) ( α ∗ , β ∗ ) . If α ∗ = 1 − α j \alpha^* = 1-\alpha_j α ∗ = 1 − α j and ⊤ = Ver ( c r s , u j 1 − α j , 1 − α j , β ∗ ) \top= \operatorname{Ver}(\mathsf{crs},u_j^{1-\alpha_j},1-\alpha_j,\beta^*) ⊤ = Ver ( crs , u j 1 − α j , 1 − α j , β ∗ ) , then B 2 \mathcal{B}_2 B 2 runs τ ′ ′ ← Sign ( c r s , sigk j 1 − α j , α j ) \tau'' \leftarrow\operatorname{Sign}(\mathsf{crs},\operatorname{sigk}_j^{1-\alpha_j},\alpha_j) τ ′′ ← Sign ( crs , sigk j 1 − α j , α j ) and outputs ( u j 1 − α j , 1 − α j , β ∗ , α j , τ ′ ′ ) (u_j^{1-\alpha_j},1-\alpha_j,\beta^*,\alpha_j,\tau'') ( u j 1 − α j , 1 − α j , β ∗ , α j , τ ′′ ) ; otherwise it aborts.
We compute the probability that B 2 \mathcal{B}_2 B 2 outputs the tuple. Condition on a good T T T , which fixes j j j and u ′ = ( u j 0 , u j 1 ) u'=(u_j^0,u_j^1) u ′ = ( u j 0 , u j 1 ) . The state of ( A , B , E ) (A,B,E) ( A , B , E ) at this point is ∣ ξ ( T ) ⟩ |\xi(T)\rangle ∣ ξ ( T )⟩ , and hence, by Equations (43) and (50) , the probability that the computational-basis measurement of ( A , B ) (A,B) ( A , B ) yields α ∗ = 1 − α j \alpha^*=1-\alpha_j α ∗ = 1 − α j together with some β ∗ \beta^* β ∗ satisfying ⊤ = Ver ( c r s , u j 1 − α j , 1 − α j , β ∗ ) \top=\operatorname{Ver}(\mathsf{crs},u_j^{1-\alpha_j},1-\alpha_j,\beta^*) ⊤ = Ver ( crs , u j 1 − α j , 1 − α j , β ∗ ) is exactly ∥ ∣ φ 1 − α j ( T ) ⟩ ∥ 2 \lVert|\varphi_{1-\alpha_j}(T)\rangle\rVert^2 ∥ ∣ φ 1 − α j ( T )⟩ ∥ 2 . Averaging over the good transcripts, the probability that B 2 \mathcal{B}_2 B 2 outputs the tuple is exactly η \eta η by Equation (54) .
Finally, we verify that the output tuple wins the security game of Definition 2.9 . The two messages 1 − α j 1-\alpha_j 1 − α j and α j \alpha_j α j are distinct. The pair ( 1 − α j , β ∗ ) (1-\alpha_j,\beta^*) ( 1 − α j , β ∗ ) passes the verification, because B 2 \mathcal{B}_2 B 2 has checked it and Ver \operatorname{Ver} Ver is classical and deterministic. The pair ( α j , τ ′ ′ ) (\alpha_j,\tau'') ( α j , τ ′′ ) is generated by the honest signing algorithm with the honestly generated signing key sigk j 1 − α j \operatorname{sigk}_j^{1-\alpha_j} sigk j 1 − α j , which has never signed before, and hence passes the verification with probability 1 − negl ( λ ) 1-\operatorname{negl}(\lambda) 1 − negl ( λ ) by the correctness of the one-shot signature scheme. The verification key u j 1 − α j u_j^{1-\alpha_j} u j 1 − α j is generated by B 2 \mathcal{B}_2 B 2 itself, which is allowed because in Definition 2.9 the adversary outputs the verification key. Hence B 2 \mathcal{B}_2 B 2 , which is QPT, wins the security game of Definition 2.9 with probability at least η − negl ( λ ) \eta-\operatorname{negl}(\lambda) η − negl ( λ ) , and the security of the one-shot signature scheme gives η ≤ negl ( λ ) \eta\leq\operatorname{negl}(\lambda) η ≤ negl ( λ ) .
By Equations (48) , (49) , (53) , (55) and (56) , Pr [ b ′ = b ] ≤ 1 2 + negl ( λ ) \Pr[b'=b]\leq\frac{1}{2}+\operatorname{negl}(\lambda) Pr [ b ′ = b ] ≤ 2 1 + negl ( λ ) . The security of the one-shot signature scheme is invoked only against the QPT reductions B 1 \mathcal{B}_1 B 1 and B 2 \mathcal{B}_2 B 2 , which run entirely within the QPT phase of the game; all other steps are equalities of quantum states or bounds on the trace distance, and the unbounded phase of A \mathcal{A} A is taken into account in Equation (49) . This establishes everlasting security.
Certified Freeze
Definitions
Definition 6.1 (QPKE in the CRS model). A QPKE scheme in the common reference string (CRS) model is a tuple ( Setup , KeyGen , PKGen , Enc , Dec ) (\operatorname{Setup},\operatorname{KeyGen},\operatorname{PKGen},\operatorname{Enc},\operatorname{Dec}) ( Setup , KeyGen , PKGen , Enc , Dec ) of QPT algorithms, where Setup ( 1 λ ) → c r s \operatorname{Setup}(1^\lambda)\to\mathsf{crs} Setup ( 1 λ ) → crs outputs a classical common reference string c r s \mathsf{crs} crs , and ( KeyGen , PKGen , Enc , Dec ) (\operatorname{KeyGen},\operatorname{PKGen},\operatorname{Enc},\operatorname{Dec}) ( KeyGen , PKGen , Enc , Dec ) are as in Definition 2.11 except that they take c r s \mathsf{crs} crs as an additional input. The correctness, the security, and the everlasting security are defined in the same way as in Definitions 2.11 and 2.12 except that c r s ← Setup ( 1 λ ) \mathsf{crs}\leftarrow\operatorname{Setup}(1^\lambda) crs ← Setup ( 1 λ ) is run by a trusted party at the beginning, and c r s \mathsf{crs} crs is given to the adversary. For simplicity, we sometimes omit c r s \mathsf{crs} crs from the inputs of the algorithms.
Definition 6.2 (Certified freeze). A QPKE scheme ( Setup , KeyGen , PKGen , Enc , Dec ) (\operatorname{Setup},\operatorname{KeyGen},\operatorname{PKGen},\operatorname{Enc},\operatorname{Dec}) ( Setup , KeyGen , PKGen , Enc , Dec ) in the CRS model supports certified freeze if there exist the following three additional algorithms.
Freeze ( s k ) → ( c e r t , s k ∗ , c o u n t ) \operatorname{Freeze}(\mathsf{sk})\to(\mathsf{cert},\mathsf{sk}^*,\mathsf{count}) Freeze ( sk ) → ( cert , sk ∗ , count ) : The freezing algorithm is a QPT algorithm that takes a secret key s k \mathsf{sk} sk as input, and outputs a classical certificate c e r t \mathsf{cert} cert , a post-freeze secret key s k ∗ \mathsf{sk}^* sk ∗ , and a count c o u n t ∈ { 0 , 1 , 2 , … } \mathsf{count}\in\{0,1,2,\ldots\} count ∈ { 0 , 1 , 2 , … } for the total number of produced public keys.
FreezeVer ( v k , c e r t , c o u n t ) → ⊤ / ⊥ \operatorname{FreezeVer}(\mathsf{vk},\mathsf{cert},\mathsf{count})\to\top/\perp FreezeVer ( vk , cert , count ) → ⊤/ ⊥ : The certificate verification algorithm is a classical deterministic polynomial-time algorithm that takes the verification key v k \mathsf{vk} vk , a certificate c e r t \mathsf{cert} cert , and a count c o u n t \mathsf{count} count as input, and outputs ⊤ \top ⊤ or ⊥ \perp ⊥ .
Index ( v k , c t ) → i / ⊥ \operatorname{Index}(\mathrm{vk},\mathrm{ct}) \to i/\perp Index ( vk , ct ) → i / ⊥ : The index algorithm is a classical deterministic polynomial-time algorithm that takes in a ciphertext c t \mathrm{ct} ct as well as the verification key v k \mathrm{vk} vk and outputs either an index i ∈ { 1 , 2 , … } i \in\{1,2,\ldots\} i ∈ { 1 , 2 , … } or ⊥ \perp ⊥ .
We do not require that PKGen \operatorname{PKGen} PKGen remains executable on s k ∗ \mathrm{sk}^{*} sk ∗ ; indeed, the point of the freeze is to fix the number of public keys that can be used, as formalized by the freeze binding below.
We require the following four properties.
Index validity. For any polynomial k k k and any m ∈ { 0 , 1 } m \in\{0,1\} m ∈ { 0 , 1 } ,
Pr [ Index ( v k , c t k ( λ ) ) = k ( λ ) : c r s ← Setup ( 1 λ ) ( v k , s k 0 ) ← KeyGen ( 1 λ ) ( p k j , s k j ) ← PKGen ( s k j − 1 ) ( j ∈ [ k ( λ ) ] ) c t k ( λ ) ← Enc ( v k , p k k ( λ ) , m ) ] ≥ 1 − negl ( λ ) . (57) \Pr\left[
\begin{aligned}
\operatorname{Index}(\mathrm{vk},\mathrm{ct}_{k(\lambda)}) &= k(\lambda):\\
\mathrm{crs} &\leftarrow\operatorname{Setup}(1^\lambda)\\
(\mathrm{vk},\mathrm{sk}_0) &\leftarrow\operatorname{KeyGen}(1^\lambda)\\
(\mathrm{pk}_j,\mathrm{sk}_j) &\leftarrow\operatorname{PKGen}(\mathrm{sk}_{j-1})\quad(j\in[k(\lambda)])\\
\mathrm{ct}_{k(\lambda)} &\leftarrow\operatorname{Enc}(\mathrm{vk},\mathrm{pk}_{k(\lambda)},m)
\end{aligned}
\right]
\ge1-\operatorname{negl}(\lambda). \tag*{(57)} Pr Index ( vk , ct k ( λ ) ) crs ( vk , sk 0 ) ( pk j , sk j ) ct k ( λ ) = k ( λ ) : ← Setup ( 1 λ ) ← KeyGen ( 1 λ ) ← PKGen ( sk j − 1 ) ( j ∈ [ k ( λ )]) ← Enc ( vk , pk k ( λ ) , m ) ≥ 1 − negl ( λ ) . (57)
Freeze correctness. For any polynomial k k k ,
Pr [ FreezeVer ( v k , c e r t , c o u n t ) = ⊤ ∧ c o u n t = k ( λ ) : c r s ← Setup ( 1 λ ) ( v k , s k 0 ) ← KeyGen ( 1 λ ) ( p k j , s k j ) ← PKGen ( s k j − 1 ) ( j ∈ [ k ( λ ) ] ) ( c e r t , s k ∗ , c o u n t ) ← Freeze ( s k k ( λ ) ) ] ≥ 1 − negl ( λ ) . (58) \Pr\left[
\begin{aligned}
\operatorname{FreezeVer}(\mathrm{vk},\mathrm{cert},\mathrm{count}) &= \top\\
{}\wedge\ \mathrm{count} &= k(\lambda):\\
\mathrm{crs} &\leftarrow\operatorname{Setup}(1^\lambda)\\
(\mathrm{vk},\mathrm{sk}_0) &\leftarrow\operatorname{KeyGen}(1^\lambda)\\
(\mathrm{pk}_j,\mathrm{sk}_j) &\leftarrow\operatorname{PKGen}(\mathrm{sk}_{j-1})\quad(j\in[k(\lambda)])\\
(\mathrm{cert},\mathrm{sk}^{*},\mathrm{count}) &\leftarrow\operatorname{Freeze}(\mathrm{sk}_{k(\lambda)})
\end{aligned}
\right]
\ge1-\operatorname{negl}(\lambda). \tag*{(58)} Pr FreezeVer ( vk , cert , count ) ∧ count crs ( vk , sk 0 ) ( pk j , sk j ) ( cert , sk ∗ , count ) = ⊤ = k ( λ ) : ← Setup ( 1 λ ) ← KeyGen ( 1 λ ) ← PKGen ( sk j − 1 ) ( j ∈ [ k ( λ )]) ← Freeze ( sk k ( λ ) ) ≥ 1 − negl ( λ ) . (58)
Decryption after freezing. For any polynomial k k k and any ( m 1 , … , m k ( λ ) ) ∈ { 0 , 1 } k ( λ ) (m_1,\ldots,m_{k(\lambda)})\in\{0,1\}^{k(\lambda)} ( m 1 , … , m k ( λ ) ) ∈ { 0 , 1 } k ( λ ) ,
Pr [ ∀ i ∈ [ k ( λ ) ] m i ← Dec ( s k ∗ , c t i ) : c r s ← Setup ( 1 λ ) ( v k , s k 0 ) ← KeyGen ( 1 λ ) ( p k j , s k j ) ← PKGen ( s k j − 1 ) ( j ∈ [ k ( λ ) ] ) ( c e r t , s k ∗ , c o u n t ) ← Freeze ( s k k ( λ ) ) c t i ← Enc ( v k , p k i , m i ) ( i ∈ [ k ( λ ) ] ) ] ≥ 1 − negl ( λ ) . (59) \Pr\left[
\begin{aligned}
\forall i\in[k(\lambda)]\quad m_i &\leftarrow\operatorname{Dec}(\mathrm{sk}^{*},\mathrm{ct}_i):\\
\mathrm{crs} &\leftarrow\operatorname{Setup}(1^\lambda)\\
(\mathrm{vk},\mathrm{sk}_0) &\leftarrow\operatorname{KeyGen}(1^\lambda)\\
(\mathrm{pk}_j,\mathrm{sk}_j) &\leftarrow\operatorname{PKGen}(\mathrm{sk}_{j-1})\quad(j\in[k(\lambda)])\\
(\mathrm{cert},\mathrm{sk}^{*},\mathrm{count}) &\leftarrow\operatorname{Freeze}(\mathrm{sk}_{k(\lambda)})\\
\mathrm{ct}_i &\leftarrow\operatorname{Enc}(\mathrm{vk},\mathrm{pk}_i,m_i)\quad(i\in[k(\lambda)])
\end{aligned}
\right]
\ge1-\operatorname{negl}(\lambda). \tag*{(59)} Pr ∀ i ∈ [ k ( λ )] m i crs ( vk , sk 0 ) ( pk j , sk j ) ( cert , sk ∗ , count ) ct i ← Dec ( sk ∗ , ct i ) : ← Setup ( 1 λ ) ← KeyGen ( 1 λ ) ← PKGen ( sk j − 1 ) ( j ∈ [ k ( λ )]) ← Freeze ( sk k ( λ ) ) ← Enc ( vk , pk i , m i ) ( i ∈ [ k ( λ )]) ≥ 1 − negl ( λ ) . (59)
where the k ( λ ) k(\lambda) k ( λ ) executions of Dec \operatorname{Dec} Dec take the classical part of s k ∗ \mathrm{sk}^{*} sk ∗ as input, as in the correctness of Definition 6.1.
Index consistency. Here we allow Enc \operatorname{Enc} Enc to output a special symbol ⊥ \perp ⊥ , which means that Enc \operatorname{Enc} Enc rejects the given public key. For any c r s \mathrm{crs} crs , any v k \mathrm{vk} vk , any m ∈ { 0 , 1 } m\in\{0,1\} m ∈ { 0 , 1 } , and any quantum state ρ \rho ρ given to Enc \operatorname{Enc} Enc as the public key,
Pr [ c t ≠ ⊥ ∧ Index ( v k , c t ) = ⊥ : c t ← Enc ( v k , ρ , m ) ] = 0. (60) \Pr[\mathrm{ct}\ne\perp\ \wedge\ \operatorname{Index}(\mathrm{vk},\mathrm{ct})=\perp:\mathrm{ct}\leftarrow\operatorname{Enc}(\mathrm{vk},\rho,m)]=0. \tag*{(60)} Pr [ ct = ⊥ ∧ Index ( vk , ct ) =⊥: ct ← Enc ( vk , ρ , m )] = 0. (60)
That is, Enc \operatorname{Enc} Enc never outputs a ciphertext that is rejected by Index \operatorname{Index} Index .
Definition 6.3 (Ciphertext uniqueness). We say that a QPKE scheme in the CRS model augmented with Index \operatorname{Index} Index satisfies ciphertext uniqueness if for any QPT adversary A \mathcal{A} A , the probability that A \mathcal{A} A wins the following experiment is ≤ negl ( λ ) \le\operatorname{negl}(\lambda) ≤ negl ( λ ) .
c r s ← Setup ( 1 λ ) \mathrm{crs}\leftarrow\operatorname{Setup}(1^\lambda) crs ← Setup ( 1 λ ) .
A ( 1 λ , c r s ) \mathcal{A}(1^\lambda,\mathrm{crs}) A ( 1 λ , crs ) outputs a verification key v k \mathrm{vk} vk and two ciphertexts c t 1 \mathrm{ct}_1 ct 1 and c t 2 \mathrm{ct}_2 ct 2 .
Run ℓ i ← Index ( v k , c t i ) \ell_i\leftarrow\operatorname{Index}(\mathrm{vk},\mathrm{ct}_i) ℓ i ← Index ( vk , ct i ) for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } .
A \mathcal{A} A wins if ℓ 1 = ℓ 2 ≠ ⊥ \ell_1=\ell_2\ne\perp ℓ 1 = ℓ 2 = ⊥ and c t 1 ≠ c t 2 \mathrm{ct}_1\ne\mathrm{ct}_2 ct 1 = ct 2 .
Definition 6.4 (Freeze binding). We say that a Q P K E QPKE QP K E scheme in the C R S CRS C R S model augmented with (Freeze, FreezeVer, Index) satisfies freeze binding if for any Q P T QPT QP T adversary A \mathcal{A} A , the probability that A \mathcal{A} A wins the following experiment is ≤ negl ( λ ) \leq\operatorname{negl}(\lambda) ≤ negl ( λ ) .
c r s ← S e t u p ( 1 λ ) \mathsf{crs} \leftarrow\mathsf{Setup}(1^\lambda) crs ← Setup ( 1 λ ) .
A ( 1 λ , c r s ) \mathcal{A}(1^\lambda, \mathsf{crs}) A ( 1 λ , crs ) outputs a verification key v k \mathsf{vk} vk , a ciphertext c t \mathsf{ct} ct , a certificate c e r t \mathsf{cert} cert , and a count c o u n t \mathsf{count} count .
Run b ← F r e e z e V e r ( v k , c e r t , c o u n t ) b \leftarrow\mathsf{FreezeVer}(\mathsf{vk}, \mathsf{cert}, \mathsf{count}) b ← FreezeVer ( vk , cert , count ) and ℓ ← I n d e x ( v k , c t ) \ell\leftarrow\mathsf{Index}(\mathsf{vk}, \mathsf{ct}) ℓ ← Index ( vk , ct ) .
A \mathcal{A} A wins if b = ⊤ b = \top b = ⊤ , ℓ ≠ ⊥ \ell\neq\bot ℓ = ⊥ , and c o u n t < ℓ \mathsf{count} < \ell count < ℓ .
Ciphertext uniqueness and freeze binding together bound the number of ciphertexts accepted by Index: once a certificate with a count c o u n t \mathsf{count} count is accepted by FreezeVer under v k \mathsf{vk} vk , no Q P T QPT QP T adversary, including the receiver itself, can produce more than c o u n t \mathsf{count} count distinct ciphertexts accepted by Index under v k \mathsf{vk} vk , except with negligible probability.
Lemma 6.5. Suppose that a Q P K E QPKE QP K E scheme in the C R S CRS C R S model augmented with (Freeze, FreezeVer, Index) satisfies ciphertext uniqueness and freeze binding. Then for any Q P T QPT QP T adversary A \mathcal{A} A , the probability that A \mathcal{A} A wins the following experiment is ≤ negl ( λ ) \leq\operatorname{negl}(\lambda) ≤ negl ( λ ) .
c r s ← S e t u p ( 1 λ ) \mathsf{crs} \leftarrow\mathsf{Setup}(1^\lambda) crs ← Setup ( 1 λ ) .
A ( 1 λ , c r s ) \mathcal{A}(1^\lambda, \mathsf{crs}) A ( 1 λ , crs ) outputs a verification key v k \mathsf{vk} vk , a certificate c e r t \mathsf{cert} cert , a count c o u n t \mathsf{count} count , and ciphertexts c t 1 , … , c t N \mathsf{ct}_1,\ldots,\mathsf{ct}_N ct 1 , … , ct N .
A \mathcal{A} A wins if ⊤ = F r e e z e V e r ( v k , c e r t , c o u n t ) \top= \mathsf{FreezeVer}(\mathsf{vk}, \mathsf{cert}, \mathsf{count}) ⊤ = FreezeVer ( vk , cert , count ) , N > c o u n t N > \mathsf{count} N > count , the ciphertexts c t 1 , … , c t N \mathsf{ct}_1,\ldots,\mathsf{ct}_N ct 1 , … , ct N are distinct, and I n d e x ( v k , c t i ) ≠ ⊥ \mathsf{Index}(\mathsf{vk},\mathsf{ct}_i) \neq\bot Index ( vk , ct i ) = ⊥ for all i ∈ [ N ] i \in[N] i ∈ [ N ] .
Proof. Let ℓ i : = I n d e x ( v k , c t i ) \ell_i := \mathsf{Index}(\mathsf{vk},\mathsf{ct}_i) ℓ i := Index ( vk , ct i ) for i ∈ [ N ] i \in[N] i ∈ [ N ] . Whenever A \mathcal{A} A wins, either ℓ i > c o u n t \ell_i > \mathsf{count} ℓ i > count for some i ∈ [ N ] i \in[N] i ∈ [ N ] , or ℓ i ≤ c o u n t \ell_i \leq\mathsf{count} ℓ i ≤ count for all i ∈ [ N ] i \in[N] i ∈ [ N ] . In the latter case, the N N N indices ℓ 1 , … , ℓ N \ell_1,\ldots,\ell_N ℓ 1 , … , ℓ N take values in { 1 , … , c o u n t } \{1,\ldots,\mathsf{count}\} { 1 , … , count } , and hence ℓ i = ℓ j \ell_i = \ell_j ℓ i = ℓ j for some i ≠ j i \neq j i = j by the pigeonhole principle, because N > c o u n t N > \mathsf{count} N > count . Let B 1 \mathcal{B}_1 B 1 be the Q P T QPT QP T adversary that runs A \mathcal{A} A , computes ℓ 1 , … , ℓ N \ell_1,\ldots,\ell_N ℓ 1 , … , ℓ N , and outputs ( v k , c t i , c e r t , c o u n t ) (\mathsf{vk},\mathsf{ct}_i,\mathsf{cert},\mathsf{count}) ( vk , ct i , cert , count ) for an i i i with ℓ i > c o u n t \ell_i > \mathsf{count} ℓ i > count if such i i i exists. Let B 2 \mathcal{B}_2 B 2 be the Q P T QPT QP T adversary that runs A \mathcal{A} A , computes ℓ 1 , … , ℓ N \ell_1,\ldots,\ell_N ℓ 1 , … , ℓ N , and outputs ( v k , c t i , c t j ) (\mathsf{vk},\mathsf{ct}_i,\mathsf{ct}_j) ( vk , ct i , ct j ) for a pair i ≠ j i \neq j i = j with ℓ i = ℓ j ≠ ⊥ \ell_i = \ell_j \neq\bot ℓ i = ℓ j = ⊥ if such a pair exists. B 1 \mathcal{B}_1 B 1 and B 2 \mathcal{B}_2 B 2 are Q P T QPT QP T , because N N N is bounded by a polynomial in λ \lambda λ as A \mathcal{A} A is Q P T QPT QP T . The probability that A \mathcal{A} A wins is at most the sum of the probability that B 1 \mathcal{B}_1 B 1 wins the experiment of Definition 6.4 and the probability that B 2 \mathcal{B}_2 B 2 wins the experiment of Definition 6.3, both of which are negligible.
Lemma 6.5 is stated for ciphertexts accepted by Index. Combined with the index consistency, it also bounds the ciphertexts generated by honest senders who are given public keys by a malicious receiver.
Corollary 6.6. Suppose that a Q P K E QPKE QP K E scheme in the C R S CRS C R S model augmented with (Freeze, FreezeVer, Index) satisfies index consistency, ciphertext uniqueness, and freeze binding. Then for any Q P T QPT QP T adversary A \mathcal{A} A , the probability that A \mathcal{A} A wins the following experiment is ≤ negl ( λ ) \leq\operatorname{negl}(\lambda) ≤ negl ( λ ) .
c r s ← S e t u p ( 1 λ ) \mathsf{crs} \leftarrow\mathsf{Setup}(1^\lambda) crs ← Setup ( 1 λ ) .
A ( 1 λ , c r s ) \mathcal{A}(1^\lambda, \mathsf{crs}) A ( 1 λ , crs ) outputs a verification key v k \mathsf{vk} vk .
A \mathcal{A} A can make encryption queries: A \mathcal{A} A sends a quantum state ρ \rho ρ and a message m ∈ { 0 , 1 } m \in\{0,1\} m ∈ { 0 , 1 } , and the challenger returns c t ← E n c ( v k , ρ , m ) \mathsf{ct} \leftarrow\mathsf{Enc}(\mathsf{vk},\rho,m) ct ← Enc ( vk , ρ , m ) . The queries model honest senders who are given public keys by A \mathcal{A} A .
A \mathcal{A} A outputs a certificate c e r t \mathsf{cert} cert and a count c o u n t \mathsf{count} count .
A \mathcal{A} A wins if ⊤ = F r e e z e V e r ( v k , c e r t , c o u n t ) \top= \mathsf{FreezeVer}(\mathsf{vk},\mathsf{cert},\mathsf{count}) ⊤ = FreezeVer ( vk , cert , count ) and the number of distinct ciphertexts other than ⊥ \perp ⊥ returned by the challenger is larger than c o u n t \mathsf{count} count .
Proof. Let A ′ \mathcal{A}' A ′ be the QPT adversary that runs A \mathcal{A} A , answers the encryption queries by running E n c \mathsf{Enc} Enc by itself, and outputs v k \mathsf{vk} vk , c e r t \mathsf{cert} cert , c o u n t \mathsf{count} count , and the distinct ciphertexts other than ⊥ \perp ⊥ returned to A \mathcal{A} A . By the index consistency, all these ciphertexts are accepted by I n d e x \mathsf{Index} Index . Hence A ′ \mathcal{A}' A ′ wins the experiment of Lemma 6.5 whenever A \mathcal{A} A wins, and the claim follows from Lemma 6.5 . □ \square □
Remark 6.7. The freeze does not prevent the receiver from handing out public keys after the freeze. For example, in the construction of § 6.2 , a malicious receiver can sign the chain messages and the stop message first, publish the certificate with a count c o u n t \mathsf{count} count , and only then generate the public keys of the original scheme and combine them with the unused signing keys s i g k 1 , … , s i g k c o u n t \mathsf{sigk}_{1},\ldots,\mathsf{sigk}_{\mathsf{count}} sigk 1 , … , sigk count to form p k 1 ′ , … , p k c o u n t ′ \mathsf{pk}'_{1},\ldots,\mathsf{pk}'_{\mathsf{count}} pk 1 ′ , … , pk count ′ of Equation (62) . What the freeze fixes is the number c o u n t \mathsf{count} count of positions, and hence the number of distinct ciphertexts accepted by I n d e x \mathsf{Index} Index (Lemma 6.5 and Corollary 6.6 ). Note also that the bound is on the number of distinct ciphertexts, and not on the number of executions of E n c \mathsf{Enc} Enc , the number of quantum states handed out as public keys, or the number of times the same ciphertext is reused.
Construction
We use the following security of one-shot signatures, which is stronger than that of Definition 2.9 .
Definition 6.8 (Strong security of one-shot signatures). A one-shot signature scheme ( S e t u p , G e n , S i g n , V e r ) (\mathsf{Setup},\mathsf{Gen},\mathsf{Sign},\mathsf{Ver}) ( Setup , Gen , Sign , Ver ) satisfies strong security if for any QPT adversary A \mathcal{A} A ,
Pr [ ⊤ ← V e r ( c r s , v k , m 0 , σ 0 ) ∧ ⊤ ← V e r ( c r s , v k , m 1 , σ 1 ) ∧ ( m 0 , σ 0 ) ≠ ( m 1 , σ 1 ) : c r s ← S e t u p ( 1 λ ) ( v k , m 0 , σ 0 , m 1 , σ 1 ) ← A ( 1 λ , c r s ) ] ≤ negl ( λ ) . (61) \Pr\left[
\begin{gathered}
\top\leftarrow\mathsf{Ver}(\mathsf{crs},\mathsf{vk},m_{0},\sigma_{0})\\
\land\ \top\leftarrow\mathsf{Ver}(\mathsf{crs},\mathsf{vk},m_{1},\sigma_{1})\\
\land\ (m_{0},\sigma_{0}) \ne(m_{1},\sigma_{1})
\end{gathered}
:
\begin{gathered}
\mathsf{crs} \leftarrow\mathsf{Setup}(1^\lambda)\\
(\mathsf{vk},m_{0},\sigma_{0},m_{1},\sigma_{1}) \leftarrow\mathcal{A}(1^\lambda,\mathsf{crs})
\end{gathered}
\right] \le\operatorname{negl}(\lambda). \tag*{(61)} Pr ⊤ ← Ver ( crs , vk , m 0 , σ 0 ) ∧ ⊤ ← Ver ( crs , vk , m 1 , σ 1 ) ∧ ( m 0 , σ 0 ) = ( m 1 , σ 1 ) : crs ← Setup ( 1 λ ) ( vk , m 0 , σ 0 , m 1 , σ 1 ) ← A ( 1 λ , crs ) ≤ negl ( λ ) . (61)
As noted in Remark 2.10 , the known constructions of one-shot signatures [37 , 16 ] satisfy strong security.
Theorem 6.9. If one-shot signatures with strong security and QPKE with quantum public keys exist, then there exists a QPKE scheme with quantum public keys in the CRS model that supports certified freeze (Definition 6.2) and satisfies ciphertext uniqueness (Definition 6.3) and freeze binding (Definition 6.4 ). Moreover, if the original QPKE scheme satisfies everlasting security, then so does the constructed one.
Because strong security implies the security of Definition 2.9 , we obtain the following corollary from Theorems 5.1 and 6.9 .
Corollary 6.10. If one-shot signatures with strong security exist, then there exists an everlasting-secure QPKE scheme with quantum public keys in the CRS model that supports certified freeze and satisfies ciphertext uniqueness and freeze binding.
Proof of Theorem 6.9 . Let ( K e y G e n , P K G e n , E n c , D e c ) (\mathsf{KeyGen},\mathsf{PKGen},\mathsf{Enc},\mathsf{Dec}) ( KeyGen , PKGen , Enc , Dec ) be a QPKE scheme with quantum public keys, and let ( S e t u p , G e n , S i g n , V e r ) (\mathsf{Setup},\mathsf{Gen},\mathsf{Sign},\mathsf{Ver}) ( Setup , Gen , Sign , Ver ) be a one-shot signature scheme with strong security.
We construct a QPKE scheme ( S e t u p ′ , K e y G e n ′ , P K G e n ′ , E n c ′ , D e c ′ ) (\mathsf{Setup}',\mathsf{KeyGen}',\mathsf{PKGen}',\mathsf{Enc}',\mathsf{Dec}') ( Setup ′ , KeyGen ′ , PKGen ′ , Enc ′ , Dec ′ ) in the CRS model with ( F r e e z e , F r e e z e V e r , I n d e x ) (\mathsf{Freeze},\mathsf{FreezeVer},\mathsf{Index}) ( Freeze , FreezeVer , Index ) as follows.
:::
KeyGen′ ( 1 λ ) ^{\prime}(1^{\lambda}) ′ ( 1 λ ) : Run ( v k , s k 0 ) ← KeyGen ( 1 λ ) (\mathsf{vk},\mathsf{sk}_0) \leftarrow\operatorname{KeyGen}(1^{\lambda}) ( vk , sk 0 ) ← KeyGen ( 1 λ ) and ( w 1 , s i g k 1 ) ← Gen ( c r s ) (w_1,\mathsf{sigk}_1) \leftarrow\operatorname{Gen}(\mathsf{crs}) ( w 1 , sigk 1 ) ← Gen ( crs ) . Output v k ′ : = ( v k , w 1 ) \mathsf{vk}^{\prime} := (\mathsf{vk},w_1) vk ′ := ( vk , w 1 ) and s k 0 ′ : = ( s k 0 , ( ) , s i g k 1 ) \mathsf{sk}^{\prime}_0 := (\mathsf{sk}_0,(),\mathsf{sigk}_1) sk 0 ′ := ( sk 0 , ( ) , sigk 1 ) , where ( ) () ( ) is the empty list of pairs.
PKGen′ ( s k t − 1 ′ ) ^{\prime}(\mathsf{sk}^{\prime}_{t-1}) ′ ( sk t − 1 ′ ) (the t t t -th invocation): Parse s k t − 1 ′ = ( s k t − 1 , ( μ s , τ s ) s ≤ t − 1 , s i g k t ) \mathsf{sk}^{\prime}_{t-1} = (\mathsf{sk}_{t-1},(\mu_s,\tau_s)_{s\leq t-1},\mathsf{sigk}_t) sk t − 1 ′ = ( sk t − 1 , ( μ s , τ s ) s ≤ t − 1 , sigk t ) .
Run ( p k t , s k t ) ← PKGen ( s k t − 1 ) (\mathsf{pk}_t,\mathsf{sk}_t) \leftarrow\operatorname{PKGen}(\mathsf{sk}_{t-1}) ( pk t , sk t ) ← PKGen ( sk t − 1 ) .
Run ( v t , s i g k ~ t ) ← Gen ( c r s ) (v_t,\widetilde{\mathsf{sigk}}_t) \leftarrow\operatorname{Gen}(\mathsf{crs}) ( v t , sigk t ) ← Gen ( crs ) and ( w t + 1 , s i g k t + 1 ) ← Gen ( c r s ) (w_{t+1},\mathsf{sigk}_{t+1}) \leftarrow\operatorname{Gen}(\mathsf{crs}) ( w t + 1 , sigk t + 1 ) ← Gen ( crs ) .
Set μ t : = ( t , v t , w t + 1 ) \mu_t := (t,v_t,w_{t+1}) μ t := ( t , v t , w t + 1 ) and run τ t ← Sign ( c r s , s i g k t , μ t ) \tau_t \leftarrow\operatorname{Sign}(\mathsf{crs},\mathsf{sigk}_t,\mu_t) τ t ← Sign ( crs , sigk t , μ t ) . This consumes s i g k t \mathsf{sigk}_t sigk t . Here and below, a tuple is regarded as a bit string from which all its components are uniquely recovered (for example, the concatenation of the components together with their lengths). In particular, two tuples are equal as bit strings if and only if all their components are equal.
Output
p k t ′ : = ( p k t , s i g k ~ t , t , ( μ s , τ s ) s ≤ t ) (62) \mathsf{pk}^{\prime}_t := (\mathsf{pk}_t,\widetilde{\mathsf{sigk}}_t,t,(\mu_s,\tau_s)_{s\leq t}) \tag*{(62)} pk t ′ := ( pk t , sigk t , t , ( μ s , τ s ) s ≤ t ) (62)
and s k t ′ : = ( s k t , ( μ s , τ s ) s ≤ t , s i g k t + 1 ) \mathsf{sk}^{\prime}_t := (\mathsf{sk}_t,(\mu_s,\tau_s)_{s\leq t},\mathsf{sigk}_{t+1}) sk t ′ := ( sk t , ( μ s , τ s ) s ≤ t , sigk t + 1 ) . We write Q \mathbf{Q} Q and S \mathbf{S} S for the registers of p k t ′ \mathsf{pk}^{\prime}_t pk t ′ that contain p k t \mathsf{pk}_t pk t and s i g k t \mathsf{sigk}_t sigk t , respectively.
Enc′ ( v k ′ , p k ′ , m ) ^{\prime}(\mathsf{vk}^{\prime},\mathsf{pk}^{\prime},m) ′ ( vk ′ , pk ′ , m ) : Parse v k ′ = ( v k , w 1 ) \mathsf{vk}^{\prime} = (\mathsf{vk},w_1) vk ′ = ( vk , w 1 ) .
Measure all the registers of p k ′ \mathsf{pk}^{\prime} pk ′ except for Q \mathbf{Q} Q and S \mathbf{S} S in the computational basis to obtain a bit string x x x . (For the honestly generated p k t ′ \mathsf{pk}^{\prime}_t pk t ′ , x = ( t , ( μ s , τ s ) s ≤ t ) x=(t,(\mu_s,\tau_s)_{s\leq t}) x = ( t , ( μ s , τ s ) s ≤ t ) .)
Run c t ← Enc ( v k , Q , m ) \mathsf{ct} \leftarrow\operatorname{Enc}(\mathsf{vk},\mathbf{Q},m) ct ← Enc ( vk , Q , m ) , where the state of the register Q \mathbf{Q} Q is used as the public key.
Run π ← Sign ( c r s , S , c t ) \pi\leftarrow\operatorname{Sign}(\mathsf{crs},\mathbf{S},\mathsf{ct}) π ← Sign ( crs , S , ct ) , where the state of the register S \mathbf{S} S is used as the signing key.
Set
c t ′ : = ( x , c t , π ) . (63) \mathsf{ct}^{\prime} := (x,\mathsf{ct},\pi). \tag*{(63)} ct ′ := ( x , ct , π ) . (63)
If Index ( v k ′ , c t ′ ) = ⊥ \operatorname{Index}(\mathsf{vk}^{\prime},\mathsf{ct}^{\prime}) = \perp Index ( vk ′ , ct ′ ) =⊥ , where Index \operatorname{Index} Index is defined below, output ⊥ \perp ⊥ . Otherwise, output c t ′ \mathsf{ct}^{\prime} ct ′ .
Dec′ ( s k t ′ , c t ′ ) ^{\prime}(\mathsf{sk}^{\prime}_t,\mathsf{ct}^{\prime}) ′ ( sk t ′ , ct ′ ) : Parse s k t ′ = ( s k t , ( μ s , τ s ) s ≤ t , s i g k t + 1 ) \mathsf{sk}^{\prime}_t = (\mathsf{sk}_t,(\mu_s,\tau_s)_{s\leq t},\mathsf{sigk}_{t+1}) sk t ′ = ( sk t , ( μ s , τ s ) s ≤ t , sigk t + 1 ) and c t ′ = ( x , c t , π ) \mathsf{ct}^{\prime}=(x,\mathsf{ct},\pi) ct ′ = ( x , ct , π ) . Run m ′ ← Dec ( s k t , c t ) m^{\prime} \leftarrow\operatorname{Dec}(\mathsf{sk}_t,\mathsf{ct}) m ′ ← Dec ( sk t , ct ) and output m ′ m^{\prime} m ′ . If the parsing of c t ′ \mathsf{ct}^{\prime} ct ′ fails, output 0 0 0 . The post-freeze secret key s k ∗ = ( s k t , ( μ s , τ s ) s ≤ t ) \mathsf{sk}^{*}=(\mathsf{sk}_t,(\mu_s,\tau_s)_{s\leq t}) sk ∗ = ( sk t , ( μ s , τ s ) s ≤ t ) is used in the same way.
Freeze( s k t ′ ) (\mathsf{sk}^{\prime}_t) ( sk t ′ ) : Parse s k t ′ = ( s k t , ( μ s , τ s ) s ≤ t , s i g k t + 1 ) \mathsf{sk}^{\prime}_t = (\mathsf{sk}_t,(\mu_s,\tau_s)_{s\leq t},\mathsf{sigk}_{t+1}) sk t ′ = ( sk t , ( μ s , τ s ) s ≤ t , sigk t + 1 ) . Run τ ∗ ← Sign ( c r s , s i g k t + 1 , ⊥ ) \tau^{*} \leftarrow\operatorname{Sign}(\mathsf{crs},\mathsf{sigk}_{t+1},\perp) τ ∗ ← Sign ( crs , sigk t + 1 , ⊥ ) , where ⊥ \perp ⊥ is a fixed bit string that is not the encoding of any tuple. This consumes s i g k t + 1 \mathsf{sigk}_{t+1} sigk t + 1 . Output c e r t : = ( ( μ s , τ s ) s ≤ t , τ ∗ ) \mathsf{cert} := ((\mu_s,\tau_s)_{s\leq t},\tau^{*}) cert := (( μ s , τ s ) s ≤ t , τ ∗ ) , c o u n t : = t \mathsf{count}:=t count := t , and the post-freeze secret key s k ∗ : = ( s k t , ( μ s , τ s ) s ≤ t ) \mathsf{sk}^{*}:=(\mathsf{sk}_t,(\mu_s,\tau_s)_{s\leq t}) sk ∗ := ( sk t , ( μ s , τ s ) s ≤ t ) .
FreezeVer( v k ′ , c e r t , c o u n t ) (\mathsf{vk}^{\prime},\mathsf{cert},\mathsf{count}) ( vk ′ , cert , count ) : Parse v k ′ = ( v k , w 1 ) \mathsf{vk}^{\prime}=(\mathsf{vk},w_1) vk ′ = ( vk , w 1 ) and c e r t = ( ( μ s , τ s ) s ≤ c o u n t , τ ∗ ) \mathsf{cert}=((\mu_s,\tau_s)_{s\leq\mathsf{count}},\tau^{*}) cert = (( μ s , τ s ) s ≤ count , τ ∗ ) , and parse each μ s \mu_s μ s as ( s , v s , w s + 1 ) (s,v_s,w_{s+1}) ( s , v s , w s + 1 ) , i.e., the first component of μ s \mu_s μ s has to be s s s . If the parsing fails, output ⊥ \perp ⊥ . Check ⊤ = Ver ( c r s , w s , μ s , τ s ) \top= \operatorname{Ver}(\mathsf{crs},w_s,\mu_s,\tau_s) ⊤ = Ver ( crs , w s , μ s , τ s ) for all s ∈ { 1 , … , c o u n t } s\in\{1,\ldots,\mathsf{count}\} s ∈ { 1 , … , count } and ⊤ = Ver ( c r s , w c o u n t + 1 , ⊥ , τ ∗ ) \top= \operatorname{Ver}(\mathsf{crs},w_{\mathsf{count}+1},\perp,\tau^{*}) ⊤ = Ver ( crs , w count + 1 , ⊥ , τ ∗ ) . Output ⊤ \top ⊤ if and only if all the checks pass.
Index(v k ′ vk' v k ′ , c t ′ ct' c t ′ ): Parse v k ′ = ( v k , w 1 ) vk' = (vk, w_1) v k ′ = ( v k , w 1 ) , c t ′ = ( x , c t , π ) ct' = (x, ct, \pi) c t ′ = ( x , c t , π ) , and x = ( t , ( μ s , τ s ) s ≤ t ) x = (t, (\mu_s, \tau_s)_{s \le t}) x = ( t , ( μ s , τ s ) s ≤ t ) with t ≥ 1 t \ge1 t ≥ 1 , and parse each μ s \mu_s μ s as ( s , v s , w s + 1 ) (s, v_s, w_{s+1}) ( s , v s , w s + 1 ) , i.e., the first component of μ s \mu_s μ s has to be s s s . If the parsing fails, output ⊥ \perp ⊥ . Check ⊤ = Ver ( c r s , w s , μ s , τ s ) \top= \operatorname{Ver}(crs, w_s, \mu_s, \tau_s) ⊤ = Ver ( cr s , w s , μ s , τ s ) for all s ∈ { 1 , … , t } s \in\{1, \ldots, t\} s ∈ { 1 , … , t } and ⊤ = Ver ( c r s , v t , c t , π ) \top= \operatorname{Ver}(crs, v_t, ct, \pi) ⊤ = Ver ( cr s , v t , c t , π ) . Output t t t if all the checks pass, and output ⊥ \perp ⊥ otherwise.
All algorithms are QPT, and FreezeVer and Index are classical and deterministic, because so is Ver. The classical part of s k t ′ sk'_t s k t ′ contains that of s k t sk_t s k t , and hence Dec' acts only on the classical part of the secret key.
Correctness. Consider the experiment of the correctness, and write k k k for k ( λ ) k(\lambda) k ( λ ) . For each i ∈ [ k ] i \in[k] i ∈ [ k ] , Enc'(v k ′ vk' v k ′ , p k i ′ pk'_i p k i ′ , m i m_i m i ) computes ( x i , c t i , π i ) (x_i, ct_i, \pi_i) ( x i , c t i , π i ) with x i = ( i , ( μ s , τ s ) s ≤ i ) x_i = (i, (\mu_s, \tau_s)_{s \le i}) x i = ( i , ( μ s , τ s ) s ≤ i ) and c t i ← ct_i \leftarrow c t i ← Enc(v k vk v k , p k i pk_i p k i , m i m_i m i ), and outputs it unless Index rejects it. We first bound the probability that Index rejects ( x i , c t i , π i ) (x_i, ct_i, \pi_i) ( x i , c t i , π i ) . Since μ s = ( s , v s , w s + 1 ) \mu_s = (s, v_s, w_{s+1}) μ s = ( s , v s , w s + 1 ) , the parsing in Index succeeds, and the checks of Index are the verifications of the i + 1 i+1 i + 1 pairs ( μ s , τ s ) s ≤ i (\mu_s, \tau_s)_{s \le i} ( μ s , τ s ) s ≤ i and ( c t i , π i ) (ct_i, \pi_i) ( c t i , π i ) , each of which is generated by the honest signing algorithm with an honestly generated signing key that has never signed before. By the correctness of the one-shot signature scheme and the union bound, all the checks pass with probability 1 − negl ( λ ) 1 - \operatorname{negl}(\lambda) 1 − negl ( λ ) , in which case Enc' outputs ( x i , c t i , π i ) (x_i, ct_i, \pi_i) ( x i , c t i , π i ) and Index(v k ′ vk' v k ′ , ( x i , c t i , π i ) (x_i, ct_i, \pi_i) ( x i , c t i , π i ) ) = i = i = i . Here we use the correctness for adversarially chosen messages, because the messages μ s \mu_s μ s are correlated with crs. Hence, by the union bound over i ∈ [ k ] i \in[k] i ∈ [ k ] , Enc' outputs ⊥ \perp ⊥ for some i ∈ [ k ] i \in[k] i ∈ [ k ] with probability at most k ⋅ negl ( λ ) = negl ( λ ) k \cdot\operatorname{negl}(\lambda) = \operatorname{negl}(\lambda) k ⋅ negl ( λ ) = negl ( λ ) . If Enc' outputs ( x i , c t i , π i ) (x_i, ct_i, \pi_i) ( x i , c t i , π i ) , then Dec'(s k ′ sk' s k ′ , ( x i , c t i , π i ) (x_i, ct_i, \pi_i) ( x i , c t i , π i ) ) outputs the output of Dec(s k k , c t i sk_k, ct_i s k k , c t i ). Hence, if m i ← m_i \leftarrow m i ← Dec'(s k ′ sk' s k ′ , c t ′ ct' c t ′ ) fails for some i ∈ [ k ] i \in[k] i ∈ [ k ] , then Enc' outputs ⊥ \perp ⊥ for some i ∈ [ k ] i \in[k] i ∈ [ k ] , or m i ← m_i \leftarrow m i ← Dec(s k k , c t i sk_k, ct_i s k k , c t i ) fails for some i ∈ [ k ] i \in[k] i ∈ [ k ] . The former occurs with probability at most negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) as shown above, and the latter occurs with probability at most negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) by the correctness of the original scheme, because ( v k , ( p k j , s k j ) j ≤ k ) (vk, (pk_j, sk_j)_{j \le k}) ( v k , ( p k j , s k j ) j ≤ k ) and ( c t i ) i ≤ k (ct_i)_{i \le k} ( c t i ) i ≤ k are distributed as in the original scheme. Hence the correctness follows.
Security. Let A ′ A' A ′ be an adversary against the constructed scheme. We construct an adversary A A A against the original scheme as follows.
On receiving v k vk v k from the challenger, A A A runs c r s ← Setup ′ ( 1 λ ) crs \leftarrow\operatorname{Setup}'(1^\lambda) cr s ← Setup ′ ( 1 λ ) and ( w 1 , sig k 1 ) ← Gen ( c r s ) (w_1, \operatorname{sig}k_1) \leftarrow\operatorname{Gen}(crs) ( w 1 , sig k 1 ) ← Gen ( cr s ) , and sends c r s crs cr s and v k ′ : = ( v k , w 1 ) vk' := (vk, w_1) v k ′ := ( v k , w 1 ) to A ′ A' A ′ .
When A ′ A' A ′ makes the t t t -th public-key query, A A A makes a public-key query to obtain p k t pk_t p k t , runs the steps 2 and 3 of PKGen' by itself, and sends p k t ′ pk'_t p k t ′ of Equation (62) to A ′ A' A ′ .
When A ′ A' A ′ sends the register P that is used as the public key for the challenge ciphertext (step 3 of the security game of Definition 2.11), A A A sends its subregister Q to the challenger, and receives c t ct c t , where the subregisters Q and S of P are determined by the fixed layout of the public keys of the constructed scheme, as in Enc'. A A A measures all the subregisters of P except for Q and S in the computational basis to obtain x x x , runs π ← Sign ( c r s , S , c t ) \pi\leftarrow\operatorname{Sign}(crs, S, ct) π ← Sign ( cr s , S , c t ) , and sets c t ′ : = ( x , c t , π ) ct' := (x, ct, \pi) c t ′ := ( x , c t , π ) . A A A sends ⊥ \perp ⊥ to A ′ A' A ′ if Index(v k ′ vk' v k ′ , c t ′ ct' c t ′ ) = ⊥ = \perp =⊥ , and sends c t ′ ct' c t ′ to A ′ A' A ′ otherwise.
A A A outputs the output b ′ b' b ′ of A ′ A' A ′ .
The measurement that yields x x x and the execution of Enc on Q by the challenger act on different registers, and A A A computes Index on the classical data it holds. Hence A A A perfectly simulates the security game of the constructed scheme for A ′ A' A ′ with the same challenge bit b b b . Therefore the probability of b ′ = b b' = b b ′ = b is the same in the two games. If A ′ A' A ′ is QPT, so is A A A , and the security of the constructed scheme follows from that of the original scheme. If A ′ A' A ′ is an adversary of the form of Definition 2.12 , so is A A A , because all the operations added by A A A are QPT and are applied during the interaction with the challenger. Hence the everlasting security of the constructed scheme follows from that of the original scheme.
Certified freeze. We first show the index validity. The experiment of the index validity is the same as that of the correctness except that only the k ( λ ) k(\lambda) k ( λ ) -th public key is used for encryption, and the argument in the proof of the correctness for i = k ( λ ) i = k(\lambda) i = k ( λ ) applies verbatim: Enc ′ \operatorname{Enc}^{\prime} Enc ′ outputs ct k ( λ ) ′ \operatorname{ct}^{\prime}_{k(\lambda)} ct k ( λ ) ′ and Index ( vk ′ , ct k ( λ ) ′ ) = k ( λ ) \operatorname{Index}(\operatorname{vk}^{\prime},\operatorname{ct}^{\prime}_{k(\lambda)}) = k(\lambda) Index ( vk ′ , ct k ( λ ) ′ ) = k ( λ ) with probability 1 − negl ( λ ) 1 - \operatorname{negl}(\lambda) 1 − negl ( λ ) .
Next we show the freeze correctness. In the experiment of the freeze correctness, count = k ( λ ) \operatorname{count} = k(\lambda) count = k ( λ ) by construction, the parsing in FreezeVer \operatorname{FreezeVer} FreezeVer succeeds, and the checks of FreezeVer \operatorname{FreezeVer} FreezeVer are the verifications of the k ( λ ) + 1 k(\lambda) + 1 k ( λ ) + 1 pairs ( μ s , τ s ) s ≤ k ( λ ) (\mu_s,\tau_s)_{s\leq k(\lambda)} ( μ s , τ s ) s ≤ k ( λ ) and ( ⊥ , τ ∗ ) (\perp,\tau^*) ( ⊥ , τ ∗ ) , each of which is generated by the honest signing algorithm with an honestly generated signing key that has never signed before. By the correctness of the one-shot signature scheme and the union bound, all the checks pass with probability 1 − negl ( λ ) 1 - \operatorname{negl}(\lambda) 1 − negl ( λ ) .
Next we show the decryption after freezing. Freeze acts only on sig k ( λ ) + 1 \operatorname{sig}_{k(\lambda)+1} sig k ( λ ) + 1 , which is contained in neither pk i ′ \operatorname{pk}^{\prime}_i pk i ′ for i ∈ [ k ( λ ) ] i \in[k(\lambda)] i ∈ [ k ( λ )] nor sk k ( λ ) \operatorname{sk}_{k(\lambda)} sk k ( λ ) , and hence the joint distribution of ( pk i ′ ) i ≤ k ( λ ) (\operatorname{pk}^{\prime}_i)_{i\leq k(\lambda)} ( pk i ′ ) i ≤ k ( λ ) and sk k ( λ ) \operatorname{sk}_{k(\lambda)} sk k ( λ ) is the same as in the experiment of the correctness. Moreover, sk ∗ \operatorname{sk}^* sk ∗ contains sk k ( λ ) \operatorname{sk}_{k(\lambda)} sk k ( λ ) , and Dec ′ \operatorname{Dec}^{\prime} Dec ′ uses only this component of the secret key. Hence the executions of Dec ′ \operatorname{Dec}^{\prime} Dec ′ with sk ∗ \operatorname{sk}^* sk ∗ are identical to those with sk k ( λ ) ′ \operatorname{sk}^{\prime}_{k(\lambda)} sk k ( λ ) ′ , and the decryption after freezing follows from the correctness shown above.
Finally, the index consistency holds with probability 0 0 0 in Equation (60) by construction: Enc ′ \operatorname{Enc}^{\prime} Enc ′ outputs a string other than ⊥ \perp ⊥ only if Index accepts it, for any crs, any vk ′ \operatorname{vk}^{\prime} vk ′ , any m m m , and any quantum state given as the public key.
Ciphertext uniqueness. Let A \mathcal{A} A be a QPT adversary that wins the experiment of Definition 6.3 with probability ϵ \epsilon ϵ . We construct a QPT adversary B \mathcal{B} B against the strong security of the one-shot signature scheme as follows. B ( 1 λ , crs ) \mathcal{B}(1^\lambda,\operatorname{crs}) B ( 1 λ , crs ) runs ( vk ′ , ct 1 ′ , ct 2 ′ ) ← A ( 1 λ , crs ) (\operatorname{vk}^{\prime},\operatorname{ct}^{\prime}_1,\operatorname{ct}^{\prime}_2) \leftarrow\mathcal{A}(1^\lambda,\operatorname{crs}) ( vk ′ , ct 1 ′ , ct 2 ′ ) ← A ( 1 λ , crs ) , and aborts unless ct 1 ′ ≠ ct 2 ′ \operatorname{ct}^{\prime}_1 \ne\operatorname{ct}^{\prime}_2 ct 1 ′ = ct 2 ′ and Index ( vk ′ , ct 1 ′ ) = Index ( vk ′ , ct 2 ′ ) ≠ ⊥ \operatorname{Index}(\operatorname{vk}^{\prime},\operatorname{ct}^{\prime}_1) = \operatorname{Index}(\operatorname{vk}^{\prime},\operatorname{ct}^{\prime}_2) \ne\perp Index ( vk ′ , ct 1 ′ ) = Index ( vk ′ , ct 2 ′ ) = ⊥ . Otherwise, let t t t be the common output of Index. Then vk ′ \operatorname{vk}^{\prime} vk ′ parses as ( vk , w 1 ) (\operatorname{vk},w_1) ( vk , w 1 ) , and, for each i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } , ct i ′ \operatorname{ct}^{\prime}_i ct i ′ parses as ( ( t , ( μ i , s , τ i , s ) s ≤ t ) , ct i , π i ) ((t,(\mu_{i,s},\tau_{i,s})_{s\leq t}),\operatorname{ct}_i,\pi_i) (( t , ( μ i , s , τ i , s ) s ≤ t ) , ct i , π i ) with μ i , s = ( s , v i , s , w i , s + 1 ) \mu_{i,s} = (s,v_{i,s},w_{i,s+1}) μ i , s = ( s , v i , s , w i , s + 1 ) . We set w i , 1 : = w 1 w_{i,1} := w_1 w i , 1 := w 1 . Exactly one of the following two cases occurs.
Case 1: there exists s ≤ t s \leq t s ≤ t with ( μ 1 , s , τ 1 , s ) ≠ ( μ 2 , s , τ 2 , s ) (\mu_{1,s},\tau_{1,s}) \ne(\mu_{2,s},\tau_{2,s}) ( μ 1 , s , τ 1 , s ) = ( μ 2 , s , τ 2 , s ) . Let r r r be the smallest such index. Since μ 1 , s = μ 2 , s \mu_{1,s} = \mu_{2,s} μ 1 , s = μ 2 , s for all s < r s < r s < r , we have w 1 , r = w 2 , r w_{1,r} = w_{2,r} w 1 , r = w 2 , r (for r = 1 r = 1 r = 1 , both are w 1 w_1 w 1 ). B \mathcal{B} B outputs ( w 1 , r , μ 1 , r , τ 1 , r , μ 2 , r , τ 2 , r ) (w_{1,r},\mu_{1,r},\tau_{1,r},\mu_{2,r},\tau_{2,r}) ( w 1 , r , μ 1 , r , τ 1 , r , μ 2 , r , τ 2 , r ) .
Case 2: ( μ 1 , s , τ 1 , s ) = ( μ 2 , s , τ 2 , s ) (\mu_{1,s},\tau_{1,s}) = (\mu_{2,s},\tau_{2,s}) ( μ 1 , s , τ 1 , s ) = ( μ 2 , s , τ 2 , s ) for all s ≤ t s \leq t s ≤ t . Then v 1 , t = v 2 , t v_{1,t} = v_{2,t} v 1 , t = v 2 , t . Moreover, because ct 1 ′ ≠ ct 2 ′ \operatorname{ct}^{\prime}_1 \ne\operatorname{ct}^{\prime}_2 ct 1 ′ = ct 2 ′ as bit strings while their first components coincide, we have ( ct 1 , π 1 ) ≠ ( ct 2 , π 2 ) (\operatorname{ct}_1,\pi_1) \ne(\operatorname{ct}_2,\pi_2) ( ct 1 , π 1 ) = ( ct 2 , π 2 ) . B \mathcal{B} B outputs ( v 1 , t , ct 1 , π 1 , ct 2 , π 2 ) (v_{1,t},\operatorname{ct}_1,\pi_1,\operatorname{ct}_2,\pi_2) ( v 1 , t , ct 1 , π 1 , ct 2 , π 2 ) .
In both cases, the two message-signature pairs output by B \mathcal{B} B are distinct, and both pass the verification under the verification key output by B \mathcal{B} B , because Index has accepted both ct 1 ′ \operatorname{ct}^{\prime}_1 ct 1 ′ and ct 2 ′ \operatorname{ct}^{\prime}_2 ct 2 ′ and Ver is classical and deterministic. Hence B \mathcal{B} B wins the game of Equation (61) with probability ϵ \epsilon ϵ , and therefore ϵ ≤ negl ( λ ) \epsilon\leq\operatorname{negl}(\lambda) ϵ ≤ negl ( λ ) . Note that the two pairs can differ only in the signatures, which is the reason why we need strong security.
Freeze binding. Let A \mathcal{A} A be a QPT adversary that wins the experiment of Definition 6.4 with probability ϵ \epsilon ϵ . We construct a QPT adversary B \mathcal{B} B against the strong security of the one-shot signature scheme as follows. B ( 1 λ , crs ) \mathcal{B}(1^\lambda,\operatorname{crs}) B ( 1 λ , crs ) runs ( vk ′ , ct ′ , cert , count ) ← A ( 1 λ , crs ) (\operatorname{vk}^{\prime},\operatorname{ct}^{\prime},\operatorname{cert},\operatorname{count}) \leftarrow\mathcal{A}(1^\lambda,\operatorname{crs}) ( vk ′ , ct ′ , cert , count ) ← A ( 1 λ , crs ) and t ← Index ( vk ′ , ct ′ ) t \leftarrow\operatorname{Index}(\operatorname{vk}^{\prime},\operatorname{ct}^{\prime}) t ← Index ( vk ′ , ct ′ ) , and aborts unless T = FreezeVer ( vk ′ , cert , count ) \operatorname{T} = \operatorname{FreezeVer}(\operatorname{vk}^{\prime},\operatorname{cert},\operatorname{count}) T = FreezeVer ( vk ′ , cert , count ) , t ≠ ⊥ t \ne\perp t = ⊥ , and count < t \operatorname{count} < t count < t . Otherwise, vk ′ \operatorname{vk}^{\prime} vk ′ parses as ( vk , w 1 ) (\operatorname{vk},w_1) ( vk , w 1 ) , cert \operatorname{cert} cert parses as ( ( μ s , τ s ) s ≤ count , τ ∗ ) ((\mu_s,\tau_s)_{s\leq\operatorname{count}},\tau^*) (( μ s , τ s ) s ≤ count , τ ∗ ) with μ s = ( s , v s , w s + 1 ) \mu_s = (s,v_s,w_{s+1}) μ s = ( s , v s , w s + 1 ) , and ct ′ \operatorname{ct}^{\prime} ct ′ parses as ( ( t , ( μ s ′ , τ s ′ ) s ≤ t ) , ct , π ) ((t,(\mu^{\prime}_s,\tau^{\prime}_s)_{s\leq t}),\operatorname{ct},\pi) (( t , ( μ s ′ , τ s ′ ) s ≤ t ) , ct , π ) with μ s ′ = ( s , v s ′ , w s + 1 ′ ) \mu^{\prime}_s = (s,v^{\prime}_s,w^{\prime}_{s+1}) μ s ′ = ( s , v s ′ , w s + 1 ′ ) . We set w 1 ′ : = w 1 w^{\prime}_1 := w_1 w 1 ′ := w 1 . Exactly one of the following two cases occurs.
Case 1: there exists s ≤ count s \leq\operatorname{count} s ≤ count with μ s ′ ≠ μ s \mu^{\prime}_s \ne\mu_s μ s ′ = μ s . Let r r r be the smallest such index. Since μ s ′ = μ s \mu^{\prime}_s = \mu_s μ s ′ = μ s for all s < r s < r s < r , we have w r ′ = w r w^{\prime}_r = w_r w r ′ = w r (for r = 1 r = 1 r = 1 , both are w 1 w_1 w 1 ). Then B \mathcal{B} B outputs ( w r , μ r , τ r , μ r ′ , τ r ′ ) (w_r,\mu_r,\tau_r,\mu^{\prime}_r,\tau^{\prime}_r) ( w r , μ r , τ r , μ r ′ , τ r ′ ) .
Case 2: μ s ′ = μ s \mu'_s=\mu_s μ s ′ = μ s for all s ≤ c o u n t s\le\mathit{count} s ≤ count . Then w c o u n t + 1 ′ = w c o u n t + 1 w'_{\mathit{count}+1}=w_{\mathit{count}+1} w count + 1 ′ = w count + 1 (for c o u n t = 0 \mathit{count}=0 count = 0 , both are w 1 w_1 w 1 ), and the position c o u n t + 1 \mathit{count}+1 count + 1 exists in the chain of c t ′ \mathrm{ct}' ct ′ because c o u n t < t \mathit{count}<t count < t . Then B \mathcal{B} B outputs ( w c o u n t + 1 , μ c o u n t + 1 ′ , τ c o u n t + 1 ′ , ⊥ , τ ∗ ) (w_{\mathit{count}+1},\mu'_{\mathit{count}+1},\tau'_{\mathit{count}+1},\perp,\tau^*) ( w count + 1 , μ count + 1 ′ , τ count + 1 ′ , ⊥ , τ ∗ ) .
In both cases, the two messages output by B \mathcal{B} B are distinct: in Case 1 by the definition of r r r , and in Case 2 because μ c o u n t + 1 ′ \mu'_{\mathit{count}+1} μ count + 1 ′ is an encoding of a tuple and ⊥ \perp ⊥ is not. Both signatures pass the verification under the verification key output by B \mathcal{B} B , because FreezeVer and Index have accepted and Ver is classical and deterministic. Hence B \mathcal{B} B wins the game of Equation (61) with probability ϵ \epsilon ϵ , and therefore ϵ ≤ negl ( λ ) \epsilon\le\operatorname{negl}(\lambda) ϵ ≤ negl ( λ ) .
Remark 6.11. In the security game of Definition 6.1, the adversary does not receive the certificate. In practice, however, the receiver publishes the certificate, and hence the adversary can see it. We therefore note that the security and the everlasting security of the constructed scheme hold even in the following extended game: at any point during the interaction with the challenger, the adversary can once instruct the challenger to run Freeze on the current secret key and receive ( c e r t , c o u n t ) (\mathrm{cert},\mathit{count}) ( cert , count ) , after which public-key queries are answered with ⊥ \perp ⊥ . Indeed, the adversary A \mathcal{A} A in the proof of Theorem 6.9 holds all the signing keys of the one-shot signature scheme, including the unused s i g k t + 1 \mathrm{sigk}_{t+1} sigk t + 1 after t t t public-key queries, and hence it can simulate Freeze by itself without any additional query to the challenger: it runs τ ∗ ← Sign ( c r s , s i g k t + 1 , ⊥ ) \tau^*\leftarrow\operatorname{Sign}(\mathrm{crs},\mathrm{sigk}_{t+1},\perp) τ ∗ ← Sign ( crs , sigk t + 1 , ⊥ ) and returns c e r t = ( ( μ s , τ s ) s ≤ t , τ ∗ ) \mathrm{cert}=((\mu_s,\tau_s)_{s\le t},\tau^*) cert = (( μ s , τ s ) s ≤ t , τ ∗ ) and c o u n t = t \mathit{count}=t count = t to A ′ \mathcal{A}' A ′ . The rest of the simulation is unchanged, regardless of whether the freeze is requested before or after the challenge.
2QKE with Security for Alice
As is explained in § 1.3 , in the 2QKE constructed in the proof of Theorem 3.1 , Eve can learn Alice’s key, and Eve can make Alice’s key different from Bob’s key. In this section, we show that both issues are resolved if Bob additionally sends a short classical bit string, which is a masked tag of an AMD code [8 , 11 ] , over the authenticated classical channel.
We consider the following variant of Definition 2.6: Bob sends not only a quantum state but also a classical bit string to Alice, where the latter is sent over the authenticated classical channel, and Alice outputs α ∈ { 0 , 1 , ⊥ } \alpha\in\{0,1,\perp\} α ∈ { 0 , 1 , ⊥ } , where ⊥ \perp ⊥ means that Alice aborts.
Definition 7.1 (Security for Alice). A 2QKE satisfies security for Alice if for any QPT Eve who outputs a bit e e e ,
Pr [ α ∉ { β , ⊥ } ] ≤ negl ( λ ) , (64) \Pr[\alpha\notin\{\beta,\perp\}]\le\operatorname{negl}(\lambda), \tag*{(64)} Pr [ α ∈ / { β , ⊥ }] ≤ negl ( λ ) , (64)
Pr [ e = α ∧ α ≠ ⊥ ] ≤ 1 2 Pr [ α ≠ ⊥ ] + negl ( λ ) . (65) \Pr[e=\alpha\land\alpha\ne\perp]\le\frac{1}{2}\Pr[\alpha\ne\perp]+\operatorname{negl}(\lambda). \tag*{(65)} Pr [ e = α ∧ α = ⊥ ] ≤ 2 1 Pr [ α = ⊥ ] + negl ( λ ) . (65)
Here, Eve can freely read the classical messages and can freely modify the quantum messages.
We can actually show the following everlasting security:
Definition 7.2 (Everlasting security for Alice). A 2QKE satisfies everlasting security for Alice if the following holds for any Eve of the following form: during the execution of the protocol, Eve can freely read the classical messages and can freely modify the quantum messages, but all of her operations are QPT; after the protocol terminates, Eve applies computationally-unbounded operations on all the registers that she keeps, and outputs a bit e e e . The requirement is that Equation (64) and Equation (65) hold.
Construction. We construct a 2QKE that satisfies security for Alice (Definition 7.1) by modifying the 2QKE constructed in the proof of Theorem 3.1 . All step numbers below refer to the latter. We identify { 0 , 1 } λ \{0,1\}^{\lambda} { 0 , 1 } λ with the finite field of order 2 λ 2^{\lambda} 2 λ : a bit string ( u 1 , … , u λ ) (u_1,\ldots,u_{\lambda}) ( u 1 , … , u λ ) is regarded as the polynomial ∑ i = 1 λ u i x i − 1 \sum_{i=1}^{\lambda}u_i x^{i-1} ∑ i = 1 λ u i x i − 1 over F 2 \mathbb{F}_2 F 2 modulo a fixed irreducible polynomial of degree λ \lambda λ . For u , v ∈ { 0 , 1 } λ u,v\in\{0,1\}^{\lambda} u , v ∈ { 0 , 1 } λ , u v ∈ { 0 , 1 } λ uv\in\{0,1\}^{\lambda} uv ∈ { 0 , 1 } λ is the product in the field, i.e., the product of the two polynomials modulo the irreducible polynomial. (It is neither the inner product nor the bitwise product.) The sum in the field is the bitwise XOR u ⊕ v ∈ { 0 , 1 } λ u\oplus v\in\{0,1\}^{\lambda} u ⊕ v ∈ { 0 , 1 } λ . Let n : = 3 λ n:=3\lambda n := 3 λ .
Alice runs steps 1–6 independently n n n times. For each j ∈ [ n ] j\in[n] j ∈ [ n ] , let v k j \mathrm{vk}_j vk j , a j a_j a j , and ( A j , B j , C j ) (A_j,B_j,C_j) ( A j , B j , C j ) be the verification key, the bit a a a , and the registers of the j j j -th execution, respectively.
Bob samples u , v , w ← { 0 , 1 } λ u,v,w\leftarrow\{0,1\}^{\lambda} u , v , w ← { 0 , 1 } λ and sets k : = ( u , v , w ) ∈ { 0 , 1 } n k:=(u,v,w)\in\{0,1\}^{n} k := ( u , v , w ) ∈ { 0 , 1 } n . For each j ∈ [ n ] j\in[n] j ∈ [ n ] , Bob performs the measurement { Π v k j , I − Π v k j } \{\Pi^{\mathrm{vk}_j},I-\Pi^{\mathrm{vk}_j}\} { Π vk j , I − Π vk j } of step 7 on the registers of the j j j -th execution. If the result is I − Π v k j I-\Pi^{\mathrm{vk}_j} I − Π vk j for at least one j j j , Bob sends ⊥ \perp ⊥ over the classical channel and the maximally-mixed state over the quantum channel. Otherwise, Bob applies Z k j Z^{k_j} Z k j on A j A_j A j for each j ∈ [ n ] j\in[n] j ∈ [ n ] , returns all the registers to Alice, and sends
t : = u v ⊕ w ∈ { 0 , 1 } λ (66) t:=uv\oplus w\in\{0,1\}^{\lambda} \tag*{(66)} t := uv ⊕ w ∈ { 0 , 1 } λ (66)
over the classical channel. In both cases, Bob outputs the first bit of u u u as β \beta β .
If Alice receives ⊥ \perp ⊥ , she outputs α : = ⊥ \alpha:=\perp α :=⊥ . Otherwise, for each j ∈ [ n ] j\in[n] j ∈ [ n ] , Alice runs step 8 of the j j j -th execution, and let k j ′ k'_j k j ′ be its output, i.e., the measurement result plus a j a_j a j . She parses k j ′ = ( u j ′ , v j ′ , w j ′ ) k'_j=(u'_j,v'_j,w'_j) k j ′ = ( u j ′ , v j ′ , w j ′ ) . If u j ′ v j ′ ⊕ w j ′ = t u'_jv'_j\oplus w'_j=t u j ′ v j ′ ⊕ w j ′ = t , she outputs the first bit of u j ′ u'_j u j ′ as α \alpha α . Otherwise, she outputs α : = ⊥ \alpha:=\perp α :=⊥ .
Theorem 7.3. If one-time secure digital signatures with quantum signatures exist, then the above 2QKE satisfies correctness, everlasting security (Definition 2.7 ), and everlasting security for Alice (Definition 7.2).
Remark 7.4. In the above 2QKE, Eve cannot make Alice abort depending on Bob’s key:
∣ Pr [ α ≠ ⊥ ∣ β = 0 ] − Pr [ α ≠ ⊥ ∣ β = 1 ] ∣ ≤ negl ( λ ) . (67) \left|\Pr[\alpha\ne\perp\mid\beta=0]-\Pr[\alpha\ne\perp\mid\beta=1]\right|\le\operatorname{negl}(\lambda). \tag*{(67)} ∣ Pr [ α = ⊥∣ β = 0 ] − Pr [ α = ⊥∣ β = 1 ] ∣ ≤ negl ( λ ) . (67)
In fact, the proof of Theorem 7.3 shows that, except for a negligible probability, whether Alice aborts is determined by an event that is independent of Bob’s key.
The proof of Theorem 7.3 is based on the following lemma, which shows that the only thing that Eve can do on Alice’s string k ′ k' k ′ is to add a string that is independent of Bob’s string k k k .
Lemma 7.5. Let ρ \rho ρ be the joint state of k k k , α \alpha α , and all the registers that Eve keeps when the protocol terminates. Let ρ ′ \rho' ρ ′ be the same state in the following modified execution, which is a hypothetical experiment used only in the proof: Bob does not apply Z k j Z^{k_j} Z k j on A j A_j A j for any j ∈ [ n ] j\in[n] j ∈ [ n ] . Alice runs step 8 of the n n n executions as in the real execution, and let d ∈ { 0 , 1 } n d\in\{0,1\}^{n} d ∈ { 0 , 1 } n be the string of its outputs, i.e., d j d_j d j is Alice’s measurement result of the j j j -th execution plus a j a_j a j . Then k ′ k' k ′ is defined as k ′ : = d ⊕ k k':=d\oplus k k ′ := d ⊕ k . Then, for any QPT Eve,
∥ ρ − ρ ′ ∥ 1 ≤ negl ( λ ) . (68) \lVert\rho-\rho'\rVert_1\le\operatorname{negl}(\lambda). \tag*{(68)} ∥ ρ − ρ ′ ∥ 1 ≤ negl ( λ ) . (68)
Proof. As in the proof of Theorem 3.1 , we assume without loss of generality that Eve applies a QPT unitary V 1 V_1 V 1 on the registers ( A j , B j , C j ) j ∈ [ n ] (A_j,B_j,C_j)_{j\in[n]} ( A j , B j , C j ) j ∈ [ n ] and her register E E E initialized to ∣ 0 … 0 ⟩ \lvert0\ldots0\rangle ∣ 0 … 0 ⟩ , and forwards ( A j , B j , C j ) j ∈ [ n ] (A_j,B_j,C_j)_{j\in[n]} ( A j , B j , C j ) j ∈ [ n ] to Bob.
Let ∣ σ j ( 0 ) ⟩ |\sigma_j(0)\rangle ∣ σ j ( 0 )⟩ , ∣ σ j ( 1 ) ⟩ |\sigma_j(1)\rangle ∣ σ j ( 1 )⟩ , and P j P_j P j be the signatures and the Pauli of the j j j -th execution. We can assume that Alice obtains a j a_j a j in the following way: instead of step 5, she generates
1 2 ∑ m ∈ { 0 , 1 } ∣ m ⟩ R j ∣ m ⟩ A j ∣ σ j ( m ) ⟩ B j P j ∣ σ j ( 1 − m ) ⟩ C j , (69) \frac{1}{\sqrt{2}}\sum_{m\in\{0,1\}} |m\rangle_{R_j}|m\rangle_{A_j}|\sigma_j(m)\rangle_{B_j}P_j|\sigma_j(1-m)\rangle_{C_j}, \tag*{(69)} 2 1 m ∈ { 0 , 1 } ∑ ∣ m ⟩ R j ∣ m ⟩ A j ∣ σ j ( m ) ⟩ B j P j ∣ σ j ( 1 − m ) ⟩ C j , (69)
keeps the register R j R_j R j , and measures R j R_j R j in the Hadamard basis at the end of the protocol to obtain a j a_j a j . In fact, a j a_j a j is uniformly random, the state of the other registers is that of step 5, and Alice uses a j a_j a j only at the end of the protocol. Then, in the modified execution, adding k j k_j k j to d j d_j d j is equivalent to adding k j k_j k j to a j a_j a j , which is equivalent to applying Z k j Z^{k_j} Z k j on R j R_j R j before measuring it, because Z Z Z flips the result of the Hadamard-basis measurement. Therefore the two executions are different only in the following point: when Bob’s measurement accepts, Z k j Z^{k_j} Z k j is applied on A j A_j A j in the real execution, and on R j R_j R j in the modified execution.
Fix k k k , the verification keys, the signatures, and the Paulis. For m ∈ { 0 , 1 } n m\in\{0,1\}^n m ∈ { 0 , 1 } n , define
∣ ξ m ⟩ : = V 1 ( ⨂ j ∈ [ n ] ∣ m j ⟩ A j ∣ σ j ( m j ) ⟩ B j P j ∣ σ j ( 1 − m j ) ⟩ C j ) ⊗ ∣ 0 … 0 ⟩ E ∣ 0 … 0 ⟩ B ′ , (70) |\xi_m\rangle:= V_1\left(\bigotimes_{j\in[n]} |m_j\rangle_{A_j}|\sigma_j(m_j)\rangle_{B_j}P_j|\sigma_j(1-m_j)\rangle_{C_j}\right)\otimes|0\ldots0\rangle_E|0\ldots0\rangle_{B'}, \tag*{(70)} ∣ ξ m ⟩ := V 1 j ∈ [ n ] ⨂ ∣ m j ⟩ A j ∣ σ j ( m j ) ⟩ B j P j ∣ σ j ( 1 − m j ) ⟩ C j ⊗ ∣0 … 0 ⟩ E ∣0 … 0 ⟩ B ′ , (70)
where B ′ B' B ′ is Bob’s ancilla register, so that the state before Bob’s measurement is 2 − n / 2 ∑ m ∈ { 0 , 1 } n ∣ m ⟩ R ∣ ξ m ⟩ 2^{-n/2}\sum_{m\in\{0,1\}^n}|m\rangle_R|\xi_m\rangle 2 − n /2 ∑ m ∈ { 0 , 1 } n ∣ m ⟩ R ∣ ξ m ⟩ with R : = ( R 1 , … , R n ) R := (R_1,\ldots,R_n) R := ( R 1 , … , R n ) . Let Π : = ⨂ j ∈ [ n ] Π j v k j \Pi:= \bigotimes_{j\in[n]}\Pi^{v k_j}_j Π := ⨂ j ∈ [ n ] Π j v k j , Z k : = ⨂ j ∈ [ n ] Z k j Z^k := \bigotimes_{j\in[n]}Z^{k_j} Z k := ⨂ j ∈ [ n ] Z k j , and k ⋅ m : = ⨁ j ∈ [ n ] k j m j k\cdot m := \bigoplus_{j\in[n]} k_jm_j k ⋅ m := ⨁ j ∈ [ n ] k j m j . The unnormalized states after Bob’s measurement accepts and Z k Z^k Z k is applied on A : = ( A 1 , … , A n ) A := (A_1,\ldots,A_n) A := ( A 1 , … , A n ) in the real execution and on R R R in the modified execution are
∣ Φ ⟩ : = 1 2 n ∑ m ∈ { 0 , 1 } n ∣ m ⟩ R ⊗ Z A k Π ∣ ξ m ⟩ , (71) |\Phi\rangle:= \frac{1}{\sqrt{2^n}}\sum_{m\in\{0,1\}^n}|m\rangle_R\otimes Z^k_A\Pi|\xi_m\rangle, \tag*{(71)} ∣Φ ⟩ := 2 n 1 m ∈ { 0 , 1 } n ∑ ∣ m ⟩ R ⊗ Z A k Π∣ ξ m ⟩ , (71)
∣ Φ ′ ⟩ : = 1 2 n ∑ m ∈ { 0 , 1 } n ( − 1 ) k ⋅ m ∣ m ⟩ R ⊗ Π ∣ ξ m ⟩ , (72) |\Phi'\rangle:= \frac{1}{\sqrt{2^n}}\sum_{m\in\{0,1\}^n}(-1)^{k\cdot m}|m\rangle_R\otimes\Pi|\xi_m\rangle, \tag*{(72)} ∣ Φ ′ ⟩ := 2 n 1 m ∈ { 0 , 1 } n ∑ ( − 1 ) k ⋅ m ∣ m ⟩ R ⊗ Π∣ ξ m ⟩ , (72)
respectively. All the subsequent operations are identical in the two executions. Because ∥ ∣ x ⟩ ⟨ x ∣ − ∣ y ⟩ ⟨ y ∣ ∥ 1 ≤ 2 ∥ ∣ x ⟩ − ∣ y ⟩ ∥ \lVert|x\rangle\langle x|-|y\rangle\langle y|\rVert_1\le2\lVert|x\rangle-|y\rangle\rVert ∥ ∣ x ⟩ ⟨ x ∣ − ∣ y ⟩ ⟨ y ∣ ∥ 1 ≤ 2 ∥ ∣ x ⟩ − ∣ y ⟩∥ for any vectors ∣ x ⟩ |x\rangle ∣ x ⟩ and ∣ y ⟩ |y\rangle ∣ y ⟩ of norm at most 1, it therefore suffices to show that the expectation of ∥ ∣ Φ ⟩ − ∣ Φ ′ ⟩ ∥ \lVert|\Phi\rangle-|\Phi'\rangle\rVert ∥ ∣Φ ⟩ − ∣ Φ ′ ⟩∥ over the fixed values is negligible.
We have
Π ∣ ξ m ⟩ = ∑ m ′ ∈ { 0 , 1 } n ∣ m ′ ⟩ ⟨ m ′ ∣ A ⊗ I Π ∣ ξ m ⟩ (73) \Pi|\xi_m\rangle= \sum_{m'\in\{0,1\}^n}|m'\rangle\langle m'|_A\otimes I\;\Pi|\xi_m\rangle \tag*{(73)} Π∣ ξ m ⟩ = m ′ ∈ { 0 , 1 } n ∑ ∣ m ′ ⟩ ⟨ m ′ ∣ A ⊗ I Π∣ ξ m ⟩ (73)
and Z A k ∣ m ′ ⟩ A = ( − 1 ) k ⋅ m ′ ∣ m ′ ⟩ A Z^k_A|m'\rangle_A=(-1)^{k\cdot m'}|m'\rangle_A Z A k ∣ m ′ ⟩ A = ( − 1 ) k ⋅ m ′ ∣ m ′ ⟩ A . The terms with m ′ = m m'=m m ′ = m of ∣ Φ ⟩ |\Phi\rangle ∣Φ ⟩ and ∣ Φ ′ ⟩ |\Phi'\rangle ∣ Φ ′ ⟩ therefore cancel each other, and we obtain
∣ Φ ⟩ − ∣ Φ ′ ⟩ = 1 2 n ∑ m ∣ m ⟩ R ⊗ ∑ m ′ ≠ m ( ( − 1 ) k ⋅ m ′ − ( − 1 ) k ⋅ m ) ( ∣ m ′ ⟩ ⟨ m ′ ∣ A ⊗ I ) Π ∣ ξ m ⟩ . (74) \begin{aligned}
|\Phi\rangle-|\Phi'\rangle
&=\frac{1}{\sqrt{2^n}}\sum_m |m\rangle_R\otimes\sum_{m'\ne m}\left((-1)^{k\cdot m'}-(-1)^{k\cdot m}\right)\left(|m'\rangle\langle m'|_A\otimes I\right)\Pi|\xi_m\rangle. \tag*{(74)}
\end{aligned} ∣Φ ⟩ − ∣ Φ ′ ⟩ = 2 n 1 m ∑ ∣ m ⟩ R ⊗ m ′ = m ∑ ( ( − 1 ) k ⋅ m ′ − ( − 1 ) k ⋅ m ) ( ∣ m ′ ⟩ ⟨ m ′ ∣ A ⊗ I ) Π∣ ξ m ⟩ . (74)
The terms with different ( m , m ′ ) (m,m') ( m , m ′ ) are orthogonal to each other, because they have different states on ( R , A ) (R,A) ( R , A ) , and ∣ ( − 1 ) k ⋅ m ′ − ( − 1 ) k ⋅ m ∣ ≤ 2 \left|(-1)^{k\cdot m'}-(-1)^{k\cdot m}\right|\le2 ( − 1 ) k ⋅ m ′ − ( − 1 ) k ⋅ m ≤ 2 . Therefore
∥ ∣ Φ ⟩ − ∣ Φ ′ ⟩ ∥ 2 ≤ 4 2 n ∑ m ∑ m ′ ≠ m ∥ ( ∣ m ′ ⟩ ⟨ m ′ ∣ A ⊗ I ) Π ∣ ξ m ⟩ ∥ 2 . (75) \lVert|\Phi\rangle-|\Phi'\rangle\rVert^2\le\frac{4}{2^n}\sum_m\sum_{m'\ne m}\left\|\left(|m'\rangle\langle m'|_A\otimes I\right)\Pi|\xi_m\rangle\right\|^2. \tag*{(75)} ∥ ∣Φ ⟩ − ∣ Φ ′ ⟩ ∥ 2 ≤ 2 n 4 m ∑ m ′ = m ∑ ∥ ( ∣ m ′ ⟩ ⟨ m ′ ∣ A ⊗ I ) Π∣ ξ m ⟩ ∥ 2 . (75)
The right-hand side of Equation (75) is four times the probability of the following event: Alice samples m ← { 0 , 1 } n m \leftarrow\{0,1\}^{n} m ← { 0 , 1 } n and sends the state to which V 1 V_1 V 1 is applied in Equation (70) , Bob’s measurement accepts, and the result of the computational-basis measurement of A A A is not m m m . If the event occurs, there exists j ∈ [ n ] j \in[n] j ∈ [ n ] such that the measurement { Π v k j j , I − Π v k j j } \{\Pi_{v_{k_j}}^j,I-\Pi_{v_{k_j}}^j\} { Π v k j j , I − Π v k j j } accepts and the result on A j A_j A j is 1 − m j 1-m_j 1 − m j . For each j ∈ [ n ] j \in[n] j ∈ [ n ] , the probability of the latter, averaged over the fixed values, is negligible from the one-time security of the digital signature scheme, which is shown in the same way as the claim in the proof of Theorem 3.1 : the adversary samples k k k and m m m , outputs the message m j m_j m j , receives the signature ∣ σ j ( m j ) ⟩ \lvert\sigma_j(m_j)\rangle ∣ σ j ( m j )⟩ , generates the states of the other executions by itself, applies V 1 V_1 V 1 , measures A j A_j A j in the computational basis, and outputs the state of B j B_j B j if the result is 1 − m j 1-m_j 1 − m j . (Because each P l P_l P l is a uniformly random Pauli, the adversary can use a uniformly random computational-basis state instead of P l ∣ σ l ( 1 − m l ) ⟩ P_l\lvert\sigma_l(1-m_l)\rangle P l ∣ σ l ( 1 − m l )⟩ .) Hence, by the union bound, the expectation of the right-hand side of Equation (75) is negligible, and so is the expectation of ∥ ∣ Φ ⟩ − ∣ Φ ′ ⟩ ∥ \lVert\lvert\Phi\rangle-\lvert\Phi'\rangle\rVert ∥∣ Φ ⟩ − ∣ Φ ′ ⟩∥ by Jensen’s inequality.
Proof of Theorem 7.3. Correctness follows from that of the 2QKE of Theorem 3.1 and the union bound: if Eve does nothing, k ′ = k k'=k k ′ = k with probability 1 − negl ( λ ) 1-\operatorname{negl}(\lambda) 1 − negl ( λ ) , in which case α = β \alpha=\beta α = β .
For the security, we consider the modified execution of Lemma 7.5 , where k ′ = d ⊕ k k'=d\oplus k k ′ = d ⊕ k . We parse d = ( d u , d v , d w ) d=(d_u,d_v,d_w) d = ( d u , d v , d w ) . Let u 1 u_1 u 1 be the first bit of u u u , i.e., β = u 1 \beta=u_1 β = u 1 , and let G G G be the event that Bob’s measurement accepts and d = 0 n d=0^n d = 0 n .
We first show that, in the modified execution, ( u , v ) (u,v) ( u , v ) is independent of whether Bob’s measurement accepts, d d d , and the state of the registers that Eve keeps. The reason is as follows. Whether Bob’s measurement accepts does not depend on k k k , because Bob uses k k k only after his measurement. Because Bob does not apply Z k j Z^{k_j} Z k j , the only message that depends on k k k is t = u v ⊕ w t=uv\oplus w t = uv ⊕ w of Equation (66) , which Bob sends over the classical channel. Hence d d d and the state of the registers that Eve keeps depend on k k k only through t t t , and t t t is independent of ( u , v ) (u,v) ( u , v ) because w w w is uniformly random.
Alice does not abort if and only if Bob’s measurement accepts and ( u ⊕ d u ) ( v ⊕ d v ) ⊕ w ⊕ d w = u v ⊕ w (u\oplus d_u)(v\oplus d_v)\oplus w\oplus d_w=uv\oplus w ( u ⊕ d u ) ( v ⊕ d v ) ⊕ w ⊕ d w = uv ⊕ w , i.e.,
u d v ⊕ v d u ⊕ d u d v ⊕ d w = 0. (76) ud_v\oplus vd_u\oplus d_ud_v\oplus d_w=0. \tag*{(76)} u d v ⊕ v d u ⊕ d u d v ⊕ d w = 0. (76)
If d = 0 n d=0^n d = 0 n , Equation (76) is satisfied. If d ≠ 0 n d\ne0^n d = 0 n , Equation (76) is satisfied with probability at most 2 − λ 2^{-\lambda} 2 − λ , which is shown as follows.
If d u = d v = 0 λ d_u=d_v=0^\lambda d u = d v = 0 λ , then d w ≠ 0 λ d_w\ne0^\lambda d w = 0 λ , and Equation (76) is d w = 0 λ d_w=0^\lambda d w = 0 λ . Hence it is not satisfied.
If d v ≠ 0 λ d_v\ne0^\lambda d v = 0 λ , Equation (76) is u d v = v d u ⊕ d u d v ⊕ d w ud_v=vd_u\oplus d_ud_v\oplus d_w u d v = v d u ⊕ d u d v ⊕ d w . Because d v d_v d v has the inverse in the field, for each v v v and d d d , there is exactly one u u u that satisfies it. Because u u u is uniformly random and independent of v v v and d d d , it is satisfied with probability 2 − λ 2^{-\lambda} 2 − λ .
If d u ≠ 0 λ d_u\ne0^\lambda d u = 0 λ , Equation (76) is satisfied with probability 2 − λ 2^{-\lambda} 2 − λ in the same way, where the roles of u u u and v v v are exchanged.
Therefore we obtain the following. If G G G occurs, Alice does not abort, and α = u 1 \alpha=u_1 α = u 1 because u ′ = u u'=u u ′ = u . If G G G does not occur, i.e., if Bob’s measurement rejects or d ≠ 0 n d\ne0^n d = 0 n , α = ⊥ \alpha=\perp α =⊥ except for probability 2 − λ 2^{-\lambda} 2 − λ . Hence α ∈ { u 1 , ⊥ } \alpha\in\{u_1,\perp\} α ∈ { u 1 , ⊥ } except for probability 2 − λ 2^{-\lambda} 2 − λ . Because β = u 1 \beta=u_1 β = u 1 , this means Pr [ α ≠ { β , ⊥ } ] ≤ 2 − λ \Pr[\alpha\ne\{\beta,\perp\}]\le2^{-\lambda} Pr [ α = { β , ⊥ }] ≤ 2 − λ . Moreover,
Pr [ e = α ∧ α ≠ ⊥ ] ≤ Pr [ e = u 1 ∧ G ] + 2 − λ . (77) \Pr[e=\alpha\land\alpha\ne\perp]\le\Pr[e=u_1\land G]+2^{-\lambda}. \tag*{(77)} Pr [ e = α ∧ α = ⊥ ] ≤ Pr [ e = u 1 ∧ G ] + 2 − λ . (77)
= 1 2 Pr [ G ] + 2 − λ ≤ 1 2 Pr [ α ≠ ⊥ ] + 2 − λ . (78) =\frac{1}{2}\Pr[G]+2^{-\lambda}\le\frac{1}{2}\Pr[\alpha\ne\perp]+2^{-\lambda}. \tag*{(78)} = 2 1 Pr [ G ] + 2 − λ ≤ 2 1 Pr [ α = ⊥ ] + 2 − λ . (78)
Here, the first inequality is because α = u 1 \alpha= u_1 α = u 1 if G G G occurs, and the probability that G G G does not occur and α ≠ ⊥ \alpha\ne\perp α = ⊥ is at most 2 − λ 2^{-\lambda} 2 − λ . The equality is because u 1 u_1 u 1 is uniformly random and independent of e e e and G G G (e e e is obtained from the registers that Eve keeps, and G G G is determined by whether Bob’s measurement accepts and d d d ), and therefore
Pr [ e = u 1 ∧ G ] = ∑ c ∈ { 0 , 1 } Pr [ u 1 = c ] Pr [ e = c ∧ G ] (79) \Pr[e = u_1 \land G] = \sum_{c \in\{0,1\}} \Pr[u_1 = c]\Pr[e = c \land G] \tag*{(79)} Pr [ e = u 1 ∧ G ] = c ∈ { 0 , 1 } ∑ Pr [ u 1 = c ] Pr [ e = c ∧ G ] (79)
= 1 2 ∑ c ∈ { 0 , 1 } Pr [ e = c ∧ G ] = 1 2 Pr [ G ] . (80) = \frac{1}{2}\sum_{c \in\{0,1\}} \Pr[e = c \land G] = \frac{1}{2}\Pr[G]. \tag*{(80)} = 2 1 c ∈ { 0 , 1 } ∑ Pr [ e = c ∧ G ] = 2 1 Pr [ G ] . (80)
The last inequality is because α ≠ ⊥ \alpha\ne\perp α = ⊥ if G G G occurs. Moreover, because β = u 1 \beta= u_1 β = u 1 is uniformly random and independent of the state of the registers that Eve keeps, Pr [ e = β ] = 1 2 \Pr[e = \beta] = \frac{1}{2} Pr [ e = β ] = 2 1 even if e e e is obtained by a computationally-unbounded operation on Eve’s registers after the protocol terminates.
Finally, we show the theorem. In the real execution, we have
Pr [ α ∉ { β , ⊥ } ] ≤ 2 − λ + negl ( λ ) , (81) \Pr[\alpha\notin\{\beta, \perp\}] \le2^{-\lambda} + \operatorname{negl}(\lambda), \tag*{(81)} Pr [ α ∈ / { β , ⊥ }] ≤ 2 − λ + negl ( λ ) , (81)
Pr [ e = α ∧ α ≠ ⊥ ] ≤ 1 2 Pr [ α ≠ ⊥ ] + negl ( λ ) , (82) \Pr[e = \alpha\land\alpha\ne\perp] \le\frac{1}{2}\Pr[\alpha\ne\perp] + \operatorname{negl}(\lambda), \tag*{(82)} Pr [ e = α ∧ α = ⊥ ] ≤ 2 1 Pr [ α = ⊥ ] + negl ( λ ) , (82)
Pr [ e = β ] ≤ 1 2 + negl ( λ ) , (83) \Pr[e = \beta] \le\frac{1}{2} + \operatorname{negl}(\lambda), \tag*{(83)} Pr [ e = β ] ≤ 2 1 + negl ( λ ) , (83)
which are Equation (64) , Equation (65) , and the everlasting security, respectively. The reason is as follows. We have shown above that the same three inequalities hold in the modified execution without negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) . From Equation (68) , the probability of each of the events α ∉ { β , ⊥ } \alpha\notin\{\beta, \perp\} α ∈ / { β , ⊥ } , e = α ∧ α ≠ ⊥ e = \alpha\land\alpha\ne\perp e = α ∧ α = ⊥ , α ≠ ⊥ \alpha\ne\perp α = ⊥ , and e = β e = \beta e = β in the real execution is different from that in the modified execution only negligibly. Here, we can use Equation (68) because each event is determined by k k k , α \alpha α , and the registers that Eve keeps: β \beta β is the first bit of u u u , which is a part of k k k , and e e e is obtained from the registers that Eve keeps.
Acknowledgements
Acknowledgements. TM is supported by JST CREST JPMJCR23I3, JST Moonshot R&D JPMJMS2061-5-1-1, JST FOREST, MEXT QLEAP, the Grant-in-Aid for Transformative Research Areas (A) 21H05183, and the Grant-in-Aid for Scientific Research (A) No.22H00522.
AI Disclosure. We used Claude Fable 5.1 and ChatGPT-6 Astra to assist with writing proofs and Introduction. The authors verified all texts, and retain full responsibility for all content of the paper.
Proof of lem:qots-from-evsp
Proof. We first show item 1. Let (Mint, Vr fy) be a public-key quantum money mini-scheme. We construct an EV-StatePuzz (Samp, Ver) as follows.
Samp ( 1 λ ) \operatorname{Samp}(1^\lambda) Samp ( 1 λ ) : Run ( s , ρ s ) ← Mint ( 1 λ ) (s,\rho_s) \leftarrow\operatorname{Mint}(1^\lambda) ( s , ρ s ) ← Mint ( 1 λ ) , and output the puzzle s s s and the answer ψ s : = ρ s \psi_s := \rho_s ψ s := ρ s .
Ver ( 1 λ , s , ρ ) \operatorname{Ver}(1^\lambda,s,\rho) Ver ( 1 λ , s , ρ ) : Run Vrfy ( 1 λ , s , ρ ) \operatorname{Vrfy}(1^\lambda,s,\rho) Vrfy ( 1 λ , s , ρ ) and output its output.
Correctness. The correctness experiment of ( Samp , Ver ) (\operatorname{Samp},\operatorname{Ver}) ( Samp , Ver ) is identical to that of ( Mint , Vrfy ) (\operatorname{Mint},\operatorname{Vrfy}) ( Mint , Vrfy ) , and hence
Pr [ ⊤ ← Ver ( 1 λ , s , ψ s ) : ( s , ψ s ) ← Samp ( 1 λ ) ] (84) \Pr[\top\leftarrow\operatorname{Ver}(1^\lambda,s,\psi_s) : (s,\psi_s) \leftarrow\operatorname{Samp}(1^\lambda)] \tag*{(84)} Pr [ ⊤ ← Ver ( 1 λ , s , ψ s ) : ( s , ψ s ) ← Samp ( 1 λ )] (84)
= Pr [ ⊤ ← Vrfy ( 1 λ , s , ρ s ) : ( s , ρ s ) ← Mint ( 1 λ ) ] ≥ 1 − negl ( λ ) . (85) = \Pr[\top\leftarrow\operatorname{Vrfy}(1^\lambda,s,\rho_s) : (s,\rho_s) \leftarrow\operatorname{Mint}(1^\lambda)] \ge1-\operatorname{negl}(\lambda). \tag*{(85)} = Pr [ ⊤ ← Vrfy ( 1 λ , s , ρ s ) : ( s , ρ s ) ← Mint ( 1 λ )] ≥ 1 − negl ( λ ) . (85)
Security. Assume there exists a QPT A \mathcal{A} A and a polynomial p p p such that
Pr [ ⊤ ← Ver ( 1 λ , s , A ( 1 λ , s ) ) : ( s , ψ s ) ← Samp ( 1 λ ) ] ≥ 1 p ( λ ) (86) \Pr[\top\leftarrow\operatorname{Ver}(1^\lambda,s,\mathcal{A}(1^\lambda,s)) : (s,\psi_s) \leftarrow\operatorname{Samp}(1^\lambda)] \ge\frac{1}{p(\lambda)} \tag*{(86)} Pr [ ⊤ ← Ver ( 1 λ , s , A ( 1 λ , s )) : ( s , ψ s ) ← Samp ( 1 λ )] ≥ p ( λ ) 1 (86)
for infinitely-many λ \lambda λ . We construct a QPT adversary B \mathcal{B} B against the security of the mini-scheme as follows. B ( 1 λ , s , ρ s ) \mathcal{B}(1^\lambda,s,\rho_s) B ( 1 λ , s , ρ s ) runs ρ ← A ( 1 λ , s ) \rho\leftarrow\mathcal{A}(1^\lambda,s) ρ ← A ( 1 λ , s ) , and outputs the state σ \sigma σ over two registers whose first register contains the received money state ρ s \rho_s ρ s and whose second register contains ρ \rho ρ . Because Samp = Mint \operatorname{Samp}=\operatorname{Mint} Samp = Mint , the input s s s to A \mathcal{A} A is distributed identically to that in the security experiment of the EV-StatePuzz. In the execution of Vrfy 2 ( 1 λ , s , σ ) \operatorname{Vrfy}_2(1^\lambda,s,\sigma) Vrfy 2 ( 1 λ , s , σ ) , the two invocations of Vrfy ( 1 λ , s , ⋅ ) \operatorname{Vrfy}(1^\lambda,s,\cdot) Vrfy ( 1 λ , s , ⋅ ) act on the two disjoint registers of σ \sigma σ , and therefore, by the union bound,
Pr [ ⊤ ← Vrfy 2 ( 1 λ , s , σ ) ] ≥ 1 − Pr [ ⊥ ← Vrfy ( 1 λ , s , ρ s ) ] − Pr [ ⊥ ← Vrfy ( 1 λ , s , ρ ) ] (87) \Pr\left[\top\leftarrow\operatorname{Vrfy}_2(1^\lambda,s,\sigma)\right] \ge1-\Pr[\bot\leftarrow\operatorname{Vrfy}(1^\lambda,s,\rho_s)]-\Pr[\bot\leftarrow\operatorname{Vrfy}(1^\lambda,s,\rho)] \tag*{(87)} Pr [ ⊤ ← Vrfy 2 ( 1 λ , s , σ ) ] ≥ 1 − Pr [ ⊥ ← Vrfy ( 1 λ , s , ρ s )] − Pr [ ⊥ ← Vrfy ( 1 λ , s , ρ )] (87)
≥ 1 p ( λ ) − negl ( λ ) , (88) \ge\frac{1}{p(\lambda)}-\operatorname{negl}(\lambda), \tag*{(88)} ≥ p ( λ ) 1 − negl ( λ ) , (88)
where we used the correctness of the mini-scheme for the first register, which is untouched by A \mathcal{A} A , and Pr [ ⊤ ← Vrfy ( 1 λ , s , ρ ) ] ≥ 1 p ( λ ) \Pr[\top\leftarrow\operatorname{Vrfy}(1^\lambda,s,\rho)] \ge\frac{1}{p(\lambda)} Pr [ ⊤ ← Vrfy ( 1 λ , s , ρ )] ≥ p ( λ ) 1 for the second register. This breaks the security of the money scheme. This completes the proof of item 1.
Next we show item 2. Let ( Samp , PVer ) (\operatorname{Samp},\operatorname{PVer}) ( Samp , PVer ) be an EV-StatePuzz, where we write PVer \operatorname{PVer} PVer for its verification algorithm in order to distinguish it from the verification algorithm of the signature scheme. We construct a one-time digital signature scheme ( KeyGen , Sign , Ver ) (\operatorname{KeyGen},\operatorname{Sign},\operatorname{Ver}) ( KeyGen , Sign , Ver ) as follows.
KeyGen ( 1 λ ) \operatorname{KeyGen}(1^\lambda) KeyGen ( 1 λ ) : For each b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } , run ( s b , ψ b ) ← Samp ( 1 λ ) (s_b,\psi_b) \leftarrow\operatorname{Samp}(1^\lambda) ( s b , ψ b ) ← Samp ( 1 λ ) . Output v k : = ( s 0 , s 1 ) \mathrm{vk}:=(s_0,s_1) vk := ( s 0 , s 1 ) and s i g k : = ( s i g k 0 , s i g k 1 ) \mathrm{sig}_k:=(\mathrm{sig}_{k_0},\mathrm{sig}_{k_1}) sig k := ( sig k 0 , sig k 1 ) , where s i g k b \mathrm{sig}_{k_b} sig k b is the register containing ψ b \psi_b ψ b .
Sign ( s i g k , m ) \operatorname{Sign}(\mathrm{sig}_k,m) Sign ( sig k , m ) : Output the register s i g k m \mathrm{sig}_{k_m} sig k m , whose state is σ : = ψ m \sigma:=\psi_m σ := ψ m .
Ver ( v k , m , σ ) \operatorname{Ver}(\mathrm{vk},m,\sigma) Ver ( vk , m , σ ) : Run PVer ( 1 λ , s m , σ ) \operatorname{PVer}(1^\lambda,s_m,\sigma) PVer ( 1 λ , s m , σ ) and output its output.
Correctness. An honestly generated signature on m m m is ψ m \psi_m ψ m , which is the answer of the puzzle s m s_m s m , and ( s m , ψ m ) (s_m,\psi_m) ( s m , ψ m ) is distributed as an output of Samp ( 1 λ ) \operatorname{Samp}(1^\lambda) Samp ( 1 λ ) . Thus the correctness immediately follows from the correctness of the EV-StatePuzz.
One-time security. Assume that there exists a QPT A = ( A 1 , A 2 ) \mathcal{A} = (\mathcal{A}_1,\mathcal{A}_2) A = ( A 1 , A 2 ) and a polynomial p p p that breaks the one-time security with probability 1 / p ( λ ) 1/p(\lambda) 1/ p ( λ ) for infinitely many λ \lambda λ . We construct a QPT adversary B \mathcal{B} B against the security of the EV-StatePuzz as follows.
B ( 1 λ , s ∗ ) \mathcal{B}(1^\lambda, s^*) B ( 1 λ , s ∗ ) :
Sample b ∗ ← { 0 , 1 } b^* \leftarrow\{0,1\} b ∗ ← { 0 , 1 } uniformly at random.
Set s b ∗ : = s ∗ s_{b^*} := s^* s b ∗ := s ∗ and run ( s 1 − b ∗ , ψ 1 − b ∗ ) ← Samp ( 1 λ ) (s_{1-b^*}, \psi_{1-b^*}) \leftarrow\operatorname{Samp}(1^\lambda) ( s 1 − b ∗ , ψ 1 − b ∗ ) ← Samp ( 1 λ ) .
Set v k : = ( s 0 , s 1 ) \mathrm{vk} := (s_0,s_1) vk := ( s 0 , s 1 ) and run ( m , s t ) ← A 1 ( v k ) (m,\mathrm{st}) \leftarrow\mathcal{A}_1(\mathrm{vk}) ( m , st ) ← A 1 ( vk ) .
If m = b ∗ m = b^* m = b ∗ , abort. Otherwise, set σ : = ψ 1 − b ∗ \sigma:= \psi_{1-b^*} σ := ψ 1 − b ∗ and run σ ′ ← A 2 ( σ , s t ) \sigma' \leftarrow\mathcal{A}_2(\sigma,\mathrm{st}) σ ′ ← A 2 ( σ , st ) .
Output σ ′ \sigma' σ ′ .
Note that B \mathcal{B} B never uses the answer of the puzzle s ∗ s^* s ∗ : the signing query is answered only when m = 1 − b ∗ m = 1-b^* m = 1 − b ∗ , in which case the signature is ψ 1 − b ∗ \psi_{1-b^*} ψ 1 − b ∗ , which B \mathcal{B} B sampled by itself.
Since s ∗ s^* s ∗ is distributed identically to the puzzle part of a fresh output of Samp ( 1 λ ) \operatorname{Samp}(1^\lambda) Samp ( 1 λ ) , and since the answer ψ b ∗ \psi_{b^*} ψ b ∗ is discarded in the real experiment when m = 1 − b ∗ m = 1-b^* m = 1 − b ∗ , the experiment that B \mathcal{B} B simulates for A \mathcal{A} A conditioned on not aborting is distributed identically to the real one-time security experiment. Moreover, b ∗ b^* b ∗ is uniformly random and independent of the entire execution of A \mathcal{A} A , and in particular of m m m . Let W W W be the event that A \mathcal{A} A wins, i.e., Ver ( v k , 1 − m , σ ′ ) \operatorname{Ver}(\mathrm{vk},1-m,\sigma') Ver ( vk , 1 − m , σ ′ ) outputs ⊤ \top ⊤ , so that Pr [ W ] = 1 / p ( λ ) \Pr[W] = 1/p(\lambda) Pr [ W ] = 1/ p ( λ ) . Conditioned on b ∗ = 1 − m b^* = 1-m b ∗ = 1 − m , which occurs with probability 1 / 2 1/2 1/2 independently of W W W , B \mathcal{B} B does not abort, and A \mathcal{A} A wins if and only if PVer ( 1 λ , s 1 − m , σ ′ ) = PVer ( 1 λ , s ∗ , σ ′ ) \operatorname{PVer}(1^\lambda,s_{1-m},\sigma') = \operatorname{PVer}(1^\lambda,s^*,\sigma') PVer ( 1 λ , s 1 − m , σ ′ ) = PVer ( 1 λ , s ∗ , σ ′ ) outputs ⊤ \top ⊤ . Therefore,
Pr [ ⊤ ← PVer ( 1 λ , s ∗ , ρ ) : ( s ∗ , ψ s ∗ ) ← Samp ( 1 λ ) ρ ← B ( 1 λ , s ∗ ) ] ≥ 1 2 p ( λ ) (89) \Pr\left[
\begin{array}{c}
\top\leftarrow\operatorname{PVer}(1^\lambda,s^*,\rho):\\
(s^*,\psi_{s^*}) \leftarrow\operatorname{Samp}(1^\lambda)\\
\rho\leftarrow\mathcal{B}(1^\lambda,s^*)
\end{array}
\right] \ge\frac{1}{2p(\lambda)} \tag*{(89)} Pr ⊤ ← PVer ( 1 λ , s ∗ , ρ ) : ( s ∗ , ψ s ∗ ) ← Samp ( 1 λ ) ρ ← B ( 1 λ , s ∗ ) ≥ 2 p ( λ ) 1 (89)
for infinitely many λ \lambda λ , which breaks the security of the EV-StatePuzz. This completes the proof of item 2. ∎