A Post-Quantum Interactive Hashing Theorem

A Post-Quantum Interactive Hashing Theorem Céline Chevalier1 , Laurent Holin2 , and Quoc-Huy Vu3

arXiv:2611.06124v1 [quant-ph] 4 Nov 2026

1

CRED, Université Panthéon-Assas, DIENS, École normale supérieure, PSL University, CNRS, Inria, France celine.chevalier@ens.fr 2 DIENS, École normale supérieure, PSL University, CNRS, Inria, France laurent.holin@ens.fr 3 De Vinci Higher Education, De Vinci Research Center, Paris, France quoc.huy.vu@ens.fr

Abstract Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols, including perfectly hiding commitments from one-way permutations [NOVY93]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for 𝖭𝖯 and statistically hiding commitments from arbitrary one-way functions [NOV06, HR07]. In this note, we give a post-quantum security proof for this multi-output interactive hashing protocol with arbitrary relations. AI usage statement. The authors developed an initial approach to quantum rewinding for interactive hashing, combining the framework of Lombardi, Ma, and Spooner [LMS22] with a new coin-regularization technique. The first proof draft based on this approach did not establish the claimed result. The authors then developed a second proof approach based on Huang and Kalai’s memoryless-rewinding framework [HK25]. This approach establishes binding for efficiently verifiable relations. The authors supplied ChatGPT 5.6 with these two drafts and asked it to combine the approaches. ChatGPT-5.6 then produced the current proof, introducing two new ingredients: the error decomposition and error recording. The proof is different from the one the authors had in mind when making this request. Interestingly, the generated proof crucially relies on a technical lemma (Lemma 4.4) proved by the authors for their first approach, although its use in that approach led to a fatal circularity in the parameter choices. ChatGPT-6 was subsequently used for proof review, revision, choosing the parameters, and writing assistance. All mathematical claims and arguments in the final manuscript were independently verified by the authors, who take full responsibility for the content. According to the IACR AI Policy, we declare this work as having Substantial AI contribution.

1

Contents 1 Introduction 1.1 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

2 Preliminaries 2.1 Singular vector algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9

3 Multi-output interactive hashing

10

4 Post-quantum two-opening binding for arbitrary relations 4.1 The extractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Quantum rewinding with the coin trick . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 From normalization errors to recording . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Description of the extractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Analysis of the extractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 The honest tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Error decomposition and its operational interpretations . . . . . . . . . . . . . . . . . 4.2.3 Ideal extraction bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Completion of the binding proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 11 11 14 17 18 18 18 21 22

2

1 Introduction Interactive hashing allows two parties to select a small set containing one party’s private input, while limiting that party’s control over the other outputs. Introduced by Ostrovsky, Venkatesan, and Yung [OVY93], it was used by Naor, Ostrovsky, Venkatesan, and Yung to construct perfectly hiding commitments from one-way permutations [NOVY98]. Its multi-output generalization is a building block in constructions of statistical zeroknowledge arguments for 𝖭𝖯 and statistically hiding commitments from arbitrary one-way functions [NOV06, HNO+ 09]. Interactive hashing also has applications in quantum cryptography. Morimae and Yamakawa [MY23] use a coherent execution of the NOVY protocol to construct remote state preparation secure against classical adversaries, and hence proofs of quantumness, from classically secure full-domain trapdoor permutations. They explicitly left the security of the underlying NOVY construction against quantum adversaries as an open problem [MY23]. Our contribution. We give a post-quantum security proof for the generalized interactive hashing protocol with multi-bit outputs and arbitrary relations, introduced by Nguyen, Ong, and Vadhan [NOV06]. The theorem gives two immediate applications. First, combining the coherent interactive hashing construction of [MY23] with the framework of [BK25], we obtain classical verification of quantum computation from post-quantum secure full-domain trapdoor permutations. This answers an open question of Morimae and Yamakawa [MY23]. Corollary 1.1. There exists a classical verification for quantum computation protocol for every language in 𝖡𝖰𝖯, assuming post-quantum secure full-domain trapdoor permutations. Second, we recover the original NOVY commitment construction in the post-quantum setting. Corollary 1.2. There exists a post-quantum secure perfect hiding commitment scheme, assuming post-quantum secure one-way permutations. Concurrent and independent works. During the preparation of this manuscript, we became aware of two concurrent and independent works establishing post-quantum security of the NOVY bit-commitment scheme from post-quantum one-way permutations. Dupuis et al. [DLM+ 26] prove sum-binding and collapsebinding and use the latter to obtain perfect zero-knowledge classical arguments for 𝖭𝖯 against quantum adversaries. Chen, Wang, and Xie [CWX26] prove quantum sum-binding and extend the construction to efficiently verifiable one-way puzzles with nearly uniform puzzle distributions. They also give an oracle separation ruling out fully black-box constructions of quantum-computation classical-communication (QCCC) commitments from general efficiently verifiable one-way puzzles. Both works analyze the NOVY protocol, whereas our work considers the multi-output interactive hashing protocol of Nguyen, Ong, and Vadhan [NOV06] for arbitrary relations. Although interactive hashing with efficiently verifiable relations suffices for the applications considered here and in the two concurrent works, interactive hashing with arbitrary relations is essential to the constructions and proofs based on one-way functions in [NOV06, HR07]. We therefore expect our interactive hashing theorem to be useful in extending those constructions to the post-quantum setting. A complete post-quantum analysis of those constructions is left for future work.

1.1 Technical overview We give an overview of our proof of post-quantum two-opening binding for the multi-output interactive hashing protocol of [NOV06] between a sender and a receiver. In this protocol, the sender holds a secret string 𝑦 ∈ {0, 1}𝑞 , and the parties interact for 𝑚 ∶= 𝑞 − 𝑘 rounds, where 1 ≤ 𝑘 < 𝑞. In round 𝑖 = 0, … , 𝑚 − 1, the receiver sends a uniformly random hash ℎ𝑖 ∈ 0𝑖 1{0, 1}𝑞−𝑖−1 , and the honest sender replies with the bit 𝑐𝑖 = ℎ𝑖 (𝑦) ∶= ⟨ℎ𝑖 , 𝑦⟩. The resulting transcript 𝜗 determines an affine bijection ≅

𝐶𝜗 ∶ {0, 1}𝑘 ,,,→ {𝑢 ∈ {0, 1}𝑞 ∶ ℎ𝑖 (𝑢) = 𝑐𝑖 for all 0 ≤ 𝑖 < 𝑚}. The form of the hashes makes these 𝑚 equations linearly independent, leaving exactly 2𝑘 compatible strings. The honest sender’s input is one of these strings, and its private output is an index 𝑧 ∈ {0, 1}𝑘 such that 𝐶𝜗 (𝑧) = 𝑦. 3

The two-opening binding property is defined as follows. Fix an arbitrary relation 𝕎 ⊆ {0, 1}𝑞 × 𝒳, where 𝒳 is the witness space, and write 𝕎𝑦 ∶= {𝑥 ∈ 𝒳 ∶ (𝑦, 𝑥) ∈ 𝕎}. We call an execution of a possibly malicious sender against the honest receiver a real execution. Suppose that, after a real execution, a malicious quantum sender 𝑆 ∗ produces, in a single joint measurement, a pair ((𝑥0 , 𝑧0 ), (𝑥1 , 𝑧1 )) satisfying 𝑧0 ≠ 𝑧1 ,

𝑥0 ∈ 𝕎𝐶𝜗 (𝑧0 ) ,

𝑥1 ∈ 𝕎𝐶𝜗 (𝑧1 )

𝑞 with probability at least 𝜀. Then there exists an( extractor ℰ ) that, given a uniformly random challenge 𝑌 ← {0, 1} , 2 𝑘 2 outputs a witness in 𝕎𝑌 with probability Ω 𝜀 ∕(2 𝑞 ) .

Classical proof. We first briefly give an overview of the classical proof of [NOV06], which is based on a rewinding reduction and a combinatorial analysis of the protocol’s transcript tree. A node at level 𝑖, for 0 ≤ 𝑖 ≤ 𝑚, represents a partial transcript 𝑁 = (ℎ0 , 𝑐0 , … , ℎ𝑖−1 , 𝑐𝑖−1 ), and 𝐿𝑖 denotes the set of all such nodes. For 𝑖 < 𝑚, each child has the form (𝑁, ℎ, 𝑐), where ℎ ∈ ℋ𝑖 ∶= 0𝑖 1{0, 1}𝑞−𝑖−1 is the next receiver hash and 𝑐 ∈ {0, 1} is the sender’s response. The strings compatible with the prefix form the set 𝑈(𝑁) ∶= {𝑦 ∈ {0, 1}𝑞 ∶ ℎ𝑗 (𝑦) = 𝑐𝑗 for all 0 ≤ 𝑗 < 𝑖},

|𝑈(𝑁)| = 2𝑞−𝑖 .

Given a uniformly random challenge 𝑌, the extractor interacts with a cheating sender and repeatedly rewinds it to select compatible receiver hash functions ℎ for which the sender’s response satisfies 𝑐 = ℎ(𝑌), thereby keeping 𝑌 in the affine subspace determined by the transcript. A balancing argument controls the efficiency of this steering procedure and the loss in the sender’s double-opening probability. To avoid excessive conditioning, the extractor does not rewind to find compatible hash functions for all 𝑚 rounds. Instead, it executes the last 𝒪(log(𝑞∕𝜀)) rounds honestly (that is, there is no rewinding in these rounds). The analysis shows that, if the sender produces two distinct valid openings with probability 𝜀, the extractor obtains a witness for 𝑌 with probability at least 2−𝑘 𝗉𝗈𝗅𝗒(𝜀∕𝑞). This gives two-opening binding whenever finding a witness for a uniformly random challenge is sufficiently hard. Overview of our quantum proof. The main idea of our proof is to replace classical rewinding with a quantum rewinding procedure that can bias a malicious sender toward the challenge 𝑌. We build on the quantum rewinding framework of [LMS22], which uses the singular-vector transformation techniques of [GSLW19]. However, rewinding may alter the sender’s residual quantum state and its probability of producing two distinct outputs with valid witnesses. Rather than requiring rewinding to preserve this success probability, we develop a method to account for the errors introduced by this rewinding process using recording maps. Our proof consists of four main ingredients: • Coin-regularized quantum rewinding. We introduce an auxiliary coin register to overcome the spectral obstruction in directly applying singular-vector transformation. This yields an efficient rewinding procedure that preserves compatibility with the target 𝑌 on every non-aborting branch. • From normalization errors to recording. We compare the rewound execution with the real execution and identify the normalization errors arising from their difference. Although these errors need not be small individually, an operator Fourier argument allows us to realize them, up to a scalar factor, as the Kraus operators of an efficient recording map. In particular, we show that an error operator can be interpreted as a successful branch operator for a recorded label. • Target switching. Motivated by this recording interpretation, the extractor randomly chooses between a normal strategy with no recording, which rewinds toward 𝑌, and target-switching strategies, which apply the recording map at an intermediate round to obtain a recorded label 𝑍 and subsequently rewind toward 𝑍. Every strategy ends with a fresh honest tail, and the extraction target remains the original 𝑌. • Error decomposition. An exact hybrid identity expresses each scaled branch operator of a real execution as a normal term (i.e., error-free), single-error terms, and a double-error remainder. The normal and 4

single-error terms correspond to the normal and target-switching strategies, respectively. Each doubleerror term corresponds to an experiment with two recordings; on the successful outcomes being analyzed, the recorded labels are distinct and fixed before the honest tail. Fresh receiver randomness exponentially suppresses the probability that both labels remain compatible with the final transcript, allowing us to bound the remainder and conclude that the extraction strategies collectively achieve the desired success probability. We now unpack each one. Coin-regularized quantum rewinding. Our starting point is the quantum rewinding framework of [LMS22], based on the singular-vector transformation techniques of [GSLW19] (QSVT). The basic idea is to coherently transform the sender’s next-message computation to favor a response compatible with the challenge. Fix an intermediate node 𝑁 ∈ 𝐿𝑖 , and write 𝖪𝑁;ℎ,𝑐 for the sender’s next-message Kraus operator corresponding to receiver hash ℎ ∈ ℋ𝑖 and response 𝑐 ∈ {0, 1}, including any fresh workspace initialization. Thus ∑ † 𝖪 𝖪 = 𝖨. For a target 𝑦 ∈ 𝑈(𝑁), define the averaged compatibility operator 𝑐 𝑁;ℎ,𝑐 𝑁;ℎ,𝑐 [ ] ̄ (𝑖) (𝑦) = 𝔼 𝖪† Π 𝖪 . 𝑁;ℎ,ℎ(𝑦) 𝑁;ℎ,ℎ(𝑦) ℎ←ℋ𝑖

