WorksPhysics and Astronomy
A Post-Quantum Interactive Hashing Theorem
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 [NOVY92]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for NP 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 [8] 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 [5]. 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.
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 [13], it was used by Naor, Ostrovsky, Venkatesan, and Yung to construct perfectly hiding commitments from one-way permutations [12]. Its multi-output generalization is a building block in constructions of statistical zero-knowledge arguments for and statistically hiding commitments from arbitrary one-way functions [10, 6].
Interactive hashing also has applications in quantum cryptography. Morimae and Yamakawa [9] 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 [9].
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 [10].
The theorem gives two immediate applications. First, combining the coherent interactive hashing construction of [9] with the framework of [1], we obtain classical verification of quantum computation from post-quantum secure full-domain trapdoor permutations. This answers an open question of Morimae and Yamakawa [9].
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. [3] prove sum-binding and collapse-binding and use the latter to obtain perfect zero-knowledge classical arguments for against quantum adversaries. Chen, Wang, and Xie [2] 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 [10] 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 [10, 7]. 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.
Technical overview
We give an overview of our proof of post-quantum two-opening binding for the multi-output interactive hashing protocol of [10] between a sender and a receiver. In this protocol, the sender holds a secret string , and the parties interact for rounds, where . In round , the receiver sends a uniformly random hash , and the honest sender replies with the bit . The resulting transcript determines an affine bijection
The form of the hashes makes these equations linearly independent, leaving exactly compatible strings. The honest sender’s input is one of these strings, and its private output is an index such that .
The two-opening binding property is defined as follows. Fix an arbitrary relation , 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 satisfying
with probability at least . Then there exists an extractor that, given a uniformly random challenge , outputs a witness in with probability .
Classical proof. We first briefly give an overview of the classical proof of [10], which is based on a rewinding reduction and a combinatorial analysis of the protocol’s transcript tree. A node at level , for , represents a partial transcript
and denotes the set of all such nodes. For , each child has the form , where is the next receiver hash and is the sender’s response. The strings compatible with the prefix form the set
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 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 . 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 [8], which uses the singular-vector transformation techniques of [4]. 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
single-error terms correspond to the normal and target-switching strategies, respectively. Each double-error 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 [8], based on the singular-vector transformation techniques of [4] (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 , 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 [4], as used in [8], encounters a subtle obstruction. That is, the averaged compatibility operator , whose eigenvalues 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 and prepare the coin in the state
Instead of accepting only responses satisfying , the coin-adjusted compatibility condition is , where is the coin’s measurement outcome. Thus the branch corresponds to a compatible response, whereas corresponds to an incompatible response with a small weight .
We then define the corresponding coherent accepting map as
Its associated POVM element satisfies . Since , we obtain . 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.
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 , 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
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 [8, 4]. 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.
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 , independently of its quantum state. By its definition, we have
Then , and the non-aborting rewound branch satisfies
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
We then have the exact identity
The operator measures the deviation between the operator-valued normalization required by the polar transformation and the constant normalization arising in the balanced case. It vanishes when .
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
Since , the normalization error is a function of the bias operator . We prove a technical lemma on the operator Fourier bound (Lemma 4.4), which gives
which also yields . Hence .
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.
Indeed, the operators satisfy . Completing these successful Kraus 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 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 , with transcript . Write
Here 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 is the transcript’s prefix at round . By Equation (1), . Let
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
The normal term 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 is the branch operator for recording , these summands suggest alternative extraction strategies.
However, the operator factor 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 :
Substitution gives the exact error decomposition
We call 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 . Each single-error term is 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 . We will analyze and bound the double-error remainder below, after introducing our extractor, based on this error decomposition.
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 and a sufficiently large absolute constant , set
The ideal extractor of Construction 4.8 proceeds as follows, using ideal rewinding and recording maps and aborting if any invoked procedure aborts.
Choose a uniform strategy index .
If , apply for all prefix rounds. If , apply for the first rounds, call at the current node to obtain , and apply for the remaining prefix rounds. Intuitively, index selects the normal strategy, and index selects target-switching strategy to record at round , for .
Run the last rounds honestly with fresh independent hashes. Invoke and measure the sender’s joint-output procedure once to obtain . Return if and , for some ; 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 , so the extractor returns . For a target-switching strategy, it counts branches in which the original target is and the recording map outputs , so the extractor returns , the witness for .
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 and . Since , we have
Apart from the scalar factor , 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 , even conditioned on the complete preceding history and an arbitrary residual sender state. Consequently, each double-error term has norm at most
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 is bounded away from one by an absolute constant, . Hence, by the triangle inequality, the double-error remainder has norm at most . If , then , so choosing sufficiently large makes this bound a small fraction of , the lower bound on the norm of the scaled real prefix. If , 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 index, yield the ideal extraction bound , as established in Proposition 4.12.
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 for the extraction probability of the efficient implementation, we obtain
as claimed.
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 .
Singular vector algorithms
In this section, we recall a selection of algorithms from [8] 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 and for the left and right singular vectors with , and define the Jordan subspace . When the subspace is two-dimensional and also contains , which are singular vectors of with the same singular value . Let .
Singular-vector transformation.
Theorem 2.1 (Singular vector transformation [8 Theorem 6.1]). There is a uniform family of circuits with and gates and of size such that the following holds. For a left singular vector of with singular value , whenever , the circuit returns the corresponding right singular vector with success probability at least . 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 , define
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:
In particular, is an isometry on . For every , the transformation admits a coherent efficient implementation with auxiliary registers initialized to . Write
For every , this implementation satisfies
The circuit uses calls to the coherent measurements.
Proof. Apply [4 Theorem 26] to a SVD , with input projector , output projector , threshold , and projected error . Coherent measurement access means , where and is the bit-flip gate. The phase construction of [4 Lemma 19] computes and uncomputes this auxiliary qubit, returning it to . Let denote this unitary circuit with exact phase rotations, and define its isometry by
Thus includes both the system and auxiliary outputs and satisfies . [4 Theorem 26] implies for every unit . Since both output vectors have norm one,
giving the desired bound. With singular-value threshold and error , the construction uses coherent measurement calls, also by [4 Theorem 26].
Multi-output interactive hashing
Definition 3.1. A multi-output interactive hashing scheme is a polynomial-time protocol where both parties receive common inputs , receives a private input , with the common output being a circuit , and the private output of being a string . We denote to be the input length and to be the output length. The protocol must satisfy the following security properties:
(Correctness) For all and all , letting
we have that .
(Perfect hiding) For all , is distributed identically to , where
(Post-quantum computational two-opening binding) Let be an arbitrary relation, and write . Let
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 and a QPT oracle algorithm such that, for every QPT sender , every relation , and every inverse-polynomial , the following implication holds. If
where the above probability is over the randomness and measurements of and , then
Protocol 3.2 (Multi-output interactive hashing [10]).
Inputs:
Input length and output length , both given as common input.
String , given as private input to sender .
Protocol: : Select such that each is a random vector over of the form (i.e., zeros followed by a one, and random choice for the last positions). For , do the following:
Output:
Common output is a circuit , computing an affine transformation whose image is .
Output of is a string 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 [10]. In the rest of the paper, we give a post-quantum security proof for the two-opening binding property.
Post-quantum two-opening binding for arbitrary relations
Definitions. Fix integers , , and let . Fix a relation family . Write for . We define the tree of transcripts as follows.
For , the set of hash functions of the form is denoted as , that is .
Nodes. A node at level is a prefix transcript of length , i.e., . Let denote the set of nodes at level . For define
Transcript. A final transcript determines a leaf . Its output map is the efficiently computable affine bijection
Thus 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 well-formed, non-aborting output satisfying
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.
The extractor
Quantum rewinding with the coin trick
Notation. Fix an input string . Fix a round , 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 whenever introduced.
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 , let .
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
and where
Both are projectors on . Write for the coin label at round . Intuitively, means “the sender’s answer is compatible”, otherwise means “the sender’s answer is incompatible”.
Define the averaged compatibility operator and the bias operator by
The operator is the bias operator: it measures the deviation of from . We suppress the fixed node in this notation. For a residual state , its averaged compatibility probability is . The operators are projectors on , and their average is a positive contraction on the same space.
The next-message Kraus operator for response with hash input , and its corresponding POVM element, are
For fixed , the operators form a POVM, since
The coin-regularized accepting map prepares , applies , and then applies . Its branch expansion is
The coin trick. Using
we get
Consequently,
On , this product acts as on the sender register while fixing the prepared hash and coin states. Moreover,
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 Rewind). At a node , for and the fixed coin parameter , the ideal procedure acts on the supplied sender state as follows:
Initialize. Prepare the hash register in and the coin register in .
Transform. Apply the ideal action of from Lemma 2.2.
Sender response. Apply .
Measure and advance. Measure . If , return . Otherwise retain the response and the resulting sender state, and move to .
Before measurement, its isometry on the sender space is
Its non-aborting branch operator is
Lemma 4.3 (Efficient implementation of Rewind). At every intermediate node , , for and , the CPTP map of defined in Definition 4.2 can be approximated efficiently with error at most , using queries to the sender’s next-message unitaries and their adjoints.
Proof. Apply Lemma 2.2 with , , , and . By the coin trick, every squared singular value on 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
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 . The circuit uses oracle calls.
From normalization errors to recording
Next, we prove the following operator Fourier bound.
Lemma 4.4 (Operator Fourier bound). For every intermediate node , ,
Furthermore, there is an efficient CPTP map with a classical outcome, whose successful label- branch has Kraus operator .
Proof. Recall that every has the form where . Define
The operator is a Hermitian unitary, so . We also write for . depends on the sender’s strategy but not on the target . The -dependence enters only through the character :
Squaring the bias operator:
Average over :
Cross terms (). For , write , where and . 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 and , we have and
Choose a coordinate where is nonzero. Pairing each with the string obtained by flipping that coordinate cancels the two character values. Hence
Diagonal terms (). Here , so , and .
Result. Only diagonal terms survive in Equation (15):
Since , this proves Equation (14).
To construct the CPTP map, define
Then . For an input sender state , the CPTP map is defined as follows:
Prepare and reflect. Prepare a uniform -register and apply controlled by that register, obtaining
Fourier transform. Apply Hadamards to the -register. The resulting state is
Relabel. Append a qubit , then compute coherently, giving
Measurement. Using , the resulting isometry is
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 , , and the coin parameter . For a string , define the normalization error operator
The ideal recording map takes as input the sender’s internal state , and acts as follows:
Measure. Perform the quantum measurement with outcomes , specified by the Kraus operators for and .
Successful output. On outcome , return the recorded label and retain the residual sender state
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 , , the normalization-error operators in Definition 4.5 satisfy
Hence , including its classical output and abort outcome, is a CPTP map. Furthermore, for any , 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, . 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 . Second, a *conditional correction @references тәшки?
applies a quantum operation controlled by the label register, with successful Kraus operator constructed as follows. Let , and define
Since , the bias operator satisfies . Hence and . This also yields . Recall that by Equation (12), and the definition of , we have
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 , the binomial series gives
Its coefficients satisfy and . Since , the truncated polynomial
satisfies
As , a degree suffices to make this error at most .
We implement this polynomial using the linear-combination and product constructions of [4 Lemmas 52 and 53]. The Fourier representation in the proof of Lemma 4.4 gives a uniform block encoding of , and hence of . By the product construction [4 Lemma 53], using separate ancilla registers gives block encodings of the powers .
Next, apply the linear-combination construction with blocks and weights . Since , 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,
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 of its ideal operation. A hybrid argument then bounds the total operator error by . This yields a successful contraction satisfying
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. .
Proof. Let and . Since , we have . Moreover,
so
Consequently, for every vector ,
Since both operators are Hermitian, this implies .
Description of the extractor
Fix a constant and an integer sufficiently large. Let
Let . Note that , and whenever .
Construction 4.8 (Extractor). In the following, Rewind and Record from Definitions 4.2 and 4.5 are implemented efficiently with error at most . On input , the extractor uses the parameters in Equation (19), does the following:
Choose a uniform strategy index .
Rewound prefix.
If : run Rewind at rounds .
If : let be the recording round. Run Rewind at rounds ; apply Record to obtain ; run Rewind at rounds .
Honest continuation. At node , choose random , and query along the way to arrive at node . These hashes are fresh and independent of the preceding history.
Output. Invoke and measure the sender’s joint-output procedure to obtain . Return if and for some ; otherwise return .
Analysis of the extractor
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,
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 and consider any round , 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
for , which follow from compatibility, would force to be zero as well, giving . Write the fresh hash as , where is uniform. Consider two cases:
If , then is uniform.
If , then , so the two hash values always differ.
Thus, we always have
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 .
Error decomposition and its operational interpretations
Denote a complete transcript/output outcome as
where is the full transcript. Let be the set of these outcomes satisfying Equation (10), and define their ordered endpoints by
Here are output indices; the corresponding -bit IH outputs , opened by the witnesses , are called the endpoints. For , these endpoints are distinct and compatible with every prefix of .
Let . At a selected round , let
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
Let , , and , with an empty product equal to .
Lemma 4.10 (Error decomposition). For every such path and ordered pair of compatible endpoints,
Proof. For any composable operator sequences , , a hybrid argument replacing one factor at a time gives
Apply this identity and Equation (20), first with endpoint , to obtain
Apply the same identity with endpoint to each remaining scaled real prefix to obtain:
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), 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 Record. 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
We call this the restricted branch norm.
Let be the success probability of the normal strategy with ideal primitives and no recording, and that of the target-switching strategy with recording at round , for . Both measure the probability of returning a witness for a uniform original target , conditioned on strategy index and , 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, 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.
Proof. The real execution. For Equation (22), , so summing good-output branch probabilities of the real execution gives .
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 . For uniform , let be the string returned by this strategy. Then
The inequality follows from : on this event, the extractor returns .
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 , records at node , and applies in rounds . By Definition 4.5, its successful branch is
The recorded label changes the subsequent rewinding target. However, the requested witness remains a witness for . On every counted output, the output pair contains , which the extractor returns. For uniform , let be the string returned by this strategy. Then
The inequality follows from the fact that : on this event, the extractor returns . 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.
Run rounds honestly, reaching .
Apply to obtain , then run in rounds $i,\ldots,j-1.
Apply to obtain , then run in rounds .
Run the last rounds honestly, then invoke and measure the sender’s joint-output procedure.
Abort on any or failure.
Its branch with recorded labels is
Let be the leaf reached after the honest continuation. Using , we obtain
The first inequality follows from the fact that . The second inequality follows from Lemma 4.9. This proves Equation (25).
Ideal extraction bound
We now bound the double-error remainder.
Proposition 4.12 (Ideal extraction bound). Let denote the success probability of the extractor in Construction 4.8, using ideal implementations of its subroutines. If , then for a sufficiently large fixed ,
Proof. Applying the triangle inequality to Equation (21) and using Lemma 4.11, we obtain
We first bound the double-error remainder. Since , , and , we have . Consequently,
If , our choice of ensures that $2^{-\beta}\leq\varepsilon/B$. If , the remainder is empty. Thus, by choosing the absolute constant sufficiently large, the last term in Equation (27) is at most p\geq\varepsilon$, it follows that
By Cauchy–Schwarz,
Recall that the ideal extractor chooses each strategy index uniformly at random; index selects recording round . Therefore,
where the last equality follows from and . Finally, our parameter choices give
Substituting these bounds yields
as claimed.
Completion of the binding proof
Proof of Theorem 4.1. Assume . Let 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
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 such operations, a hybrid argument and contractivity of trace distance give, using Equation (19),
Choosing the multiplicative constant in the definition of sufficiently small makes this loss at most half that lower bound. Hence
Moreover, Equation (19) gives
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 , the above extraction bound implies
for some sufficiently large absolute constant , establishing the two-opening binding property of Definition 3.1.
Acknowledgments. We thank the authors of [2] 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-CE48-7926-01 CTQC), the French ANR projects SecNISQ (ANR-21-CE47-0014) and HQI (ANR-22-PNCQ-0002).
References
- [1]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. 3arxiv.org/abs/2411.04234
- [2]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, 22arxiv.org/abs/2609.33098
- [3]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. 3arxiv.org/abs/2610.33185
- [4]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, 16DOI
- [5]Andrew Huang and Yael Tauman Kalai. Parallel repetition for post-quantum arguments. In 66th FOCS, pages 1894–1902. IEEE Computer Society Press, December 2025. 1arxiv.org/abs/2506.02277
- [6]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. 3DOI
- [7]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
- [8]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, 9arxiv.org/abs/2111.12257
- [9]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
- [10]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, 11DOI
- [12]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. 3DOI
- [13]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