Post-quantum Resettably-Sound Zero Knowledge

Abstract

We study post-quantum zero-knowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (Barak-Goldreich-Goldwasser-Lindell, FOCS ‘01), providing a malicious efficient prover with oracle access to the verifier’s next-message-function, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier’s function, and in particular can query it in superposition.

The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding post-quantum zero knowledge.

We prove the following results:

• Black-Box Barriers. Quantum resetting exactly captures the power of black-box zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with black-box zero knowledge, except for languages in $\mathbf {BQP}$. Leveraging this, we prove that constant-round public-coin, or three message, protocols cannot be black-box post-quantum zero-knowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is very different due to the essential difference between classical and quantum resetting.

• A Resettably-Sound Non-Black-Box Zero-Knowledge Protocol. Under the (quantum) Learning with Errors assumption and quantum fully-homomorphic encryption, we construct a post-quantum resettably-sound zero knowledge protocol for $\mathbf {NP}$. We rely on non-black-box simulation techniques, thus overcoming the black-box barrier for such protocols.

• From Resettable Soundness to The Impossibility of Quantum Obfuscation. Assuming one-way functions, we prove that any quantumly-resettably-sound zero-knowledge protocol for $\mathbf {NP}$ implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.

A full version of this paper is available at https://eprint.iacr.org/2021/349.pdf.

M. Kellner—Member of the Check Point Institute of Information Security.

1 Introduction

Zero-knowledge protocols, introduced by Goldwasser, Micali, and Rackoff [GMR89], are a cornerstone of cryptography. They allow proving the validity of any statement in $\mathbf {NP}$ without revealing anything but its validity [GMW91]. After over three and a half decades of research, zero knowledge protocols are well understood in terms of their expressiveness and round complexity, and various enhancements of zero knowledge have been considered.

In this work, we consider zero knowledge protocols with post-quantum security, namely, protocols that can be executed by classical parties, but where both soundness and zero knowledge are guaranteed against efficient quantum adversaries. Starting from the seminal work of Watrous [Wat09], our understanding of post-quantum zero knowledge has been gradually improving, and yet it is still far behind our understanding of classical zero knowledge. Beyond the obvious need for post-quantum computational assumptions, the design and analysis of post-quantum zero knowledge protocols is challenged by quantum phenomena such as the no-cloning theorem [WZ82] and state disturbance [FP96], which often deem classical techniques insufficient.

Resettable Soundness. We focus on the notion of resettable soundness, introduced by Barak, Goldreich, Goldwasser, and Lindell [BGGL01] and by Micali and Reyzin [MR01]. In the classical setting, resettably-sound protocols remain sound even against a prover that has the ability to reset the honest verifier to its initial state and random tape, and repeat the interaction in any way it chooses (equivalent to the ability to rewind the verifier to any previous message). The threat of reset attacks arises in various settings, when fresh randomness cannot be generated on the fly and parties are subject to physical resets. Examples include verifiers that run on smart cards or virtual machines. Accordingly security against resetting attacks has received much attention [CGGM00, KP01, MR01] [DGS09, GS09, COSV12, OV12, COPV13, COP+14, BP15, CPS16].

Beyond the protection it provides in the above settings, resettable soundness has played an important role in understanding a foundational question regarding (classical) zero knowledge protocols—the gap between black box zero knowledge and non black box zero knowledge. In the first, the zero knowledge simulator can only access the verifier as a black box, whereas in the second, it can make explicit use of the verifier’s code. Indeed, resettably-sound protocols cannot have a black-box zero knowledge simulator [BGGL01]; roughly speaking, this is because a resetting prover effectively has the same rewinding power as a zero knowledge simulator, and can accordingly use any black box simulation strategy in order to cheat. In fact, several other black-box zero knowledge impossibilities can be derived by a reduction to the impossibility of resettably sound black-box zero knowledge [GK96b, BGGL01, PTW11].

This Work: Quantum Resettable Soundness. We investigate resettable soundness in the quantum setting. That is, we consider classical protocols that are sound against quantum resetting attacks and (plain) zero knowledge against quantum malicious verifiers. Our goal is twofold: First, constructing such protocols to deal with resetting scenarios in a quantum world. Second, in light of the role that resettable soundness plays in the classical setting, we expect that in the quantum setting too, understanding resettable soundness would shed light on basic questions regarding post-quantum zero knowledge.

1.1 Contributions

We first model resetting attacks in a quantum world and define the corresponding notion of resettable soundness. We consider a strong definition that provides the resetting prover quantum access to the honest verifier’s next message function, for some fixed verifier randomness. In particular, the resetting prover may not only rewind the verifier, but also do it in superposition. This model aims to capture the worst possible behavior of an efficient quantum attacker in a setting where resetting is possible. Furthermore, the model captures the capabilities of a black box zero knowledge simulator in the quantum setting (the model is further discussed in the technical overview). Throughout, we restrict attention to efficient resetting provers and accordingly to arguments [BCC88] (offering computational soundness) rather than proofs (offering statistical soundness).

We next describe our results regarding the construction and implications of the above notion of resettable soundness (further discussion of the model and definition can be found in the technical overview below).

Quantum Black Box Barriers. As intended our definition provides a quantum resetting prover with the power of a quantum black-box zero knowledge simulator. This yields a black box barrier analogous to the one in the classical setting.

Observation 1 (Informal)

Post-quantum resettably-sound black-box zero knowledge is impossible, except for languages in $\mathbf {BQP}$.

Building on this fact, we then prove that the Goldreich-Krawczyk black box zero knowledge barriers from the classical setting [GK96b] translate to the quantum setting. More generally, we show that under minimal assumptions, any three-message or constant-round public-coin zero-knowledge protocol can be converted into a quantum resettably-sound argument, while preserving black-box zero knowledge.

Theorem 2

(Informal). Assuming post-quantum one-way functions, post-quantum zero knowledge protocols that are three message or constant-round public-coin, with a negligible soundness error, can be made resettably sound. Such protocols cannot be black-box zero knowledge, except for languages in $\mathbf {BQP}$.

We note that the classical barriers proven by [GK96b] do not apply here, as they only consider classical zero-knowledge simulators, rather than the quantum ones in our setting. The transformation behind the above theorem is in fact the same as the corresponding classical transformation [BGGL01]. However, the analysis of the transformation is different and more challenging due to the essential difference between classical resetting and quantum resetting, which is superposition resetting attacks (see technical overview).

The resulting black-box barrier holds for general zero knowledge protocols, in particular, for arguments. In the case of proofs (with statistical rather than computational soundness), there is evidence that three-message or constant-round public-coin zero knowledge (for non-trivial languages) is impossible altogether (even non-black-box) [BLV06, KRR17, FGJ18]. In the case of black-box zero knowledge, this barrier for proofs was proven (unconditionally) by Jain, Kolla, Midrijanis, and Reichardt [JKMR09]. Finally, we note that like in the classical setting, the resulting barriers, in fact, hold also in a semi-black-box model where the simulator is allowed to depend on the circuit size of the simulated verifier. In the fully black-box model, the barriers can be proven without relying on one way functions.

A Resettably-Sound Protocol via Quantum Non-Black-Box Techniques. Aiming to constructing post-quantum resettably-sound zero knowledge, we are faced with the above mentioned black-box impossibility. In the classical setting, the corresponding black box impossibility of resettably-sound can be circumvented relying on non-black-box simulation. Indeed, the pioneering work of Barak shows how to construct constant-round public-coin zero knowledge arguments from collision-resistant hashing [Bar01], to which one can apply the [BGGL01] transformation to obtain resettable soundness. In the quantum setting, however, constant-round public-coin zero knowledge arguments for now remain out of reach.

Nevertheless, under standard assumptions (Quantum Learning with Errors [Reg05] and Quantum Fully-Homomorphic Encryption [Bra18, Mah18]) we construct a post-quantum resettably-sound zero knowledge protocol relying on (quantum) non-black-box simulation.

Theorem 3

(Informal). Assuming the hardness of $\mathsf {QLWE}$ and the existence of $\mathsf {QFHE}$ there exists a post-quantum resettably sound zero-knowledge argument for $\mathbf {NP}$.

Our construction starts from the recent construction of post-quantum constant-round (non-black-box) zero-knowledge [BS20] and modifies it. While non-black-box techniques do not seem inherent for constant round zero knowledge with plain soundness (see [CCY20] in related work), in our setting they become essential. While the non-black-box technique we use is similar to that of [BS20], resettable soundness, requires a new proof, which encounters several technical challenges emerging from quantum resetting.