This operator measures the sender’s average probability of producing a response 𝑐 compatible with 𝑦, that is, 𝑐 = ℎ(𝑦). However, directly applying the singular-vector transformation of [GSLW19], as used in [LMS22], ̄ (𝑖) (𝑦), whose eigenvalues encounters a subtle obstruction. That is, the averaged compatibility operator Π are the squared singular values of the coherent accepting map constructed from 𝖪𝑁;ℎ,ℎ(𝑦) , may have zero or arbitrarily small eigenvalues. For instance, a malicious sender may, on some quantum state, produce a response incompatible with 𝑦 with probability one. Consequently, the polar factor of the accepting map may fail to be an isometry on the entire sender space, while arbitrarily small positive singular values may render its implementation via QSVT inefficient. Our idea to overcome this obstruction is to introduce an auxiliary coin register. Fix a small parameter 𝜂 ∈ (0, 1∕2) and prepare the coin in the state √ || ⟩ √ ||𝜒𝜂 = 1 − 𝜂 |0⟩ + 𝜂 |1⟩ . Instead of accepting only responses satisfying 𝑐 = ℎ(𝑦), the coin-adjusted compatibility condition is 𝑐 = ℎ(𝑦) ⊕ 𝑟, where 𝑟 is the coin’s measurement outcome. Thus the branch 𝑟 = 0 corresponds to a compatible response, whereas 𝑟 = 1 corresponds to an incompatible response with a small weight 𝜂. We then define the corresponding coherent accepting map as ∑ (√ 1 𝖡𝑁,𝑦 |||𝜓⟩ = √ 1 − 𝜂 |ℎ, 0⟩ 𝖪𝑁;ℎ,ℎ(𝑦) |||𝜓⟩ |ℋ𝑖 | ℎ∈ℋ𝑖 √ ) + 𝜂 |ℎ, 1⟩ 𝖪𝑁;ℎ,1−ℎ(𝑦) |||𝜓⟩ . ̄ (𝑖) (𝑦). Since 0 ⪯ Π ̄ (𝑖) (𝑦) ⪯ 𝖨, Its associated POVM element 𝖰𝑁,𝑦 ∶= 𝖡†𝑁,𝑦 𝖡𝑁,𝑦 satisfies 𝖰𝑁,𝑦 = 𝜂𝖨 + (1 − 2𝜂)Π √ we obtain 𝜂𝖨 ⪯ 𝖰𝑁,𝑦 ⪯ (1 − 𝜂)𝖨. In particular, every singular value of 𝖡𝑁,𝑦 is at least 𝜂, independently of the malicious sender’s strategy. The coin effectively ensures that this transformation is well-defined and efficiently implementable. −1∕2

The rewinding operation. We can now define an ideal rewinding step 𝖱𝖾𝗐𝗂𝗇𝖽𝑦 . Let 𝖵𝑁,𝑦 ∶= 𝖡𝑁,𝑦 𝖰𝑁,𝑦 . Since 𝖰𝑁,𝑦 ⪰ 𝜂𝖨, we have 𝖵†𝑁,𝑦 𝖵𝑁,𝑦 = 𝖨. Thus 𝖵𝑁,𝑦 is an isometry. At a node 𝑁, 𝖱𝖾𝗐𝗂𝗇𝖽𝑦 applies the isometry 𝖵𝑁,𝑦 and measures the hash and coin registers, obtaining (ℎ, 𝑟). If 𝑟 = 1, it aborts. Otherwise, it retains the response 𝑐 = ℎ(𝑦) and continues from the child transcript (𝑁, ℎ, 𝑐) with the post-measurement residual sender state. The non-aborting branch associated with ℎ is √ 1−𝜂 −1∕2 𝑦 𝖠𝑁;ℎ = 𝖪 𝖰 . |ℋ𝑖 | 𝑁;ℎ,ℎ(𝑦) 𝑁,𝑦 5

Consequently, every successful rewinding step preserves the compatibility of 𝑦 with the transcript. We note that the coin does not guarantee that every rewinding step succeeds. In particular, a sender may have no compatible-response amplitude on some input state. Its purpose is instead to make the QSVT efficiently implementable, even in such cases. To implement this map 𝖵𝑁,𝑦 , we use the singular-vector transformation in the coherent form recalled in Lemma 2.2 from [LMS22, GSLW19]. Definition 4.2 and Lemma 4.3 give the formal definition of 𝖱𝖾𝗐𝗂𝗇𝖽𝑦 and its efficient approximate implementation. The normalization error. Although rewinding preserves compatibility with the target, it generally changes the sender’s residual quantum state and the distribution of classical transcript outcomes (ℎ, 𝑐). Rather than proving that rewinding preserves the sender’s success probability directly, we therefore compare the sender’s evolution under rewinding with its evolution in a real execution, keeping track of both the residual quantum state and the probability of each outcome. 1 For a fixed hash function ℎ, write 𝖧𝑁;ℎ = √ 𝖪𝑁;ℎ,ℎ(𝑦) for the corresponding real branch operator. |ℋ𝑖 |

First, consider the balanced case in which the sender’s average probability of producing a response compatible with a target 𝑦 is exactly 1∕2, independently of its quantum state. By its definition, we have ̄ (𝑖) (𝑦) = 𝖨 . Π 2 Then 𝖰𝑁,𝑦 = 𝖨∕2, and the non-aborting rewound branch satisfies 𝑦

𝖠𝑁;ℎ = 𝜁𝖧𝑁;ℎ ,

𝜁 ∶=

√ 2(1 − 𝜂).

Thus, in this balanced case, rewinding amplifies the corresponding real branch by the fixed factor 𝜁. For a general malicious sender, define the normalization-error operator √ 𝖤𝑁,𝑦 ∶= 𝖨 − 2𝖰𝑁,𝑦 . We then have the exact identity

𝑦

𝜁𝖧𝑁;ℎ = 𝖠𝑁;ℎ (𝖨 − 𝖤𝑁,𝑦 ).

(1)

The operator 𝖤𝑁,𝑦 measures the deviation between the operator-valued normalization required by the polar √ ̄ (𝑖) (𝑦) = transformation and the constant normalization 2𝖨 arising in the balanced case. It vanishes when Π 𝖨∕2. Importantly, this normalization error is not an error caused by approximating QSVT: it is present even for the exact polar isometry. Nor can we expect 𝖤𝑁,𝑦 to have small operator norm for every target. A malicious sender may be strongly biased toward or against particular responses. Thus, a direct hybrid argument that bounds the normalization errors individually would not suffice to relate the rewound execution to the real execution. Instead, we establish a collective operator bound using the Fourier structure of interactive hashing, as described next. From normalization errors to recording. Define the bias operator ̄ (𝑖) (𝑦) − 𝖨 . 𝖣(𝑖) (𝑦) ∶= Π 2 𝖨

Since 𝖰𝑁,𝑦 = + (1 − 2𝜂)𝖣(𝑖) (𝑦), the normalization error 𝖤𝑁,𝑦 is a function of the bias operator 𝖣(𝑖) (𝑦). 2 We prove a technical lemma on the operator Fourier bound (Lemma 4.4), which gives ∑

𝖣(𝑖) (𝑦)2 =

𝑦∈𝑈(𝑁)

∑

𝖨 , 2

which also yields 𝖤2𝑁,𝑦 ⪯ 4𝖣(𝑖) (𝑦)2 . Hence 𝑦∈𝑈(𝑁) 𝖤2𝑁,𝑦 ⪯ 2𝖨. This inequality suggests a different way to handle the normalization errors. We can realize each error operator, up to a fixed scalar factor, as the successful branch operator of a recording map. 6

Indeed, the operators 𝖱𝑁,𝑦 ∶=

∑ 𝖤𝑁,𝑦 √ satisfy 𝖱† 𝖱 ⪯ 𝖨. Completing these successful Kraus 𝑦∈𝑈(𝑁) 𝑁,𝑦 𝑁,𝑦 2

operators with an abort outcome defines a CPTP map, which we denote by 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 .√On a successful outcome, the map produces a recorded label 𝑦 and applies the corresponding operator 𝖤𝑁,𝑦 ∕ 2 to the residual sender state. We note that this recording map 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 is efficiently implementable. Its formal definition and efficient implementation are given in Definition 4.5 and Lemma 4.6. Thus a product containing an error operator can be interpreted, up to its scalar factor, as applying the recording map and continuing with the resulting sender state. This is the key observation motivating our extractor. Why the extractor may switch targets. To see how recording leads to extraction, consider a successful real execution followed by a joint output ((𝑥0 , 𝑧0 ), (𝑥1 , 𝑧1 )), with transcript 𝜗. Write 𝑢 ∶= 𝐶𝜗 (𝑧0 ),

𝑣 ∶= 𝐶𝜗 (𝑧1 ),

𝑥0 ∈ 𝕎𝑢 ,

𝑥1 ∈ 𝕎𝑣 .

Here 𝑧0 ≠ 𝑧1 are the 𝑘-bit opening indices, while 𝑢 ≠ 𝑣 are the corresponding 𝑞-bit IH output strings, which we call the endpoints. Both 𝑢 and 𝑣 are compatible with every prefix of this transcript. Along this fixed path, write 𝖧𝑗 for the 𝑦 𝑦 𝑦 real branch operator at round 𝑗, and let 𝖫𝑗 = 𝜁𝖧𝑗 . For 𝑦 ∈ {𝑢, 𝑣}, let 𝖠𝑗 ∶= 𝖠𝑁 ;ℎ and 𝖤𝑗 ∶= 𝖤𝑁𝑗 ,𝑦 denote the 𝑗

𝑗

corresponding rewinding branch and normalization-error operator, where 𝑁𝑗 = (ℎ0 , 𝑐0 , … , ℎ𝑗−1 , 𝑐𝑗−1 ) is the 𝑦 𝑦 transcript’s prefix at round 𝑗. By Equation (1), 𝖫𝑗 = 𝖠𝑗 (𝖨 − 𝖤𝑗 ). Let 𝑦

𝑦

𝑦

𝖠𝑏∶𝑎 = 𝖠𝑏−1 ⋯ 𝖠𝑎 ,

𝖫𝑏∶𝑎 = 𝖫𝑏−1 ⋯ 𝖫𝑎 .

We first compare the scaled real prefix with rewinding toward 𝑣. For the first 𝛼 rounds, where 𝛼 is the prefix length chosen below, a hybrid argument gives ∑ 𝑣 𝑣 𝖫𝛼∶0 = 𝖠𝑣𝛼∶0 − 𝖠𝛼∶𝑗 𝖤𝑗 𝖫𝑗∶0 . 𝑗<𝛼

The normal term 𝖠𝑣𝛼∶0 corresponds to rewinding toward 𝑣 throughout the prefix. This motivates a normal strategy, which rewinds toward the externally chosen target 𝑌. √ Each summand contains a normalization-error operator 𝖤𝑣𝑗 . Since 𝖤𝑣𝑗 ∕ 2 is the branch operator for recording 𝑣, these summands suggest alternative extraction strategies. However, the operator factor 𝖫𝑗∶0 preceding 𝖤𝑣𝑗 is still a scaled real prefix. We therefore apply a second hybrid argument to this prefix, now comparing it with rewinding toward the other endpoint 𝑢: ∑ 𝑢 𝑢 𝖫𝑗∶0 = 𝖠𝑢𝑗∶0 − 𝖠𝑗∶𝑖 𝖤𝑖 𝖫𝑖∶0 . 𝑖<𝑗

Substitution gives the exact error decomposition 𝖫𝛼∶0 = 𝖠𝑣𝛼∶0 −

∑

𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶0

𝑗<𝛼

+

∑

𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶𝑖 𝖤𝑢𝑖 𝖫𝑖∶0 .

(2)

0≤𝑖<𝑗<𝛼

We call 𝖠𝑣𝛼∶0 the normal term, the summands in the first sum single-error terms, and those in the second sum double-error terms. The sum of all double-error terms is the double-error remainder. After the common honest tail and joint output, the normal term √ is a branch of the normal strategy with external target 𝑌 = 𝑣, returning 𝑥1 ∈ 𝕎𝑣 . Each single-error term is 2 times a branch of a target-switching strategy: rewind toward 𝑢, record 𝑍 = 𝑣 at round 𝑗, and then rewind toward 𝑣. The external target remains 𝑌 = 𝑢, so the returned witness is 𝑥0 ∈ 𝕎𝑢 . We will analyze and bound the double-error remainder below, after introducing our extractor, based on this error decomposition.

7