From Resettable Soundness to Quantumly Unobfuscatable Functions. In the classical setting, resettably-sound zero knowledge is known to be intimately related to the impossibility of virtual black box obfuscation [BGI+12]. In particular, assuming one-way functions any resettably-sound zero knowledge protocol for $\mathbf {NP}$ implies a family of unobfuscatable functions [BP15]. We show that this result translates also to the quantum setting; specifically there exists classical function families that cannot be obfuscated as quantum states according to the quantum virtual black box notion of Alagic and Fefferman [AF16].

Theorem 4

(Informal). If there exists a post-quantum resettably-sound zero-knowledge argument for $\mathbf {NP}$ and post-quantum one-way functions, then quantum virtual black-box obfuscation is impossible.

Such an impossibility was recently shown by Ananth and La Placa [AP20b] and by Alagic, Brakerski, Dulek, and Schaffner [ABDS20]. The combination of Theorems 3, 4 yields an alternative, albeit more complicated, proof of this result (under similar assumptions). We note that differently from the classical setting where the impossibility of black box obfuscation is unconditional, in the quantum setting it relies on $\mathsf {QLWE}$ and strongly relies on quantum homomorphic encryption. Following the above theorem, any advancement in the construction of quantumly resettably sound protocols, and in particular the construction of constant-round public-coin or three-message protocols, is likely to also advance our understanding of quantum unobfuscatability.

2 Technical Overview

In this section, we provide a technical overview of the paper.

2.1 Defining Post-quantum Resettable Soundness

In the classical setting [BGGL01], a resetting attack by a malicious prover $\mathsf {rP}$ is modeled by providing the prover oracle access to the next-message function of honest verifier $\mathsf {V}(x,\cdot ~;r)$ for the common input x and randomness r that is sampled uniformly and fixed once and for all. The prover then has the ability to query a partial transcript $\mathsf {ts}$, including prover messages up to some round i, and obtain back the verifier message in round $i+1$. In a successful attack, after polynomially many queries, the prover manages to output a full transcript $\mathsf {ts}$ for some false statement x, which yet convinces the verifier $\mathsf {V}(x,\mathsf {ts};r)$.

Aiming to generalize this to the quantum setting, there are two conceivable definitions. The first considers quantum provers, which are only given classical access to $\mathsf {V}(x,\cdot ~;r)$. The second, which we consider in this work, provides the prover with quantum access to $\mathsf {V}(x,\cdot ~;r)$; namely, access to the unitary map $|{\mathsf {ts}}\rangle |{y}\rangle \mapsto |{\mathsf {ts}}\rangle |{y \oplus \mathsf {V}(x,\mathsf {ts};r)}\rangle$; in particular, it may now query $\mathsf {V}(x,\cdot ~;r)$ in superposition. While the first may still provide meaningful security in settings where classical access can be enforced, the second resists stronger resetting scenarios in which the attacker can perform quantum resetting and remain secure even in settings where classical access could be hard to enforce (similar considerations arise when considering CCA and signatures against quantum adversaries, see for instance [BZ13]). Finally, our definition captures the abilities of a black-box zero-knowledge simulator, and will thus be useful for proving black-box barriers on post-quantum zero knowledge.

Proving that resettably-sound protocols cannot be black box zero knowledge, except for languages in $\mathbf {BQP}$, now follows a standard argument similar to the classical one [BGGL01]. Roughly, speaking this is because a quantum resetting prover has the ability to run a quantum black-box simulator for the verifier $\mathsf {V}(x,\cdot ~;r)$, in order to produce a cheating transcript. Indeed, by zero knowledge and completeness, for any true statement x, the simulator almost always generates an accepting transcript, and unless it can decide the underlying language (meaning that it is in $\mathbf {BQP}$), it must also be able to do so for some false statements.

Variants. A natural strengthening of the above definition allows the prover to also choose the statements x that it provides the oracle with; namely get access to $\mathsf {V}(\cdot ~,\cdot ~;r)$. In the body, we prove that this stronger notion can be obtained from the simpler notion assuming subexponentially-secure (post-quantum) pseudorandom functions. We note that all the implications of resettable soundness shown in this work, already follow from the simpler notion of resettable soundness.

Also, as already noted we restrict attention to efficient resetting provers, namely arguments. We note that classically, resettably-sound zero knowledge proofs, namely against unbounded provers, are only possible for trivial languages [BGGL01], and this carries over to the quantum setting. Again, all implications shown in this work already follow from resettably-sound zero knowledge arguments.

2.2 3-Message and Constant-Round-Public-Coin Protocols Can Be Made Resettably Sound

We now explain how 3-message protocols and constant-round public-coin protocols are made resettably sound. The transformation does not change the honest prover, and thus preserves black box zero knowledge, and any other privacy guarantee, such as witness indistinguishability (which we will use later on). This in turn yields quantum black-box zero-knowledge barriers on 3-message or constant-round public-coin protocols (with a negligible soundness error).

3-Message Protocols. The transformation for three-message protocols is essentially identical to the classical one [BGGL01]. Given the original verifier $\mathsf {V}$ for the protocol, we consider a new verifier $\tilde{\mathsf {V}}$ whose randomness consists of a random seed k for a pseudorandom function secure under quantum access [Zha12]. Given a statement x and first prover message $\alpha$, the verifier $\tilde{\mathsf {V}}$ derives randomness r by applying the PRF and derives the second message $\beta$, by applying the original verifier with corresponding randomness:

$$r = \mathsf {PRF}_k(\alpha ), \qquad \beta = \mathsf {V}(x,\alpha ;r) .$$

As expected $\tilde{\mathsf {V}}(x,\alpha ,\beta ,\gamma ;k)$ accepts if the original verifier $\mathsf {V}(x,\alpha ,\beta ,\gamma ;r)$ accepts.

In the classical setting, resettable soundness is proven by a relatively simple reduction to the soundness of the original protocol. In the quantum setting, however, proving security is significantly more challenging. Before we address these challenges let us start by recalling the classical reduction to develop basic intuition. We are given a resetting prover $\mathsf {rP}$, which without loss of generality, never makes the same query twice, and always queries the oracle $\tilde{\mathsf {V}}$ on the cheating transcript it eventually outputs. Roughly speaking, the reduction, which aims to cheat $\mathsf {V}$ in a single interaction, will aim to embed this interaction in a random position in an execution of the resetting $\mathsf {rP}^{\tilde{\mathsf {V}}(x,\cdot ~;k)}$ and forward that execution to the external verifier $\mathsf {V}$. All other executions are internally simulated by the reduction. By pseudorandomness, the view of the simulated $\mathsf {rP}$ is indistinguishable from its view in a resetting attack and will include some cheating execution. With noticeable probability (inverse proportional to the number of queries that $\mathsf {rP}$ makes), the reduction hits the cheating execution and wins.

In the quantum setting, however, it is not a-priori clear how such a reduction would work. In particular, any query made by $\mathsf {rP}$ to $\tilde{\mathsf {V}}$ may now include a superposition of super-polynomially many transcripts. Furthermore, merely observing the prover queries disrupts its state and could affect the probability it produces a cheating transcript. Embedding an execution at a random position is also tricky. When we forward some message $\alpha$ to the external verifier, and obtain back a message $\beta$, we have to answer consistently with $\beta$ all oracle queries to $\alpha$. However, whereas in the classical case, we could assume that no $\alpha$ is queried more than once (because queries can be stored), now it may be that $\alpha$ takes part in all superposition queries that the prover makes.

Similar difficulties arise when trying to prove the soundness of the Fiat-Shamir transformation [FS86] in the quantum random oracle model [BDF+10], and were, in fact, successfully circumvented in recent works [LZ19, DFMS19, DFM20]. Indeed, both in the Fiat-Shamir setting and in our setting, we can still hope to obtain an analog of the classical reduction. Specifically, by measuring a random query made by $\mathsf {rP}$, forwarding the result $\alpha$ to the external verifier, and consistently answering with $\beta$ any future query $\alpha$ by reprogramming the classical function $\tilde{\mathsf {V}}$.

The intuition is that for the prover to succeed in outputting a convincing transcript $(\alpha ,\beta ,\gamma )$, the message $\alpha$ has to appear in one of his superposition queries with noticeable weight; otherwise, it gains almost no information on the corresponding verifier message $\beta$, and will fail to break soundness. Furthermore, when measuring such a query we are likely to obtain $\alpha$, without disturbing the prover’s state too much (in the extreme case that $\alpha$ occurs with probability one, the state is not disturbed at all). If the reduction hits the first such query (where $\alpha$ is significant), then it suffices that it is consistent with $\alpha$ in future queries and does not have to worry about past queries.

This intuition is elegantly captured and made rigorous by Don, Fehr, Majenz, and Schaffner [DFMS19, DFM20]. They prove reprogramming and simulation lemmas that establish the validity of (a slight variant of) the described reduction in the case of Fiat Shamir, where the message $\beta$ is chosen uniformly at random. In our setting, $\beta$ is an arbitrary message derived by the verifier. Nevertheless, relying on their reprogramming lemma, we can prove an appropriate simulation lemma for our setting.

A Useful Generalization: Many-Round Almost Resettable Protocols. We also show a generalization of the three-message transformation that allows to take any single-prefix resettably-sound protocol and make it (fully) resettably sound. Single-prefix resettably sound protocols are almost resettably sound. They allow the resetting prover to use a single classical first message and accordingly obtain a single response to this message from the verifier. Only starting from the prover’s next message it is allowed to quantumly reset; namely all interactions (even if in superposition) start with the same classical prover message and verifier response. A three message protocol is indeed the simplest example of a single-prefix resettably-sound protocol, since the verifier has a single message, and if this message is not reset, then there is no resetting whatsoever, and resettable soundness is synonymous to plain soundness.

This generalization turns out to be useful, and is used later on in our construction of a resettably sound (non-black-box) zero knowledge protocol for $\mathbf {NP}$. To obtain this generalization, we first extend the reprogramming lemma from [DFM20] to the case of reprogramming an entire oracle, specified by some prefix. This allows us to extend the previously described reduction, which given a fully resetting prover can turn it into a single prefix resetting prover. The difference is that now rather than obtaining from the external verifier a response $\beta$ to the measured $\alpha$, it obtains oracle access to an oracle $\tilde{\mathsf {V}}(x,\alpha ,\cdot ~;r)$ specified by the prefix $\alpha$ (and implicitly a response $\beta$). This oracle effectively allows to perform resetting attacks, but only starting from the next prover message.

Constant-Round Public-Coin Protocols. Another example where classical resettable soundness can be achieved is that of constant round public-coin protocols. Also here we obtain an analogous transformation in the quantum setting, now based on multi-value reprogramming lemmas from [DFM20], used there to deal with multi-message Fiat Shamir.

Beyond 3-Message or Constant-Round Public-Coin? We note that we should not hope to transform arbitrary protocols into resettably-sound ones; indeed, multi-message post-quantum zero knowledge protocols for $\mathbf {NP}$ do exist, and are even public coin [Wat09]. But what does it take for a protocol to be (transformable to) resettably sound? Here one bottleneck is the (in)ability of the reduction to simulate internally the interactions that are not forwarded to the external verifier. More specifically, the question is whether the reduction could simulate continuations that start consistently with the external verifier and then diverge. In general private-coin protocols, this may not be possible as the private coins of the external verifier are not known to the reduction. In contrast, in three-message protocols this is not a problem, as there is nothing to continue (the verifier has a single message). Similarly, also in public coin protocols, simulating continuations is easy—the reduction samples the random messages on its own.

This is, however, not the only bottleneck. A second bottleneck is that the reduction has to hit the cheating execution with noticeable probability, and since the reduction has to guess on the fly which messages to forward to the external verifier, this probability may decrease exponentially in the number of rounds. Hence, even for public coin protocols, the transformation only works for a constant number of rounds. In fact, this is tight—the round complexity of Watrous’ zero knowledge public-coin proofs [Wat09] can be reduced to any super constant function $\omega (1)$. (For instance, by starting from Blum’s Hamiltonicity protocol [Blu86] that has constant soundness, repeating it in parallel logarithmically many times, and then sequentially $\omega (1)$ times.)

2.3 Constructing a Resettably Sound Non-Black-Box Zero-Knowledge Protocol

We now outline the main ideas and techniques behind our construction of a resettably-sound non-black-box zero-knowledge protocol for $\mathbf {NP}$. Our starting point is the post-quantum zero knowledge protocol of Bitansky and Shmueli [BS20]. We next describe the main challenges in turning this protocol into a quantumly resettably sound protocol.

A Bird’s Eye View of the BS Protocol. At a high level (and oversimplifying), the BS protocol consists of two phases. First, the verifier provides a quantum extractable commitment to a challenge message. Then the parties execute a standard zero knowledge sigma protocol to prove the statement x, where the verifier opens the commitment from the first phase. The extractor for the first-phase commitment is non-black-box, using the code of a sender (the verifier in this case), it can extract the underlying message while faithfully simulating the quantum state of the sender. This gives rise to a corresponding non-black-box simulation strategy, which first extracts the verifier challenge and can then cheat in the sigma protocol.

Already at this level, one can see that the protocol is not resettably sound, even classically, let alone quantumly. A resetting prover can first run the verifier until the opening phase, obtain the challenge, then reset the verifier, and like the simulator use the obtained challenge to cheat in the sigma protocol. Indeed, the reason that the actual simulator in the BS protocol does not follow this black-box strategy is that it does not work for malicious quantum verifiers, whereas a resetting prover only has to cheat a classical verifier.

Following the above observation, we change the above high level blueprint. We rely on the Feige-Lapidot-Shamir [FLS99] trapdoor paradigm. In the first-phase, the BS extractable commitment is used to set up a trapdoor statement t. In the second phase, the prover provides a witness-indistinguishable proof that either x is a true statement or t is a true statement. To guarantee soundness, the trapdoor statement is set up so that it is indistinguishable from a false statement, and thus relying on the soundness of the second-phase proof, a convincing proof must mean that x is a true statement. In contrast, a simulator given the code of the verifier should be able to efficiently extract a witness for the trapdoor statement t, and can then use it in the second phase proof indistinguishably from the prover (who uses the witness for x).

Given that we are interested in quantum resettable soundness, we have to guarantee that the indistinguishability of the trapdoor statement t from a false statement, holds even against quantum resetting attacks. Furthermore, we have to guarantee that the second-phase proof is resettably sound. For the latter, we can use standard constant-round public-coin witness-indistinguishable proofs; indeed, we have already shown that such proofs can be made quantumly-resettably sound, while preserving witness indistinguishability. The more involved part is establishing indistinguishability of the trapdoor statement from a false one under resetting.

A Resettably-Secure Trapdoor Phase. We now dive deeper into the construction of a resettably-secure trapdoor phase. In terms of extractability (of a trapdoor witness), we first present a trapdoor phase that is only extractable against a restricted class of verifiers that are non-aborting and explainable. The notion of non-aborting explainable verifiers considers verifiers whose messages can always be explained as a behavior of the honest (classical) verifier with respect to some randomness (finding this explanation may be inefficient); in particular, they never abort. This simpler setting will already capture the main challenges we need to deal with. We will later discuss how this restriction is removed.

Similarly to the BS extractable commitment, we rely on three basic tools:

• Quantum fully-homomorphic encryption (QFHE)—an encryption scheme that allows to homomorphically apply any polynomial-size quantum circuit C to an encryption of x to obtain a new encryption of C(x), proportional in size to the result |C(x)| (the size requirement is known as compactness).

• Compute-and-compare program obfuscation (CCO). A compute-and-compare program $\mathbf {CC}[f,v,z]$ is given by a function f (represented as a classical circuit) and a target string v in its range; it accepts every input x such that $f(x)=v$, and rejects all other inputs. A corresponding obfuscator compiles any such program into a program $\widetilde{\mathbf {CC}}$ with the same functionality. In terms of security, provided that the target v has high entropy conditioned on f, the obfuscated program is computationally indistinguishable from a simulated dummy program that is independent of f, v, z, and rejects all inputs.

• Secure function evaluation (SFE) that can be thought of as homomorphic encryption with an additional circuit privacy guarantee, which says that the result of homomorphic evaluation of a circuit, reveals nothing about the evaluated circuit to the decryptor, except of course from the result of evaluation.

We now describe a (still simplified) trapdoor phase, which is essentially the same as the BS extractable commitment, except for how the randomness of the verifier is handled. In the trapdoor phase the verifier has two randomized steps; we denote the randomness used in these rounds by $r_1$ and $r_2$, respectively.

• 1. The prover $\mathsf {P}$ samples a secret key $\mathsf {sk}$ for SFE, and sends a commitment $\mathsf {cmt}$ to $\mathsf {sk}$.