The extractor. The preceding error decomposition motivates an extractor with two types of execution: the normal strategy and the target-switching strategies. Formally, we divide the 𝑚 rounds into a prefix of length 𝛼 and a fresh honest tail of length 𝛽. For a fixed absolute 0 < 𝜃 < 1∕4 and a sufficiently large absolute constant 𝐵, set 𝜃 𝜂= , 𝛽 = min{𝑚, ⌈log2 (𝐵∕𝜀)⌉}, 𝛼 = 𝑚 − 𝛽. 𝑞 The ideal extractor of Construction 4.8 proceeds as follows, using ideal rewinding and recording maps and aborting if any invoked procedure aborts. 1. Choose a uniform strategy index 𝑠 ∈ {0, … , 𝛼}. 2. If 𝑠 = 0, apply 𝖱𝖾𝗐𝗂𝗇𝖽𝑌 for all 𝛼 prefix rounds. If 𝑗 > 0, apply 𝖱𝖾𝗐𝗂𝗇𝖽𝑌 for the first 𝑗 − 1 rounds, call 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 at the current node to obtain 𝑍, and apply 𝖱𝖾𝗐𝗂𝗇𝖽𝑍 for the remaining prefix rounds. Intuitively, index 0 selects the normal strategy, and index 𝑗 + 1 selects target-switching strategy to record at round 𝑗, for 0 ≤ 𝑗 < 𝛼. 3. Run the last 𝛽 rounds honestly with fresh independent hashes. Invoke and measure the sender’s jointoutput procedure once to obtain ((𝑥0 , 𝑧0 ), (𝑥1 , 𝑧1 )). Return 𝑥𝑏 if 𝐶𝜗 (𝑧𝑏 ) = 𝑌 and 𝑧0 ≠ 𝑧1 , for some 𝑏 ∈ {0, 1}; otherwise return ⊥. To show that the extractor works, we analyze particular branches of these strategies. For the normal strategy, it counts branches in which the external challenge 𝑌 equals the second IH output string 𝑣 = 𝐶𝜗 (𝑧1 ), so the extractor returns 𝑥1 . For a target-switching strategy, it counts branches in which the original target is 𝑢 and the recording map outputs 𝑍 = 𝑣, so the extractor returns 𝑥0 , the witness for 𝑢 = 𝐶𝜗 (𝑧0 ). Why two errors suffice. It remains to bound the double-error remainder in Equation (2). Consider a double-error term with normalization-error operators 𝖤𝑢𝑖 and 𝖤𝑣𝑗 at rounds 𝑖 < 𝑗. The recording maps have √ √ successful Kraus operators 𝖱𝑁𝑖 ,𝑢 = 𝖤𝑢𝑖 ∕ 2 and 𝖱𝑁𝑗 ,𝑣 = 𝖤𝑣𝑗 ∕ 2. Since 𝖫𝑖∶0 = 𝜁 𝑖 𝖧𝑖∶0 , we have 𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶𝑖 𝖤𝑢𝑖 𝖫𝑖∶0 = 2𝜁 𝑖 𝖠𝑣𝛼∶𝑗 𝖱𝑁𝑗 ,𝑣 𝖠𝑢𝑗∶𝑖 𝖱𝑁𝑖 ,𝑢 𝖧𝑖∶0 . Apart from the scalar factor 2𝜁 𝑖 , the right-hand side is the prefix Kraus operator for the branch (𝑈, 𝑉) = (𝑢, 𝑣) of the following experiment. It executes the first 𝑖 rounds as in a real execution, applies the recording map to obtain 𝑈, rewinds toward 𝑈 until round 𝑗, applies the recording map to obtain 𝑉, and rewinds toward 𝑉 until the end of the rewinding phase. Both recorded labels 𝑈, 𝑉 are fixed before the last 𝛽 rounds. On the jointly valid outputs counted by this term, they equal the distinct terminal endpoints 𝑢, 𝑣, so both must belong to the final interactive-hashing output set. We show in Lemma 4.9 that two distinct strings fixed before the honest tail remain simultaneously compatible after its 𝛽 rounds with probability at most 2−𝛽 , even conditioned on the complete preceding history and an arbitrary residual sender state. Consequently, each double-error term has norm at most 2𝜁 𝑖 2−𝛽∕2 . This explains why two levels of the error decomposition suffice. A single-error term need not have small norm, but corresponds to a target-switching strategy. Each double-error term instead admits an interpretation involving two recorded labels, whose simultaneous survival through the honest ∑ tail is unlikely. Moreover, since 𝜁 > 1 is bounded away from one by an absolute constant, 0≤𝑖<𝑗<𝛼 𝜁 𝑖 = 𝒪(𝜁 𝛼 ). Hence, by ( ) the triangle inequality, the double-error remainder has norm at most 𝒪 𝜁 𝛼 2−𝛽∕2 . If 𝛼 > 0, then 2−𝛽 ≤ 𝜀∕𝐵, √ so choosing 𝐵 sufficiently large makes this bound a small fraction of 𝜁 𝛼 𝜀, the lower bound on the norm of the scaled real prefix. If 𝛼 = 0, the double-error remainder is empty. Applying the triangle inequality to Equation (2), we conclude that the normal and single-error terms cannot all be small. These terms correspond to the normal and target-switching strategies, respectively. Their interpretations as physical extraction experiments, together with Cauchy–Schwarz and the random choice of 𝜀2

index, yield the ideal extraction bound 𝑝ext = Ω( 𝑘 2 ), as established in Proposition 4.12. 2 𝑞

8

Finally, replacing the ideal rewinding and recording maps with their efficient approximate implementations incurs an additive loss of 𝒪(𝑞𝜈), which can be controlled to be at most half the ideal lower bound. Writing 𝑝̃ ext for the extraction probability of the efficient implementation, we obtain 𝑝̃ ext = Pr [𝑋 ∈ 𝕎𝑌 ] = Ω(

𝜀2 2𝑘 𝑞 2

),

as claimed.

2 Preliminaries We write 𝜆 for the security parameter and 𝑈𝑑 for a uniformly random 𝑑-bit string. Relations. A relation 𝕎 is a set of pairs (𝑥, 𝑤) where 𝑥 is an instance and 𝑤 is a witness. The corresponding language ℒ𝕎 is the set of instances 𝑥 for which there exists a witness 𝑤 such that (𝑥, 𝑤) ∈ 𝕎.

2.1 Singular vector algorithms In this section, we recall a selection of algorithms from [LMS22] rewinding framework. Notation. Throughout this section we will consider the interaction between two binary projective measurements 𝖠 = (Π𝖠 , 𝖨 − Π𝖠 ), 𝖡 = (Π𝖡⟩ , 𝖨 − Π𝖡 ). ⟩Let Π𝖠 Π𝖡 = 𝖵Σ𝖶† be a fixed singular value decomposition with | | singular values 𝑠𝑗 . We write |||𝑣𝑗,1 and |||𝑤𝑗,1 for the left and right singular vectors with 𝑠𝑗 > 0, and define the ⟩ ⟩ | | Jordan subspace 𝒮𝑗 ∶= span(|||𝑣𝑗,1 , |||𝑤𝑗,1 ). When 𝑠𝑗 < 1 the subspace 𝒮𝑗 is two-dimensional and also contains ⟩ ⟩ || || 2 ||𝑣𝑗,0 , ||𝑤𝑗,0 , which are singular vectors of (𝖨 − Π𝖠 )(𝖨 − Π𝖡 ) with the same singular value 𝑠𝑗 . Let 𝑝𝑗 ∶= 𝑠𝑗 . Singular-vector transformation. Theorem 2.1 (Singular vector transformation [LMS22, Theorem 6.1]). There is a uniform family of circuits √ {𝖳𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆𝑎,𝛿 }𝑎,𝛿∈(0,1] with 𝖴𝖠 and 𝖴𝖡 gates and of size 𝑂(log(1∕𝛿)∕ 𝑎) such that the following holds. For a left | ⟩ | ⟩ singular vector |||𝑣𝑗,1 of Π𝖠 Π𝖡 with singular value 𝑠𝑗 , whenever 𝑎 ≤ 𝑠𝑗2 , the circuit 𝖳𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆𝑎,𝛿 [𝖠 → 𝖡](|||𝑣𝑗,1 ) ⟩ | returns the corresponding right singular vector |||𝑤𝑗,1 with success probability at least 1 − 𝛿. Each Jordan subspace 𝒮𝑗 is invariant under 𝖳𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆𝑎,𝛿 for every 𝑎. The next lemma gives a coherent version of Theorem 2.1. Lemma 2.2 (Coherent fixed-runtime singular-vector transformation). Let 𝖠 = (Π𝖠 , 𝖨 − Π𝖠 ), 𝖡 = (Π𝖡 , 𝖨 − Π𝖡 ) be projective measurements on a common state space 𝒮. For any threshold 0 < 𝑎 < 1, define ∑ | ⟩⟨ | ∑ | ⟩⟨ ||𝑣𝑗,1 𝑣𝑗,1 || , ||𝑤𝑗,1 𝑣𝑗,1 ||| . 𝖯𝑎 = 𝖳𝑎 = | | | | 𝑠𝑗2 ≥𝑎

𝑠𝑗2 ≥𝑎

Here 𝖯𝑎 projects onto the input singular vectors whose squared singular values are at least 𝑎. The partial isometry 𝖳𝑎 specifies the ideal action of 𝖳𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆𝑎 [𝖠 → 𝖡] on this subspace: ⟩ | ⟩ | 𝖳𝑎 |||𝑣𝑗,1 = |||𝑤𝑗,1 (𝑠𝑗2 ≥ 𝑎), 𝖳†𝑎 𝖳𝑎 = 𝖯𝑎 . In particular, 𝖳𝑎 is an isometry on image(𝖯𝑎 ). For every 0 < 𝛿 < 1, the transformation admits a coherent efficient implementation with auxiliary registers initialized to |0⟩. Write ˜ |||𝜓⟩ = 𝖳𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆𝑎,𝛿 [𝖠 → 𝖡](|||𝜓⟩ |0⟩). 𝖳 For every |||𝜓⟩ ∈ image(𝖯𝑎 ), this implementation satisfies | | ‖‖‖𝖳 ‖‖ ˜| ‖ ||𝜓⟩ − (𝖳𝑎 ||𝜓⟩) |0⟩‖‖ ≤ 𝛿‖ ||𝜓⟩ ‖. The circuit uses 𝑂(𝑎−1∕2 log(2∕𝛿)) calls to the coherent measurements. 9

† Proof. Apply √ [GSLW19, Theorem 26] to2 a SVD Π𝖡 Π𝖠 = 𝖶Σ𝖵 , with input projector Π𝖠 , output projector Π𝖡 , threshold 𝑎, and projected error 𝜏 = 𝛿 ∕8. Coherent measurement access means 𝖴𝖣 = Π𝖣 ⊗ 𝖷 + (𝖨 − Π𝖣 ) ⊗ 𝖨, where 𝐷 ∈ {𝐴, 𝐵} and 𝖷 is the bit-flip gate. The phase construction of [GSLW19, Lemma 19] computes and uncomputes this auxiliary qubit, returning it to |0⟩. Let 𝖢0 denote this unitary circuit with exact phase rotations, and define its isometry by 𝖶0 |||𝜓⟩ = 𝖢0 (|||𝜓⟩ |0⟩).

Thus 𝖶0 includes both the system and auxiliary outputs and satisfies 𝖶†0 𝖶0 = 𝖨. [GSLW19, Theorem 26] | | implies |||1 − (⟨𝜓 ||| 𝖳†𝑎 ⊗ ⟨0|)𝖶0 |||𝜓⟩||| ≤ 𝜏 for every unit |||𝜓⟩ ∈ image(𝖯𝑎 ). Since both output vectors have norm one, [ ] ‖‖ || ‖2 † ‖‖𝖶0 |𝜓⟩ − (𝖳𝑎 |||𝜓⟩) |0⟩‖‖‖ = 2 − 2 Re (⟨𝜓 ||| 𝖳𝑎 ⊗ ⟨0|)𝖶0 |||𝜓⟩ ≤ 2𝜏 = 𝛿 2 ∕4, giving the desired bound. With singular-value threshold