• 2. The verifier $\mathsf {V}$ uses randomness $r_1$ to sample:

  • two random strings u and v,

  • a secret key $\mathsf {sk}'$ for an FHE scheme,

  • an FHE encryption $\mathsf {ct}'_u = \mathsf {QFHE.Enc}_{\mathsf {sk}'}(u)$ of u,

  • an obfuscation $\widetilde{\mathbf {CC}}$ of $\mathbf {CC}[f,v,\mathsf {sk}']$, where $f = \mathsf {QFHE.Dec}_{\mathsf {sk}'}$ is the FHE decryption circuit.

  It then sends $(\mathsf {ct}'_u,\widetilde{\mathbf {CC}})$ to the prover $\mathsf {P}$.

• 3. The prover $\mathsf {P}$:

  • sends $\mathsf {ct}_{u'}$, a string $u'$ encrypted using SFE (the honest prover sets $u'$ arbitrarily).

  • proves using a resettably-sound witness-indistinguishable argument that $\mathsf {ct}_{u'}$ is a valid SFE encryption corresponding to the secret key $\mathsf {sk}$ underlying the commitment $\mathsf {cmt}$.

• 4. The verifier $\mathsf {V}$:

  • uses the SFE homomorphic evaluation to compute the function $C_{u \rightarrow v}$ that given input u, returns v (and otherwise $\bot$).

  • To derive the randomness for this evaluation, $\mathsf {V}$ interprets its randomness $r_2$ as a seed for a pseudorandom function and applies it to the prover messages $(\mathsf {cmt},\mathsf {ct}_{u'})$.

  • $\mathsf {V}$ then returns the resulting ciphertext to $\mathsf {P}$.

• 5. The trapdoor statement t is set to be:

“There exists a ciphertext $\mathsf {ct}^*$ that the program $\widetilde{\mathbf {CC}}$ does not reject."

Basic Intuition. We start by building basic intuition on how the above protocol achieves the goal of a trapdoor phase. For starters we will ignore the resetting attacks, and recall the intuition from BS. Then we will address the main challenges in proving resettable security, and how they are met. (A reader familiar with BS may want to skip directly to the resettable security paragraph.)

Let us start by explaining how a non-black-box simulator can use the circuit of an explainable verifier in order to obtain a witness proving the trapdoor statement. The simulator acts honestly in the first step, and then obtains the CC obfuscation $\widetilde{\mathbf {CC}}$ and FHE encryption $\mathsf {ct}'_u$ of the string u. The main point is that now the simulator can homomorphically continue the protocol under the FHE encryption. That is, it will evaluate the (quantum) verifier under the encryption, where it has the secret u in the clear and can use it in the SFE protocol to obtain back the secret target value v (the hiding of SFE encryption is used to argue that such an execution is indistinguishable from a real one where a dummy encryption is sent). Going back out of the encryption, the simulator now actually holds an encryption $\mathsf {ct}^*$ of v, and in particular $\widetilde{\mathbf {CC}}$ does not reject $\mathsf {ct}^*$, but rather outputs the FHE secret key $\mathsf {sk}'$. Thus, the ciphertext $\mathsf {ct}^*$ obtained by the simulator is a valid trapdoor witness. The reason we require $\widetilde{\mathbf {CC}}$ to output $\mathsf {sk}'$, rather than an arbitrary accept value, is for the simulator to be able to decrypt the internal verifier quantum state and faithfully continue the simulation.

We now turn to explain why to a malicious (but for now, non-resetting) prover, who does not obtain the code of the verifier, the trapdoor statement is indistinguishable from a false statement. Specifically, we would like to argue that we can replace the obfuscation $\widetilde{\mathbf {CC}}$ with a simulated one that rejects all inputs. To see this, we first argue that the prover cannot send an SFE encryption $\mathsf {ct}_{u'}$ such that $u'=u$ , except with negligible probability. Indeed, given only the first sender message $(\mathsf {ct}'_u,\widetilde{\mathbf {CC}})$, the receiver obtains no information about u. Hence, we can invoke the CCO security and replace the obfuscation $\widetilde{\mathbf {CC}}$ with a simulated one, which is independent of the secret FHE key $\mathsf {sk}$. This, in turn, allows us to invoke the security of encryption to argue that the first message $(\mathsf {ct}'_u,\widetilde{\mathbf {CC}})$ hides u. While this means that the prover does not obtain u in the clear, we still need to argue that it cannot send an encryption of u. This is done using a non-uniform reduction and is exactly the purpose of the prover commitment $\mathsf {cmt}$ to the SFE secret key $\mathsf {sk}$, which allows us to provide the reduction with $\mathsf {sk}$ as non-uniform advice. Having established that no SFE encryption of u is sent we can invoke the circuit privacy guarantee to completely remove the value v from the prover’s view and now we also replace $\widetilde{\mathbf {CC}}$ with a simulated one that rejects all inputs.

Resettable Security. The above argument establishing indistinguishability of the trapdoor statement from a false statement, does not consider resettable attackers. We now discuss the difficulties arising from resetting attacks and how they are dealt with.

Recall that a resetting quantum attacker may perform superposition queries. Accordingly, now when arguing that it cannot produce an SFE encryption of u, we would like to argue that SFE encryptions of u have negligible weight in any query made by $\mathsf {rP}$; in other words, projecting the queries on the space of non-u queries has little effect on the experiment. Indeed, we can prove this if the resetting prover is guaranteed to always use the same SFE encryption key, in which case we can non-uniformly hardwire this key into our reduction like before. The problem is that a resetting prover may start many executions, each with a different SFE key; in fact it can run exponentially many such executions in superposition. This is where we use our reduction to single-prefix resetting provers (discussed in the previous section). The reduction allows us to obtain new prover that in all executions sends the same commitment $\mathsf {cmt}$ and uses the same secret key; any resetting attempt is done from the next message and onward.

Having established that the prover queries do not include encryptions of the secret u (or rather have a small projection on this space), we would like to invoke as before the circuit privacy guarantee. However, this should be done with care. The problem is the prover still has the ability to send many ciphertexts and receive evaluations on each one of them. This is the reason we invoke a pseudorandom function to derive randomness in this step, which ensures that each evaluation uses (pseudo)independent randomness. Proving security, however, is not straightforward. In the classical setting, this is not an issue—the overall number of queries is polynomial and thus we can use a standard hybrid argument, invoking circuit privacy polynomially many times. In the quantum setting, however, where queries include a superposition over exponentially many ciphertexts, this is unclear. In fact, there is a basic problem here, which we find interesting on its own. Assume that for two efficient samplers $S_0(x)$ is computationally indistinguishable from $S_1(x)$ for any input x; are the two oracles $F_i(x) := S_i(x;R(x))$ indistinguishable (quantumly), when R is a random function? Zhandry [Zha12] shows that this is the case if $S_i(x) = S_i(y)$ for any x, y, but the general case is unclear.

Fortunately, in our case, we can take a straightforward approach to solve it, by guaranteeing that circuit privacy is statistical, and ensuring that the statistical error is smaller than the total number of ciphertexts in the support, and thus a naive hybrid argument still works. Doing so again requires care, as the size of SFE ciphertexts and the statistical security guaranteed may be related. We show how to deal with this by forcing the prover to also commit to the randomness used in SFE encryptions so that the number of hybrids only depends (exponentially) on the fixed length of the encrypted plaintext.

General Verifiers. In the described trapdoor protocol, we have made two simplifying assumptions regarding the verifier—that it is explainable and that it is non-aborting. We deal with the first restriction using a common approach based on witness indistinguishable proofs by the verifier [BKP19, BS20]. This time however, we need to rely on resettable statistical witness indistinguishability. Statistically-witness-indistinguishable ZAPs are known under super-polynomial hardness of $\mathsf {QLWE}$ [GJJM20, BFJ+20] and are resettable as they only include one round. We also give a solution using only polynomial hardness of $\mathsf {QLWE}$, based on Unruh’s notion of collapse binding statistically-hiding hash functions, which leads to statistical witness-indistinguishable protocols [Unr16b, Unr16a], while these protocols are not resettably-witness-indistinguishable as is, we show how to make them resettably secure.

As for dealing with verifier aborts, we rely on a general approach from [BS20], which roughly asserts that it is sufficient to be able to construct two separate zero knowledge simulators, one for verifiers that do not abort and one for verifiers that do, and which do not affect the probability of aborting (more than negligibly). They show that two such simulators can always be combined to one full-fledged simulator using Watrous’ rewinding lemma [Wat09].

2.4 From Resettable Soundness to Quantum Unobfuscatability

Finally, we outline the construction of quantumly unobfuscatable functions from resettably-sound zero-knowledge protocols for $\mathbf {NP}$ and one-way functions. Informally, an unobfuscatable function family is a family of classical functions $\left\{ f_k\right\}$ indexed by a secret k. Given quantum oracle access to a random $f_k$ in the family, no efficient quantum learner should be able to learn some secret function s(k) of the key. In contrast, given any quantum state $\rho$ and quantum circuit C such that for some k and and all inputs x, $C(\rho ,x)$ computes the classical value $f_k(x)$, one could efficiently extract from C and $\rho$ the corresponding secret s(k).

Our construction closely follows the construction of classically unobfuscatable functions from classical resettably sound zero knowledge protocols [BP15], while making some adaptations to the analysis stemming from the difference between the classical and quantum settings. Roughly speaking, our family of functions $\left\{ f_{r,\varphi ,s}\right\}$ is indexed by randomness r and statement $\varphi$ for the (honest) verifier given by our resettably-sound protocol, and some secret s. The statement $\varphi$ is taken from some $\mathbf {NP}$ language $\mathcal {L}$ where random statements $\varphi \in \mathcal {L}$ are indistinguishable from statement not in $\mathcal {L}$ (for instance pseudorandom strings vs random strings for a sufficiently stretching pseudorandom generator). The function generally computes the verifier next message function $\mathsf {V}(\varphi ,\cdot ;r)$ with two exceptions. For some fixed public input $\mathtt {statement}$, the function will output the statement $\varphi$. Also, given any accepting transcript $\mathsf {ts}$, the function outputs its secret s.

To argue unlearnability, we show that any efficient quantum learner $\mathsf {L}$ that given oracle access to a random $f_{r,\varphi ,s}$ finds s can be transformed into a prover that violates quantum resettable soundness. For this, we first show that any learner that manages find s with noticeable probability, can be translated into a learner that that given access to $\mathsf {V}(\varphi ,\cdot ;r)$ finds an accepting transcript $\mathsf {ts}$, still with noticeable probability. For this we rely on a quantum one-way to hiding lemma by Ambainis, Hamburg, and Unruh [AHU19]. We then rely on the fact that $\varphi$ is indistinguishable from a false statement to deduce that the prover will also succeed for no statements and thus break resettable soundness.

Finally, we show that we can use the non-black-box zero knowledge simulator to extract an accepting transcript with overwhelming probability. Given a quantum circuit C and state $\rho$ implementing the function $f_{r,\varphi ,s}$, say perfectly (although almost perfectly would still do). We can realize a quantum circuit along with quantum auxiliary input $\rho$ that implement the verifier $\mathsf {V}(\varphi ,\cdot ;r)$. Here perfect correctness guarantees that when the constructed verifier computes its next messages, the state $\rho$ is not disturbed, and thus we can repeatedly compute next messages. We can now run our non-black-box simulator (which also works relative to quantum auxiliary input), and by zero knowledge and completeness obtain an accepting transcript.

2.5 Related Work

We now mention additional related work, elaborate on some of the related works mentioned earlier, and address concurrent work.

Classical Resettable Security. The notion of resetting attacks was first considered by Canetti, Goldreich, Goldwasser, and Micali [CGGM00]. They defined and constructed protocols that are zero knowledge against resetting attacks. Resettable soundness was then introduced and achieved by Barak, Goldreich, Goldwasser, and Lindell [BGGL01]. Deng, Sahai, and Goyal showed how to construct a simultaneously resettable zero knowledge protocol [DGS09], this result was later followed by Goyal [Goy13] who gave a public coin protocol, by Chung, Ostrovsky, Pass and Visconti [COP+14] who gave a protocol based on one-way functions, and by Chongchitmate, Ostrovsky, and Visconti [COV17] who gave a constant round protocol, based on various standard assumptions. Goyal and Sahai [GS09] and Goyal and Maji [GM11] defined and constructed varioues forms of resettable secure computation. Bitansky and Paneth [BP12, BP13, BP15] constructed resettably-sound protocols with various improved features based on unobfuscatability. Chung, Pass, and Seth [CPS13] constructed resettably-sound zero knowledge based on one-way functions. Finally, Chung, Ostrovsky, Pass, and Venkitasubramaniam [COP+14] presented a 4-round resettably sound zero-knowledge based on one-way functions.

Post-Quantum Zero-Knowledge for $\mathbf {NP}$. The study of post-quantum zero-knowledge (QZK) protocols was initiated by Van De Graaf [VDGC97], who first observed that traditional zero-knowledge simulation techniques, based on rewinding, fail against quantum verifiers. Subsequent work has further explored different flavors of zero knowledge and their limitations [Wat02], and also demonstrated that relaxed notions such as zero-knowledge with a trusted common reference string can be achieved [Kob03, DFS04]. Watrous [Wat09] was the first to show that the barriers of quantum information theory can be crossed, demonstrating a post-quantum zero-knowledge protocol for $\mathbf {NP}$ (in a polynomial number of rounds). A constant round non-black-box zero knowledge protocol was constructed by Bitansky and Shmueli [BS20] based on $\mathsf {QLWE}$ and quantum fully homomorphic encryption. Similar techniques for non black-box extraction were also developed by [AP20a]. Subsequently, Agarwal, Bartusek, Goyal, Khurana, and Malavolta [ABG+20] extended the BS construction to obtain parallel zero knowledge based on spooky encryptions for relations computable by quantum circuits.

Very recently Chia, Chung and Yamakawa [CCY20] showed that the Goldreich-Kahan protocol [GK96a] satisfies a relaxed notion called (post-quantum) $\varepsilon$-zero knowledge; the protocol is based on collapse binding hash functions in the case of proofs, and on one-way functions in the case of arguments.

Barriers for 3-Message and Constant-Round Public-Coin Proofs. Classically, 3-message and constant-round public-coin zero knowledge arguments are subject to black-box barriers [GK96b], but can in fact be classically achieved using non-black-box simulation (under appropriate computational assumptions) [Bar01, BKP18]. In the case of proofs, there is evidence that they are unlikely to exists altogether (including non-black-box zero knowledge). Specifically, constant-round public-coin proofs do not exist assuming appropriate Fiat-Shamir hash functions [FS86, DNRS03, BLV06]. Kalai and the Rothblums [KRR17] gave such an instantiation of a Fiat Shamir hash assuming subepxoenential indistinguishability obfuscation, and strong forms of point obfuscation. Jain, Fleischhacker, and Goyal [FGJ18] extended their impossibility to also rule out three-message proofs. The mentioned implications also hold in the quantum setting, assuming post-quantum analogs of the corresponding assumptions. Jain, Kolla, Midrijanis and Reichardt [JKMR09] showed that for black-box zero knowledge, proofs can be ruled out unconditionally.

Simulating Quantum Oracles. Quantum oracles have been a fundamental aspect of quantum computation from the start. Querying the oracle in superposition created the need to develop new proof techniques. Specifically when proving security of quantum protocols in the Quantum Random Oracle Model ([BDF+10]). The main issue is the lack of ability to record the queries asked by the adversaries and to easily reprogram the answers. Nevertheless, many results were achieved even without these abilities [Zha12, Unr14, Zha15, ES15, Unr15, TU16, ABB+17, KLS18]. Following Zhandry’s work [Zha18] on recording random oracles, many other results were proven such as the Fiat-Shamir transform [LZ19, DFMS19, DFM20], the Micali CS Proofs [CMS19], 4-round Luby-Rackoff construction [HI19] and more.

Quantum Obfuscation. Quantum obfuscation was first proposed by [AF16]. It’s impossibility is not implied by the impossibility proved in [BGI+12]. In recent work, [ABDS20] showed the impossibility of such schemes based on the hardness of $\mathsf {QLWE}$. A related stronger notion called Secure Software Leasing was dealt in [AP20b] and [KNY20], showing the impossibility of such generic scheme (based on $\mathsf {QLWE}$ and the existence of $\mathsf {QFHE}$), and the possibility of such schemes for restricted classes of functions (pseudo-random functions and evasive functions) under sub-exponential $\mathsf {QLWE}$.

Concurrent Work. In a concurrent and independent work, Chia, Chung, Liu and Yamakawa [CCLY21], prove new black-box barriers on post-quantum zero knowledge. They show that black-box $\varepsilon$-zero-knowledge is impossible for three-message and constant-round public-coin protocols, and that black-box zero knowledge is impossible for general constant round protocols (also private coin). The barriers on $\varepsilon$-zero-knowledge for public-coin and three-message also follow directly from our resettable-soundness transformations, but the barrier for general constant-round protocols does not. The other results in this paper (the construction of a resettably-sound protocol and the connection to unobfuscatability) do not overlap with their work.

Technically, while Chia et al. do not explicitly consider resettable soundness, the barriers on three-message and public-coin protocols are proven similarly (using measure-and-reprogram techniques). To achieve the result on general constant-round, they first extend a classical result by Barak and Lindell [BL04] on the impossibility of a strict polynomial-time black-box simulator. This is again done using similar measure-and-reprogram techniques. Then, they further extend the result to expected-time simulators. This requires novel ideas and strongly relies on quantum entanglement; in particular, in the classical setting, such a barrier does not exist.

3 Defining Post-Quantum Resettable Soundness

In this section, we present our definition of resettable soundness, and show and immediate implication of this definition, regarding the triviality of black-box zero-knowledge arguments with resettable soundness.

3.1 Post-Quantum Resettable Soundness

We present our definition for post-quantum resettable soundness. Our definition deals with giving oracle access to fixed verifier. We shall use $\mathsf {V}\left( x,\cdot ;r\right)$ to denote the interaction of algorithm $\mathsf {V}$ on instance x fixed randomness r (where the input is a partial transcript). Also, to denote the application of $\mathsf {V}$’s predicate on a transcript $\mathsf {ts}$ we shall write $\mathsf {V}\left( x,\mathsf {ts};r\right)$. The definition of resettable soundness is as follows,

Definition 1 (Post-Quantum Resettable Soundness)

A classical interactive protocol $\langle \mathsf {P},\mathsf {V}\rangle$ for language $\mathcal {L}$ has resettable soundness against quantum provers, if for any malicious $\text{ qpt }$ resetting prover $\mathsf {rP}= \left\{ \mathsf {rP}_{\lambda },|{\psi _{\lambda }}\rangle \right\} _{\lambda \in {\mathbb N}}$ there exists a negligible function $\mu \left( \cdot \right)$ such for any security parameter $\lambda \in {\mathbb N}$ and any $x \in \{0,1\}^{\lambda } \setminus \mathcal {L}$ it holds that,

where $\mathsf {ts}$ is a transcript of a possible interaction between $\mathsf {P},\mathsf {V}$. $\mathsf {V}\left( x,\cdot ;r\right)$ is the function that computes $\mathsf {V}$’s next message, on instance x and some fixed randomness r, given as input a transcript of a partial interaction.

4 Transforming Protocols to Achieve Quantum Resettable Soundness

In this section we show that classical three-message protocols as well as constant-round public-coin protocols can be made resettably sound assuming one-way functions. The transformation is simple and similar to the one from the classical setting [BGGL01], however, having to deal with quantum resetting attacks, the analysis is significantly different. The transformation preserves black-box zero-knowledge; accordingly, we deduce as a corollary that post-quantum black-box zero-knowledge protocols cannot be 3-message or constant-round public-coin, except for trivial languages.

4.1 Quantum Oracle Notations

We rely on a couple of lemmas proved in [DFM20]. We restate them here again, while augmenting some of the notation, to fit with our conventions. Let $\mathsf {A}^{H}$ be a quantum oracle-aided algorithm. For a q-query algorithm, without loss of generality, $\mathsf {A}$ can be described as having the following registers, query registers on which we apply the unitary $\mathcal{O}_{H}$ computing $|{x}\rangle |{y}\rangle \rightarrow |{x}\rangle |{y\oplus H\left( x\right) }\rangle$, X, Z which are output registers, and E holds any other internal qubits used by $\mathsf {A}$. More so, the operation of $\mathsf {A}$ on its initial state can be described as,

$$ \mathsf {A}^{H} = \mathsf {A}_{q}\mathcal{O}_{H}\dots \mathsf {A}_{1}\mathcal{O}_{H}, $$

where $\mathsf {A}_{i}$ is a sequence of unitaries. Like [DFM20] we use the following notation for $i<j \in \left[ q\right]$

$$ \mathsf {A}^{H}_{i\rightarrow j} = \mathsf {A}_{j}\mathcal{O}_{H}\dots \mathsf {A}_{i+1}\mathcal{O}_{H} . $$

We also denote $\mathsf {A}^{H}_{i\rightarrow j} = \mathsf {Id}$ for $i\ge j \in \left[ q\right]$. Assuming $\mathsf {A}$ gets as initial input a pure state $|{\phi _0}\rangle$, we denote,

$$ |{\phi ^{H}_{i}}\rangle = \mathsf {A}^{H}_{0\rightarrow i } |{\phi _0}\rangle . $$

For a function H we denote by $H_{x\rightarrow \theta }$ the same function where x is remapped to $\theta$:

$$ H_{x\rightarrow \theta }\left( x'\right) = {\left\{ \begin{array}{ll} H\left( x'\right) &{} x' \ne x \\ \theta &{} x'=x \end{array}\right. }. $$

4.2 Transforming 3 Message Private Coin Protocols

We show that any 3 message interactive protocol $\langle \mathsf {P},\mathsf {V}\rangle$ can be transformed to a quantum resettably sound one, assuming the existence of quantum secure PRFs. More formally we show the following,

Proposition 1 (Compiler For 3 Message Protocols)

Assuming quantum-secure one-way functions, any 3 message protocol $\langle \mathsf {P},\mathsf {V}\rangle$ with negligible soundness for a language $\mathcal {L}$, can be transformed to into a post-quantum resettably sound protocol $\langle \mathsf {P},\tilde{\mathsf {V}}\rangle$. More so, if $\langle \mathsf {P},\mathsf {V}\rangle$ is (black-box) zero-knowledge then so is $\langle \mathsf {P},\tilde{\mathsf {V}}\rangle$.

Combining proposition 1 with observation 1 immediately implies the following corollary,

Corollary 1

If $\mathcal {L}$ has a 3 message post-quantum black-box zero-knowledge protocol, then $\mathcal {L}\in \mathbf {BQP}$.

Single Value Reprogramming. To prove our construction presented in 4.2, we shall rely on a lemma by [DFM20].

Lemma 1

(Single Value Reprogramming Lemma ([DFM20])). Let $\mathsf {A}$ be a q-query oracle quantum algorithm. Then, for any function $H: {\mathcal{X}}\rightarrow {\mathcal{Y}}$, any $x \in \mathcal{X}$ and $\theta \in \mathcal{Y}$, and any projection $\varPi _{x,\theta }$ acting on the Z register (which may depend on $x,\theta$), it holds that

$$\begin{aligned}&\mathop {{\mathbb E}}_{i,b}\left[ \left\| {\left( |{{{x}}}\rangle \langle {{{x}}}|\otimes \varPi _{x,\theta }\right) \left( \mathsf {A}_{i+b\rightarrow q}^{H_{x\rightarrow \theta }}\right) \left( \mathsf {A}_{i\rightarrow i+b}^{H}\right) \left( |{{{x}}}\rangle \langle {{{x}}}|\right) |{\phi _i^H}\rangle } \right\| _{2}^{2} \right] \ge \\&\frac{\left\| {\left( |{{{x}}}\rangle \langle {{{x}}}| \otimes \varPi _{x,\theta }\right) |{\phi _q^{H_{x\rightarrow \theta }}}\rangle } \right\| _2^2}{(2q+1)^2}, \end{aligned}$$

where the expectation is over uniform $\left( i,b\right) \in \left\{ 0,\ldots ,q-1\right\} \times \{0,1\}\cup \left\{ \left( q,0\right) \right\}$. We emphasize that first $|{{{x}}}\rangle \langle {{{x}}}|$ acts on query register, while the second acts on the X register.

Remark 1

We state here the technical lemma and not the existence of a simulator, as done in the multiple values reprogramming in the public-coin case, since unlike [DFM20] we use this lemma to reprogram a non-uniform output function, in our private-coin transform.

Construction. Fix some language $\mathcal {L}$ with a three-message protocol $\langle \mathsf {P},\mathsf {V}\rangle$ whose message we denote by $(\alpha ,\beta ,\gamma )$. Assume V uses $m\left( \lambda \right)$ bits of randomness. We present the protocol $\langle \mathsf {P},\tilde{\mathsf {V}}\rangle$. $\mathsf {P}$ is exactly the same, where as $\tilde{\mathsf {V}}$ is described in 1.

The fact that the protocol preserves completeness and zero-knowledge follows readily, we focus on proving resettable soundness. To show resettable soundness, we show an efficient reduction from a resetting prover $\mathsf {rP}$ to a prover $\tilde{\mathsf {P}}$ for the original protocol, which preserves the cheating probability up to a polynomial loss.

Fix a malicious quantum resetting prover $\mathsf {rP}$ for a false instance x. Assume that $\mathsf {rP}$ makes at most q oracle queries, and has non-uniform advice $|{\psi _{0}}\rangle$. Assume $\mathsf {rP}$ has registers A, Z, E and query registers. The query registers are for querying a first message $\alpha$ and receiving the corresponding second message $\beta$. A, Z will hold the outputted first and third message, and E holds any internal qubits used. Then, $\tilde{\mathsf {P}}$ will perform as follows,

We show that,

Claim

$$ \Pr \left[ \langle \tilde{\mathsf {P}},\mathsf {V}\rangle \left( x\right) = 1\right] \ge \frac{1}{\left( 2q+1\right) ^2}\Pr _{k}\left[ \langle \mathsf {rP},\tilde{\mathsf {V}}\left( x,\cdot ;k\right) \rangle \left( x\right) =1\right] -\mathrm {negl}\left( \lambda \right) . $$

Proof

We denote by $\tilde{\mathsf {V}}^{R}$ a version of $\tilde{\mathsf {V}}$ such that $\tilde{\mathsf {V}}$ uses a truly random function R to derive its randomness (i.e. it runs $\mathsf {V}\left( x,\cdot ,R\left( \alpha \right) \right)$ for a first message $\alpha$). From the pseudo-randomness of the PRF it holds that,

$$\begin{aligned} \Pr _{k}\left[ \langle \mathsf {rP},\tilde{\mathsf {V}}\left( x,\cdot ;k\right) \rangle \left( x\right) =1\right] -\mathrm {negl}\left( \lambda \right) \le \mathop {{\mathbb E}}_{R}\left[ \Pr \left[ \langle \mathsf {rP},\tilde{\mathsf {V}}^{R}\rangle \left( x\right) =1\right] \right] \end{aligned}$$

(1)

We also denote $\tilde{\mathsf {P}}^{R}$ to be the malicious prover that uses $\tilde{V}^{R}$ (where R is a truly random function) instead of $\mathsf {V}\left( x,\cdot ;k\right)$ as the oracle for $\mathsf {rP}$. Again by pseudo-randomness of the PRF it holds that,

$$\begin{aligned} \Pr \left[ \langle \tilde{\mathsf {P}},\mathsf {V}\rangle \left( x\right) = 1\right] \ge \mathop {{\mathbb E}}_{R}\left[ \Pr \left[ \langle \tilde{\mathsf {P}}^{R},\mathsf {V}\rangle \left( x\right) = 1\right] \right] -\mathrm {negl}\left( \lambda \right) \end{aligned}$$

(2)

We define the event $W\left( i,b,\alpha ,r,R\right)$ to be the event where after sampling an external verifier’s randomness r, sampling i, b by $\tilde{\mathsf {P}}^{R}$ and measuring $\alpha$ as the first message in stage 4, $\tilde{\mathsf {P}}^{R}$ succeeds in convincing the external verifier. Then it holds that,

$$\begin{aligned} \mathop {{\mathbb E}}_{R}\left[ \Pr \left[ \langle \tilde{\mathsf {P}}^{R},\mathsf {V}\rangle \left( x\right) = 1\right] \right] =&\mathop {{\mathbb E}}_{r,R}\left[ \Pr \left[ \langle \tilde{\mathsf {P}}^{R},\mathsf {V}\left( x;r\right) \rangle \left( x\right) =1 \right] \right] \\ =&\sum _{\alpha }\mathop {{\mathbb E}}_{r,R}\left[ \mathop {{\mathbb E}}_{i,b}\left[ \Pr \left[ W\left( i,b,\alpha ,r,R\right) \right] \right] \right] .\\ \end{aligned}$$

Also, we note that,

$$ \Pr \left[ W\left( i,b,\alpha ,r,R\right) \right] = \left\| {|{{{\alpha }}}\rangle \langle {{{\alpha }}}| \otimes \varPi _{\mathsf {V}\left( x,\cdot ;r\right) }^{\alpha }\left( \mathsf {rP}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}_{i+b\rightarrow q}\right) \left( \mathsf {rP}^{\tilde{\mathsf {V}}^{R}}_{i\rightarrow i+b}\right) |{{{\alpha }}}\rangle \langle {{{\alpha }}}||{\psi ^{\tilde{\mathsf {V}}^{R}}_{i}}\rangle } \right\| ^{2} , $$

where

$$\varPi ^{\alpha }_{f} = \sum _{c: f\left( \alpha ,f\left( \alpha \right) ,c\right) =1}|{{{c}}}\rangle \langle {{{c}}}| , $$

the first $|{{{\alpha }}}\rangle \langle {{{\alpha }}}|$ is applied to the query register, the second $|{{{\alpha }}}\rangle \langle {{{\alpha }}}|$ is applied to the A register, and $\varPi ^{\alpha }_{V\left( x,\cdot ;r\right) }$ is applied to the Z register. Hence, it holds,

$$\begin{aligned}&\mathop {{\mathbb E}}_{R}\left[ \Pr \left[ \langle \tilde{\mathsf {P}}^{R},\mathsf {V}\rangle \left( x\right) = 1\right] \right] = \\&\sum _{\alpha }\mathop {{\mathbb E}}_{r,R}\left[ \mathop {{\mathbb E}}_{i,b}\left[ \left\| {|{{{\alpha }}}\rangle \langle {{{\alpha }}}| \otimes \varPi _{\mathsf {V}\left( x,\cdot ;r\right) }^{\alpha }\left( \mathsf {rP}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}_{i+b\rightarrow q}\right) \left( \mathsf {rP}^{\tilde{\mathsf {V}}^{R}}_{i\rightarrow i+b}\right) |{{{\alpha }}}\rangle \langle {{{\alpha }}}||{\psi ^{\tilde{\mathsf {V}}^{R}}_{i}}\rangle } \right\| ^{2}\right] \right] . \end{aligned}$$

For any fixed $\alpha ,r,R$ by the single value reprogramming lemma (1), it holds that,

$$\begin{aligned}&\mathop {{\mathbb E}}_{i,b}\left[ \left\| {|{{{\alpha }}}\rangle \langle {{{\alpha }}}| \otimes \varPi _{\mathsf {V}\left( x,\cdot ;r\right) }^{\alpha }\left( \mathsf {rP}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}_{i+b\rightarrow q}\right) \left( \mathsf {rP}^{\tilde{\mathsf {V}}^{R}}_{i\rightarrow i+b}\right) |{{{\alpha }}}\rangle \langle {{{\alpha }}}||{\psi ^{\tilde{\mathsf {V}}^{R}}_{i}}\rangle } \right\| ^{2}\right] \ge \\&\frac{\left\| {\left( |{{{\alpha }}}\rangle \langle {{{\alpha }}}|\right) \otimes \varPi _{\mathsf {V}\left( x,\cdot ;r\right) }^{\alpha }|{\psi _{q}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}}\rangle } \right\| ^{2}}{\left( 2q+1\right) ^{2}} . \end{aligned}$$

Above, $|{\psi _{q}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}}\rangle =\mathsf {rP}^{\tilde{V}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}|{\psi _0}\rangle$ . Hence it holds that,

$$\begin{aligned} \mathop {{\mathbb E}}_{R}\left[ \Pr \left[ \langle \tilde{\mathsf {P}}^{R},\mathsf {V}\rangle \left( x\right) = 1\right] \right] \ge&\sum _{\alpha }\mathop {{\mathbb E}}_{r,R}\left[ \frac{\left\| {\left( |{{{\alpha }}}\rangle \langle {{{\alpha }}}|\right) \otimes \varPi _{\mathsf {V}\left( x,\cdot ;r\right) }^{\alpha }|{\psi _{q}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}}\rangle } \right\| ^{2}}{\left( 2q+1\right) ^{2}}\right] \\ =&\sum _{\alpha }\mathop {{\mathbb E}}_{r,R}\left[ \frac{\left\| {\left( |{{{\alpha }}}\rangle \langle {{{\alpha }}}|\right) \otimes \varPi _{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}^{\alpha }|{\psi _{q}^{\tilde{\mathsf {V}}^{R}_{\alpha \rightarrow \mathsf {V}\left( x,\alpha ;r\right) }}}\rangle } \right\| ^{2}}{\left( 2q+1\right) ^{2}}\right] \\ \underset{\left( *\right) }{=}&\sum _{\alpha }\mathop {{\mathbb E}}_{r,R}\left[ \frac{\left\| {\left( |{{{\alpha }}}\rangle \langle {{{\alpha }}}|\right) \otimes \varPi ^{\alpha }_{\tilde{\mathsf {V}}^{R}}|{\psi _{q}^{\tilde{\mathsf {V}}^{R}}}\rangle } \right\| ^{2}}{\left( 2q+1\right) ^{2}}\right] \\ =&\mathop {{\mathbb E}}_{R}\left[ \frac{\Pr \left[ \langle \mathsf {rP},\tilde{\mathsf {V}}^{R}\rangle \left( x\right) =1\right] }{\left( 2q+1\right) ^2}\right] , \end{aligned}$$

where $\left( *\right)$ follows for any $x,\alpha$ and uniformly sampled r, R the oracles $\tilde{V}^{R}$ and $\tilde{V}^{R}_{\alpha \rightarrow \left( x,\alpha ;r\right) }$ are perfectly indistinguishable. Thus, it holds

$$ \mathop {{\mathbb E}}_{R}\left[ \Pr \left[ \langle \tilde{\mathsf {P}}^{R},\mathsf {V}\rangle \left( x\right) = 1\right] \right] \ge \mathop {{\mathbb E}}_{R}\left[ \frac{\Pr \left[ \langle \mathsf {rP},\tilde{\mathsf {V}}^{R}\rangle \left( x\right) =1\right] }{\left( 2q+1\right) ^2}\right] . $$

Hence, by combining Eqs. 1, 2 with the equation above, the claim follows.

4.3 Deterministic-Prefix Resetting Provers

5 A Post-Quantum Resettably Sound Zero Knowledge Protocol

In this section we present a post-quantum resettably-sound zero-knowledge protocol. The protocol is also constant-round.

Ingredients and Notation:

• A post-quantum pseudorandom function $\mathsf {PRF}$.

• A post-quantum non-interactive commitment scheme $\mathsf {Com}$.

• A post-quantum compute and compare obfuscator $\mathsf {Obf}$.