√ ) ( log(1∕𝜏) 𝑎 and error 𝜏, the construction uses 𝑑 = 𝒪( √ ) = 𝒪 𝑎−1∕2 log(2∕𝛿)

coherent measurement calls, also by [GSLW19, Theorem 26].

𝑎

3 Multi-output interactive hashing Definition 3.1. A multi-output interactive hashing scheme is a polynomial-time protocol ⟨𝑆𝖨𝖧 , 𝑅𝖨𝖧 ⟩ where both parties receive common inputs (1𝑞 , 1𝑘 ), 𝑆𝖨𝖧 receives a private input 𝑦 ∈ {0, 1}𝑞 , with the common output being a circuit 𝐶 ∶ {0, 1}𝑘 → {0, 1}𝑞 , and the private output of 𝑆𝖨𝖧 being a string 𝑧 ∈ {0, 1}𝑘 . We denote 𝑞 to be the input length and 𝑘 to be the output length. The protocol ⟨𝑆𝖨𝖧 , 𝑅𝖨𝖧 ⟩ must satisfy the following security properties: 1. (Correctness) For all 𝑅∗ and all 𝑦 ∈ {0, 1}𝑞 , letting 𝐶 = ⟨𝑆𝖨𝖧 (𝑦), 𝑅∗ ⟩(1𝑞 , 1𝑘 ) and 𝑧 = 𝗈𝗎𝗍𝗉𝗎𝗍𝑆𝖨𝖧 ⟨𝑆𝖨𝖧 (𝑦), 𝑅∗ ⟩,

(3)

we have that 𝐶(𝑧) = 𝑦. 2. (Perfect hiding) For all 𝑅∗ , (𝑉, 𝑍) is distributed identically to (𝑉, 𝑈𝑘 ), where 𝑉 = 𝗏𝗂𝖾𝗐𝑅∗ ⟨𝑆𝖨𝖧 (𝑈𝑞 ), 𝑅∗ ⟩ and 𝑍 = 𝗈𝗎𝗍𝗉𝗎𝗍𝑆𝖨𝖧 ⟨𝑆𝖨𝖧 (𝑈𝑞 ), 𝑅∗ ⟩.

(4)

3. (Post-quantum computational two-opening binding) Let 𝕎 be an arbitrary relation, and write 𝕎𝑦 ∶= {𝑥 ∶ (𝑦, 𝑥) ∈ 𝕎}. Let 𝐶 = ⟨𝑆 ∗ , 𝑅𝖨𝖧 ⟩(1𝑞 , 1𝑘 ) and ((𝑥0 , 𝑧0 ), (𝑥1 , 𝑧1 )) = 𝗈𝗎𝗍𝗉𝗎𝗍𝑆∗ ⟨𝑆 ∗ , 𝑅𝖨𝖧 ⟩,

(5)

where 𝗈𝗎𝗍𝗉𝗎𝗍𝑆∗ denotes one application of the sender’s output procedure to its residual state, followed by one measurement of the designated register containing the two output pairs. There exist a constant 𝑐 > 0 and a 𝖰𝖯𝖳 oracle algorithm 𝒜 such that, for every 𝖰𝖯𝖳 sender 𝑆 ∗ , every relation 𝕎, and every inverse-polynomial 0 < 𝜀 ≤ 1, the following implication holds. If [ ] Pr 𝑥0 ∈ 𝕎𝐶(𝑧0 ) ∧ 𝑥1 ∈ 𝕎𝐶(𝑧1 ) ∧ 𝑧0 ≠ 𝑧1 > 𝜀, (6) where the above probability is over the randomness and measurements of 𝑅𝖨𝖧 and 𝑆 ∗ , then [ ∗ ] Pr 𝑞 𝒜𝑆 (𝑦, 1𝑞 , 1𝑘 , 𝜀) ∈ 𝕎𝑦 > 2−𝑘 ⋅ (𝜀∕𝑞)𝑐 . 𝑦←{0,1}

Protocol 3.2 (Multi-output interactive hashing ⟨𝑆𝖨𝖧 , 𝑅𝖨𝖧 ⟩ [NOV06]). Inputs: 1. Input length 1𝑞 and output length 1𝑘 , both given as common input. 10

(7)

2. String 𝑦 ∈ {0, 1}𝑞 , given as private input to sender 𝑆𝖨𝖧 . Protocol: 𝑅𝖨𝖧 : Select ℎ0 , ℎ1 , … , ℎ𝑞−𝑘−1 such that each ℎ𝑖 is a random vector over 𝔽2 of the form 0𝑖 1{0, 1}𝑞−𝑖−1 (i.e., 𝑖 zeros followed by a one, and random choice for the last 𝑞 − 𝑖 − 1 positions). For 𝑗 = 0, … , 𝑞 − 𝑘 − 1, do the following: 𝑅𝖨𝖧 → 𝑆𝖨𝖧 ∶ Send ℎ𝑗 .

(8)

𝑆𝖨𝖧 → 𝑅𝖨𝖧 ∶ Send 𝑐𝑗 = ⟨ℎ𝑗 , 𝑦⟩.

(9)

Output: • Common output is a circuit 𝐶 ∶ {0, 1}𝑘 → {0, 1}𝑞 , computing an affine transformation whose image is {𝑦 ∶ ⟨ℎ𝑗 , 𝑦⟩ = 𝑐𝑗 ∀𝑗 = 0, … , 𝑞 − 𝑘 − 1}. • Output of 𝑆𝖨𝖧 is a string 𝑧 ∈ {0, 1}𝑘 such that 𝐶(𝑧) = 𝑦. (In fact, 𝑧 can be taken to be the last 𝑘 bits of 𝑦.) It is easy to see the correctness of Protocol 3.2. Its statistical hiding property follows from the classical analysis in [NOV06]. In the rest of the paper, we give a post-quantum security proof for the two-opening binding property.

4 Post-quantum two-opening binding for arbitrary relations Definitions. Fix integers 𝑞 ≥ 2, 1 ≤ 𝑘 < 𝑞, and let 𝑚 = 𝑞 − 𝑘. Fix a relation family 𝕎 ∶= {𝕎𝑦 }𝑦∈{0,1}𝑞 . Write ℎ(𝑦) ∶= ⟨ℎ, 𝑦⟩ for ℎ, 𝑦 ∈ {0, 1}𝑞 . We define the tree of transcripts as follows. • For 0 ≤ 𝑖 < 𝑞, the set of hash functions of the form 0𝑖 1{0, 1}𝑞−𝑖−1 is denoted as ℋ𝑖 , that is ℋ𝑖 ∶= {0𝑖 1𝑤 ∣ 𝑤 ∈ {0, 1}𝑞−𝑖−1 }. • Nodes. A node at level 𝑖 is a prefix transcript 𝑁 of length 𝑖, i.e., 𝑁 = (ℎ0 , 𝑐0 , … , ℎ𝑖−1 , 𝑐𝑖−1 ). Let 𝐿𝑖 denote the set of nodes at level 𝑖. For 𝑁 ∈ 𝐿𝑖 define 𝑈(𝑁) ∶= {𝑦 ∈ {0, 1}𝑞 ∶ ∀𝑗 < 𝑖, ℎ𝑗 (𝑦) = 𝑐𝑗 },

|𝑈(𝑁)| = 2𝑞−𝑖 .

• Transcript. A final transcript 𝜗 determines a leaf 𝑁(𝜗) ∈ 𝐿𝑚 . Its output map is the efficiently computable affine bijection ≅

𝐶𝜗 ∶ {0, 1}𝑘 ,,,→ 𝑈(𝑁(𝜗)). Thus 𝑧 ∈ {0, 1}𝑘 denotes an output index, and 𝐶𝜗 (𝑧) denotes the corresponding IH output. Let 𝑝 denote the probability, in a real execution followed by the single measured joint output, of a wellformed, non-aborting output satisfying 𝑧0 ≠ 𝑧1 ,

𝑥0 ∈ 𝕎𝐶𝜗 (𝑧0 ) ,

𝑥1 ∈ 𝕎𝐶𝜗 (𝑧1 ) .

(10)

We reserve ⊥ as a failure symbol outside 𝕎𝑦 , so ⊥ ∉ 𝕎𝑦 for every 𝑦. Theorem 4.1 (Two-opening binding of multi-output interactive hashing). The multi-output interactive hashing protocol described in Protocol 3.2 satisfies post-quantum computational two-opening binding as defined in Definition 3.1.

4.1 The extractor 4.1.1 Quantum rewinding with the coin trick Notation. Fix an input string 𝑦 ∈ {0, 1}𝑞 . Fix a round 0 ≤ 𝑖 < 𝑚, a node 𝑁 ∈ 𝐿𝑖 . Let 𝒮 be one padded sender space containing all its private, response, and workspace registers throughout the protocol. Known zero workspaces are included from the outset; sender unitaries act as the identity on registers reserved for later rounds. All sender-space operators below are defined on this whole space, and all operations act as the identity on any inaccessible reference. Fresh reduction ancillas are initialized to |0⟩ whenever introduced. 11

1

• Let ℋ𝑖 denote a register with basis {|ℎ⟩ ∶ ℎ ∈ ℋ𝑖 }, and let |+𝐻 ⟩ℋ𝑖 ∶= √ |ℋ𝑖 | (ℎ)

• Let 𝖲𝑖

∑

ℎ∈ℋ𝑖 |ℎ⟩.

denote the unitary on 𝒮 that the sender applies at round 𝑖 on input a hash function ℎ ∈ ℋ𝑖 , (ℎ)

abbreviating 𝖲𝑖,𝑁 at the fixed node. (ℎ)

• Let 𝒞𝑖 denote the subregister of 𝒮 that the sender measures to obtain its response 𝑐𝑖 after applying 𝖲𝑖 . √ √ | ⟩ • Let ℛ𝑖 be a single-qubit ancilla register. For 𝜂 ∈ (0, 1∕2), let |||𝜒𝜂 ℛ ∶= 1 − 𝜂 |0⟩ + 𝜂 |1⟩. 𝑖 (𝑖)

Let 𝖯𝑐 = |𝑐⟩⟨𝑐|𝒞𝑖 ⊗ 𝖨, and define the hash-controlled sender unitary by 𝖳𝑁 = Define the projector:

∑

ℎ∈ℋ𝑖 |ℎ⟩⟨ℎ|

(ℎ)

⊗ 𝖨ℛ𝑖 ⊗ 𝖲𝑖,𝑁 .

(ℎ)† (

(𝑖)

Πℎ (𝑦) ∶= 𝖲𝑖

) (ℎ) |⟨ℎ, 𝑦⟩⟩⟨⟨ℎ, 𝑦⟩|𝒞𝑖 ⊗ 𝖨 𝖲𝑖 .

(𝑖)

Intuitively, Πℎ (𝑦) projects onto the subspace of 𝒮 where the sender’s response is compatible with 𝑦 under the hash function ℎ (that is, its output 𝑐𝑖 equals ⟨ℎ, 𝑦⟩). (𝑖) (𝑖) Define the binary projective measurement 𝖢(𝑖) = (Π𝖢 , 𝖨 − Π𝖢 ) where (𝑖)

Π𝖢 =

∑ ℎ∈ℋ𝑖

(𝑖)

( (𝑖) |ℎ⟩⟨ℎ|ℋ𝑖 ⊗ |0⟩⟨0|ℛ𝑖 ⊗ Πℎ (𝑦) ) (𝑖) + |1⟩⟨1|ℛ𝑖 ⊗ (𝖨 − Πℎ (𝑦)) ,

(𝑖)

and 𝖴(𝑖) = (Π𝖴 , 𝖨 − Π𝖴 ) where | ⟩⟨ | (𝑖) Π𝖴 = |+𝐻 ⟩⟨+𝐻 |ℋ𝑖 ⊗ |||𝜒𝜂 𝜒𝜂 |||ℛ ⊗ 𝖨𝒮 . 𝑖

Both are projectors on ℋ𝑖 ⊗ ℛ𝑖 ⊗ 𝒮. Write 𝑟𝑖 for the coin label at round 𝑖. Intuitively, 𝑟𝑖 = 0 means “the sender’s answer is compatible”, otherwise 𝑟𝑖 = 1 means “the sender’s answer is incompatible”. Define the averaged compatibility operator and the bias operator by ̄ (𝑖) (𝑦) ∶= Π

1 ∑ (𝑖) Π (𝑦), |ℋ𝑖 | ℎ∈ℋ ℎ 𝑖

̄ (𝑖) (𝑦) − 𝖨 . 𝖣(𝑖) (𝑦) ∶= Π 2 ̄ (𝑖) (𝑦) from 𝖨∕2. We suppress the fixed The operator 𝖣(𝑖) (𝑦) is the bias operator: it measures the deviation of Π [ (𝑖) ] ̄ (𝑦) . The node 𝑁 in this notation. For a residual state 𝜌, its averaged compatibility probability is Tr 𝜌Π (𝑖) (𝑖) ̄ (𝑦) is a positive contraction on the same space. operators Πℎ (𝑦) are projectors on 𝒮, and their average Π The next-message Kraus operator for response 𝑐 with hash input ℎ, and its corresponding POVM element, are (𝑖) (ℎ) 𝖪𝑁;ℎ,𝑐 = 𝖯𝑐 𝖲𝑖,𝑁 , 𝖬𝑁;ℎ,𝑐 = 𝖪†𝑁;ℎ,𝑐 𝖪𝑁;ℎ,𝑐 . For fixed 𝑁, ℎ, the operators {𝖬𝑁;ℎ,𝑐 }𝑐∈{0,1} form a POVM, since ∑ 𝑐∈{0,1}

𝖬𝑁;ℎ,𝑐 =

∑ 𝑐∈{0,1}

𝖪†𝑁;ℎ,𝑐 𝖪𝑁;ℎ,𝑐 = 𝖨𝒮 .

| ⟩ (𝑖) The coin-regularized accepting map 𝖡𝑁,𝑦 prepares |+𝐻 ⟩ |||𝜒𝜂 , applies Π𝖢 , and then applies 𝖳𝑁 . Its branch expansion is ∑ (√ 1 𝖡𝑁,𝑦 |||𝜓⟩ = √ 1 − 𝜂 |ℎ, 0⟩ 𝖪𝑁;ℎ,ℎ(𝑦) |||𝜓⟩ |ℋ𝑖 | ℎ∈ℋ𝑖 √ ) + 𝜂 |ℎ, 1⟩ 𝖪𝑁;ℎ,1−ℎ(𝑦) |||𝜓⟩ . 12

(11)

The coin trick. Using ⟨

1 , ⟨+𝐻 |ℎ⟩ = √ ||ℋ || | 𝑖|

| ⟩ √ 𝜒𝜂 |||0 = 1 − 𝜂,

⟨

| ⟩ √ 𝜒𝜂 |||1 = 𝜂,

we get 𝖰𝑁,𝑦 ∶= 𝖡†𝑁,𝑦 𝖡𝑁,𝑦 =

) 1 ∑ ( (𝑖) (𝑖) (1 − 𝜂)Πℎ (𝑦) + 𝜂(𝖨 − Πℎ (𝑦)) |ℋ𝑖 | ℎ∈ℋ 𝑖

̄ (𝑖) (𝑦) = 1 𝖨 + (1 − 2𝜂)𝖣(𝑖) (𝑦). = 𝜂𝖨 + (1 − 2𝜂)Π 2

Consequently,

(12)

| ⟩⟨ | (𝑖) (𝑖) (𝑖) Π𝖴 Π𝖢 Π𝖴 = |+𝐻 ⟩⟨+𝐻 |ℋ𝑖 ⊗ |||𝜒𝜂 𝜒𝜂 |||ℛ ⊗ 𝖰𝑁,𝑦 . 𝑖

(𝑖) On image(Π𝖴 ), this product acts as 𝖰𝑁,𝑦 on the sender register while fixing the prepared hash and coin states.

Moreover,

𝜂𝖨 ⪯ 𝖰𝑁,𝑦 ⪯ (1 − 𝜂)𝖨. The coin trick gives a lower bound on every singular value on this input space, independently of the unknown sender state. Definition 4.2 (Ideal rewinding step 𝖱𝖾𝗐𝗂𝗇𝖽). At a node 𝑁 ∈ 𝐿𝑖 , for 𝑦 ∈ 𝑈(𝑁) and the fixed coin parameter 𝜂, the ideal procedure 𝖱𝖾𝗐𝗂𝗇𝖽𝑦 acts on the supplied sender state as follows: | ⟩ 1. Initialize. Prepare the hash register in |+𝐻 ⟩ and the coin register in |||𝜒𝜂 . 2. Transform. Apply the ideal action of 𝖳𝗋𝖺𝗇𝗌𝖿𝗈𝗋𝗆𝜂 [𝖴(𝑖) → 𝖢(𝑖) ] from Lemma 2.2. 3. Sender response. Apply 𝖳𝑁 . 4. Measure and advance. Measure (ℎ, 𝑟). If 𝑟 = 1, return ⊥. Otherwise retain the response 𝑐 = ℎ(𝑦) and the resulting sender state, and move to (𝑁, ℎ, 𝑐). Before measurement, its isometry on the sender space is −1∕2

𝖵𝑁,𝑦 = 𝖡𝑁,𝑦 𝖰𝑁,𝑦 ,

𝖵†𝑁,𝑦 𝖵𝑁,𝑦 = 𝖨.

Its non-aborting branch operator is 𝑦 𝖠𝑁;ℎ =

√ 1−𝜂 −1∕2 𝖪𝑁;ℎ,ℎ(𝑦) 𝖰𝑁,𝑦 . √ |ℋ𝑖 |

(13)

Lemma 4.3 (Efficient implementation of 𝖱𝖾𝗐𝗂𝗇𝖽). At every intermediate node 𝑁 ∈ 𝐿𝑖 , 0 ≤ 𝑖 < 𝑚, for 𝑦 ∈ 𝑈(𝑁) and 0 < 𝜈 < 1, the CPTP map of 𝖱𝖾𝗐𝗂𝗇𝖽𝑦 defined in Definition 4.2 can be approximated efficiently with error at ( ) most 𝜈, using 𝒪 𝜂 −1∕2 log(2∕𝜈) queries to the sender’s next-message unitaries and their adjoints. Proof. Apply Lemma 2.2 with 𝖠 = 𝖴(𝑖) , 𝖡 = 𝖢(𝑖) , 𝑎 = 𝜂, and 𝛿 = 𝜈∕2. By the coin trick, every squared singular (𝑖) (𝑖) value on image(Π𝖴 ) is at least 𝜂, so 𝖯𝑎 = Π𝖴 , where 𝖯𝑎 is defined in Lemma 2.2. It remains to show that (𝑖)

(𝑖)

phase operations for the two projectors Π𝖴 and Π𝖢 can be implemented efficiently with a constant number (𝑖)

of calls to the sender’s unitaries and their adjoints. For Π𝖴 , no queries are needed: unprepare the known hash and coin states, apply the phase conditional on both registers being zero, and prepare the hash and coin (𝑖) states again. For Π𝖢 , define the known response projector ∑ (𝑖) 𝖬𝑦 = |ℎ, 𝑟⟩⟨ℎ, 𝑟| ⊗ 𝖯ℎ(𝑦)⊕𝑟 . ℎ∈ℋ𝑖 , 𝑟∈{0,1}

(𝑖)

(𝑖)

Since Π𝖢 = 𝖳†𝑁 𝖬𝑦 𝖳𝑁 , each phase operation for Π𝖢 requires one call to the sender’s next-message unitary, a known response phase, and one call to its adjoint. Thus, the coherent implementation of 𝖱𝖾𝗐𝗂𝗇𝖽𝑦 approximates 𝖵𝑁,𝑦 within error 𝜈∕2. The circuit uses ( −1∕2 ) 𝒪 𝜂 log(2∕𝜈) oracle calls. 13

4.1.2 From normalization errors to recording Next, we prove the following operator Fourier bound. Lemma 4.4 (Operator Fourier bound). For every intermediate node 𝑁 ∈ 𝐿𝑖 , 0 ≤ 𝑖 < 𝑚, ∑

𝖣(𝑖) (𝑦)2 =

𝑦∈𝑈(𝑁)

𝖨 . 2

(14)

Furthermore, √ there is an efficient CPTP map with a classical outcome, whose successful label-𝑦 branch has Kraus operator 2𝖣(𝑖) (𝑦). Proof. Recall that every ℎ ∈ ℋ𝑖 has the form ℎ = 0𝑖 1𝑤 where 𝑤 ∈ {0, 1}𝑞−𝑖−1 . Define (ℎ)†

(𝑖)

(𝑖)

(ℎ)

𝖠𝑤 = 𝖲𝑖,𝑁 (𝖯0 − 𝖯1 )𝖲𝑖,𝑁 . The operator 𝖠𝑤 is a Hermitian unitary, so 𝖠2𝑤 = 𝖨. We also write 𝖠ℎ ∶= 𝖠𝑤 for ℎ = 0𝑖 1𝑤. 𝖠ℎ depends on the sender’s strategy but not on the target 𝑦. The 𝑦-dependence enters only through the character (−1)⟨ℎ,𝑦⟩ : (𝑖)

Πℎ (𝑦) =

1( 2

) 𝖨 + (−1)ℎ(𝑦) 𝖠ℎ .

Squaring the bias operator: 𝖣(𝑖) (𝑦)2 =

∑ 1 ′ (−1)⟨ℎ⊕ℎ , 𝑦⟩ 𝖠ℎ 𝖠ℎ′ . 4|ℋ𝑖 |2 ℎ,ℎ′ ∈ℋ 𝑖

Average over 𝑦 ∈ 𝑈(𝑁): 𝔼

𝖣(𝑖) (𝑦)2 =

𝑦∈𝑈(𝑁)

∑ [ ] 1 ′ 𝔼 (−1)⟨ℎ⊕ℎ , 𝑦⟩ 𝖠ℎ 𝖠ℎ′ . 2 4|ℋ𝑖 | ℎ,ℎ′ ∈ℋ 𝑦∈𝑈(𝑁)

(15)

𝑖

Cross terms (ℎ ≠ ℎ′ ). For 𝑦 ∈ 𝑈(𝑁), write 𝑦 = (𝑦<𝑖 , 𝑏, 𝑡), where 𝑏 = 𝑦𝑖 ∈ {0, 1} and 𝑡 = (𝑦𝑖+1 , … , 𝑦𝑞−1 ) ∈ {0, 1}𝑞−𝑖−1 . We note that for every pair (𝑏, 𝑡), there is a unique 𝑦 𝑏,𝑡 ∈ 𝑈(𝑁) whose suffix from coordinate 𝑖 onward is (𝑏, 𝑡), since the first 𝑖 transcript equations uniquely determine the preceding coordinates. Thus (𝑏, 𝑡) ↦→ 𝑦 𝑏,𝑡 is a bijection, and a uniform 𝑦 ∈ 𝑈(𝑁) has a uniform suffix (𝑏, 𝑡). For distinct ℎ = 0𝑖 1𝑤 and ℎ′ = 0𝑖 1𝑤′ , we have 𝑤 ≠ 𝑤′ and ′ 𝑏,𝑡 ′ (−1)⟨ℎ⊕ℎ ,𝑦 ⟩ = (−1)⟨𝑤⊕𝑤 ,𝑡⟩ . Choose a coordinate where 𝑤 ⊕ 𝑤′ is nonzero. Pairing each 𝑡 with the string obtained by flipping that coordinate cancels the two character values. Hence [ ] ′ 𝔼 (−1)⟨ℎ⊕ℎ , 𝑦⟩ = 0. 𝑦∈𝑈(𝑁)

Diagonal terms (ℎ = ℎ′ ). Here ℎ ⊕ ℎ = 0, so (−1)⟨0,𝑦⟩ = 1, and 𝖠ℎ 𝖠ℎ = 𝖠2ℎ = 𝖨. Result. Only diagonal terms survive in Equation (15): 𝔼

𝖣(𝑖) (𝑦)2 =

𝑦∈𝑈(𝑁)

∑ 𝖨 1 𝖨 = . 2 4|ℋ𝑖 | 4|ℋ𝑖 | ℎ∈ℋ 𝑖

Since |𝑈(𝑁)| = 2|ℋ𝑖 |, this proves Equation (14). To construct the CPTP map, define ˆ𝑡 = 𝖠

1 ∑ (−1)⟨𝑤,𝑡⟩ 𝖠𝑤 . |ℋ𝑖 | 𝑤

ˆ 𝑡 ∕2. For an input sender state |||𝜓⟩, the CPTP map is defined as follows: Then 𝖣(𝑖) (𝑦 𝑏,𝑡 ) = (−1)𝑏 𝖠

14

1. Prepare and reflect. Prepare a uniform 𝑤-register and apply 𝖠𝑤 controlled by that register, obtaining 1 ∑ |𝑤⟩ 𝖠𝑤 |||𝜓⟩ . √ |ℋ𝑖 | 𝑤 2. Fourier transform. Apply Hadamards to the 𝑤-register. The resulting state is ∑ ˆ 𝑡 |||𝜓⟩ . |𝑡⟩ 𝖠 𝑡

∑

1

3. Relabel. Append a qubit |−⟩ = √

2

𝑏

(−1)𝑏 |𝑏⟩, then compute 𝑦 𝑏,𝑡 coherently, giving 1 ∑ | ⟩ ˆ || (−1)𝑏 |||𝑦 𝑏,𝑡 𝖠 √ 𝑡 |𝜓⟩ . 2 𝑏,𝑡

ˆ 𝑡 ∕2, the resulting isometry is 4. Measurement. Using 𝖣(𝑖) (𝑦 𝑏,𝑡 ) = (−1)𝑏 𝖠 √ ∑ 𝖥𝑁 = 2 𝖥†𝑁 𝖥𝑁 = 𝖨. |𝑦⟩ 𝖣(𝑖) (𝑦),

(16)

𝑦∈𝑈(𝑁)

Measuring 𝑦 gives the claimed CPTP map. Finally, we note that the circuit uses one sender call and one adjoint call. Definition 4.5 (Ideal recording map 𝖱𝖾𝖼𝗈𝗋𝖽). Fix an intermediate node 𝑁 ∈ 𝐿𝑖 , 0 ≤ 𝑖 < 𝑚, and the coin parameter 0 < 𝜂 < 1∕2. For a string 𝑧 ∈ 𝑈(𝑁), define the normalization error operator √ 𝖤𝑁,𝑧 = 𝖨 − 2𝖰𝑁,𝑧 . The ideal recording map 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 takes as input the sender’s internal state 𝜌, and acts as follows: the quantum measurement with outcomes 𝑈(𝑁) ∪ {⊥}, specified by the Kraus operators 1. Measure. Perform √ ∑ 𝖱𝑁,𝑧 = 𝖤𝑁,𝑧 ∕ 2 for 𝑧 ∈ 𝑈(𝑁) and 𝖱𝑁,⊥ = (𝖨 − 𝑧 𝖱†𝑁,𝑧 𝖱𝑁,𝑧 )1∕2 . 2. Successful output. On outcome 𝑍 = 𝑧, return the recorded label 𝑧 and retain the residual sender state 𝜌𝑧 =

𝖤𝑁,𝑧 𝜌𝖤𝑁,𝑧 [ ], Tr 𝖤2𝑁,𝑧 𝜌

Pr[𝑍 = 𝑧] =

1 [ 2 ] Tr 𝖤𝑁,𝑧 𝜌 . 2

3. Abort. On the abort outcome, discard all local registers and return ⊥. The following lemma proves that 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 defines a CPTP map and can be approximated efficiently. Lemma 4.6 (Efficient implementation of 𝖱𝖾𝖼𝗈𝗋𝖽). At every intermediate node 𝑁 ∈ 𝐿𝑖 , 0 ≤ 𝑖 < 𝑚, the normalization-error operators in Definition 4.5 satisfy ∑ 𝖤2𝑁,𝑦 ⪯ 2𝖨. (17) 𝑦∈𝑈(𝑁)

Hence 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 , including its classical output and abort outcome, is a CPTP map. Furthermore, for any 0 < 𝜈 < 1, the CPTP map of 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 can be approximated efficiently with error at most 𝜈. Proof. We first show that 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 defines a CPTP map. By Claim 4.7, 𝖤2𝑁,𝑦 ⪯ 4𝖣(𝑖) (𝑦)2 . Summing over 𝑦 ∈ 𝑈(𝑁) and applying Lemma 4.4 gives Equation (17). Next, we implement the recording map 𝖱𝖾𝖼𝗈𝗋𝖽𝑁 in two stages. First, √ Fourier recording applies the coherent isometry 𝖥𝑁 from Equation (16), whose label-𝑧 branch operator is 2𝖣(𝑖) (𝑧). Second, a conditional correction

15

applies a quantum operation controlled by the label register, with successful Kraus operator 𝖦𝑁,𝑧 constructed as follows. Let 𝑎 = 1 − 2𝜂, and define √ )−1 ( 𝖷𝑁,𝑦 = −2𝑎𝖣(𝑖) (𝑦), 𝖦𝑁,𝑦 = −𝑎 𝖨 + 𝖨 − 𝖷𝑁,𝑦 . ̄ (𝑖) (𝑦) ⪯ 𝖨, the bias operator satisfies −𝖨∕2 ⪯ 𝖣(𝑖) (𝑦) ⪯ 𝖨∕2. Hence ‖𝖷𝑁,𝑦 ‖ ≤ 𝑎 < 1 and Since 0 ⪯ Π 𝑎 √ 𝖨 − 𝖷𝑁,𝑦 ⪰ (1 − 𝑎)𝖨 = 2𝜂𝖨. This also yields ‖𝖦𝑁,𝑦 ‖ ≤ < 1. Recall that 𝖨 − 𝖷𝑁,𝑦 = 2𝖰𝑁,𝑦 by 1+ 1−𝑎

Equation (12), and the definition of 𝖤𝑁,𝑦 , we have

√ √ )−1 1 ( 𝖦𝑁,𝑦 2𝖣(𝑖) (𝑦) = √ 𝖨 + 𝖨 − 𝖷𝑁,𝑦 𝖷𝑁,𝑦 2 √ 𝖨 − 𝖨 − 𝖷𝑁,𝑦 𝖤𝑁,𝑦 = = √ . √ 2 2

(18)

On failure, discard all local registers and return ⊥; on success, measure the label register and return its outcome together with the residual sender state. Thus applying the correction 𝖦𝑁,𝑦 after a successful Fourier recording 𝖥𝑁 realizes Definition 4.5. Finally, we give an efficient approximation to this ideal recording map. In fact, it suffices to approximate the correction 𝖦𝑁,𝑦 coherently, controlled by the recorded label 𝑦. For |𝑥| < 1, the binomial series gives (2𝑛)

∑

1 = 𝑐𝑛 𝑥 𝑛−1 , √ 1 + 1 − 𝑥 𝑛≥1 Its coefficients satisfy 𝑐𝑛 ≥ 0 and

∑

𝑐𝑛 ∶=

𝑛

4𝑛 (2𝑛 − 1)

.

‖‖

‖‖

𝑐 = 1. Since ‖‖𝖷𝑁,𝑦 ‖‖ ≤ 𝑎 < 1, the truncated polynomial 𝑛≥1 𝑛 (𝑑)

𝖦𝑁,𝑦 ∶= −𝑎

𝑑 ∑

𝑐𝑛 𝖷𝑛−1 𝑁,𝑦

𝑛=1

satisfies

∑ ‖‖ ‖‖ ‖‖𝖦𝑁,𝑦 − 𝖦(𝑑) ‖≤𝑎 𝑐𝑛 𝑎𝑛−1 ≤ 𝑎𝑑+1 . 𝑁,𝑦 ‖ ‖ ‖ 𝑛>𝑑 ( ) As 𝑎 = 1 − 2𝜂 ≤ 𝑒−2𝜂 , a degree 𝑑 = 𝒪 𝜂 −1 log(2∕𝜈) suffices to make this error at most 𝜈∕4. We implement this polynomial using the linear-combination and product constructions of [GSLW19, Lemmas 52 and 53]. The Fourier representation in the proof of Lemma 4.4 gives a uniform block encoding of 2𝖣(𝑖) (𝑦), and hence of 𝖷𝑁,𝑦 . By the product construction [GSLW19, Lemma 53], using separate ancilla registers gives block encodings of the powers 𝖷𝑛−1 𝑁,𝑦 . ∑𝑑 Next, apply the linear-combination construction with blocks −𝖷𝑛−1 𝑎𝑐𝑛 ≤ 𝑁,𝑦 and weights 𝑎𝑐𝑛 . Since 𝑛=1 (𝑑)

𝑎 < 1, assign the remaining weight to a dummy zero block. The resulting block encoding of 𝖦𝑁,𝑦 has normalization one and requires no amplitude amplification. The label dependence enters only through efficiently computable parity phases, so the construction is coherent in 𝑦. A controlled response reflection uses a forward sender call, a controlled known response phase, and an adjoint sender call. Thus, the block (𝑑) encoding of 𝖦𝑁,𝑦 uses polynomially many gates and sender queries. Write the ideal and polynomial successful recording operators as 𝖱𝑁 ∶=

∑ 𝑦∈𝑈(𝑁)

Since 𝖥𝑁 is an isometry,

|𝑦⟩ 𝖱𝑁,𝑦 ,

⎛ ∑ ⎞ (𝑑) (𝑑) 𝖱𝑁 ∶= ⎜ |𝑦⟩⟨𝑦| ⊗ 𝖦𝑁,𝑦 ⎟ 𝖥𝑁 . ⎝𝑦∈𝑈(𝑁) ⎠

‖‖ ‖‖ ‖ ‖‖ ‖‖𝖱𝑁 − 𝖱(𝑑) ‖ ≤ sup ‖‖‖𝖦𝑁,𝑦 − 𝖦(𝑑) ‖ ≤ 𝜈∕4. 𝑁 ‖ 𝑁,𝑦 ‖ ‖ ‖ 𝑦∈𝑈(𝑁) ‖ ‖ 16

Hence, the approximation error does not depend on the number of labels. The coefficients 𝑐𝑛 can be computed exactly in polynomial time. Let 𝑇 be the number of non-oracle (𝑑) elementary gates in the circuit implementing 𝖱𝑁 . Implement each gate within operator-norm distance 𝜈∕(4𝑇) of its ideal operation. A hybrid argument then bounds the total operator error by 𝜈∕4. This yields a successful contraction ˜ 𝖱𝑁 satisfying ‖‖˜ ‖‖ ‖‖𝖱𝑁 − 𝖱𝑁 ‖‖ ≤ 𝜈∕2. Completing the ideal successful recording contraction 𝑅𝑁 and its approximation 𝑅˜𝑁 with abort outcomes, while discarding all local registers on abort, yields CPTP maps differing by at most 𝜈. Measuring the recorded label cannot increase this error. Claim 4.7. 𝖤2𝑁,𝑦 ⪯ 4𝖣(𝑖) (𝑦)2 . Proof. Let 𝑎 = 1 − 2𝜂 ∈ (0, 1) and Λ =

√ 𝖨 + 2𝑎𝖣(𝑖) (𝑦). Since Λ ⪰ 0, we have ‖(𝖨 + Λ)−1 ‖ ≤ 1. Moreover,

(𝖨 + Λ)𝖤𝑁,𝑦 = 𝖨 − Λ2 = −2𝑎𝖣(𝑖) (𝑦), so

𝖤𝑁,𝑦 = −2𝑎(𝖨 + Λ)−1 𝖣(𝑖) (𝑦).

Consequently, for every vector |||𝜓⟩, ‖𝖤𝑁,𝑦 |||𝜓⟩ ‖ ≤ 2𝑎‖𝖣(𝑖) (𝑦) |||𝜓⟩ ‖ ≤ 2‖𝖣(𝑖) (𝑦) |||𝜓⟩ ‖. Since both operators are Hermitian, this implies 𝖤2𝑁,𝑦 ⪯ 4𝖣(𝑖) (𝑦)2 . 4.1.3 Description of the extractor Fix a constant 0 < 𝜃 < 1∕4 and an integer 𝐵 ≥ 2 sufficiently large. Let 𝜂=

𝜃 , 𝑞

⌈ 𝐵⌉ }, 𝛽 = min{𝑚, log2 𝜀

𝜈 = Θ(

𝜀2 ). 2𝑘 (𝑞 + 1)3

(19)

Let 𝛼 = 𝑚 − 𝛽 ≥ 0. Note that 2𝛽 < 2𝐵∕𝜀, and 2−𝛽 ≤ 𝜀∕𝐵 whenever 𝛼 > 0. Construction 4.8 (Extractor). In the following, 𝖱𝖾𝗐𝗂𝗇𝖽 and 𝖱𝖾𝖼𝗈𝗋𝖽 from Definitions 4.2 and 4.5 are implemented ∗ 𝑆∗ efficiently with error at most 𝜈. On input (𝜎𝗂𝗇 ; 𝑌, 1𝑞 , 1𝑘 , 𝜀), the extractor ℰ𝑆 uses the parameters in Equation (19), does the following: 1. Choose a uniform strategy index 𝑠 ∈ {0, … , 𝛼}. 2. Rewound prefix. • If 𝑠 = 0: run 𝖱𝖾𝗐𝗂𝗇𝖽𝑌 at rounds 0, … , 𝛼 − 1. • If 𝑠 > 0: let 𝑗 = 𝑠 − 1 be the recording round. Run 𝖱𝖾𝗐𝗂𝗇𝖽𝑌 at rounds 0, … , 𝑗 − 1; apply 𝖱𝖾𝖼𝗈𝗋𝖽𝑁𝑗 to obtain 𝑍; run 𝖱𝖾𝗐𝗂𝗇𝖽𝑍 at rounds 𝑗, … , 𝛼 − 1. 3. Honest continuation. At node 𝑁 ∈ 𝐿𝛼 , choose random ℎ𝛼 ← ℋ𝛼 , … , ℎ𝛼+𝛽−1 ← ℋ𝛼+𝛽−1 , and query 𝑆 ∗ ˜ = (𝑁, ℎ𝛼 , 𝑐𝛼 , … , ℎ𝛼+𝛽−1 , 𝑐𝛼+𝛽−1 ) ∈ 𝐿𝑞−𝑘 . These hashes are fresh and along the way to arrive at node 𝑁 independent of the preceding history. 4. Output. Invoke and measure the sender’s joint-output procedure to obtain ((𝑥0 , 𝑧0 ), (𝑥1 , 𝑧1 )). Return 𝑥𝑏 if 𝑧0 ≠ 𝑧1 and 𝐶𝜗 (𝑧𝑏 ) = 𝑌 for some 𝑏 ∈ {0, 1}; otherwise return ⊥.

17

4.2 Analysis of the extractor 4.2.1 The honest tail Lemma 4.9 (Few bad descendants). Consider a node 𝑁 ∈ 𝐿𝛼 and two classical strings 𝑢 ≠ 𝑣 fixed before the last 𝛽 rounds. Consider the continuation of the protocol for 𝛽 further rounds with an honest receiver, resulting in a random descendant leaf 𝑁 ′ ∈ 𝐿𝛼+𝛽 . Then, [ ] Pr 𝑢, 𝑣 ∈ 𝑈(𝑁 ′ ) ≤ 2−𝛽 . The probability includes the receiver’s fresh hashes and the sender’s measurement outcomes. Proof. If either string is outside 𝑈(𝑁), the probability is zero. Otherwise, let 𝑑 = 𝑢 ⊕ 𝑣 ≠ 0 and consider any round 𝑡 ∈ {𝛼, … , 𝛼 + 𝛽 − 1}, conditioned that both strings are still compatible with the current node 𝑁𝑡 . First, we note that the suffix 𝑑≥𝑡 is nonzero. Indeed, if it were zero, back-substitution into the equalities ⨁𝑞−1 0 = ⟨ℎ𝑠 , 𝑑⟩ = 𝑑𝑠 ⊕ 𝓁=𝑠+1 (ℎ𝑠 )𝓁 𝑑𝓁 for 𝑠 < 𝑡, which follow from compatibility, would force 𝑑𝑡−1 , … , 𝑑0 to be zero as well, giving 𝑑 = 0. Write the fresh hash as ℎ𝑡 = 0𝑡 1𝑤, where 𝑤 is uniform. Consider two cases: • If 𝑑>𝑡 ≠ 0, then ⟨ℎ𝑡 , 𝑑⟩ = 𝑑𝑡 ⊕ ⟨𝑤, 𝑑>𝑡 ⟩ is uniform. • If 𝑑>𝑡 = 0, then 𝑑𝑡 = 1, so the two hash values always differ. Thus, we always have Pr [ℎ𝑡 (𝑢) = ℎ𝑡 (𝑣)] ≤

ℎ𝑡 ←ℋ𝑡

1 . 2

Both strings can survive this round only if their hash values agree, regardless of the[ sender’s response or residual ] state. Applying this conditional bound successively over the 𝛽 rounds gives Pr 𝑢, 𝑣 ∈ 𝑈(𝑁 ′ ) ≤ 2−𝛽 . 4.2.2 Error decomposition and its operational interpretations Denote a complete transcript/output outcome as ( ) 𝜔 = 𝜗, ((𝑥0 , 𝑧0 ), (𝑥1 , 𝑧1 )) , where 𝜗 = (ℎ0 , 𝑐0 , … , ℎ𝑚−1 , 𝑐𝑚−1 ) is the full transcript. Let 𝒢 be the set of these outcomes satisfying Equation (10), and define their ordered endpoints by 𝑢 ∶= 𝐶𝜗 (𝑧0 ),

𝑣 ∶= 𝐶𝜗 (𝑧1 ).

Here 𝑧0 , 𝑧1 ∈ {0, 1}𝑘 are output indices; the corresponding 𝑞-bit IH outputs (𝑢, 𝑣), opened by the witnesses (𝑥0 , 𝑥1 ), are called the endpoints. For 𝜔 ∈ 𝒢, these endpoints are distinct and compatible with every prefix of 𝜗. √ Let 𝜁 = 2(1 − 𝜂). At a selected round 𝑗 < 𝛼, let 1 𝖧𝑗 = √ 𝖪𝑁𝑗 ;ℎ𝑗 ,𝑐𝑗 , |ℋ𝑗 |

𝖫𝑗 = 𝜁𝖧𝑗 . 𝑦

Thus 𝖧𝑗 is the real branch operator and 𝖫𝑗 its scaled version. Let 𝖠𝑗 denote the branch Equation (13) for the 𝑦

fixed hash and reply, and let 𝖤𝑗 = 𝖤𝑁𝑗 ,𝑦 . For 𝑦 ∈ {𝑢, 𝑣}, compatibility gives the exact factorization 𝑦

𝖫𝑗 = 𝖠𝑗 𝑦

𝑦

√ 𝑦 𝑦 2𝖰𝑁𝑗 ,𝑦 = 𝖠𝑗 (𝖨 − 𝖤𝑗 ).

(20)

𝑦

Let 𝖠𝑏∶𝑎 = 𝖠𝑏−1 ⋯ 𝖠𝑎 , 𝖫𝑏∶𝑎 = 𝖫𝑏−1 ⋯ 𝖫𝑎 , and 𝖧𝑏∶𝑎 = 𝖧𝑏−1 ⋯ 𝖧𝑎 , with an empty product equal to 𝖨. Lemma 4.10 (Error decomposition). For every such path and ordered pair of compatible endpoints, 𝖫𝛼∶0 = 𝖠𝑣𝛼∶0 − +

∑

𝛼−1 ∑

𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶0

𝑗=0

𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶𝑖 𝖤𝑢𝑖 𝖫𝑖∶0 .

0≤𝑖<𝑗<𝛼

18

(21)

Proof. For any composable operator sequences 𝖷𝑗 , 𝖸𝑗 , a hybrid argument replacing one factor at a time gives 𝖷𝑏∶0 − 𝖸𝑏∶0 =

∑

𝖸𝑏∶𝑗+1 (𝖷𝑗 − 𝖸𝑗 )𝖷𝑗∶0 .

𝑗<𝑏

Apply this identity and Equation (20), first with endpoint 𝑣, to obtain ∑ 𝑣 𝑣 𝖫𝛼∶0 = 𝖠𝑣𝛼∶0 − 𝖠𝛼∶𝑗 𝖤𝑗 𝖫𝑗∶0 . 𝑗<𝛼

Apply the same identity with endpoint 𝑢 to each remaining scaled real prefix to obtain: ∑ 𝑢 𝑢 𝖫𝑗∶0 = 𝖠𝑢𝑗∶0 − 𝖠𝑗∶𝑖 𝖤𝑖 𝖫𝑖∶0 . 𝑖<𝑗

The two equalities together prove Equation (21). For the rest of the proof, we define the following notation and terminology. • In the error decomposition in Equation (21), 𝖠𝑣𝛼∶0 is the normal term, the summands in the first sum are single-error terms, and those in the second sum are double-error terms. The sum of all double-error terms is the double-error remainder. • A recorded label is a 𝑞-bit measurement outcome of 𝖱𝖾𝖼𝗈𝗋𝖽. A successful recorded label belongs to 𝑈(𝑁) at the recording node 𝑁. 𝑆∗ • Fix a purification |||𝜓⟩ of the sender’s initial input 𝜎𝗂𝗇 . For a fixed prefix, let 𝖳𝜔 be the Kraus operator for the last 𝛽 honest rounds and the measured joint output specified by 𝜔.

For any path-dependent prefix operator 𝖯𝜔 , write 1∕2

⎛∑ 2⎞ ‖𝖳𝖯‖𝒢 ∶= ⎜ ‖𝖳𝜔 𝖯𝜔 |||𝜓⟩‖ ⎟ ⎝𝜔∈𝒢 ⎠

.

We call this the restricted branch norm. • Let 𝑝norm be the success probability of the normal strategy with ideal primitives and no recording, and 𝑝𝑗 be that of the target-switching strategy with recording at round 𝑗, for 0 ≤ 𝑗 < 𝛼. Both measure the probability of returning a witness for a uniform original target 𝑌, conditioned on strategy index 𝑠 = 0 and 𝑠 = 𝑗 + 1, respectively. We next give an operational interpretation of the terms in Equation (21). The key observation is that the 𝑦 normalization error itself provides a way to obtain a new rewinding target. Although 𝖤𝑗 can have negative √ 𝑦 eigenvalues, 𝖤𝑗 ∕ 2 is the successful branch operator of 𝖱𝖾𝖼𝗈𝗋𝖽𝑁𝑗 for outcome 𝑦. Thus, up to explicit scalar factors, the normal term and the single-error terms correspond to successful branches of the ideal extractor, while the double-error terms correspond to branches of a two-record experiment. Lemma 4.11. The restricted branch norms of the terms in Equation (21) satisfy (22)

‖𝖳𝖫𝛼∶0 ‖𝒢2 = 𝜁 2𝛼 𝑝,

(23)

‖𝖳𝖠𝑣𝛼∶0 ‖𝒢2 ≤ 2𝑞 𝑝norm , ‖𝖳𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶0 ‖𝒢2 ≤ 2𝑞+1 𝑝𝑗 , ‖𝖳𝖠𝑣𝛼∶𝑗 𝖤𝑣𝑗 𝖠𝑢𝑗∶𝑖 𝖤𝑢𝑖 𝖫𝑖∶0 ‖𝒢2 ≤ 4𝜁 2𝑖 2−𝛽

(24) (𝑖 < 𝑗).

(25)

Proof. The real execution. For Equation (22), 𝖫𝛼∶0 = 𝜁 𝛼 𝖧𝛼∶0 , so summing good-output branch probabilities of the real execution gives 𝜁 2𝛼 𝑝.

19

The normal term: no recording. For Equation (23), consider the ideal extractor without recording. For an outcome 𝜔 ∈ 𝒢, its branch on input 𝑌 = 𝑣 rewinds toward 𝑣 throughout the prefix, then executes the honest continuation and returns 𝑥1 ∈ 𝕎𝑣 . For uniform 𝑌 ∈ {0, 1}𝑞 , let 𝑋 be the string returned by this strategy. Then ∑ 𝑝norm = Pr [𝑋 ∈ 𝕎𝑌 ] ≥ Pr [𝑌 = 𝑣] Pr [𝜔 ∈ 𝒢, 𝐶𝜗 (𝑧1 ) = 𝑣 ||| 𝑌 = 𝑣] 𝑣∈{0,1}𝑞 ⏟⎴⎴⏟⎴⎴⏟ 2−𝑞

∑‖ ‖‖𝖳𝜔 𝖠𝑣 |||𝜓⟩‖‖‖2 = 2−𝑞 𝛼∶0 ‖ ‖ 𝜔∈𝒢

‖ ‖2 = 2−𝑞 ‖‖‖𝖳𝖠𝑣𝛼∶0 ‖‖‖ . 𝒢 The inequality follows from {𝜔 ∈ 𝒢, 𝑌 = 𝑣} ⊆ {𝑋 ∈ 𝕎𝑌 }: on this event, the extractor returns 𝑋 = 𝑥1 ∈ 𝕎𝑌 . A single-error term: one recording. For Equation (24), fix the strategy that records at round 𝑗, and select its branches with 𝑌 = 𝑢 and recording outcome 𝑍 = 𝑣. That is, the extractor first applies 𝖱𝖾𝗐𝗂𝗇𝖽𝑢 in rounds 0, … , 𝑗 − 1, records 𝑣 at node 𝑁𝑗 , and applies 𝖱𝖾𝗐𝗂𝗇𝖽𝑣 in rounds 𝑗, … , 𝛼 − 1. By Definition 4.5, its successful branch is √ 𝖳𝜔 𝖠𝑣𝛼∶𝑗 (𝖤𝑣𝑗 ∕ 2)𝖠𝑢𝑗∶0 |||𝜓⟩ . The recorded label changes the subsequent rewinding target. However, the requested witness remains a witness for 𝑌 = 𝑢. On every counted output, the output pair contains 𝑥0 ∈ 𝕎𝑢 , which the extractor returns. For uniform 𝑌 ∈ {0, 1}𝑞 , let 𝑋 be the string returned by this strategy. Then ∑ 𝑝𝑗 = Pr [𝑋 ∈ 𝕎𝑌 ] ≥ Pr [𝑌 = 𝑢] Pr [𝜔 ∈ 𝒢, 𝐶𝜗 (𝑧0 ) = 𝑢, 𝑍 = 𝐶𝜗 (𝑧1 ) ||| 𝑌 = 𝑢] 𝑞 𝑢∈{0,1} ⏟⎴⎴⏟⎴⎴⏟ 2−𝑞

‖‖2 𝖤𝑣𝑗 ∑ ‖‖‖‖ ‖ 𝑣 𝑢 | ‖‖𝖳𝜔 𝖠𝛼∶𝑗 √ 𝖠𝑗∶0 ||𝜓⟩‖‖‖ ‖‖ ‖‖ 2 𝜔∈𝒢 ‖ ‖ ‖ 𝑣 𝑣 𝑢 ‖‖2 ‖ −𝑞−1 ‖‖𝖳𝖠𝛼∶𝑗 𝖤𝑗 𝖠𝑗∶0 ‖‖ . =2 ‖𝒢 ‖ = 2−𝑞

The inequality follows from the fact that {𝜔 ∈ 𝒢, 𝑌 = 𝑢, 𝑍 = 𝑣} ⊆ {𝑋 ∈ 𝕎𝑌 }: on this event, the extractor returns 𝑋 = 𝑥0 ∈ 𝕎𝑢 = 𝕎𝑌 . The condition 𝑍 = 𝑣 restricts the outcomes of the recording map from Definition 4.5. A double-error term: a two-recording experiment. For Equation (25), consider the following experiment. 1. Run rounds 0, … , 𝑖 − 1 honestly, reaching 𝑁𝑖 . 2. Apply 𝖱𝖾𝖼𝗈𝗋𝖽𝑁𝑖 to obtain 𝑈, then run 𝖱𝖾𝗐𝗂𝗇𝖽𝑈 in rounds 𝑖, … , 𝑗 − 1. 3. Apply 𝖱𝖾𝖼𝗈𝗋𝖽𝑁𝑗 to obtain 𝑉, then run 𝖱𝖾𝗐𝗂𝗇𝖽𝑉 in rounds 𝑗, … , 𝛼 − 1. 4. Run the last 𝛽 rounds honestly, then invoke and measure the sender’s joint-output procedure. 5. Abort on any 𝖱𝖾𝖼𝗈𝗋𝖽 or 𝖱𝖾𝗐𝗂𝗇𝖽 failure. Its branch with recorded labels (𝑈, 𝑉) = (𝑢, 𝑣) is √ √ 𝖳𝜔 𝖠𝑣𝛼∶𝑗 (𝖤𝑣𝑗 ∕ 2)𝖠𝑢𝑗∶𝑖 (𝖤𝑢𝑖 ∕ 2)𝖧𝑖∶0 |||𝜓⟩ .

20

Let 𝑁 ′ be the leaf reached after the honest continuation. Using 𝖫𝑖∶0 = 𝜁 𝑖 𝖧𝑖∶0 , we obtain ‖2 ‖‖ 𝑣 𝑣 𝑢 𝑢 ‖‖𝖳𝖠𝛼∶𝑗 𝖤𝑗 𝖠𝑗∶𝑖 𝖤𝑖 𝖫𝑖∶0 ‖‖‖ ‖𝒢 ‖ ‖ ‖‖2 𝖤𝑣𝑗 𝖤𝑢𝑖 ∑ ‖‖‖ ‖ 𝑣 𝑢 | ‖‖𝖳𝜔 𝖠𝛼∶𝑗 √ 𝖠𝑗∶𝑖 √ 𝖧𝑖∶0 ||𝜓⟩‖‖‖ = 4𝜁 2𝑖 ‖‖ ‖‖ 2 2 𝜔∈𝒢 ‖ ‖ = 4𝜁 2𝑖 Pr [𝜔 ∈ 𝒢, 𝑈 = 𝑢, 𝑉 = 𝑣] ∑ ] [ | ≤ 4𝜁 2𝑖 Pr [𝑁𝛼 = 𝑁, 𝑈 = 𝑎, 𝑉 = 𝑏] Pr 𝑎, 𝑏 ∈ 𝑈(𝑁 ′ ) ||| 𝑁𝛼 = 𝑁, 𝑈 = 𝑎, 𝑉 = 𝑏 𝑁∈𝐿𝛼 ⏟⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⏟⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⎴⏟ 𝑎,𝑏∈{0,1}𝑞 , 𝑎≠𝑏 ≤2−𝛽

≤ 4𝜁 2𝑖 2−𝛽 . The first inequality follows from the fact that {𝜔 ∈ 𝒢, 𝑈 = 𝑢, 𝑉 = 𝑣} ⊆ {𝑈 ≠ 𝑉, 𝑈, 𝑉 ∈ 𝑈(𝑁 ′ )}. The second inequality follows from Lemma 4.9. This proves Equation (25). 4.2.3 Ideal extraction bound We now bound the double-error remainder. Proposition 4.12 (Ideal extraction bound). Let 𝑝ext denote the success probability of the extractor in Construction 4.8, using ideal implementations of its subroutines. If 𝑝 ≥ 𝜀, then for a sufficiently large fixed 𝐵, 𝑝ext = Ω(

𝜀2 ). 2𝑘 𝑞 2

(26)

Proof. Applying the triangle inequality to Equation (21) and using Lemma 4.11, we obtain √ ∑√ ⎞ ⎛√ √ 𝜁 𝛼 𝑝 ≤ 2𝑞∕2 ⎜ 𝑝norm + 2 𝑝𝑗 ⎟ + 21−𝛽∕2 𝑗<𝛼

⎝

∑

(27)

𝜁𝑖 .

0≤𝑖<𝑗<𝛼

⎠

We first bound the double-error remainder. Since 𝑞 ≥ 2, 𝜂 = 𝜃∕𝑞, and 𝜃 < 1∕4, we have 𝜁 = √ 2 − 𝜃 > 1. Consequently, ∞ ∑ ∑ 𝑖 𝛼 𝜁 ≤𝜁 (𝑟 − 1)𝜁 −𝑟 0≤𝑖<𝑗<𝛼

=

𝑟=2 𝜁𝛼

(𝜁 − 1)2

√

2(1 − 𝜂) ≥

= 𝒪(𝜁 𝛼 ).

If 𝛼 > 0, our choice of 𝛽 ensures that 2−𝛽 ≤ 𝜀∕𝐵. If 𝛼 = 0, the remainder is empty. √ Thus, by choosing the absolute constant 𝐵 sufficiently large, the last term in Equation (27) is at most 𝜁 𝛼 𝜀∕2. Since 𝑝 ≥ 𝜀, it follows that ( √ ∑√ √ ) √ 𝑝norm + 2 𝑝𝑗 = Ω 2−𝑞∕2 𝜁 𝛼 𝜀 . 𝑗<𝛼

By Cauchy–Schwarz, 2

√ ∑√ ⎞ ⎛ ∑ ⎞ ( ) ⎛√ Ω 2−𝑞 𝜁 2𝛼 𝜀 = ⎜ 𝑝norm + 2 𝑝𝑗 ⎟ ≤ (2𝛼 + 1) ⎜𝑝norm + 𝑝𝑗 ⎟ . ⎝

𝑗<𝛼

⎠

⎝

𝑗<𝛼

⎠

Recall that the ideal extractor chooses each strategy index 𝑠 uniformly at random; index 𝑗 + 1 selects recording round 𝑗. Therefore, ∑ 𝑝norm + 𝑗<𝛼 𝑝𝑗 2−𝑞 𝜁 2𝛼 𝜀 (1 − 𝜂)𝛼 𝜀 𝑝ext = = Ω( = Ω( ) ), 𝛼+1 (𝛼 + 1)2 2𝑘+𝛽 (𝛼 + 1)2 21

where the last equality follows from 𝜁 2 = 2(1 − 𝜂) and 𝛼 + 𝛽 = 𝑞 − 𝑘. Finally, our parameter choices give (1 − 𝜂)𝛼 ≥ 1 − 𝛼𝜂 ≥ 1 − 𝜃,

2−𝛽 = Ω(𝜀),

𝛼 + 1 ≤ 𝑞.

Substituting these bounds yields 𝑝ext = Ω(

𝜀2 ), 2𝑘 𝑞 2

as claimed. 4.2.4 Completion of the binding proof Proof of Theorem 4.1. Assume 𝑝 ≥ 𝜀. Let 𝑝̃ ext denote the success probability of the efficient implementation of the extractor in Construction 4.8. By Proposition 4.12, the corresponding ideal extraction probability satisfies 𝑝ext = Ω(

𝜀2 ). 2𝑘 𝑞 2

By Lemmas 4.3 and 4.6, each ideal rewinding or recording map can be implemented with error at most 𝜈. Since the extractor invokes at most 𝑞 + 1 such operations, a hybrid argument and contractivity of trace distance give, using Equation (19), 2 ||𝑝̃ − 𝑝 || ≤ (𝑞 + 1)𝜈 = 𝒪( 𝜀 ). ext | | ext 2𝑘 𝑞 2 Choosing the multiplicative constant in the definition of 𝜈 sufficiently small makes this loss at most half that lower bound. Hence 𝜀2 𝑝̃ ext = Ω( ). 2𝑘 𝑞 2 Moreover, Equation (19) gives 𝜂 −1 = 𝒪(𝑞),

log(1∕𝜈) = 𝒪(𝑘 + log 𝑞 + log(1∕𝜀)).

Since the extractor executes at most 𝑞 protocol rounds, Lemmas 4.3 and 4.6 imply that its worst-case running time is polynomial in the protocol parameters. Finally, since 𝜀∕𝑞 ≤ 1∕2, the above extraction bound implies 𝑝̃ ext > 2−𝑘 (𝜀∕𝑞)𝑐 for some sufficiently large absolute constant 𝑐 > 2, establishing the two-opening binding property of Definition 3.1. Acknowledgments. We thank the authors of [CWX26] for discussions on the overlap between the two works. This work was supported in part by the French-American ANR-NSF project CTQC (ANR-25-CE487926-01 CTQC), the French ANR projects SecNISQ (ANR-21-CE47-0014) and HQI (ANR-22-PNCQ-0002).

22

References [BK25]

James Bartusek and Dakshita Khurana. On the power of oblivious state preparation. In Yael Tauman Kalai and Seny F. Kamara, editors, CRYPTO 2025, Part II, volume 16001 of LNCS, pages 575–607. Springer, Cham, August 2025. 3

[CWX26]

Boyang Chen, Yiming Wang, and Ziyi Xie. The breakdown of classical Minicrypt equivalences in the quantum-computation classical-communication model. arXiv:2609.33098, 2026. Version 3, 4 October 2026. 3, 22

[DLM+ 26] Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub, Louis Salvail, and Louis-Charles Thibodeau. Post-quantum perfect zero-knowledge arguments for NP from any one-way permutation. arXiv:2610.33185, 2026. Version 1, 23 October 2026. 3 [GSLW19] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Moses Charikar and Edith Cohen, editors, 51st ACM STOC, pages 193–204. ACM Press, June 2019. 4, 5, 6, 10, 16 [HK25]

Andrew Huang and Yael Tauman Kalai. Parallel repetition for post-quantum arguments. In 66th FOCS, pages 1894–1902. IEEE Computer Society Press, December 2025. 1

[HNO+ 09] Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing, 39(3):1153–1218, 2009. 3 [HR07]

Iftach Haitner and Omer Reingold. Statistically-hiding commitment from any one-way function. In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 1–10. ACM Press, June 2007. 1, 3

[LMS22]

Alex Lombardi, Fermi Ma, and Nicholas Spooner. Post-quantum zero knowledge, revisited or: How to do quantum rewinding undetectably. In 63rd FOCS, pages 851–859. IEEE Computer Society Press, October / November 2022. 1, 4, 5, 6, 9

[MY23]

Tomoyuki Morimae and Takashi Yamakawa. Proofs of quantumness from trapdoor permutations. In Yael Tauman Kalai, editor, ITCS 2023, volume 251, pages 87:1–87:14. LIPIcs, January 2023. 3

[NOV06]

Minh-Huyen Nguyen, Shien Jin Ong, and Salil P. Vadhan. Statistical zero-knowledge arguments for NP from any one-way function. In 47th FOCS, pages 3–14. IEEE Computer Society Press, October 2006. 1, 3, 4, 10, 11

[NOVY93] Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions (extended abstract). In Ernest F. Brickell, editor, CRYPTO’92, volume 740 of LNCS, pages 196–214. Springer, Berlin, Heidelberg, August 1993. 1 [NOVY98] Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung. Perfect zero-knowledge arguments for NP using any one-way permutation. Journal of Cryptology, 11(2):87–108, March 1998. 3 [OVY93]

Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung. Fair games against an all-powerful adversary. In Jin-Yi Cai, editor, Advances in Computational Complexity Theory, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 155–169. American Mathematical Society, 1993. 1, 3

23

Related documents

• The security of practical quantum key distribution#6600
• Compressed Permutation Oracles Revisited#1075938
• Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation#1455666
• Time-space lower bounds for breaking quantum cryptography#1160915
• Time-space lower bounds for breaking quantum cryptography#1157449