• A quantum fully-homomorphic encryption scheme $( \mathsf {QFHE.Gen}, \mathsf {QFHE.Enc}, \mathsf {QFHE.QEnc}, \mathsf {QFHE.Dec}, \mathsf {QFHE.QDec}, \mathsf {QFHE.Eval})$.

• A delayed-input 3-message post-quantum WI proof $(\mathsf {WI}\mathsf {.P}, \mathsf {WI}\mathsf {.V})$ for $\mathbf {NP}$.

• A delayed-input 4-message sub-exponential statistical WI argument system $(\mathsf {sWI}\mathsf {.P}, \mathsf {sWI}\mathsf {.V})$ for $\mathbf {NP}$.

• A 2-message post-quantum input hiding, sub-exponentially statistically function hiding secure function evaluation scheme $(\mathsf {SFE.Gen},$ $\mathsf {SFE.Enc},$ $\mathsf {SFE.Eval},$ $\mathsf {SFE.Dec})$.

• Denote by $\varepsilon \in (0,1)$ a constant such that both the 4-message WI and SFE have sub-exponential statistical security with respect to (in the statistical indistinguishability guarantee in both primitives, the statistical distance is bounded by $O(2^{-\lambda ^\varepsilon })$).

The protocol is described in Subsect. 5.1.

5.1 Protocol Construction

The protocol is as follows,

• Common Input: An instance $x\in \mathcal {L}$, security parameter $\lambda := |x|$. Below we denote $\bar{\lambda }= \lambda ^{2/\varepsilon }$.

• $\mathsf {P}$’s private input: A classical witness $w \in \mathcal {R}_{\mathcal {L}}(x)$ for $x$.

• 1. Prover Commitment:$\mathsf {P}$ sends the following,

  • Non-interactive commitments to the witness, and two strings of zeros of length $\bar{\lambda }$:

    $$\mathsf {cmt}_1 \leftarrow \mathsf {Com}(1^\lambda , w),\mathsf {cmt}_2 \leftarrow \mathsf {Com}(1^\lambda , 0^{\bar{\lambda }}),\mathsf {cmt}_3 \leftarrow \mathsf {Com}(1^\lambda , 0^{\bar{\lambda }}).$$

  • Two independent first messages $\alpha _1, \alpha _2$ for two independent executions of 3-message, delayed-input WI proofs $(\mathsf {WI}\mathsf {.P}, \mathsf {WI}\mathsf {.V})$.

  • First message h of a 4-message delayed-input statistical WI argument $(\mathsf {sWI}\mathsf {.P}, \mathsf {sWI}\mathsf {.V})$, with security parameter $\bar{\lambda }$.

• 2. Extractable Commitment to Verifier Secret:$\mathsf {V}$ samples a PRF seed $s\leftarrow \{0,1\}^\lambda$. $\mathsf {V}$’s randomness for the first message is generated by applying $\mathsf {PRF}_s(\cdot )$ to the first prover message.

  • (a) $\mathsf {V}$ computes $u \leftarrow \{ 0, 1 \}^{\lambda }$, $v \leftarrow \{ 0, 1 \}^{\lambda }$, $(\mathsf {pk}, \mathsf {sk}) \leftarrow \mathsf {QFHE.Gen}(1^{\lambda })$. $\mathsf {V}$ sends

    $$ \mathsf {pk}, \mathsf {ct}_{\mathsf {V}}\leftarrow \mathsf {QFHE.Enc}_{\mathsf {pk}}(u), \widetilde{\mathbf {CC}}\leftarrow \mathsf {Obf}\Big (\mathbf {CC}\big [ \mathsf {QFHE.Dec}_{\mathsf {sk}}(\cdot ), v, \mathsf {sk}\big ]\Big ). $$

    $\mathsf {V}$ also sends $\beta _1, \beta _2$ following $\alpha _1, \alpha _2$, and $\alpha _\mathbf {s}$ following h.

  • (b) $\mathsf {P}$ sends,

    • $\mathsf {ct}_{\mathsf {P}} \leftarrow \mathsf {SFE.Enc}(1^{\bar{\lambda }} ; 0^\lambda )$ an encryption of $0^\lambda$ encrypted with security parameter $\bar{\lambda }$.

    • $\beta _\mathbf {s}$ for $h, \alpha _\mathbf {s}$ as the last message of $\mathsf {sWI}\mathsf {.V}$ in the 4-message WI protocol.

    • A WI proof $\gamma _1$, following $\alpha _1$ and $\beta _1$, that $x\in \mathcal {L}$ or, (1) the randomness used to generate $\mathsf {ct}_{\mathsf {P}}$ is the content of $\mathsf {cmt}_2$¹, and (2) the randomness for $h, \beta _\mathbf {s}$ is the content of $\mathsf {cmt}_3$.

  • (c) $\mathsf {V}$ applies $\mathsf {PRF}_s(\cdot )$ to $\left( \mathsf {ct}_\mathsf {P}, \beta _\mathbf {s}, \text { Prover's first message} \right)$ to generate randomness for its current message. It sends,

    • $\hat{\mathsf {ct}}\leftarrow \mathsf {SFE.Eval}\Big (\mathbf {CC}\big [ \mathsf {Id(\cdot )}, u, v \big ],\, \mathsf {ct}_{\mathsf {P}} \Big )$ executed with security parameter $\bar{\lambda }$, where $\mathsf {Id(\cdot )}$ is the identity function.

    • $\gamma _\mathbf {s}$, for $h, \alpha _\mathbf {s}, \beta _\mathbf {s}$, proving that the transcript of the verifier so far is explainable or, $\mathsf {cmt}_1$ is a commitment to a non-witness $z \notin \mathcal {R}_{\mathcal {L}}(x)$. The witness that $\mathsf {V}$ uses for the proof is its randomness, that proves that the transcript is explainable.

• 3. Final WI by the Prover: $\mathsf {P}$ sends $\gamma _2$ which proves that $x \in \mathcal {L}$ or, that $\mathsf {cmt}_1$ is a valid commitment and there exists a string c such that $\widetilde{\mathbf {CC}}(c) \ne \bot$. The witness that $\mathsf {P}$ uses for its proofs $\gamma _1, \gamma _2$ is w, which proves $x \in \mathcal {L}$.

• 4. Acceptance: $\mathsf {V}$ accepts if the WI statements by the prover are verified.

• 5. Aborts: During the protocol, if either party does not respond, sends a message of an incorrect form or provides a non-convincing WI proof it considered as an abort, and the other party terminates the interaction.