text:
\section{Introduction}
Zero-knowledge protocols allow to prove statements without revealing anything but the mere fact that they are true. Since their introduction by Goldwasser, Micali, and Rackoff \cite{GoldwasserMR89} they have had a profound impact on modern cryptography and theoretical computer science at large. Following more than three decades of exploration, zero-knowledge protocols are now quite well understood in terms of their expressiveness and round complexity. In particular, under standard computational assumptions, arbitrary $\NP$ statements can be proved in only a constant number of rounds \cite{goldreich1986prove,goldreich1996construct}.

In this work, we consider classical zero-knowledge protocols with {\em post-quantum security}, namely, protocols that can be executed by classical parties, but where both soundness and zero-knowledge are guaranteed even against efficient quantum adversaries. Here our understanding is far more restricted than in the classical setting. Indeed, not only are we faced with stronger adversaries, but also have to deal with the fact that quantum information behaves in a fundamentally different way than classical information, which summons new challenges in the design of zero-knowledge protocols.

In his seminal work \cite{watrous2009zero}, Watrous developed a new quantum simulation technique and used it to show that classical zero-knowledge protocols for $\NP$, such as the Goldreich-Micali-Wigderson $3$-coloring protocol \cite{goldreich1986prove}, are also zero knowledge against quantum verifiers, assuming commitments with post-quantum hiding. These protocols are, in fact, {\em proof systems} meaning that soundness holds against unbounded adversarial provers, let alone efficient quantum ones. As in the classical setting, to guarantee a negligible soundness error (the gold standard in cryptography) these protocols require a polynomial number of rounds.

Watrous' techniques do not apply for classical constant-round protocols. In fact, constant-round zero-knowledge protocols with post-quantum security remains an open question, {\em even when the honest parties and communication are allowed to be quantum.} The gap between classical and quantum zero knowledge stems from fundamental aspects of quantum information such as the no-cloning theorem \cite{Wootters:1982zz} and quantum state disturbance \cite{FuchsPeres96}. These pose a substantial barrier for classical zero-knowledge simulation techniques, a barrier that has so far been circumvented only in specific settings (such as, \cite{watrous2009zero}). Overcoming these barriers in the context of constant-round zero-knowledge seems to require a new set of techniques.

\subsection{Results}\label{subsec:results}

Under standard computational assumptions, we resolve the above open question --- we construct a classical, post-quantumly secure, computational-zero-knowledge argument for \NP in a constant number of rounds (with a negligible soundness error). That is, the honest verifier and prover (given a witness) are efficient classical algorithms. In terms of security, both zero-knowledge and soundness hold against arbitrary polynomial-size non-uniform quantum circuits.

Our construction is based on fully-homomorphic encryption supporting the evaluation of quantum circuits (QFHE) as well as additional standard classical cryptographic primitives. All are required to be secure against efficient quantum algorithms with non-uniform quantum advice. QFHE was recently constructed \cite{mahadev2018classical, brakerski2018quantum} based on the assumption that the Learning with Errors Problem \cite{Regev09} is hard for the above class of algorithms (from hereon, called \QLWE) and a circular security assumption (analogous to the assumptions required for multi-key FHE in the classical setting). All other required primitives can be based on the \QLWE assumption.\footnote{We note that cryptographic hardness assumptions against algorithms with quantum advice are considered quite often, \QLWE included (see for instance \cite{watrous2009zero,broadbent2016zero,BrakerskiCMVV18}).}

\begin{theorem}[informal]\label{intro_thm}
	Assuming \QLWE and QFHE, there exist a classical, post-quantumly secure, computational-zero-knowledge argument in a constant number of rounds for any $\lang \in \NP$.
\end{theorem}

Based on our techniques, we also construct (under the same assumptions) a fully-simulatable coin-flipping protocol, which combined with the work of Broadbent et al. \cite{broadbent2016zero}, yields constant-round zero-knowledge arguments for \QMA with quantum honest parties.

\begin{corollary}[informal]
	Assuming \QLWE and QFHE, there exist a quantum, post-quantumly secure, computational-zero-knowledge argument in a constant number of rounds for any $\lang \in \QMA$.
\end{corollary}

\paragraph{Main Technical Contribution: Non-Black-Box Quantum Extraction.} Our main technical contribution is a new technique for extracting information from quantum circuits in a constant number of rounds. The technique circumvents the quantum information barriers previously mentioned. A key feature that enables this is using the adversary's circuit representation in a non-black-box manner.

The technique, in particular, yields a constant round extractable commitment. In such a commitment protocol, the verifier can commit to a classical (polynomially long) string. This commitment is statistically binding and hiding against efficient quantum receivers. Furthermore, it guarantees the existence of a simulator, which given non-black-box access to the sender's code, can simulate its view while extracting the committed plaintext. Further details are given in the technical overview below.

\subsection{Technical Overview}

We next discuss the main challenges in the design of post-quantum zero knowledge in constant rounds, and our main technical ideas toward overcoming these challenges.

\subsubsection{Classical Protocols and the Post-Quantum Barrier}

To understand the challenges behind post-quantum zero knowledge, let us first recall how classical constant-round protocols work, and identify why they fail in the quantum setting. Classical constant-round protocols typically involve three main steps: (1) a prover commitment $\alpha$ to a set of bits, (2) a verifier challenge $\beta$, and (3) a prover response $\gamma$, in which it opens the commitments corresponding to the challenge $\beta$. For instance, in the 3-coloring protocol of \cite{goldreich1986prove}, the prover commits to the (randomly permuted) vertex colors, the verifier picks some challenge edge, and the prover opens the commitments corresponding to the vertices of that edge. To guarantee a negligible soundness error, this is repeated in parallel a polynomial number of times.

As describe so far, the protocol satisfies a rather weak zero-knowledge guarantee --- a simulator can efficiently simulate the verifier's view in the protocol {\em if it knows the verifier's challenge $\beta$ ahead of time.} To obtain an actual zero-knowledge protocol, we need to exhibit a simulator for any {\em malicious} verifier, including ones who may arbitrarily choose their challenge depending on the prover's message $\alpha$. For this purpose, an initial step (0) is added where the verifier commits ahead of time to its challenge, later opening it in step (2) \cite{goldreich1996construct}.

The added step allows the simulator to obtain the verifier's challenges ahead of time by means of {\em rewinding}. Specifically, having obtained the verifier commitment, the simulator takes a snapshot of the verifier's state and then runs it twice: first it generates a bogus prover commitment, and obtains the verifier challenge, then with the challenges at hand, it returns to the snapshot (effectively rewinding the verifier) and runs the verifier again to generate the simulated execution. The binding of the verifier's commitment guarantees that it will never use a different challenge, and thus simulation succeeds.

\paragraph{Barriers to Post-Quantum Security.} By appropriately instantiating the verifier commitment, the above protocol can be shown  to be sound against unbounded provers, and in particular efficient quantum provers. One could expect that by instantiating the prover's commitments so to guarantee hiding against quantum adversaries, we would get post-quantum zero knowledge. However, we do not know how to prove that such a protocol is zero knowledge against quantum verifiers. Indeed, the simulation strategy described above fails due to two basic concepts of quantum information theory:

\begin{itemize}
	\item {\bf No Cloning:} General quantum states cannot be copied. In particular, the simulator cannot take a snapshot of the verifier's state.

	\item {\bf Quantum State Disturbance:} General quantum circuits, which in particular perform measurements, are not reversible. Once the simulator evaluates the verifier's quantum circuit to obtain its challenge, the verifier's original state (prior to this bogus execution) has already been disturbed and cannot be recovered.
\end{itemize}

Watrous \cite{watrous2009zero} showed that in certain settings the rewinding barrier can be circumvented. He presents a \emph{quantum rewinding lemma}, which roughly shows that {\em non-rewinding} simulators that succeed in simulating any prover message with noticeable probability can be amplified into full-fledged simulators (provided certain independence conditions on the initial success probability). This allows proving that classical protocols, like the polynomial sequential repetition of the GMW protocol, are post-quantum zero knowledge (assuming commitments with hiding against quantum adversaries). The technique is insufficient, however, to prove post-quantum zero knowledge of classical {\em constant-round} protocols, such as the GK protocol described above. In GK-like protocols non-rewinding simulators with a noticeable success probability are not known.

\paragraph{Can Non-Black-Box Techniques Cross the Quantum Barriers?} Rewinding is, in fact, often an issue {\em also in the classical setting.} Starting with the work of Goldreich and Krawczyk \cite{GoldreichK96}, it was shown that constant-round zero-knowledge protocols with certain features, such as a public-coin verifier, cannot be obtained using simulators that only use the verifier's next message function as a black box. That is, simulators that are based solely on rewinding. Surprisingly, Barak \cite{Barak01} showed that these barriers can be circumvented using {\em non-black-box techniques}. He constructed a constant-round public-coin zero-knowledge protocol by having the simulator take advantage of the explicit circuit representation of the verifier. Following Barak's work, different non-black-box techniques have been introduced to solve various problems in cryptography (c.f., \cite{DengGS09,ChungLP13,Goyal13, BitanskyP15b,ChungPS16}).

A natural question is whether we can leverage classical protocols with non-black-box simulators, such as Barak's, in order to circumvent the discussed barriers in the quantum setting. Trying to answer this question reveals several challenges. One inherent challenge is that classical non-black-box techniques naturally involve cryptographic tools that support classical computations. Obtaining zero knowledge against quantum verifiers would require analogous tools for quantum computations. As an example, Barak relies on the existence of constant-round succinct proof systems for the correctness of classical computations; to obtain post-quantum zero knowledge, such a protocol would need to support also quantum computations, while (honest) verification should remain classical. Existing protocols for classical verification of quantum computations \cite{Mahadev18} are neither constant round nor succinct.

Another family of non-black-box techniques \cite{BitanskyP15b,bitansky2019weak}, different from that of Barak, is based on fully-homomorphic encryption. Here (as mentioned above) constructions for homomorphic evaluation of quantum computations exist \cite{mahadev2018classical,brakerski2018quantum}. The problem is that the mentioned non-black-box techniques {\em do perform state cloning}. Roughly speaking, starting from the same state, they evaluate the verifier's computation (at least) twice: once homomorphically, under the encryption, and once in the clear.\footnote{In fact, Barak's technique also seems to require state cloning. Roughly speaking, the same verifier state is used once for simulating the main verifier execution and once when computing the proof for the verifier's computation.} An additional hurdle is proving soundness against quantum provers. Known non-black-box techniques are sound against efficient classical provers, and often use tools that are not known in the quantum setting, such as constant-round knowledge extraction, which is further discussed below.

Our main technical contribution is devising a non-black-box technique that copes with the above challenges. We next explain the main ideas behind the technique.

\subsubsection{Our Technique: A No-Cloning Extraction Procedure}

Toward describing the technique, we first restrict attention to a more specific problem. Specifically, constructing a constant-round post-quantum zero-knowledge protocol can be reduced to the problem of constructing constant-round {\em quantumly-extractable commitments}. We recall what such commitments are and why they are sufficient, and then move to discuss the commitments we construct.

A quantumly-extractable commitment is a classical protocol between a sender $S$ and a receiver $R$. The protocol satisfies the standard (statistical) binding and post-quantum hiding, along with a plaintext extraction guarantee. Extraction requires that there exists an efficient quantum simulator $E$ that given any malicious sender $S^*$, represented by a polynomial-size quantum circuit, can simulate the view of $S^*$ in the commitment protocol while extracting the committed plaintext message. Specifically, $E(S^*)$ outputs a classical transcript $\widetilde T$, a verifier (quantum) state $\ket{\widetilde \psi}$, and an extracted plaintext $\widetilde m$ that are computationally indistinguishable from a real transcript, state, and plaintext $(T,\ket{\psi},m)$, where $T$ and $\ket{\psi}$ are the transcript and sender state generated at the end of a real interaction between the receiver $R$ and sender $S^*$, and $m$ is the plaintext fixed by the commitment transcript $T$.

Such commitments allow enhancing the classical four-step protocol described before to satisfy post-quantum zero-knowledge. We simply instantiate the verifier's commitment to the challenge $\beta$ in step (0) with a quantumly-extractable commitment. To simulate a malicious quantum verifier $V^*$, the zero-knowledge simulator can then invoke the commitment simulator $E(V^*)$, with $V^*$ acting as the sender, to obtain a simulated commitment as well as the corresponding challenge $\beta$. Now the simulator knows the challenge ahead of time, before producing the prover message $\alpha$ in step (1), and using the (simulated) verifier state $\ket{\widetilde \psi}$, can complete the simulation, {\em without any state cloning.} (Proving soundness is actually tricky on its own due to malleability concerns. We remain focused on zero knowledge.)

The challenge is of course to obtain constant-round commitments with {\em no-cloning extraction}. Indeed, classically-extractable commitments have been long known in constant rounds under minimal assumptions, based on rewinding (and thus state cloning) \cite{PrabhakaranRS02}. We next describe our non-black-box technique and how it enables quantum extraction without state cloning.

\paragraph{The Non-Black-Box Quantum Extraction Technique: A Simple Case.} To describe the technique, we first focus on a restricted class of adversarial senders that are {\em non-aborting and explainable}. The notion of non-aborting explainable senders considers senders $S^*$ whose messages can always be {\em explained} as a behavior of the honest (classical) sender with respect to {\em some} plaintext and randomness (finding this explanation may be inefficient); in particular, they never abort. The notion further restricts that of  {\em (aborting) explainable adversaries} from \cite{bitansky2019weak}, which also allows aborts. To even further simplify our exposition, we first address classical (rather than quantum) senders, but crucially, while avoiding any form of state cloning. Later on, we shall address general quantum adversaries.

Our protocol is inspired by \cite{BitanskyP15b, bitansky2019weak} and relies on two basic tools. The first is fully-homomorphic encryption (FHE) --- an encryption scheme that allows to homomorphically apply any polynomial-size 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 {\em compactness}). The second is {\em compute and compare program obfuscation} (CCO).  A compute-and-compare program $\CC{f,u,z}$ is given by a function $f$  (represented as a circuit), a target string $u$ in its range, and a message $z$; it outputs $z$ on every input $x$ such that $f(x)=u$, and rejects all other inputs. A corresponding obfuscator compiles any such program into a program $\obfC$ with the same functionality. In terms of security, provided that the target $u$ has high entropy conditioned on $f$ and $z$, the obfuscated program is computationally indistinguishable from a simulated dummy program, independent of $(f,u,z)$. Such post-quantumly-secure obfuscators are known under QLWE \cite{goyal2017lockable,wichs2017obfuscating,goyal2019perfect}.

\newpage\noindent
To commit to a message $m$, the protocol consists of three steps:
\begin{enumerate}
	\item
	The sender $S$ samples:
	\begin{itemize}
		\item two random strings $u$ and $v$,
		\item a secret key $\fheK$ for an FHE scheme,
		\item an FHE encryption $\fheCT_v = \fheE_{\fheK}(v)$ of $v$,
		\item an obfuscation $\obfC$ of $\CC{f,u,z}$, where $z = (m,\fheK)$ and $f = \fheD_{\fheK}$ is the FHE decryption circuit.
	\end{itemize}     It then sends $(\fheCT_v,\obfC)$ to the receiver $R$.

	\item
	The receiver $R$ sends a guess $v'$.

	\item
	$S$ rewards a successful guess: if $v = v'$, it sends back $u$ (and otherwise $\bot$).
\end{enumerate}
The described commitment protocol comes close to our objective. First, it is binding --- the obfuscation $\obfC$ uniquely determines $z=(m,\fheK)$. Second, it is hiding --- a receiver (even if malicious) gains no information about the message $m$. To see this, we argue that no receiver sends $v'=v$ at the second message, but with negligible probability. Indeed, given only the first sender message $(\fheCT_v,\obfC)$, the receiver obtains no information about $u$. Hence, we can invoke the CCO security and replace the obfuscation $\obfC$ with a simulated one, which is independent of the secret FHE key $\fheK$. This, in turn, allows us to invoke the security of encryption to argue that the first message $(\fheCT_v,\obfC)$ hides $v$. It follows that the third sender message is $\bot$ (rather than the target $u$) with overwhelming probability, which again by CCO security implies that the entire view of the receiver can be simulated independently of $m$.

Lastly, a non-black-box simulator, given the circuit representation of an explainable sender $S^*$, can simulate the sender's view, while extracting $m$. It first runs the sender to obtain the first message $(\fheCT_v,\obfC)$. At this point, it can use the sender's circuit $S^*$ to continue the emulation of $S^*$  {\em homomorphically under the encryption} $\fheCT_v$. The key point is that, under the encryption, we do have $v$. We can (homomorphically) feed $v$ to the sender, and obtain an encryption $\fheCT_u$ of $u$. Now, the simulator feeds $\fheCT_u$ to the obfuscation $\obfC$, and gets back $z = (m,\fheK)$. (Note that here the compactness of FHE is crucial --- the sender $S^*$ could be of arbitrary polynomial size, whereas $\obfC$ and thus also $\fheCT_u$ are of fixed size.)

Having extracted $m$, it remains to simulate the inner (for now, classical) state $\psi$ of the sender $S^*$ and the full interaction transcript $T$. These are actually available, but in encrypted form, as a result of the previous homomorphic computation. Here we use the fact that the extracted $z$ also includes the decryption key $\fheK$, allowing us to obtain the state $\psi$ and transcript $T$ {\em in the clear}.

An essential difference between the above extraction procedure and previous non-black-box extraction techniques (e.g. \cite{BitanskyP15b,bitansky2019weak} is that {\em it does not perform any state cloning}. As explained earlier, previous procedures would perform the same computation twice, once under the encryption, and once in the clear. Here we perform the computation once, partially in the clear, and partially homomorphically. Crucially, we have a mechanism to peel off the encryption at the end of second part so that we do not have to redo the computation in the clear.

\paragraph{Indistinguishability through Secure Function Evaluation.} The described protocol does not quite achieve our objective. The simulated interaction is, in fact, easy to distinguish from a real one. Indeed, in a simulated interaction the simulator's guess in the second message is $v'=v$, whereas the receiver cannot produce this value. To cope with this problem, we augment the protocol yet again, and perform the second step under a {\em secure function evaluation} (SFE) protocol. This can be thought of as homomorphic encryption with an additional {\em 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.

\newpage\noindent
The augmented protocol is similar to the previous one, except for the last two steps, now done using SFE:
\begin{enumerate}
	\item
	{\color{gray} The sender $S$ samples:
		\begin{itemize}
			\item two random strings $u$ and $v$,
			\item a secret key $\fheK$ for an FHE scheme,
			\item an FHE encryption $\fheCT_v = \fheE_{\fheK}(v)$ of $v$,
			\item an obfuscation $\obfC$ of $\CC{f,u,z}$, where $z = (m,\fheK)$ and $f = \fheD_{\fheK}$ is the FHE decryption circuit.
		\end{itemize}     It then sends $(\fheCT_v,\obfC)$ to the receiver $R$.}

	\item
	The receiver $R$ sends $\fheCT'_{v'}$, a guess $v'$ encrypted using SFE. (The honest receiver sets $v'$ arbitrarily.)

	\item
	$S$ homomorphically evaluates the function that given input $v$, returns $u$ (and otherwise $\bot$).
\end{enumerate}
Indistinguishability of the simulated sender view from the real sender view now follows since the SFE encryption $\fheCT'_{v'}$ hides $v'$. The SFE circuit privacy guarantees that the homomorphic SFE evaluation does not leak any information about the target $u$, as long as the receiver does not send an SFE encryption of $v$.

\paragraph{A Malleability Problem and its Resolution.} While we could argue before that a malicious receiver cannot output $v$ in the clear, arguing that it does not output an SFE encryption of $v$ is more tricky. In particular, the receiver might be able to somehow maul the FHE encryption $\fheCT_v$ to get an SFE encryption $\fheCT'_{v}$ of the value $v$, without actually ``knowing'' the value $v$. Classically, such malleability problems are solved using {\em extraction}. If we could efficiently extract the value encrypted in the SFE encryption $\fheCT'$, then we could rely on the previous argument. However, as explained before, efficient extraction is classically achieved using rewinding and thus state cloning. While so far we have focused on avoiding state cloning for the sake of simulating the sender, we should also avoid state cloning when proving hiding of the commitment as we are dealing with quantum receivers. It seems like we are back to square one.

To circumvent the problem, we rely on the fact that the hiding requirement of the commitment is relatively modest --- commitments to different plaintexts should be indistinguishable. This is in contrast the efficient simulation requirement for the sender (needed for efficient zero knowledge simulation). Here one commonly used solution is {\em complexity leveraging} --- we can design the SFE, FHE, and CCO so that extraction from SFE encryptions can be done in brute force, without any state cloning, and without compromising the security of the FHE and CCO. This comes at the cost of assuming subexponential (rather than just polynomial) hardness of the primitives in use.

A different solution, which is also the one we use in the body of the paper, relies on hardness against efficient quantum adversaries with {\em non-uniform quantum advice} (instead of subexponential hardness)
~Here the receiver sends a commitment to the SFE encryption key in the beginning of the protocol. The reduction establishing the hiding of the protocol gets as non-uniform advice the initial receiver (quantum) state that maximizes the probability of breaking hiding, along with the corresponding SFE key. This allows for easy extraction from SFE encryptions, without any state cloning.

The full solution contains additional steps meant to establish that the receiver's messages are appropriately structured (e.g., the receiver's commitment defines a valid SFE key, and the SFE encryption later indeed uses that key). This is done using standard techniques based on witness-indistinguishable proofs, which exist in a constant number of rounds \cite{goldreich1986prove} assuming commitments with post-quantum hiding (and in particular, QLWE).

\paragraph{Dealing with Quantum Adversaries.} Above, we have assumed for simplicity that the sender is classical and have shown a simulation strategy that requires no state cloning. We now explain how the protocol is augmented to deal with quantum senders (for now still restricting attention to non-aborting explainable senders). The first natural requirement in order to deal with quantum senders is that the cryptographic tools in use (e.g., SFE encryption) will be postqantum secure. This can be guaranteed assuming QLWE.

As already mentioned earlier in the introduction, post-quantum security alone is not enough --- we need to make sure that our non-black-box extraction technique can also work with quantum, rather than classical, circuits representing the sender $S^*$. For this purpose, we use {\em quantum} fully-homomorphic encryption (QFHE). In a QFHE scheme, the encryption and decryption keys are (classical) strings and the encryption and decryption algorithms are classical provided that the plaintext is classical (and otherwise quantum). Most importantly, QFHE allows to homomorphically evaluate quantum circuits. Such QFHE schemes were recently constructed in \cite{mahadev2018classical, brakerski2018quantum} based on \QLWE and a circular security assumption (analogous to the assumptions required for multi-key FHE in the classical setting).

The augmented protocol simply replaces the FHE scheme with a QFHE scheme (other primitives, such as the SFE and compute-and-compare are completely classical in terms of functionality and only need to be post-quantum secure). In the augmented protocol, the honest sender and receiver still act classically. In contrast, the non-black-box simulator described before is now quantum --- it homomorphically evaluates the quantum sender circuit $S^*$. A technical point is that QFHE should support the evaluation of a quantum circuit with an initial quantum state --- in our case the quantum sender $S^*$ and its inner state after it sends the first message. This is achieved by existing QFHE schemes (for instance, by using their public key encryption mode, and encrypting the initial state prior to the computation).

\paragraph{Dealing with Aborts.} So far, we have dealt with explainable senders that are non-aborting. This is indeed a strong restriction and in fact, quantumly-extractable commitments against this class of senders can be achieved using black-box techniques (see more in the related work section). However, considering general adversaries who, with noticeable probability, may abort at some stage of the protocol, existing black-box techniques completely fail. In contrast, as we explain next, our non-black-box technique achieves a meaningful guarantee even against aborting senders.

In our protocol, an aborting sender $S^*$ may refuse to perform the SFE evaluation in the last step of the protocol. In this case, the simulator will get stuck --- the simulated transcript and sender state $\ket{\psi}$ will remain forever locked under the encryption (since the simulator cannot use the obfuscation $\obfC$ to get the decryption key $\fheK$). Nevertheless, {\em in executions where there is no abort, the simulation is valid}. That is, non-aborting simulated executions are indistinguishable from non-aborting real executions; furthermore, they occur with the same probability (up to a negligible difference).

Another feature of the protocol is that if aborting executions occur with noticeable probability, they are easy to simulate by rejection sampling. To simulate an aborting execution, the simulator sends an SFE encryption $\fheCT'_{v'}$ of some arbitrary string $v'$ (e.g. the all-zero string). Crucially, it does so in the clear, rather than under the encryption. This is repeated until an aborting execution is produced. The hiding of SFE ciphertexts guarantee that this will occur with the right probability.

This gives rise to a full simulation strategy: (1) run the non-black-box simulator. If no abort occurs, simulation succeeds. Otherwise, (2) simulate an abort. Some care has to be taken to make sure that the expected running time of the simulator is polynomial. This is done using standard techniques \cite{goldreich1996construct} for estimating the probability of abort.

\paragraph{From Explainable Adversaries to Malicious Ones.} The only remaining gap is the assumption that senders are explainable; that is, the messages they send (up to the point that they possibly abort), can always be explained as messages that would be sent by the honest (classical) sender for some plaintext and randomness. The simulator we described crucially relies on this; in particular, the CCO $\obfC$ and the FHE ciphertext $\fheCT_v$ must be formed consistently with each other for the simulator to work. Crucially, it suffices that {\em there exists an explanation} for the messages, and we do not have to efficiently extract it as part of the simulation;\footnote{This is in contrast to other restrictions of the adversary considered in the literature, like semi-honest and semi-malicious adversaries \cite{GoldreichMW87, HaitnerIKLP11,BoyleG0KS13}.} indeed, efficient quantum extraction is exactly the problem we are trying to solve.

The commitment protocol against explainable senders naturally gives rise to a zero-knowledge protocol against explainable verifiers. As is often the case in the design of zero knowledge protocols (see discussion in \cite{bitansky2019weak}), dealing with explainable verifiers is actually the hard part of designing zero-knowledge protocols. Specifically, we use a generic transformation of \cite{bitansky2019weak}, slightly adapted to our setting, which converts zero-knowledge protocols against explainable verifiers to ones against arbitrary malicious verifiers. The transformation is based on constant-round (post-quantumly-secure) witness-indistinguishable proofs, which as mentioned before can be obtained based on QLWE.

\paragraph{A Note on Universal Simulators, Composition, and Verifiers with Quantum Advice.} The traditional zero knowledge requirement asks that for any malicious verifier $V^*$, there exists a simulator $\zkS_{V^*}$. However, most classical protocols achieve a stronger guarantee that flips the order of quantifiers --- they provide one {\em universal} simulator $\zkS$, which works for all verifiers. That is, $\zkS(x,V^*)$ is given as input the instance $x$ in the \NP language and any circuit $V^*$ representing the verifier, and successfully simulates the view of $V^*$ in a real interaction.
This stronger guarantee is especially useful for {\em composition}, namely, when using the zero-knowledge protocol as a subroutine inside an (outer) protocol. This is because it allows to hardwire the inner state $s$ of the adversary in the (outer) protocol into the description of $V^*$, and modularly apply the simulation guarantee.

We achieve the same universal guarantee as above with respect to (non-uniform) quantum, rather than classical, circuits. However, in the context of composability in the quantum setting, we may ask for a stronger requirement. Specifically, we would like to be able to "hardwire" into $V^*$ a quantum inner state $\ket{\psi}$, that is not necessarily efficiently generatable. Indeed, if we wish to show post-quantum security of an outer protocol that uses the zero-knowledge protocol as a subroutine, the state of the adversary in the outer protocol is quantum, and when we perform an averaging argument (to modularly use the ZK definition guarantee) and fix a specific quantum state for the verifier, that specific state might not be efficiently generatable.
Our protocol falls short of achieving this stronger feature of {\em universality with respect to quantum advice}. In a nutshell, this is because whenever our non-black-box simulator gets stuck due to an abort, we discard the simulation, and simulate from scratch an abort. The initial quantum state $\ket{\psi}$ of the verifier is disturbed due to the first (stuck) simulation, preventing us from lawfully simulating an abort relative to $V^*(\ket{\psi})$.

The lack of universality with respect to quantum advice means that when using our zero-knowledge protocol inside another protocol, one has to work harder and essentially reprove simulation validity, rather than modularly use the universal simulation guarantee. We do, however, show a somewhat relaxed form of universality with respect quantum advice, which does make composition more modular, but is not as clean as full universality.
The problem of (non-relaxed) universality with respect to quantum advice is left open.

\subsection{More Related Work on Post-Quantum Zero Knowledge}
The study of post-quantum zero-knowledge (QZK) protocols was initiated by van de Graaf \cite{van1997towards}, 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 \cite{watrous2002limits}, and also demonstrated that relaxed notions such as zero-knowledge with a trusted common reference string can be achieved \cite{Kobayashi03,damgaard2004zero}. Watrous \cite{watrous2009zero} was the first to show that the barriers of quantum information theory can be crossed, demonstrating a post-quantum zero-knowledge protocol for \NP (in a polynomial number of rounds).

\paragraph{Zero Knowledge for \QMA.} Another line of work aims at constructing quantum (rather than classical) protocols for $\QMA$ (rather than \NP). Following a sequence of works \cite{ben2006secure,liu2006consistency,dupuis2010secure, dupuis2012actively,morimae2015quantum}, Broadbent, Ji, Song and Watrous \cite{broadbent2016zero} show a zero-knowledge quantum proof system for all of \QMA~(in a polynomial number of rounds).

\paragraph{Quantum Proofs and Arguments of Knowledge.} Extracting knowledge from quantum adversaries was investigated in a sequence of works \cite{unruh2012quantum,hallgren2011classical,lunemann2011fully,ambainis2014quantum}. A line of works considered different variants of quantum proofs and arguments of knowledge (of the witness), proving both feasibility results and limitations. In particular, Unruh  \cite{unruh2012quantum} shows that assuming post-quantum injective one-way functions, some existing systems are a quantum proof of knowledge. He identifies a certain {\em strict soundness} requirement that suffices for such an implication. Ambainis, Rosmanis and Unruh \cite{ambainis2014quantum} give evidence that this requirement may be necessary.

Based on QLWE, Hallgren, Smith, and Song \cite{hallgren2011classical} and Lunemann and Nielsen \cite{lunemann2011fully} show argument of knowledge where it is also possible to simulate the prover's state (akin to our simulation requirement of the sender's state). Unruh further explores arguments of knowledge in the context of computationally binding quantum commitments \cite{unruh2016computationally, unruh2016collapse}. All of the above require a polynomial number of rounds to achieve a negligible knowledge error.

\paragraph{Zero-Knowledge Multi-Prover Interactive Proofs.} Two recent works by Chiesa et al. \cite{ChiesaFGS18} and by Grilo, Slofstra, and Yuen \cite{GriloSY19} show that \NEXP and $\MIP^*$, respectively, have {\em perfect} zero-knowledge multi-prover interactive proofs (against entangled quantum provers).

\paragraph{A Word on Strict Commitments and Non-Aborting Verifiers.} In \cite{unruh2012quantum}, Unruh introduces a notion of {\em strict commitments}, which are commitments that fix not only the plaintext, but also the randomness (e.g. Blum-Micali \cite{BlumM84}). As mentioned in our technical overview, using such commitments it is possible to obtain zero-knowledge in constant rounds {\em against non-aborting explainable verifiers} through the GK four-step template we discussed in the overview. Roughly speaking, this is because when considering verifiers that always open their (strict) commitments, we are assured that measuring their answer does not disturb the verifier state, as this answer is information theoretically fixed. This effectively allows to perform rewinding.

\section{Preliminaries}\label{sec:prel}
All algorithms of cryptographic functionalities in this work are implicitly efficient and classical (i.e. require no quantum computation or a quantum communication channel), unless noted otherwise.
We rely on the standard notions of classical Turing machines and Boolean circuits:

\begin{itemize}
	\item
	We say that a Turing machine (or algorithm) is \PPT if it is probabilistic and runs in polynomial time.

	\item
	We sometimes think about \PPT Turing machines as polynomial-size uniform families of circuits (as these are equivalent models).
	A polynomial-size circuit family $\mathcal{C}$ is a sequence of circuits $\mathcal{C}=\set{C_\secp}_{\secp\in\Nat}$, such that each circuit $C_\secp$ is of polynomial size $\secp^{O(1)}$ and has $\secp^{O(1)}$ input and output bits.
	We say that the family is uniform if there exists a polynomial-time deterministic Turing machine $M$ that on input $1^\secp$ outputs $C_\secp$.

	\item
	For a $\PPT$ Turing machine (algorithm) $M$, we denote by $M(x;r)$ the output of $M$ on input $x$ and random coins $r$. For such an algorithm, and any input $x$, we may write $m\in M(x)$ to denote the fact that $m$ is in the support of $M(x;\cdot)$.
\end{itemize}

\subsection{Quantum Computation}
We use standard notions from quantum computation.
\begin{itemize}
	\item
	We say that a Turing machine (or algorithm) is \QPT if it is quantum and runs in polynomial time.

	\item
	We sometimes think about \QPT Turing machines as polynomial-size uniform families of quantum circuits (as these are equivalent models).
	We call a polynomial-size quantum circuit familiy $\mathcal{C} = \{ C_{\secp} \}_{\secp \in \Nat}$ uniform if there exists a polynomial-time deterministic Turing machine $M$ that on input $1^\secp$ outputs $C_\secp$.

	\item
	Classical communication channels in the quantum setting are identical to classical communication channels in the classical setting, except that when a set of qubits is sent through a classical communication channel, then the qubits are automatically measured in the standard basis, and the measured (now classical-state) qubits are then sent through the channel.

	\item
	A quantum interactive algorithm (in a 2-party setting) has input divided into two registers and output divided into two registers.
	For the input qubits, one register is for an input message from the other party, and a second register is for a potential inner state the machine held.
	For the output, one register is for the message to be sent to the other party, and another register is for a potential inner state for the machine to keep to itself.
\end{itemize}

\paragraph{Quantum Adversarial Model.}
As noted at the end of the technical overview, we would like to consider security definitions that not only achieve quantum security, but are also composable and can be used modularly inside other protocols.
For this we think by default on security against polynomial-size quantum adversaries with n.u. polynomial-size quantum advice (i.e. an arbitrary quantum mixed state that's not necessarily efficiently generatable).

In some of the security definitions we will explicitly note if the security is stronger (statistical security, against unbounded algorithms) or standard quantum security (against non-uniform quantum circuits without quantum advice), and in any case, security will always hold at least against non-uniform quantum circuits (without arbitrary quantum advice).
Accordingly, an adversary will be usually denoted by $\A = \set{\A_\secp, \rho_\secp}_{\secp\in\Nat}$, where $\{ \A_\secp \}_{\secp \in \Nat}$ is a polynomial-size non-uniform sequence of quantum circuits, and $\{ \rho_\secp \}_{\secp \in \Nat}$ is some polynomial-size sequence of mixed quantum states.
All adversaries are implicitly unrestricted in their behaviour (i.e. they are fully malicious and can arbitrarily deviate from protocols).

We conclude with notions regarding indistinguishability in the quantum setting.

\begin{itemize}
	\item
	A function $f:\Nat \rightarrow [0, 1]$ is,
	\begin{itemize}
		\item
		negligible if for every constant $c \in \Nat$ there exists $N \in \Nat$ such that for all $n > N$, $f(n) < n^{-c}$.

		\item
		noticeable if there exists $c \in \Nat, N \in \Nat$ s.t. for every $n \geq N$, $f(n) \geq n^{-c}$.
	\end{itemize}

	\item
	A quantum random variable is simply a random variable that can have values that are quantum states.
	That is, a quantum r.v. induces a probability distribution over a (possibly infinite) set of quantum states.
	Such quantum r.v. can be also thought of as a mixed quantum state, which is simply a distribution over quantum states.

	\item
	For two quantum random variables $X$ and $Y$, quantum distinguisher $\zkmD$ with quantum mixed state as auxiliary input $\rho$, and $\mu \in [0, 1]$, we write $X \approx_{\zkmD(\rho),\mu} Y$ if
	\begin{align*}
		\abs{
			\Pr[\zkmD(X; \rho)=1] - \Pr[\zkmD(Y; \rho)=1]
		} \leq \mu.
	\end{align*}

	\item
	Two ensembles of quantum random variables $\mathcal{X}=\{X_{\secp}\}_{\secp\in \Nat}$ and $\mathcal{Y}=\{Y_{\secp}\}_{\secp\in \Nat}$ are said to be computationally indistinguishable, denoted by $\mathcal{X}\approx_{c} \mathcal{Y}$, if for every polynomial-size non-uniform quantum distinguisher with quantum advice $\zkmD=\set{\zkmD_\secp, \rho_\secp}_{\secp\in\Nat}$, there exists a negligible function $\mu$ such that for all $\secp \in \Nat$,
	\begin{align*}
		X_\secp \approx_{\zkmD_{\secp}(\rho_\secp),\, \mu(\secp)} Y_\secp\enspace.
	\end{align*}

	\item The trace distance between two quantum distributions $X, Y$, denoted $\TD(X, Y)$, is a generalization of statistical distance to the quantum setting and represents the maximal distinguishing advantage between two quantum distributions, by unbounded quantum algorithms.
	We thus say that $\mathcal{X}=\{X_{\secp}\}_{\secp\in \Nat}$ and $\mathcal{Y}=\{Y_{\secp}\}_{\secp\in \Nat}$ are statistically indistinguishable (and write $\mathcal{X}\approx_{s} \mathcal{Y}$), if for every unbounded non-uniform quantum distinguisher $\zkmD=\set{\zkmD_\secp}_{\secp\in\Nat}$, there exists a negligible function $\mu$ such that for all $\secp \in \Nat$,
	\begin{align*}
		\TD\left( X_\secp, Y_\secp \right) \leq \mu(\secp) \enspace.
	\end{align*}
\end{itemize}

\medskip
In what follows, we introduce the cryptographic tools we will use in this work.
As a default, all algorithms are classical and efficient unless noted otherwise, and security (which will be formally defined for each primitive) holds against efficient non-uniform quantum adversaries.

\subsection{Classical WI Proofs with Quantum Security}
We use classical constant-round proof systems for NP (where both honest prover and verifier are classical efficient algorithms) that are witness-indistinguishable, that is, the prover gets the privacy guarantee that the transcripts it generates for two witnesses of the same instance, are indistinguishable (for quantum attackers).

In what follows, we denote by $(\zkP, \zkV)$ a protocol between two parties $\zkP$ and $\zkV$.
For common input $\ins$, we denote by $\view_{\zkV}\prot{\zkP}{\zkV}(\ins)$ the output of $\zkV$ in the protocol. For honest verifiers, this output will be a single bit indicating acceptance (or rejection), malicious quantum verifiers may have arbitrary quantum output (which is captured by the verifier outputting its inner quantum state at the end of interaction).

\begin{definition}[WI Proof System for NP]\label{def:arg}
	A protocol $(\zkP, \zkV)$ with an honest \PPT prover $\zkP$ and an honest \PPT verifier $\zkV$ for a language $\lang \in\NP$ is a witness-indistinguishable proof system if it satisfies:
	\begin{enumerate}

		\item {\bf Perfect Completeness:}
		For any $\secp \in\Nat,\ins \in \lang \cap \zo^\secp, w \in \mathcal{R}_{\lang}(x)$,
		$$
		\Pr[ \view_{\zkV}\prot{\zkP(w)}{\zkV}(\ins) = 1 ]  = 1 \enspace.
		$$

		\item {\bf Statistical Soundness:}
		For any non-uniform unbounded prover $\zkmP=\set{\zkmP_\secp}_{\secp}$, there exists a negligible function $\mu(\cdot)$ such that for any security parameter $\secp\in \Nat$ and any $\ins \in \zo^\secp\setminus\lang$,
		\begin{align*}
			\Pr\left[ \view_{\zkV}\prot{\zkmP_\secp}{\zkV}(\ins)=1 \right] \leq \mu(\secp)\enspace.
		\end{align*}

		\item {\bf Witness Indistinguishability:}
		For every non-uniform quantum polynomial-size verifier $\zkmV = \{ \zkmV_\secp, \rho_\secp \}_\secp$, for any two sequences of witnesses $\{ w_\secp \}_{\secp \in \Nat}$, $\{ v_\secp \}_{\secp \in \Nat}$ s.t. for every $\secp \in \Nat$, $w_\secp$ and $v_\secp$ are both witnesses for the same $x_\secp \in \lang \cap \{ 0, 1 \}^{\secp}$, we have,
		$$
		\{\view_{\zkmV_\secp}\prot{\zkP(w_\secp)}{\zkmV_\secp(\rho_\secp)}(\ins_\secp)\}_{\secp\in\Nat}
		\approx_{c}
		\{\view_{\zkmV_\secp}\prot{\zkP(v_\secp)}{\zkmV_\secp(\rho_\secp)}(\ins_\secp)\}_{\secp\in\Nat}
		\enspace.
		$$
	\end{enumerate}
\end{definition}

\paragraph{Instantiations of WI proofs.}
3-message classical proof systems with WI follow from classical zero-knowledge proof systems such as the parallel repetition of the 3-coloring protocol \cite{goldreich1991proofs}, which is in turn based on non-interactive perfectly-binding commitments.
For the proof system to be WI against quantum attacks, we need the non-interactive commitments to be computationally hiding against quantum attacks (rather only against classical attacks).

\subsection{Sigma Protocols for NP}
We use the abstraction called {\em Sigma Protocols}, which are public-coin three-message proof systems that only give a very weak zero-knowledge guarantee.

\begin{definition}
	A sigma protocol for an $\NP$ relation $\rel$ is a three-message protocol $(\SigA,\SigB,\SigC)$ between a \PPT prover $\SigP$ and a public-coin \PPT verifier $\SigV$, with the following properties:

	\paragraph{Completeness:} for any $(\ins,\wit)\in\rel $, $\prot{\SigP(\wit)}{\SigV}(\ins)=1$.

	\paragraph{Statistical Soundness:}
	for any non-uniform unbounded prover $\zkmP=\set{\zkmP_\secp}_{\secp}$, there exists a negligible function $\mu(\cdot)$ such that for any security parameter $\secp\in \Nat$ and any $\ins \in \zo^\secp\setminus\lang$,
	$$
	\Pr\left[\prot{\zkmP}{\SigV}(\ins)=1\right]\leq  \mu(\secp)\enspace.
	$$

	\paragraph{Special Zero-Knowledge:} There exists a \PPT simulator $\SigS$ such that,
	$$
	\set{(\alpha,\gamma) \; | \; (\alpha, r_\alpha) \gets \SigP_1(\ins,\wit), \gamma = \SigP_3(\ins, r_\alpha; \beta) }_{\begin{subarray}{c} (\ins,\wit) \in\rel \\\ins,\SigB\in \zo^{\secp}\end{subarray}}
	\approx_{c}
	\set{(\SigA,\SigC)\gets \SigS(\ins,\SigB)}_{\begin{subarray}{c} (\ins,\wit) \in\rel \\\ins,\SigB\in \zo^{\secp}\end{subarray}}\enspace,
	$$
	where $r_\alpha$ is the prover's inner state that it prints for itself along with outputting $\alpha$.

\end{definition}

\noindent The next claim follows from the special zero-knowledge requirement, and will be used throughout the analysis.
\begin{claim}[First-Message Indistinguishability] \label{first_message_indisting}
	In every $\Sigma$ protocol:
	$$
	\set{\SigA \gets \SigP_1(\ins,\wit)}_{\begin{subarray}{c} (\ins,\wit) \in\rel \\|\ins|=\secp\end{subarray}}
	\approx_c
	\set{\SigA \gets \SigS_1(\ins,0^\secp)}_{\begin{subarray}{c} (\ins,\wit) \in\rel \\|\ins|=\secp\end{subarray}}\enspace,
	$$
	where $\SigP_1(\ins,\wit)$ and $\SigS_1(\ins,\SigB)$ are the distributions on the first message of the prover and simulator.
\end{claim}
\begin{proof}[Proof Sketch]
	Note that the first prover message is computed independently of the verifier's message. The claim now follows by the special zero-knowledge guarantee.

\end{proof}

\medskip\noindent
Sigma protocols are known to follow from classical zero-knowledge proof systems such as the (parallel repetition) of the 3-coloring protocol \cite{goldreich1991proofs}, which is in turn based on non-interactive perfectly-binding and computationally hiding commitments.

\subsection{Compute-and-Compare Obfuscation}
\iffalse
A public-parameters compute-and-compare (PPCC) obfuscation scheme is an obfuscation scheme for CC programs with an added algorithm that samples some public parameters for the obfuscator, that dictate the correctness of the obfuscated program.
The motivation behind this cryptographic functionality is for an interactive setting; There are existing compute-and-compare obfuscators, but, as far as we know, they have a negligible correctness error (over the choice of randomness for the obfuscation), that is, the obfuscated program's functionality might not stay the same.

In an interactive setting, where party $A$ wishes to guarantee that party $B$ sends an obfuscated program that keeps its functionality perfectly correct, letting $B$ choose the randomness for the obfuscator is problematic as it can sample the randomness maliciously. We use elementary tools and existing CC obfuscation to define such PPCC obfuscation, where party $A$ can sample the randomness that determines \emph{only} the correctness of the obfuscation, without jeopardizing security.
\fi

We define compute-and-compare (CC) circuits, and obfuscators for CC circuits.
We start by defining the class of {\em compute-and-compare circuits}.

\begin{definition}[Compute-and-Compare Circuit]
	Let $f:\zo^n\rightarrow\zo^\secp$ be a circuit, and let $u\in\zo^\secp, z\in \zo^*$ be strings. Then $\CC{f,u,z}(x)$ is a circuit that returns $z$ if $f(x)=y$, and $\bot$ otherwise.
\end{definition}

We now define compute-and-compare (CC) obfuscators (with perfect correctness). In what follows $\Obf$ is a \PPT algorithm that takes as input a CC circuit $\CC{f,u,z}$ and outputs a new circuit $\obfC$. (We assume that the CC circuit $\CC{f,u,z}$ is given in some canonical description from which $f$, $u$, and $z$ can be read.)

\begin{definition}[CC obfuscator]
	A \PPT algorithm $\Obf$ is a compute-and-compare obfuscator if it satisfies:
	\begin{enumerate}
		\item
		{\bf Perfect Correctness:} For any circuit $f:\zo^n\rightarrow\zo^\secp$, $u\in \zo^\secp$ and $z \in \zo^*$,
		$$
		\Pr\left[\forall x \in \zo^{n}:\obfC(x) = \CC{f,u,z}(x) \pST \obfC\gets \Obf(\CC{f,u,z})\right]=1 \enspace.
		$$

		\item
		{\bf Simulation:} There exists a $\PPT$ simulator $\ccSim$ such that for any polynomial-size classical circuit family $f = \{ f_\secp \}_{\secp \in \Nat}$ and polynomial-length output string $z = \{ z_\secp \}_{\secp \in \Nat}$,
		$$\{
		\obfC \; | \; u \gets U_\secp , \obfC \gets \Obf(\CC{f_\secp,u,z_\secp})
		\}_{\secp \in \Nat}
		\approx_c
		\{
		\ccSim(1^{|f_\secp|}, 1^{|z_\secp|}, 1^{\secp})
		\}_{\secp \in \Nat} \enspace .
		$$

	\end{enumerate}
\end{definition}

\paragraph{Instantiations.} Compute-and-compare obfuscators with almost-perfect correctness are constructed in \cite{goyal2017lockable,wichs2017obfuscating} based on QLWE.
Recently, CC obfuscators with perfect correctness were constructed \cite{goyal2019perfect} by Goyal, Koppula, Vusirikala and Waters, also based on QLWE.

\subsection{Non-Interactive Commitments}
We define non-interactive commitment schemes with perfect binding and computational hiding (against quantum attacks).

\begin{definition}[Non-Interactive Commitment]\label{def:com}
	A non-interactive commitment scheme is given by a \PPT algorithm $\Com(\cdot)$ with the following syntax:

	\begin{itemize}
		\item $\cmt \gets \Com(1^\secp, x) : $
		A randomized algorithm that takes as input a security parameter $\secp$ in unary and input $x \in \{ 0, 1 \}^*$, and outputs a commitment $\cmt$.

	\end{itemize}

	The commitment algorithm satisfies:
	\begin{enumerate}
		\item {\bf Perfect Binding:}
		For any $x, x' \in \{ 0, 1 \}^*$ of the same length, if $\cmt \in \Com(1^\secp, x)$, $\cmt \in \Com(1^\secp, x')$, then $x = x'$.

		\item {\bf Quantum Computational Hiding:}
		For any pair of $\ell(\secp)$-length strings $x_0 = \{ x_{0, \secp} \}_{\secp \in \Nat}$, $x_1 = \{ x_{1, \secp} \}_{\secp \in \Nat}$, where $\ell(\secp)$ is a polynomial, we have,
		$$
		\{ \Com(1^\secp, x_{0, \secp}) \}_{\secp \in \Nat}
		\approx_c
		\{ \Com(1^\secp, x_{1, \secp}) \}_{\secp \in \Nat} \enspace .
		$$
	\end{enumerate}
\end{definition}

\paragraph{Instantiations.} The above non-interactive commitments are known based on various standard assumptions, including QLWE \cite{GoyalHKW17,LombardiS19}.

\subsection{Quantum Fully Homomorphic Encryption}
In our protocol we will be using a quantum fully homomorphic encryption scheme, specifically, a scheme where a classical input can be encrypted classically and a quantum input quantumly.
Moreover, we can evaluate an encrypted input that was partially encrypted classically and partially quantumly, and if part of the output is classical, it can be decrypted by a classical decryption algorithm.
The formal definition follows.

\begin{definition}[Quantum Fully-Homomorphic Encryption]
	A quantum fully homomorphic encryption scheme is given by six algorithms $(\qheG,$ $\qheE,$ $\qheQE,$ $\qheD,$ $\qheQD,$ $\qheEv)$ with the following syntax:
	\begin{itemize}
		\item
		$(\qhepk, \qhesk) \gets \qheG(1^\secp):$ A \PPT algorithm that given a security parameter, samples a classical public key and a classical secret key.

		\item
		$c \gets \qheE_{\qhepk}(b):$ A \PPT algorithm that takes as input a bit $b$ and outputs a classical ciphertext.

		\item
		$\ket{\phi} \gets \qheQE_{\qhepk}(\ket{\psi}):$ A \QPT algorithm that takes as input a qubit $\ket{\psi}$ and outputs a ciphertext represented in qubits.

		\item
		$b \gets \qheD_{\qhesk}(c):$ A \PPT algorithm that takes as input a classical ciphertext $c$ and outputs a bit.

		\item
		$\ket{\psi} \gets \qheQD_{\qhesk}(\ket{\phi}):$ A \QPT algorithm that takes as input a quantum ciphertext $\ket{\phi}$ and outputs a qubit.

		\item
		$\mathbf{\hat{c}}, \hat{\ket{\Phi}} \gets \qheEv_{\qhepk}(C, \ket{\Phi} ):$ A \QPT algorithm that takes as input:
		\begin{enumerate}
			\item A general quantum circuit $C$ with $\ell$ input qubits and $\ell'$ output qubits, out of which $m$ are measured.
			\item A quantum ciphertext $\ket{\Phi}$ that encrypts an $\ell$-qubit state, some of the $\ell$ ciphertexts are possibly classical ciphertexts (generated by the classical encryption algorithm) encrypting classical bits.
		\end{enumerate}
		The evaluation algorithm outputs a classical ciphertext $\mathbf{\hat{c}}$ encrypting $m$ bits, plus a quantum ciphertext $\hat{\ket{\Phi}}$ encrypting an $(\ell' - m)$-qubit quantum state.
		\iffalse

		\fi
	\end{itemize}
	The scheme satisfies the following.
	\begin{itemize}
		\item {\bf Quantum Semantic Security:}
		The encryption algorithm maintains quantum semantic security.

		\item {\bf Compactness:}
		There exists a polynomial $\poly(\cdot)$ s.t. for every quantum circuit $C$ with $\ell'$ output qubits and an enryption of an input for $C$, the output size of the evaluation algorithm is $\poly(\secp, \ell')$, where $\secp$ is the security parameter of the scheme.

		\item {\bf Classicality-Preserving Quantum Homomorphism:}
		Let $\mathcal{C} = \{ C_\secp \}_{\secp \in \Nat}$ be a polynomial-size quantum circuit (where $C_{\secp}$ has $m(\secp)$ measured output qubits\footnote{Out of some total number of output qubits $\ell'(\secp)$.}), let $\ket{\Psi} = \{ \ket{\Psi}_\secp \}_{\secp \in \Nat}$ be an input state for $C$, let $(\qhepk, \qhesk) = \{ (\qhepk_\secp, \qhesk_\secp) \}_{\secp \in \Nat}$ be a pair of public and secret keys ($\forall \secp \in \Nat: (\qhepk_\secp, \qhesk_\secp)\in \qheG(1^\secp)$) and let $r = \{ r_\secp \}_{\secp}$ be randomness for the encryption algorithm.
		Then there exists a negligible function $\mu(\cdot)$ s.t. for all $\secp \in \Nat$,
		$$
		\TD\left( \rho_{0, \secp}, \rho_{1, \secp} \right) \leq \mu(\secp) \enspace ,
		$$
		where $\rho_0, \rho_1$ are the quantum distributions which are defined as follows:
		\begin{itemize}
			\item $\rho_{0, \secp}:$
			Encrypt each classical bit of $\ket{\Psi}$ with $\qheE_{\qhepk}(\cdot)$ and the rest with $\qheQE_{\qhepk}(\cdot)$ (the randomness $r$ is the total randomness used for all encryptions).
			Execute $\qheEv_{\qhepk}(C, \cdot )$ on the encryption to get $\mathbf{\hat{c}}, \hat{\ket{\Phi}}$, where $\mathbf{\hat{c}}$ is a classical ciphertext encrypting $m(\secp)$ bits.
			Then output $\qheD_{\qhesk}\left( \mathbf{\hat{c}} \right), \qheQD_{\qhesk}( \hat{\ket{\Phi}} )$.

			\item $\rho_{1, \secp}:$
			Output $C\left( \ket{\psi} \right)$.
		\end{itemize}

		\iffalse

		\fi
	\end{itemize}

\end{definition}

\paragraph{Comments about the definition:}
\begin{itemize}
	\item
	For the definition of quantum semantic security see \cite{broadbent2015quantum}.

	\item
	A circuit with $m$ measured output qubits is one where the leftmost $m$ output qubits are measured in the standard basis before they are outputted, the rest of the output qubits can either be measured or not. The choice of the classical bits being lefmost is arbitrary and is only for the sake of simplicity. If desired, our model (with the classical output on the left) can be adapted by adding swap gates to circuits with spread-out classical output (just before the end of computation).

	\item
	It might look weird at first that we don't let the evaluation algorithm $\qheEv$ explicitly know which of the ciphertexts its about to process are classical.
	This is not a problem, since the evaluation algorithm treats quantum ciphertexts and classical ciphertexts all the same; they take the same amount of qubits, and the algorithm performs on them exactly the same computations.
\end{itemize}

\paragraph{Instantiations.} Mahadev and Brakerski \cite{mahadev2018classical, brakerski2018quantum} show how to build quantum FHE from standard cryptographic assumptions; QLWE, plus a circular security assumption.
The above definition is more general then how quantum FHE is defined in these works. Specifically, \emph{classicality-preserving} quantum homomorphism with statistical correctness for \emph{every} pair $(\qhepk, \qhesk)$ of public and secret keys and randomness $r$ for the encryption algorithm, is not explicitly defined there. However, the construction of Brakerski actually does achieve this more general definition. This follows readily from the main theorem (4.1) in \cite{brakerski2018quantum}.

\subsection{Function-Hiding Secure Function Evaluation}\label{def:SFE}
We define two-message function evaluation protocols with statistical circuit privacy and quantum input privacy.
\begin{definition}[2-Message Function Hiding SFE] \label{def:1hop}
	A two-message secure function evaluation protocol $(\sfeGen,$ $\sfeEnc,$ $\sfeEval,$ $\sfeD)$ has the following syntax:
	\begin{itemize}
		\item
		$\sfedk \gets \sfeGen(1^\secp):$  a probabilistic algorithm that takes a security parameter $1^\secp$ and outputs a secret key $\sfedk$.
		\item
		$\ciph \gets\sfeEnc_{\sfedk}(\SFEin):$ a probabilistic algorithm that takes a string $\SFEin \in \zo^*$, and outputs a ciphertext $\ciph$.
		\item
		$\evciph\gets\sfeEval(\Cir,\ciph):$ a probabilistic algorithm that takes a (classical) circuit $\Cir$ and a ciphertext $\ciph$ and outputs an evaluated ciphertext $\evciph$.
		\item
		$\SFEout = \sfeD_{\sfedk}(\evciph):$ a deterministic algorithm that takes a ciphertext $\evciph$ and outputs a string $\SFEout$.
	\end{itemize}
	For any polynomial-size family of classical circuits $\mathcal{C} = \{ \Cirs_\secp \}_{\secp \in \Nat}$ (for every $\secp \in \Nat$, $\Cirs_\secp$ is a set of circuits) the scheme satisfies:
	\begin{itemize}
		\item {\bf Perfect Correctness:} For any $\secp \in \Nat$, $\SFEin \in \zo^*$ and circuit $\Cir\in\Cirs_\secp$,
		$$
		\Pr\left[
		\sfeD_{\sfedk}(\evciph) = \Cir(\SFEin) \pST
		\begin{array}{l}
		\sfedk \gets \sfeGen(1^\secp),\\
		\ciph \gets \sfeEnc_{\sfedk}(\SFEin),\\
		\evciph \gets \sfeEval(\Cir,\ciph)
		\end{array}
		\right] = 1\enspace.
		$$

		\item {\bf Quantum Input Privacy:} For any polynomial $\lin(\secp)$ and polynomial-size quantum adversary $\adv=\{ \adv_\secp, \rho_\secp \}_{\secp \in \Nat}$, there exists a negligible function $\mu(\cdot)$ such that for every two length-$\ell(\secp)$ messages $\{ x_{0, \secp} \}_{\secp \in \Nat}$, $\{ x_{1, \secp} \}_{\secp \in \Nat}$, for every $\secp \in \Nat$:
		\begin{align*}
			\Pr\left[
			\adv_\secp(\ciph) = \bit \pST
			\begin{array}{l}
				\bit \gets \zo,\\
				\sfedk \gets \sfeGen(1^\secp),\\
				\ciph \gets \sfeEnc_{\sfedk}(\SFEin_\bit)
			\end{array}
			\right]\leq \frac{1}{2} + \mu(\secp)\enspace.
		\end{align*}

		\item {\bf Statistical Circuit Privacy:} There exist unbounded algorithms, probabilistic $\HESim$ and deterministic $\Ext$, such that for every $x \in \{ 0, 1 \}^*$, $\ciph \in \sfeEnc(x)$, the extractor outputs $\Ext(\ciph) = x$, and:
		\begin{align*}
			\{
			\sfeEval(\Cir,\ciph^*)
			\}_{\begin{subarray}{c}
					\secp\in\Nat, \Cir\in\Cirs_\secp, \\ \ciph^* \in \{ 0, 1 \}^{\poly(\secp)}
			\end{subarray}}
			\approx_s
			\{
			\HESim(\Cir(\Ext(\ciph^*; 1^\secp));1^\secp) \}_{\begin{subarray}{c}\secp\in\Nat, \Cir\in\Cirs_\secp, \\ \ciph^* \in \{ 0, 1 \}^{\poly(\secp)}\end{subarray}}\enspace.
		\end{align*}

	\end{itemize}
\end{definition}

\noindent The next claim follows directly from the circuit privacy property, and will be used throughout the analysis.
\begin{claim}[Evaluations of Agreeing Circuits are Statistically Close] \label{claim:SFE_eval}
	Let $\ciph^* = \{ \ciph^*_\secp \}_{\secp \in \Nat}$ be a (possibly non-ciphertext) $\poly(\secp)$-length string, and let $C_0 = \{ C_{0, \secp} \}_{\secp \in \Nat}$, $C_1 = \{ C_{1, \secp} \}_{\secp \in \Nat}$ be two circuits such that $\forall \secp \in \Nat: C_{0, \secp}(\Ext(\ciph^*_\secp; 1^\secp)) = C_{1, \secp}(\Ext(\ciph^*_\secp; 1^\secp))$.
	Then
	$$
	\{ \sfeEval(C_{0, \secp}, \ciph^*_\secp) \}_{\secp \in \Nat}
	\approx_s
	\{ \sfeEval(C_{1, \secp}, \ciph^*_\secp) \}_{\secp \in \Nat} \enspace .
	$$
\end{claim}

Such secure function evaluation schemes are known based on post-quantum hardness of QLWE \cite{ostrovsky2014maliciously, brakerski2018two}.

\section{Constant-Round Zero-Knowledge Arguments for NP with Quantum Security}\label{sec:const-round_qzk}
In this section we construct a classical argument system for an arbitrary NP language $\lang$, with a constant number of rounds, quantum soundness and quantum zero-knowledge.
More formally, we construct a constant-round protocol satisfying the following definition (in the definition below, $\view_{\zkmV}\prot{\zkP(w)}{\zkmV}(\ins)$ denotes the interaction transcript between $\zkP(w)$ and $\zkmV$, and $\zkmV$'s inner quantum state at the end of this interaction).

\begin{definition}[Post-Quantum Zero-Knowledge Argument for NP]\label{def:reg_qzk}
	A classical protocol $(\zkP, \zkV)$ with an honest \PPT prover $\zkP$ and an honest \PPT verifier $\zkV$ for a language $\lang \in\NP$ is a quantum-secure zero-knowledge argument if it satisfies:

	\begin{enumerate}
		\item {\bf Perfect Completeness:}
		For any $\secp \in\Nat,\ins \in \lang \cap \zo^\secp, w \in \mathcal{R}_{\lang}(x)$,
		$$
		\Pr[ \view_{\zkV}\prot{\zkP(w)}{\zkV}(\ins) = 1 ]  = 1 \enspace.
		$$

		\item {\bf Quantum Computational Soundness:}
		For any non-uniform quantum polynomial-size prover $\zkmP = \set{\zkmP_\secp}_{\secp \in \Nat}$, there exists a negligible function $\mu(\cdot)$ such that for any security parameter $\secp\in \Nat$ and any $\ins \in \zo^\secp\setminus\lang$,
		\begin{align*}
			\Pr\left[ \view_{\zkV}\prot{\zkmP_\secp}{\zkV}(\ins) = 1 \right] \leq \mu(\secp)\enspace.
		\end{align*}

		\item {\bf Quantum Computational Zero-Knowledge:}
		There exists a quantum expected polynomial-time simulator $\zkS$, such that for any non-uniform quantum polynomial-size verifier $\zkmV = \set{\zkmV_\secp}_{\secp \in \Nat}$,
		$$
		\{ \view_{\zkmV_\secp}\prot{\zkP(w)}{\zkmV_\secp}(\ins)\}_{\substack{\secp\in\Nat,\\ \ins\in\lang\cap\zo^\secp,\\ w \in \mathcal{R}_{\lang}(x)}}
		\approx_{c}
		\{\zkS(\ins,\zkmV_\secp)\}_{\substack{\secp\in\Nat,\\ \ins\in\lang\cap\zo^\secp,\\ w \in \mathcal{R}_{\lang}(x)}}\enspace.
		$$
		\begin{itemize}
			\item If the verifier is a classical circuit, then the simulator is computable by a classical expected polynomial-time algorithm.
		\end{itemize}

	\end{enumerate}
\end{definition}

As mentioned in the technical overview and preliminaries, we actually prove a definiton a bit stronger then post-quantum security, that is also quantumly-semi-composable.
The definition makes it possible to use the protocol as a subprotocol inside an outer protocol, in particular enabling to prove security against quantum adversaries with quantum advice, in many cryptographic settings.
Roughly, the stronger definition states that even if the verifier has an arbitrary polynomial-size quantum advice, as long as the simulator has oracle access to samples of pairs of instance (for the zero-knowledge protocol) and quantum advice (for the malicious verifier), protocol can be simulated.
On the soundness side, security simply holds against provers with quantum advice.
The definition is given below.

\begin{definition}[Instance-Advice Distribution]
	Let $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$ be a sequence of polynomial-size quantum mixed states.
	We say that $\rho$ is an instance-advice distribution (for the language $\lang \in \NP$) if for every $\secp \in \Nat$ there exists a witness $\wit_\secp \in \mathcal{R}_{\lang}(\secp)$\footnote{$\mathcal{R}_{\lang}(\secp)$ is the set of all witnesses of $\secp$-sized instances, that is, $\wit \in \mathcal{R}_{\lang}(\secp)$ iff there exists $x \in \lang\cap\{ 0, 1 \}^\secp$ s.t. $\wit \in \mathcal{R}_{\lang}(x)$.} s.t. the first $\secp$ qubits of $\rho_\secp$ always contain an instance $\ins \in \lang, |\ins| = \secp$ s.t. $\wit_\secp \in \mathcal{R}_{\lang}(x)$.
\end{definition}

\begin{definition}[Quantum-Semi-Composable (QSC) Zero-Knowledge Argument for NP]\label{def:qzk}
	A classical protocol $(\zkP, \zkV)$ with an honest \PPT prover $\zkP$ and an honest \PPT verifier $\zkV$ for a language $\lang \in\NP$ is a quantum-semi-composable (QSC) zero-knowledge argument if it satisfies:

	\begin{enumerate}
		\item {\bf Perfect Completeness:}
		As in the above definition.

		\item {\bf Quantum (Advice) Computational Soundness:}
		For any non-uniform quantum polynomial-size prover $\zkmP = \set{\zkmP_\secp, \rho_\secp}_{\secp \in \Nat}$ (with advice), there exists a negligible function $\mu(\cdot)$ such that for any security parameter $\secp\in \Nat$ and any $\ins \in \zo^\secp\setminus\lang$,
		\begin{align*}
			\Pr\left[ \view_{\zkV}\prot{\zkmP_\secp(\rho_\secp)}{\zkV}(\ins) = 1 \right] \leq \mu(\secp)\enspace.
		\end{align*}

		\item {\bf Quantum-Semi-Composable Computational Zero-Knowledge:}
		There exists a quantum expected polynomial-time simulator $\zkS$, such that for any polynomial-size quantum verifier $\zkmV=\set{\zkmV_\secp}_{\secp \in \Nat}$ and polynomial-size instance-advice distribution $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$,
		$$
		\{ x, \view_{\zkmV_\secp}\prot{\zkP(w_\secp)}{\zkmV_\secp(\rho_\secp^{(x)})}(\ins) \; | \; (x, \rho_\secp^{(x)}) \gets \rho_\secp \}_{\secp\in\Nat}
		\approx_{c}
		\{\zkS(\zkmV_\secp, O_{\rho_\secp})\}_{\secp\in\Nat}\enspace,
		$$
		where,
		\begin{itemize}
			\item For a mixed state $\sigma$, $O_{\sigma}$ is an inputless oracle that upon activation returns a sample $\sigma$.
		\end{itemize}

	\end{enumerate}
\end{definition}

The above definition is clearly stronger then the standard one, as for a verifier without quantum advice, the simulator always "have oracle access to the verifier's advice".
As for why this definition is somewhat composable inside quantum-secure protocols, in section \ref{sec:qma} we use the semi-composable definition as part of the security proof of the quantum-secure (fully-simulatable) coin-flipping protocol, and it is made clear there how to use the definition.
As a side note, it is worth noting that in our construction, proving that the protocol is QSC ZK rather than standard post-quantum ZK is practically the same.

\paragraph{Ingredients and notation:}
\begin{itemize}
	\item
	A non-interactive commitment scheme $\Com$.
	\item
	A CC obfuscator $\Obf$.
	\item
	A quantum fully homomorphic encryption scheme $(\qheG, \qheE, \qheQE, \qheD,\newline \qheQD, \qheEv )$.
	\item
	A 2-message function-hiding secure function evaluation scheme $(\sfeGen,$ $\sfeEnc,$ $\sfeEval,$ $\sfeD)$.
	\item
	A public-coin 3-message WI proof $(\wiP, \wiV)$.
	\item
	A 3-message sigma protocol $(\SigP, \SigV)$ for the language $\lang$ with quantum security.
\end{itemize}

\paragraph{Handling Aborts and Alikes.}
For the simplicity of describing the protocol and to avoid distractions from unimportant technical issues, we set a convention to handle publicly checkable misbehaviors by the parties in the protocol.

For a security parameter $\secp$, for each message in the protocol, it is known (publicly) based on $\secp$, what is the length of each message (or upper and lower bounds on that length).
If a party sends a message in an incorrect length, the receiving party fixes it locally and trivially; if the message is too long, it cuts the message in a suitable place, and if it's too short then pads with zeros.

In the below protocol, whenever a party either aborts or fails to prove its statement in its WI proof (which is publicly verifiable), the other party ends communication, and if the party that ends communication is the verifier, it also rejects.

We describe the protocol in \figref{fig:const_round_qzk}.

\protocol
{\proref{fig:const_round_qzk}}
{A classical constant-round zero-knowledge argument for $\lang \in \NP$ with quantum security.}
{fig:const_round_qzk}
{
	\begin{description}
		\item[Common Input:] An instance $\ins \in \lang\cap \zo^\secp$, for security parameter $\secp \in \Nat$.
		\item[$\zkP$'s private input:] A polynomial-size classical witness $w \in \mathcal{R}_{\lang}(\ins)$ showing that $\ins \in \lang$.
	\end{description}

	\begin{enumerate}
		\item {\bf Initial Commitment by the Prover:}
		$\zkP$ computes $\sfedk \gets \sfeGen(1^\secp)$ and sends non-interactive commitments to the witness $\wit$ and the SFE secret key $\sfedk$: $\cmt_1 \gets \Com(1^\secp, w)$, $\cmt_2 \gets \Com(1^\secp, \sfedk)$.

		\item {\bf Extractable Commitment to a Challenge by the Verifier:}\label{qzk:verifier_commit}
		$\zkV$ computes a challenge $\beta \gets \SigV$, and proceeds to the following.
		\begin{enumerate}
			\item \label{qzk:verifier_CC}
			$\zkV$ computes $s \gets U_{\secp}, t \gets U_{\secp}, (\qhepk, \qhesk) \gets \qheG(1^{\secp})$ and sends
			$$
			\qhepk, \enspace
			\ciph_{\zkV}\gets \qheE_{\qhepk}(t), \enspace
			\obfC \gets \Obf\Big(\oCC\big[ \qheD_{\qhesk}(\cdot), s, (\qhesk, \beta) \big]\Big)\enspace .
			$$

			\item \label{qzk:prover_sfe}
			$\zkP$ sends $\ciph_{\zkP} \gets \sfeEnc_{\sfedk}(0^\secp)$, where $\sfedk$ is the SFE key that the prover sent inside $\cmt_2$.

			\item \label{qzk:verifier_response}
			$\zkV$ sends $\evciph \gets \sfeEval\Big(\oCC\big[ \mathsf{Id(\cdot)}, t, s \big],\, \ciph_{\zkP} \Big)$, where $\mathsf{Id(\cdot)}$ is the identity function.
		\end{enumerate}

		\item {\bf Sigma Protocol Messages Exchange:}
		\begin{enumerate}
			\item \label{qzk:prover_alpha}
			$\zkP$ computes $\alpha\gets \SigP(\ins, \wit)$ and sends $\alpha$.
			\item
			$\zkV$ sends the public-coin challenge $\beta$ itself.
		\end{enumerate}

		\item {\bf WI Proof by the Verifier:}\label{qzk:verifier_wi}
		$\zkV$ interacts with $\zkP$ through $(\wiP_{\zkV}, \wiV_{\zkV})$ to give $\zkP$ a WI proof of the following statement:
		\begin{itemize}
			\item
			The transcript of the verifier so far is explainable.
			\item
			{\bf Or, }there is a non-witness $u \notin \mathcal{R}_{\lang}(\ins)$ and randomness $r \in \{ 0, 1 \}^*$ s.t. $\cmt_1 = \Com(1^\secp, u; r)$.
		\end{itemize}

		\item {\bf WI Proof by the Prover:}\label{qzk:prover_wi}
		$\zkP$ interacts with $\zkV$ through $(\wiP_{\zkP}, \wiV_{\zkP})$ and uses the witness $\wit$ in order to prove to $\zkV$ the following:
		\begin{itemize}
			\item $\cmt_1$, $\cmt_2$ are both valid commitments and furthermore $\cmt_2$ is a commitment to the SFE key from the verifier's extractable commitment. That is, there exist $z, \sfedk', y, r_1, r_2, r_{\sfeGen}, r_{\sfeEnc} \in \{ 0, 1 \}^{*}$ s.t. $\cmt_1 = \Com(1^\secp, z;r_1)$, $\cmt_2 = \Com(1^\secp, \sfedk';r_2)$, $\sfedk' = \sfeGen(1^\secp; r_{\sfeGen})$, $\ciph_{\zkP} = \sfeEnc_{\sfedk'}(y;r_{\sfeEnc})$.

			\item {\bf Or,} $x \in \lang$.
		\end{itemize}

		\item {\bf Information Reveal by the Prover:}
		$\zkP$ sends $\gamma= \SigP(\ins, \wit;\alpha, \beta)$.

		\item
		{\bf Acceptance:} $\zkV$ accepts if $\SigV(\alpha, \beta, \gamma) = 1$.
	\end{enumerate}
}

\subsection{Quantum Soundness}
We will reduce the soundness of the sigma protocol to the soundness of the ZK protocol.

\begin{lemma}
	\proref{fig:const_round_qzk} has quantum soundness.
\end{lemma}
\begin{proof}
	Assume towards contradiction there exists a quantum prover $\zkmP = \{ \zkmP_\secp, \rho'_{\secp} \}_{\secp \in \Nat}$ that (for infinitely many $\secp \in \Nat$) breaks soundness with noticeable probability. We construct a successfully cheating quantum prover $\SigmP = \{ \SigmP_\secp, \rho_{\secp} \}_{\secp \in \Nat}$ for the sigma protocol.
	$\SigmP$ will be a quantum circuit that uses $\zkmP$ to interact with $\SigV$ and to break soundness of the sigma protocol, by simulating to $\zkmP$ the honest verifier's $\zkV$ responses.

	Using a simple averaging argument, we can assume w.l.o.g. that $\zkmP = \{ \zkmP_\secp, \rho'_{\secp} \}_{\secp \in \Nat}$ always sends a fixed first message (which is $\cmt_1, \cmt_2$), as we can consider the message and inner quantum state that maximizes the malicious prover's probability to cheat (this is enabled because this is the first protocol message and does not depend on a message from the verifier).
	We further add that because $\zkmP$ succeeds in convincing $\zkV$ to accept instances that are not in $\lang$ with a noticeable probability, and by the soundness of the WI proof that the prover gives in step \ref{qzk:prover_wi} of the protocol, it is in particular guaranteed that the commitment $\cmt_1$ that $\zkmP$ sends in the first message is valid, that is, there are fixed string and randomness $z, r_z \in \{ 0, 1 \}^*$ s.t. $\cmt_1 = \Com(1^{\secp}, z; r_z)$.
	As part of the non-uniform quantum advice $\rho$ of $\SigmP$, it will have the quantum advice of $\zkmP$, plus the information $z, r_z$.

	The operation of $\SigmP$ is described below.
	All operations of $\zkmP$ below are implicitly executed by $\SigmP$ (who also keeps track of the quantum inner state of $\zkmP$ and executes $\zkmP$ with that state) and the messages that $\zkmP$ "sends" are obtained by $\SigmP$.

	\medskip
	\paragraph{$\SigmP(\rho)$:}\label{soundness_reduction}
	\begin{enumerate}
		\item
		$\zkmP$ sends $\cmt_1, \cmt_2$.

		\item
		$\SigmP$ takes the role of $\zkV$ during step \ref{qzk:verifier_commit} and interacts with $\zkmP$, with two changes:
		\begin{itemize}
			\item
			$\SigmP$ does not compute $\beta$, and in step \ref{qzk:verifier_CC} it just uses $0^{|\beta|}$.

			\item
			In step \ref{qzk:verifier_response} it does not actually send an SFE evaluation of $\CC{\mathsf{Id(\cdot)}, t, s}$, but instead performs an SFE evaluation of $C_\bot$, a circuit that always outputs $\bot$.
		\end{itemize}

		At the end of this step, $\SigmP$ starts communicating with the sigma protocol verifier $\SigV$.

		\item
		$\zkmP$ sends $\alpha$, $\SigmP$ delivers the message to $\SigV$.

		\item
		$\SigV$ answers with $\beta$, $\SigmP$ delivers the message to $\zkmP$.

		\item
		$\SigmP$ takes the role of $\zkV$ in step \ref{qzk:verifier_wi} of the protocol and communicates with $\zkmP$, and uses the information $(z, r_z)$ as witness for the WI statement ($z$ is necessarily a non-witness for $x$, because $x \notin \lang$).

		\item
		$\SigmP$ takes the role of $\zkV$ and interacts with $\zkmP$ while $\zkmP$ gives a WI proof.

		\item $\zkmP$ sends $\gamma$, $\SigmP$ delivers it to $\SigV$.

	\end{enumerate}

	\medskip\noindent
	In order to show that the soundness reduction works, it will be enough to show that the transcripts that are generated by the reduction procedure, conditioned that $\zkmP$ succeeds to prove its WI statement (in step \ref{qzk:prover_wi}), are computationally indistinguishable from transcripts generated by the real interaction between $\zkmP$ and $\zkV$ (under the same condition that $\zkmP$ succeeds to prove its WI statement), this is captured by Claim \ref{claim:soundness_indistinguishability}.

	Note that if we prove this indistinguishability, our soundness proof is finished.
	To see this, observe that if the claim is true then in particular the probability that at the end of the real interaction we have $1 = \SigV(\alpha, \beta, \gamma)$ is negligibly close to the probability that in the reduction interaction we have $1 = \SigV(\alpha, \beta, \gamma)$ (note that $\zkV$ accepts only if the WI proof by the prover was accepted).
	Because we assume (towards contradiction) that the probability for $1 = \SigV(\alpha, \beta, \gamma)$ in the real interaction is noticeable, the probability for this event will also be noticeable in the reduction setting, which implies that $\SigmP$ breaks the soundness of the sigma protocol, in contradiction.
	Thus all that remains is to prove Claim \ref{claim:soundness_indistinguishability}.
\end{proof}

\begin{claim}[Soundness Reduction Transcripts Indistinguishability]\label{claim:soundness_indistinguishability}
	Let $\{ \protView_{\zkmP}\prot{\zkmP_\secp(\rho'_\secp)}{\zkV}_{\bot}(\ins_\secp) \}_{\secp \in \Nat}$ denote the distribution over transcripts and inner quantum state of $\zkmP$ generated by interaction between the malicious prover and the honest verifier of the ZK protocol, s.t. if $\zkmP$ fails to prove its WI statement, the process output is $\bot$.
	Let $\{ \protView_{\zkmP}\prot{\zkmP_\secp(\rho'_\secp)}{\SigmP_\secp(\rho_\secp)}_{\bot}(\ins_\secp) \}_{\secp \in \Nat}$ denote the distribution over transcripts and inner quantum state of $\zkmP$ generated by the interaction in the soundness reduction described above, s.t. if $\zkmP$ fails to prove its WI statement, the process output is $\bot$.
	Then,
	$$
	\{ \protView_{\zkmP}\prot{\zkmP_\secp(\rho'_\secp)}{\zkV}_{\bot}(\ins_\secp) \}_{\secp \in \Nat}
	\approx_{c}
	\{ \protView_{\zkmP}\prot{\zkmP_\secp(\rho'_\secp)}{\SigmP_\secp(\rho_\secp)}_{\bot}(\ins_\secp) \}_{\secp \in \Nat}
	\enspace .
	$$
\end{claim}

\begin{proof}
	Define the following hybrid distributions on transcripts.
	\begin{itemize}
		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(1)}:$
		A process that acts like $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}$, except that in step \ref{qzk:verifier_wi}, $\zkV$ uses the information $(z, r_z)$ as a witness for its WI statement, instead of the witness that shows its transcript is explainable.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}:$
		Recall that we assume w.l.o.g. that $\zkmP$ sends valid commitments $\cmt_1, \cmt_2$ in its first message, in particular there's an SFE secret key $\sfedk \in \sfeGen(1^\secp)$ s.t. $\cmt_2 \in \Com(1^\secp, \sfedk)$.
		Now we can describe the current process: In this process, $\zkV$ has also the information $\sfedk$, and the process acts like $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(1)}$, except that when $\zkV$ gets the prover message $\ciph_{\zkmP}$ in step \ref{qzk:prover_sfe}, it performs the following check: If $t = \sfeD_{\sfedk}( \ciph_{\zkmP} )$ then the process halts and outputs $\bot$, otherwise the interaction carries on regularly.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(3)}:$
		A process that acts like $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}$, except that in step \ref{qzk:verifier_response}, instead of performing an SFE evaluation of $\CC{\mathsf{Id(\cdot)}, t, s}$, the verifier performs an SFE evaluation of $C_\bot$.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(4)}:$
		Similar to $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(3)}$ except that the verifier does not perform the check at step \ref{qzk:prover_sfe} like described in $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}$.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(5)}:$
		In this process, $\zkV$ acts as in $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(4)}$, but with one change; in step \ref{qzk:verifier_CC} it uses $0^{|\beta|}$ instead of the $\beta$ it computed with $\SigV$.
		Observe that this distribution is exactly $\protView_{\zkmP}\prot{\zkmP}{\SigmP}_{\bot}$.
	\end{itemize}

	We now explain why $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}$ is computationally indistinguishable from $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(1)}$, and why each consecutive pair of distributions are computationally indistinguishable.
	By the transitivity of computational indistinguisability, this finishes our proof.
	\begin{itemize}
		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot} \approx_{c} \protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(1)}:$
		Follows from the witness indistinguishability property of the WI proof that the verifier gives.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(1)}
		\approx_{s}
		\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}:$
		This indistinguishability is in fact also a statistical one.
		This follows from Claim \ref{claim:find_t}, which basically says that the probability that $\ciph_{\zkmP}$ is an encryption of $t$ with the secret key $\sfedk$ is negligible, and thus the erasure of such cases can't be noticed by a distinguisher.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}
		\approx_{s}
		\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(3)}:$
		As a basic explanation, this statistical indistinguishability follows from the combination of the circuit privacy property of the SFE (specifically, Claim \ref{claim:SFE_eval}) and the soundness of the WI proof that the prover gives.

		As a fuller explanation, assume towards contradiction there's a distinguisher $\Disting$ that tells the difference between the two distributions, and by an averaging argument, consider the transcript (and inner quantum state of $\zkmP$) generated at the end of step \ref{qzk:prover_sfe}, which maximizes $\Disting$'s distinguisability adventage - this transcript fixes in particular the prover's ciphertext $\ciph_{\zkmP}$, and $t, s$, which in turn fix the circuit $\oCC\big[ \mathsf{Id(\cdot)}, t, s \big]$.
		We now consider three cases, and explain why we get a contradiction in each of them.
		\begin{enumerate}
			\item $\ciph_{\zkmP} \in \sfeEnc_{\sfedk}(t)$:
			In this case, no matter what will be generated next in the transcript, the output will be $\bot$ (by the check described in the description of $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}$), thus it is impossible to distinguish the outputs of the two processes and we get a contradiction.

			\item $\exists y \in \{ 0, 1 \}^\secp \setminus \{t\}$ s.t. $\ciph_{\zkmP} \in \sfeEnc_{\sfedk}(y)$:
			In this case, $\bot = \oCC\big[ \mathsf{Id(\cdot)}, t, s \big](y)$ and thus we get a contradiction by using the circuit privacy property of the SFE (Claim \ref{claim:SFE_eval}).

			\item Else:
			In that case, either $\ciph_{\zkmP}$ is a ciphertext encrypted with some other SFE key $\sfedk'$, or it's not a ciphertext at all.
			In these cases, the WI statement of the prover is necessarily false, and thus a non-$\bot$ output happens with at most negligible probability in both cases (by the soundness of the WI proof of $\zkmP$), thus the statistical distance between them is at most negligible, in contradiction to the assumption that $\Disting$ distinguishes with noticeable probability.
		\end{enumerate}

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(3)}
		\approx_{s}
		\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(4)}:$
		Follows from the same reasoning as in the indistinguishability $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(1)}
		\approx_{s}
		\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(2)}$.

		\item $\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(4)}
		\approx_{c}
		\protView_{\zkmP}\prot{\zkmP}{\zkV}_{\bot}^{(5)}:$
		Follows from the simulation property (obfuscation security) of the CC obfuscation scheme.
	\end{itemize}
\end{proof}

\begin{claim}[Producing an SFE Encryption of $t$ with $\sfedk$ is Hard] \label{claim:find_t}
	There's a negligible function $\mu(\cdot)$ s.t. the probability that in step \ref{qzk:prover_sfe}, $\zkmP$ sends $\ciph_{\zkmP}$ s.t. $t = \sfeD_{\sfedk}(\ciph_{\zkmP})$ (where $\sfedk$ is the SFE key inside $\cmt_2$), is bounded by $\mu(\secp)$.
\end{claim}

\begin{proof}
	The proof will be based on the security of $\qheE$, and on the simulation property (security) of the CC obfuscation.
	We start with observing that the security of $\qheE$ implies that for every efficient quantum adversary $\A = \{ \A_\secp, \rho_\secp \}_{\secp \in \Nat}$, there's a negligible function $\mu(\cdot)$ s.t. the probability that $\A$ finds $t$ given $\qhepk, \ciph \gets \qheE_{\qhepk}(t)$ for a uniformly random chosen $t \in \{ 0, 1 \}^{\secp}$, is bounded by $\mu(\secp)$ - we will assume towards contradiction that our claim is false, that is, we assume that $\zkmP$ sends $\ciph_{\zkmP}$ s.t. $t = \sfeD_{\sfedk}(\ciph_{\zkmP})$ with noticeable probability (for infinitely many security parameters), and get a contradiction with the last claim about the hardness of descovering a random encrypted $t$.

	Using $\zkmP$ and the fact that $t = \sfeD_{\sfedk}(\ciph_{\zkmP})$ with noticeable probability, we now describe a (non-uniform) algorithm $\A$ that finds $t$ given $\qhepk, \ciph \gets \qheE_{\qhepk}(t)$ for $t \gets U_{\secp}$ and thus breaks the encryption security of $\qheE$.
	As part of the non-uniform advice of $\A$, it will have the information $\sfedk$.
	So, given $\qhepk, \ciph \gets \qheE_{\qhepk}(t)$, the algorithm $\A$ will use the simulator $\ccSim^{CC}$ (from the simulation property of the CC obfuscation) and send to $\zkmP$ the following, as the protocol message sent at step \ref{qzk:verifier_CC},
	$$
	\qhepk, \; \ciph, \; \ccSim^{\text{CC}}(1^{|\qheD_{0^{|\qhesk|}}|}, 1^{|\qhesk| + |\beta|}, 1^{\secp}) \enspace ,
	$$
	where $\qheD_{0^{|\qhesk|}}$  is the (classical) decryption circuit of the QHE, where the secret key input is hard-wired to be $0^{|\qhesk|}$.
	$\zkmP$ will respond with $\ciph_{\zkmP}$, and $\A$ uses $\sfedk$ to output $\sfeD_{\sfedk}(\ciph_{\zkmP})$.

	We now use the simulation property guarantee of the CC obfuscation: Note that the probability that $\zkmP$ outputs $\ciph_{\zkmP}$ s.t. $\sfeD_{\sfedk}(\ciph_{\zkmP}) = t$ in the simulated setting, where $\A$ sends $\ccSim^{\text{CC}}(1^{|\qheD_{0^{|\qhesk|}}|}, 1^{|\qhesk| + |\beta|}, 1^{\secp})$ instead of $\obfC$, is negligibly close to the probability that it outputs $\ciph_{\zkmP}$ s.t. $\sfeD_{\sfedk}(\ciph_{\zkmP}) = t$ in the regular setting where it gets $\obfC$ - this is due to the security of the CC obfuscator.
	Because we know that in the regular interaction, $\zkmP$ sends $\ciph_{\zkmP}$ s.t. $t = \sfeD_{\sfedk}(\ciph_{\zkmP})$ with a noticeable probability (for infinitely many security parameters), this implies that so does $\A$, in contradiction.

\end{proof}

\subsection{Quantum Zero-Knowledge}\label{subsec:qzk}
We construct a simulator $\zkS$ that for every quantum verifier $\zkmV$ and an instance-advice distribution $\rho$, simulates an output distribution that is computationally indistinguishable from the output distribution generated by choosing a random instance and advice $(x, \rho^{(x)})$ from $\rho$, and then executing the interaction between the honest prover and $\zkmV(\rho^{(x)})$.
$\zkS$ uses as input the verifier's circuit and an access to copies of $\rho$, and is described below.
Every time the verifier circuit $\zkmV$ is executed, it is implicitly the simulator $\zkS$ executing it, who also keeps track of the quantum inner state of $\zkmV$ during the simulated interaction.

\paragraph{Handling Aborts in Simulation.}
In the below simulation, the simulator can halt simulation and choose to "simulate an abort" - this means it discards all information kept so far, and then executs $\zkSA(\zkmV, O_{\rho})$.
This happens when the verifier either aborts, or fails to prove the statement in its WI proof (for messages of incorrect length, the simulator acts like the prover and trivially corrects the messages).

\medskip
\paragraph{$\zkS(\zkmV, O_{\rho}):$}
\begin{enumerate}
	\item {\bf Simulation of Initial Commitments:}
	$\zkS$ samples $(\ins, \rho^{(\ins)})\gets O_{\rho}$, sets $\rho^{(x)}$ to be the inner state of $\zkmV$ (and sets $\ins$ to be at the beginning of the simulator's output transcript).
	$\zkS$ then computes $\sfedk \gets \sfeGen(1^\secp)$ and sends to $\zkmV$ the commitments $\cmt_1 \gets \Com(1^\secp, 0^{|\wit|})$, $\cmt_2 \gets \Com(1^{\secp}, \sfedk)$.

	\item {\bf Extraction Attempt:}
	\begin{enumerate}
		\item \label{simulation:verifier_CC}
		$\zkmV$ sends $\qhepk$, $\ciph_{\zkmV}$, $\obfC$, and also outputs an inner state $\ket{\psi}$.

		\item \label{simulation:extraction}
		$\zkS$ performs a non-black-box step and uses the circuit $\zkmV$:
		\begin{enumerate}
			\item
			$\zkS$ computes $\ciph_{\zkmV}^{\text{SFE}} \gets \qheEv_{\qhepk}(\sfeEnc_{\sfedk}(\cdot), \, \ciph_{\zkmV})$, where $\sfedk$ is the SFE key that is inside $\cmt_2$.
			$\zkS$ also computes $\ciph_{\ket{\psi}} \gets \qheQE_{\qhepk}(\ket{\psi})$.

			Observe that at this point, if $\ciph_{\zkmV}$ is indeed a QHE encryption of some $t$ (using the public key $\qhepk$), then the joint ciphertext $(\ciph_{\zkmV}^{\text{SFE}}, \ciph_{\ket{\psi}})$ encrypts $(\sfeEnc_{\sfedk}(t), \ket{\psi})$.

			\item
			$\zkS$ performs a quantum homomorphic evaluation of the verifier's response. It computes,
			$$
			\left( \ciph_{s}^{\text{SFE}}, \ciph_{\ket{\phi}} \right) \gets \qheEv_{\qhepk}\left(\zkmV, \left( \ciph_{\zkmV}^{\text{SFE}}, \ciph_{\ket{\psi}} \right)\right) \enspace .
			$$

			Observe that if, in addition to sending an encryption for $t$ last step, the verifier's circuit indeed performed an SFE evaluation of the circuit $\CC{\mathsf{Id(\cdot)}, t, s}$, then the joint ciphertext $(\ciph_{s}^{\text{SFE}}, \ciph_{\ket{\phi}})$ encrypts $(\sfeEnc_{\sfedk}(s), \ket{\phi})$, where $\ket{\phi}$ is the inner quantum state of $\zkmV$ after the SFE evaluation.

			\item \label{simulation:extraction_last_step}
			$\zkS$ computes $\ciph_s \gets \qheEv_{\qhepk}\left(\sfeD_{\sfedk}(\cdot), \ciph_{s}^{\text{SFE}} \right)$, and then computes $(\qhesk, \beta') = \obfC(\ciph_s)$
			Finally, $\zkS$ obtains the inner state of $\zkmV$ by decryption: $\ket{\phi} \gets \qheD_{\qhesk}(\ciph_{\ket{\phi}})$.
		\end{enumerate}
	\end{enumerate}

	\item {\bf Sigma Protocol Messages Simulation:}
	\begin{enumerate}
		\item \label{simulation:sigma_simulation}
		$\zkS$ executes $(\alpha, \gamma) \gets \SigS(x, \beta')$ (the simulator from the special zero-knowledge property of the sigma protocol) and sends $\alpha$ to $\zkmV$.

		\item \label{simulation:verifier_sends_beta}
		$\zkmV$ returns $\beta$.
	\end{enumerate}

	\item {\bf WI Proof by the Malicious Verifier:} \label{simulation:verifier_wi}
	$\zkS$ takes the role of the honest prover $\zkP$ in the WI proof $\zkmV$ gives. If $\zkmV$ fails to prove the statement, $\zkS$ executes $\zkSA$.

	\item {\bf Simulation of the Prover's WI Proof and Information Reveal:}\label{simulation:prover_wi}
	$\zkS$ gives $\zkmV$ a WI proof using the witness that shows $\cmt_1$, $\cmt_2$ are both valid commitments (and that $\cmt_2$ is a commitment to the SFE key $\sfedk$ used in step \ref{qzk:prover_sfe}).
	After the proof, $\zkS$ sends $\gamma$ to $\zkmV$.

	$\zkS$ outputs $x$, the interaction transcript and the inner quantum state of $\zkV$ as the simulation's output.
\end{enumerate}

\medskip
\paragraph{$\zkSA(\zkmV, O_{\rho})$:}
\begin{enumerate}
	\item {\bf Estimation of Probability to Abort in Simulated Transcript:} \label{abort_simulation:estimation}
	Iterate and execute the following until either there are $\secp^2$ aborts, or $2^\secp$ iterations have passed:
	Sample $\rho \gets O_\rho$ and execute $\zkS(\zkmV, \rho)$ until the end of the WI proof inside step \ref{simulation:prover_wi} of the simulation (i.e. do not perform the sending of $\gamma$), and if at some point the verifier either aborted or failed in its WI proof, count it as an abort.

	If you exitted the loop because you ran for $2^\secp$ iterations without sufficient aborts, halt and output $\zkFail$.
	Otherwise, let $N$ denote the number of iterations ($N$ is a random variable), and set $a'(\rho) = \frac{\secp^2}{N}$.

	\item {\bf Attempt to Get a Valid Abort Transcript:} \label{abort_simulation:attempt}
	Iterate until either you get an abort, or $\secp\cdot \ceil{\frac{1}{a'(\rho)}}$ iterations have passed:
	\begin{itemize}
		\item
		Sample $(\ins, \rho^{(x)})\gets O_{\rho}$ and set $\rho^{(x)}$ to be the inner state of $\zkmV$, and $\ins$ be at the beginning of the output transcript.

		\item
		Interact with $\zkmV$ as the honest prover $\zkP$ until the end of step \ref{qzk:prover_wi} of the original protocol, with exactly 3 differences:
		\begin{itemize}
			\item
			The commitment $\cmt_1$ is a commitment to $0^{|\wit|}$ rather than to $\wit$.

			\item
			The message $\alpha$ at step \ref{qzk:prover_alpha} is generated by the first-message simulator $\alpha \gets \SigS_1(\ins, 0^\secp)$ (from claim \ref{first_message_indisting}), and not by the sigma protocol prover.

			\item
			At step \ref{qzk:prover_wi}, the witness used is for the first statement in the OR expression (that the commitments $\cmt_1, \cmt_2$ are valid and consistent), and not the second (that $\ins \in \lang$).
		\end{itemize}
	\end{itemize}
	If at some point during the interaction $\zkmV$ either aborts or fails in its WI proof, count it as an abort, exit the loop and output $\zkmV$'s inner state (along with the instance $\ins$ at the beginning).

	If you exitted the loop because you ran for $\secp\cdot \ceil{\frac{1}{a'(\rho)}}$ iterations without an abort, halt and output $\zkFail$.
\end{enumerate}

\medskip
We now turn to formally proving that the simulator runs in expected polynomial time and that the transcripts it generates are computationally indistinguishable (by quantum adversaries) from the transcripts generated by the malicious verifier's real interaction with $\zkP$.
In some parts of the proof, specifically, the proof that the simulator indeed runs in expected polynomial time (Claim \ref{claim:sim_time}) and also the proof that the simulator fails to simulate only with a negligible probability (Claim \ref{claim:fail_probability}), we do an analysis similar to \cite{goldreich1996construct}, adapted to our setting.

\begin{claim}[Simulator Runs in Expected Polynomial Time]\label{claim:sim_time}
	There's a fixed polynomial $q(\cdot)$ such that for every verifier $\zkmV = \{ \zkmV_\secp \}_{\secp \in \Nat}$, and arbitrary distribution $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$, the expected running time of the simulation $\zkS(\zkmV_\secp, O_{\rho_\secp})$ is $q(|\zkmV_\secp|)$.
\end{claim}
\begin{proof}
	Denote the following probabilities:
	\begin{itemize}
		\item
		$a(\rho):$ the probability that $\zkmV(\rho^{(\ins)})$ (after sampling $(\ins, \rho^{(\ins)})\gets \rho$) aborts or fails in its WI proof (for simplicity, we refer to this scenario simply as "abort") in the {\bf standard simulation}, that is, a single iteration of the process described in step \ref{abort_simulation:estimation} of the abort simulation.

		\item
		$b(\rho):$ (will be used in later claims) the probability that $\zkmV(\rho^{(\ins)})$ aborts or fails in its WI proof (also here, we refer to this scenario as "abort") in the {\bf abort simulation}, that is, a single iteration of the process described in step \ref{abort_simulation:attempt} of the abort simulation.

		\item
		$c(\rho):$ (will be used in later claims) the probability that $\zkmV(\rho^{(\ins)})$ aborts or fails in its WI proof (also here, we refer to this scenario as "abort") in the {\bf real interaction with the honest prover}.
	\end{itemize}
	Denote by $T(\zkmV, \rho)$ the running time of the simulator on input $\zkmV_\secp$ with state $\rho_\secp$, and by $T'(\zkmV, \rho)$ the running time of the subroutine $\zkSA$ on the same input, thus,
	\begin{gather*}
		\bb{E}\left[ T(\zkmV, \rho) \right] =
		(1 - a(\rho))\cdot
		\poly(\secp) + a(\rho)\cdot \bb{E}[T'(\zkmV, \rho)] \enspace ,
	\end{gather*}
	for some polynomial $\poly(\cdot)$ that denotes the running time of the simulator when it does not get aborts from $\zkmV_\secp$ (this polynomial depends on the circuit size of $\zkmV_\secp$, which is also a polynomial in $\secp$).

	Recall that the first step of $\zkSA$ is to get $\secp^2$ aborts in the standard simulation (or score $2^\secp$ iterations), thus the expected number of iterations in this step is $\frac{\secp^2}{a(\rho)}$, and expected running time is $\frac{\secp^2}{a(\rho)}\cdot\poly(\secp)$ (note that if our control path has made it to $\zkSA$, then $a(\rho) > 0$).

	Observe that the expected running time of the second part of $\zkSA$ is bounded by
	$$
	\Pr\left[ a'(\rho) \in \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho)\right] \right]\cdot \frac{3\secp}{a(\rho)}\cdot\poly(\secp) +
	\Pr\left[ a'(\rho) \notin \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho)\right] \right]\cdot 2^{O(\secp)} \enspace ,
	$$
	thus it will be enough to show that the probability $\Pr\left[ a'(\rho) \notin \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho)\right] \right]$ is sufficiently small\footnote{For the current claim, it will in fact be enough to only show that $\Pr\left[ a'(\rho) < \frac{1}{2}\cdot a(\rho) \right]$ is sufficiently small, but we'll use the full case later so it will be beneficial to prove it now.}.
	We have,
	\begin{gather*}
		\Pr\left[ a'(\rho) \notin \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho)\right] \right] =
		\Pr\left[ a'(\rho) < \frac{1}{2}\cdot a(\rho) \right] +
		\Pr\left[ a'(\rho) > \frac{3}{2}\cdot a(\rho) \right] \enspace ,
	\end{gather*}
	and we use Chernoff bounds:
	$$
	\Pr\left[ a'(\rho) < \frac{1}{2}\cdot a(\rho) \right] \underset{(a'(\rho) = \frac{\secp^2}{N})}{=}
	\Pr\left[ \frac{2\secp^2}{a(\rho)} < N \right] \leq
	\Pr\left[ X \leq \secp^2 \right] \underset{(*)}{\leq} e^{-\frac{\secp^2}{4}} \enspace ,
	$$
	where $(*)$ follows from using the Chernoff tail bound $\Pr\left[ X \leq (1 - \delta)\mu \right] \leq e^{-\mu\cdot\delta^2\cdot\frac{1}{2}}$, with $X$ being the number of aborts in the experiment of running the simulation $\frac{2\secp^2}{a(\rho)}$ times, the expectation of $X$ is $2\secp^2$, and $\delta$ is $\frac{1}{2}$.

	By similar reasoning it can be easily verified that,
	$$
	\Pr\left[ a'(\rho) > \frac{3}{2}\cdot a(\rho) \right] =
	\Pr\left[ N < \frac{\frac{2}{3}\cdot\secp^2}{a(\rho)} \right]\leq
	\Pr\left[ X \geq (1 + \frac{1}{2})\frac{2}{3}\cdot\secp^2 \right] \leq
	e^{-\frac{\secp^2}{15}} \enspace ,
	$$
	using the Chernoff tail bound $\Pr\left[ X \geq (1 + \delta)\mu \right]\leq e^{-\frac{\delta^2}{2 + \delta}\mu}$.
\end{proof}

We now start the proof of the simulation's validity which will be broken down into four parts:
\begin{enumerate}
	\item
	We prove that the view in successful interactions (where the verifier does not abort or fail to prove its WI statement) is indistinguishable from the view in successful simulations, where there was no need to simulate an abort with $\zkSA$.

	\item
	We prove that the view in aborting interactions (where the verifier in fact does abort or fail to prove its WI statement) is indistinguishable from the view in abort simulations by $\zkSA$.

	\item
	We prove that the simulator's probability to fail in simulating the view (i.e. to output $\zkFail$) is negligible.

	\item
	Finally, using the above three claims, we prove that the (entire) simulated view is computationally indistinguishable from the real view.
\end{enumerate}

\begin{claim}[Computational Indistinguishability of Non-Aborting Part]\label{claim:non_aborting_similarity}
	Let $\zkS_{\bot}$ be a simulation algorithm that acts like $\zkS$, but if $\zkmV$ aborts or fails in its WI proof, then it just outputs $\bot$ (instead of executing $\zkSA$).
	Let $\view_{\zkmV}\prot{\zkP}{\zkmV}_{S}$ be the process of interaction between the honest prover and $\zkmV$, s.t. if $\zkmV$ aborts or fails in the WI proof, the process outputs $\bot$.
	Then, for every verifier $\zkmV$ and instance-advice distribution $\rho$,
	$$
	\{ \view_{\zkmV_\secp}\prot{\zkP(w_\secp)}{\zkmV_\secp(\rho^{(\ins)})}_{S}(\ins) | (\ins, \rho^{(\ins)}) \gets \rho_\secp \}_{\secp\in\Nat}
	\approx_{c}
	\{\zkS_{\bot}(\zkmV_\secp, \rho_\secp)\}_{\secp\in\Nat}\enspace.
	$$
\end{claim}
\begin{proof}
	First, we would like to note that the process $\zkS_{\bot}$ does not need an oracle access $O_{\rho}$ but only one sample $\rho$, because it does not need to simulate aborts (which is the only part that needs the oracle access).

	We prove the claim by a hybrid argument, specifically, we consider intermediate (hybrid) simulation processes, each consecutive pair can be shown to be computationally indistinguishable.
	\begin{itemize}
		\item $\zkS^{(1)}_{\bot}:$ For an instance-advice distribution $\rho$, this process gets the witness $\wit \in \mathcal{R}_{\lang}(\ins)$ and acts exactly like $\zkS_{\bot}$, with the exception that when it gives a WI proof in step \ref{simulation:prover_wi} of the simulation, it uses the witness $\wit$ for the second statement that says $\ins \in \lang$.

		\item $\zkS^{(2)}_{\bot}:$ This process acts like $\zkS^{(1)}_{\bot}$, with the exception that $\cmt_1$ is a commitment to $\wit$ rather than to $0^{|\wit|}$.

		\item $\zkS^{(3)}_{\bot}:$ This process acts like $\zkS^{(2)}_{\bot}$, with the exception that if the verifier's message $\beta$ from part \ref{simulation:verifier_sends_beta} of the simulation does not match the extracted $\beta'$ from part \ref{simulation:extraction_last_step} of the simulation, the process halts and outputs $\bot$.

		\item $\zkS^{(4)}_{\bot}:$ Acts like $\zkS^{(3)}_{\bot}$, with the exception that on parts \ref{simulation:sigma_simulation}, \ref{simulation:prover_wi}, instead of computing $\alpha, \gamma$ through $\SigS$, we compute $\alpha \gets \SigP(\ins, \wit)$ and $\gamma = \SigP(\ins, \wit; \alpha, \beta)$.

		\item $\zkS^{(5)}_{\bot}:$ Acts like $\zkS^{(4)}_{\bot}$, with the exception that it does not perform the check described in $\zkS^{(3)}_{\bot}$.

		\item $\zkS^{(6)}_{\bot}:$ Acts like $\zkS^{(5)}_{\bot}$, with the exception that $\cmt_2$ is a commitment to $0^{|\sfedk|}$ instead of to $\sfedk$.

		\item $\zkS^{(7)}_{\bot}:$ Acts like $\zkS^{(6)}_{\bot}$, with the exception that instead of performing the extraction procedure described in step \ref{simulation:extraction} of the simulation, if the verifier's message at step \ref{simulation:verifier_CC} was explainable and in particular $\ciph_{\zkV}$ is indeed a QHE encryption of some $t \in \{ 0, 1 \}^{\secp}$ (which can be checked inefficiently), then at step \ref{qzk:prover_sfe}, the simulator sends $\sfeEnc_{\sfedk}(t)$, and otherwise acts like $\zkS^{(6)}_{\bot}$. The interaction continues regularly without extraction.

		\item $\zkS^{(8)}_{\bot}:$ Acts like $\zkS^{(7)}_{\bot}$, with the exception that instead of performing the inefficient check on the verifier's message from step \ref{simulation:verifier_CC} (and then sending $\sfeEnc_{\sfedk}(t)$), the simulator just sends $\sfeEnc_{\sfedk}(0^\secp)$ at step \ref{qzk:prover_sfe}.

		\item $\zkS^{(9)}_{\bot}:$ Acts like $\zkS^{(8)}_{\bot}$, with the exception that $\cmt_2$ is again a commitment to $\sfedk$, rather than to $0^{|\sfedk|}$.
		Observe that this process is exactly $\view_{\zkmV}\prot{\zkP}{\zkmV}_{S}$.
	\end{itemize}

	We now turn to explaining why each pair of consecutive distributions are computationally indistinguishable (and also why $\zkS_{\bot} \approx_{c} \zkS^{(1)}_{\bot}$).
	We note that by the transitivity of computational indistinguishability, this finishes our proof.
	\begin{itemize}
		\item $\zkS_{\bot} \approx_{c} \zkS^{(1)}_{\bot}:$
		Follows from the witness-indistinguishability property of the WI proof that the simulator gives in step \ref{simulation:prover_wi}.

		\item $\zkS^{(1)}_{\bot} \approx_{c} \zkS^{(2)}_{\bot}:$
		Follows from the hiding property of the non-interactive commitment $\cmt_1$.

		\item $\zkS^{(2)}_{\bot} \approx_{s} \zkS^{(3)}_{\bot}:$
		These two distributions are in fact statistically indistinguishable.
		Note that the only difference between the distributions is the transcripts from $\zkS^{(2)}_{\bot}$ where $\beta \neq \beta'$, but were not erased by a failed WI proof. This means that either the verifier's transcript was not explainable (but still made it through the WI proof), or there was an error in the quantum homormorphic evaluation (because correctness of both SFE and CC obfuscation is perfect).
		Both scenarios happen only with a negligible probability, and thus the erasure of such cases creates only a negligible statistical distance between the distributions.

		\item $\zkS^{(3)}_{\bot} \approx_{c} \zkS^{(4)}_{\bot}:$
		Follows from the special zero-knowledge property of the sigma protocol.

		\item $\zkS^{(4)}_{\bot} \approx_{s} \zkS^{(5)}_{\bot}:$
		Also here there's more generally, a statistical indistinguishability, by the same reasoning that explains why distributions $\zkS^{(2)}_{\bot}$ and $\zkS^{(3)}_{\bot}$ are statistically indistinguishable.

		\item $\zkS^{(5)}_{\bot} \approx_{c} \zkS^{(6)}_{\bot}:$
		Follows from the hiding property of the non-interactive commitment $\cmt_2$.

		\item $\zkS^{(6)}_{\bot} \approx_{s} \zkS^{(7)}_{\bot}:$
		Follows from the perfect correctness of the SFE and CC obfuscation, and the fact that the QHE evaluation is statistically correct \emph{for every} pair $(\qhepk, \qhesk) \in \qheG$.

		\item $\zkS^{(7)}_{\bot} \approx_{c} \zkS^{(8)}_{\bot}:$
		This indistinguishability follows from the input privacy property of the SFE encryption.

		\item $\zkS^{(8)}_{\bot} \approx_{c} \zkS^{(9)}_{\bot}:$
		Here we use the hiding property of the non-interactive commitment $\cmt_2$.
	\end{itemize}
\end{proof}

Note that the above claim in particular implies that the probailities not to abort in both processes (or alternatively, probabilities to abort) are negligibly close.
\begin{corollary}[$a(\rho)$ and $c(\rho)$ are Negligibly Close]\label{corollary:a_and_c_are_close}
	Let $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$ be any sequence of instance-advice distributions, then there's a negligible function $\mu(\cdot)$ s.t. $\forall \secp \in \Nat: \abs{a(\rho_\secp) - c(\rho_\secp)} \leq \mu(\secp)$.
\end{corollary}

\begin{claim}[Computational Indistinguishability of Aborting Part]\label{claim:aborting_similarity}
	Let $\zkSA_{\bot}$ be an abort-simulation algorithm that acts exactly like executing only part \ref{abort_simulation:attempt} of $\zkSA$, but running only one iteration of it, and if there's no abort (i.e. the verifier gets to the end of the prover's WI proof without any aborts, and also succeeded in its own WI proof), it outputs $\bot$.
	Let $\view_{\zkmV}\prot{\zkP}{\zkmV}_{A}$ be the process of interaction between the honest prover and $\zkmV$, s.t. if $\zkmV$ finishes the interaction successfully until the end of the prover's WI proof, the process outputs $\bot$.
	Then, for every verifier $\zkmV$ and instance-advice distribution $\rho$,
	$$
	\{ \view_{\zkmV_\secp}\prot{\zkP(w_\secp)}{\zkmV_\secp(\rho^{(\ins)})}_{A}(\ins) | (\ins, \rho^{(\ins)}) \gets \rho_\secp \}_{\secp\in\Nat}
	\approx_{c}
	\{\zkSA_{\bot}(\zkmV_\secp, \rho_\secp)\}_{\secp\in\Nat}\enspace.
	$$
\end{claim}
\begin{proof}
	The proof will take a very similar route as the proof of Claim \ref{claim:non_aborting_similarity}.
	We consider hybrid distributions, all of which will be computationally indistinguishable.
	\begin{itemize}
		\item $\zkSA^{(1)}_{\bot}:$ This process gets the witness $\wit \in \mathcal{R}_{\lang}(\ins)$ (all next processes to come also get $\wit$) and acts exactly like $\zkSA_{\bot}$, with the exception that when it gives a WI proof in step \ref{qzk:prover_wi} of the protocol, it uses the witness $\wit$ for the second statement that says $\ins \in \lang$.

		\item $\zkSA^{(2)}_{\bot}:$ Acts exactly like $\zkSA^{(1)}_{\bot}$, with the exception that $\cmt_1$ is a commitment to $\wit$ rather than to $0^{|\wit|}$.

		\item $\zkSA^{(3)}_{\bot}:$ Acts exactly like $\zkSA^{(2)}_{\bot}$, with the exception that the message $\alpha$ at step \ref{qzk:prover_alpha} is generated by the sigma protocol $\alpha \gets \SigP(\ins, \wit)$, and not by the first-message simulator $\alpha \gets \SigS_1(\ins, 0^\secp)$ (from claim \ref{first_message_indisting}).
		Note that this process is exactly $\view_{\zkmV}\prot{\zkP}{\zkmV}_{A}$.
	\end{itemize}

	It's left to reason about the indistinguishabilities between each pair.
	\begin{itemize}
		\item $\zkSA_{\bot} \approx_{c} \zkSA^{(1)}_{\bot}:$
		Follows from the witness-indistinguishability property of the WI proof that the simulator gives (as the prover) in step \ref{qzk:prover_wi} of the protocol.

		\item $\zkSA^{(1)}_{\bot} \approx_{c} \zkSA^{(2)}_{\bot}:$
		Follows from the hiding property of the commitment $\cmt_1$.

		\item $\zkSA^{(2)}_{\bot} \approx_{c} \zkSA^{(3)}_{\bot}:$
		Follows from Claim \ref{first_message_indisting}.
	\end{itemize}
\end{proof}

Note that the above claim in particular implies that the probailities to abort in both processes (or alternatively, probabilities not to abort) are negligibly close.
\begin{corollary}[$b(\rho)$ and $c(\rho)$ are Negligibly Close]
	Let $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$ be any sequence of instance-advice distributions, then there's a negligible function $\mu(\cdot)$ s.t. $\forall \secp \in \Nat: \abs{b(\rho_\secp) - c(\rho_\secp)} \leq \mu(\secp)$.
\end{corollary}
We thus conclude that $a(\cdot), b(\cdot), c(\cdot)$ are all negligibly close to each other.

\begin{claim}[The Simulation Almost Always Succeeds]\label{claim:fail_probability}
	Let $\zkmV = \{ \zkmV_\secp \}_{\secp \in \Nat}$ be a quantum verifier and let $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$ be an instance-advice distribution, then there's a negligible function $\mu$ s.t. for every $\secp \in \Nat$:
	$$
	\Pr\left[ \zkS(\zkmV_\secp, O_{\rho_\secp}) = \zkFail \right] \leq \mu(\secp) \enspace.
	$$
\end{claim}
\begin{proof}
	We have,
	$$
	\Pr\left[ \zkS(\zkmV_\secp, O_{\rho_\secp}) = \zkFail \right] =
	$$
	\begin{equation}\label{eq_1}
		a(\rho_\secp)\cdot\left( \Pr\left[ \text{$\zkSA$ Failed in its first part} \right] + \Pr\left[ \text{$\zkSA$ Failed in its second part} \right] \right) \enspace ,
	\end{equation}
	and we start with showing that the first probability is exponentially small.
	\begin{equation}\label{eq_2}
		\Pr\left[ \text{$\zkSA$ Failed in its first part} \right] =
		\sum_{i = 0}^{\secp^2 - 1}\Pr\left[ \text{There were exactly $2^\secp - i$ fails out of $2^\secp$ tries} \right]\enspace .
	\end{equation}
	Now, recall that the probability to abort in a try (i.e. to succeed in a try) inside the first step of $\zkSA$ is $a(\rho)$, and consider two cases.
	\begin{itemize}
		\item
		$a(\rho) \leq 1/2:$ Thus the sum from \ref{eq_2} is bounded by
		$$
		\secp^2\cdot\Pr\left[ \text{There were $2^\secp$ fails} \right] =
		\secp^2\cdot(1 - a(x))^{2^\secp} \enspace ,
		$$
		and by considering the multiplicative factor $a(\rho)$ (from \ref{eq_1}) we can split to two cases (e.g. $a(\rho) \leq 2^{-\secp/2}$ and $a(\rho) > 2^{-\secp/2}$) and show that (in both cases) when the above probability is multiplied by $a(\rho)$, it is bounded by $2^{-\Omega(\secp)}$.

		\item
		$a(\rho) > 1/2:$ thus the sum from \ref{eq_2} is bounded by
		$$
		\secp^2 \cdot \Pr\left[ \text{There were exactly $2^\secp - \secp^2$ fails} \right] =
		\secp^2 \cdot {2^\secp \choose 2^\secp - \secp^2}\cdot(1 - a(\rho))^{2^\secp - \secp^2}\cdot a(\rho)^{\secp^2} \leq
		$$
		$$
		\secp^2 \cdot 2^{\secp^3}\cdot(1 - a(\rho))^{2^\secp - \secp^2} <
		\secp^2 \cdot 2^{\secp^3}\cdot2^{-2^\secp + \secp^2} \leq 2^{-\Omega(2^\secp)} \enspace .
		$$
	\end{itemize}

	\noindent It is left to show that the probability to fail in the second step is also negligible, and we calculate.
	$$
	\Pr\left[ \text{$\zkSA$ Failed in its second part} \right] \leq
	\Pr\left[ \text{There were $\frac{\secp}{a'(\rho)}$ failed trials} \right] \leq
	$$
	$$
	\Pr\left[ \text{There were $\frac{\secp}{a'(\rho)}$ failed trials} \pST a'(\rho) \in \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho) \right] \right] +
	\Pr\left[ a'(\rho) \notin \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho)\right] \right] \enspace .
	$$
	As a part of the proof of claim \ref{claim:sim_time}, we saw that $\Pr\left[ a'(\rho) \notin \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho)\right] \right] \leq e^{-\Omega(\secp^2)}$, so we only need to bound the first probability.
	$$
	\Pr\left[ \text{There were $\frac{\secp}{a'(\rho)}$ failed trials} \pST a'(\rho) \in \left[\frac{1}{2}\cdot a(\rho), \, \frac{3}{2}\cdot a(\rho) \right] \right] \leq
	$$
	$$
	\Pr\left[ \text{There were $\frac{2\secp}{3a(\rho)}$ failed trials} \right] =
	(1 - b(\rho))^{\frac{2\secp}{3a(\rho)}} \leq
	e^{-\frac{b(\rho)}{a(\rho)}\cdot \frac{2}{3}\cdot \secp} \enspace.
	$$

	Assume towards contradiction that there is some noticeable probability $\varepsilon(\secp) = \secp^{-O(1)}$ s.t. for infinitely many $\secp \in \Nat$, we have,
	$$
	\varepsilon(\secp) \leq
	a(\rho_\secp)\cdot \Pr\left[ \text{There were $\frac{\secp}{a'(\rho_\secp)}$ failed trials} \pST a'(\rho_\secp) \in \left[\frac{1}{2}\cdot a(\rho_\secp), \, \frac{3}{2}\cdot a(\rho_\secp) \right] \right] \enspace .
	$$
	Thus,
	$$
	\varepsilon(\secp) \leq
	a(\rho_\secp)\cdot e^{-\frac{b(\rho_\secp)}{a(\rho_\secp)}\cdot \frac{2}{3}\cdot \secp}
	\enspace .
	$$

	Now, we saw that $a(\rho)$ and $b(\rho)$ are negligibly close, and the last equation implies that $a(\rho)$ is a noticeable function (that is, $a(\rho_\secp)$ is a noticeable function of $\secp \in \Nat$).
	These two properties together imply that (for large values of $\secp$) we have $\frac{b(\rho_\secp)}{a(\rho_\secp)} \in [\frac{1}{2}, 2]$, in contradiction to the inequality $\varepsilon(\secp) \leq e^{-\frac{b(x)}{a(x)}\cdot \frac{2}{3}\cdot \secp}$.
\end{proof}

\medskip
We conclude with showing that the simulation is successful.
\begin{lemma}
	Let $\zkmV = \{ \zkmV_\secp \}_{\secp \in \Nat}$ be a quantum verifier and let $\rho = \{ \rho_\secp \}_{\secp \in \Nat}$ be an instance-advice distribution, then,
	$$
	\{ x, \view_{\zkmV_\secp}\prot{\zkP(w_\secp)}{\zkmV_\secp(\rho_\secp^{(x)})}(\ins) \; | \; (x, \rho_\secp^{(x)}) \gets \rho_\secp \}_{\secp\in\Nat}
	\approx_{c}
	\{\zkS(\zkmV_\secp, O_{\rho_\secp})\}_{\secp\in\Nat}\enspace.
	$$
\end{lemma}
\begin{proof}
	Denote the following distributions.
	\begin{itemize}
		\item $S_{\zkS} = \{ S_{\zkS, \secp} \}_{\secp\in \Nat}:$
		A conditional distribution of $\zkS_{\bot}(\zkmV, \rho)$, conditioned on that the output is not $\bot$ (might be an empty distribution, if $a(\rho) = 1$).

		\item $A_{\zkS} = \{ A_{\zkS, \secp} \}_{\secp\in \Nat}:$
		A conditional distribution of $\zkSA_{\bot}(\zkmV, \rho)$, conditioned on that the output is not $\bot$ (might be an empty distribution, if $b(\rho) = 0$).
	\end{itemize}
	Now, consider the distribution that with probability $1 - a(\rho)$ samples from $S_{\zkS}$, and with probability $a(\rho)$ samples from $A_{\zkS}$ - denote this distribution by $\zkS_{\text{No-Fail}}(\zkmV, \rho)$ (we do not claim nothing about the efficiency of such process).

	Note that by Claim \ref{claim:fail_probability}, $\zkS_{\text{No-Fail}}(\zkmV, \rho)$ is statistically indistinguishable from the output distribution of $\zkS(\zkmV, O_{\rho})$. This follows from three facts: (1) the (original) simulator fails only with negligible probability, (2) the verifier succeeds in the main simulation (and $\zkSA$ isn't executed) with probability $1 - a(\rho)$, and then the output distribution is exactly $S_{\zkS}$, (3) the verifier aborts or fails in its WI proof and we arrive to $\zkSA$ with probability $a(\rho)$, and then if the simulation does not fail, the output distribution is exactly $A_{\zkS}$.
	It thus remains to show that $\zkS_{\text{No-Fail}}$ is computationally indistinguishable from the distribution of the real interaction.

	We define two more conditional distributions.
	\begin{itemize}
		\item $S_{\prot{\zkP}{\zkmV}} = \{ S_{\prot{\zkP}{\zkmV}, \secp} \}_{\secp\in \Nat}:$
		A conditional distribution of $\view_{\zkmV}\prot{\zkP}{\zkmV}_{S}$, conditioned on that the output is not $\bot$ (might be an empty distribution, if $c(\rho) = 1$).

		\item $A_{\prot{\zkP}{\zkmV}} = \{ A_{\prot{\zkP}{\zkmV}, \secp} \}_{\secp\in \Nat}:$
		A conditional distribution of $\view_{\zkmV}\prot{\zkP}{\zkmV}_{A}$, conditioned on that the output is not $\bot$ (might be an empty distribution, if $c(\rho) = 0$).
	\end{itemize}

	Similarly to the proofs of claims \ref{claim:non_aborting_similarity}, \ref{claim:aborting_similarity}, we define hybrid distributions, and show in steps why each consecutive pair of distributions are computationally indistinguishable.
	\begin{itemize}
		\item $\zkS_{\text{No-Fail}}^{(1)}:$
		Like $\zkS_{\text{No-Fail}}$, except that with probability $1 - a(\rho)$ it samples from $S_{\prot{\zkP}{\zkmV}}$ instead from $S_{\zkS}$.

		\item $\zkS_{\text{No-Fail}}^{(2)}:$
		Like $\zkS_{\text{No-Fail}}^{(1)}$, except that with probability $a(\rho)$ it samples from $A_{\prot{\zkP}{\zkmV}}$ instead from $A_{\zkS}$.

		\item $\zkS_{\text{No-Fail}}^{(3)}:$
		Like $\zkS_{\text{No-Fail}}^{(2)}$, except that it samples from $A_{\prot{\zkP}{\zkmV}}$ with probability $c(\rho)$ instead of probability $a(\rho)$ (and thus also samples from $S_{\prot{\zkP}{\zkmV}}$ with probability $1 - c(\rho)$ instead of $1 - a(\rho)$).
		Observe that this distribution is exactly $\view_{\zkmV}\prot{\zkP}{\zkmV(\rho^{(\ins)})}(\ins), (\ins, \rho^{(\ins)}) \gets \rho$.
	\end{itemize}

	It is left to explain why each consecutive pair of distributions are computationally indistinguishable, and then by the transitivity of computational indistinguishability, our proof is finished.
	\begin{itemize}
		\item $\zkS_{\text{No-Fail}} \approx_{c} \zkS_{\text{No-Fail}}^{(1)}:$
		Assume towards contradiction there's an efficient quantum distinguisher $\Disting$ and a noticeable probability $\epsilon(\secp)$ s.t. for an infinite subsequence $Q \subseteq \Nat$, for every $\secp \in Q$, we have,
		$$
		\abs{
			\Pr[\Disting( \zkS_{\text{No-Fail}}(\zkmV_\secp, \rho_\secp) ) = 1] - \Pr[\Disting( \zkS_{\text{No-Fail}}^{(1)}(\zkmV_\secp, \rho_\secp) ) = 1]
		} \geq \epsilon(\secp).
		$$
		Consider two cases.
		\begin{itemize}
			\item There's an infinite subsequence $Q' \subseteq Q$ and a negligible function $\mu$ s.t. $a(\rho_\secp) \leq \mu(\secp)$ for all $\secp \in Q'$.

			In that case, the contradiction follows directly from Claim \ref{claim:non_aborting_similarity}.

			\item Otherwise, there's an infinite subsequence $Q' \subseteq Q$ where $a(\rho_\secp)$ is noticeable for all indices inside $Q'$.
			This implies that for these indices we can sample from $A_{\zkS}$ in polynomial time and overwhelming probability of success in sampling.
			The last fact implies in turn that we can still use Claim \ref{claim:non_aborting_similarity} to get a contradiction in the following manner:
			We reduce distinguishability of non-aborting parts to distinguishability between $\zkS_{\text{No-Fail}}$ and $\zkS_{\text{No-Fail}}^{(1)}$, by getting a sample from either $\zkS_\bot$ or $\view_{\zkmV}\prot{\zkP}{\zkmV}_{S}$, and if we got $\bot$, then we sample (with overwhelming probability of success) from $A_{\zkS}$.
			If the sample was from $\zkS_\bot$, then the output sample of the reduction is from a distribution that's statistically indistinguishable from $\zkS_{\text{No-Fail}}$, and if the sample came from $\view_{\zkmV}\prot{\zkP}{\zkmV}_{S}$, then the reduction output is sample from a distribution which is statistically indistinguishable from $\zkS_{\text{No-Fail}}^{(1)}$.
		\end{itemize}

		\item $\zkS_{\text{No-Fail}}^{(1)} \approx_{c} \zkS_{\text{No-Fail}}^{(2)}:$
		Assume towards contradiction there's an efficient quantum distinguisher $\Disting$ and a noticeable probability $\epsilon(\secp)$ s.t. for an infinite subsequence $Q \subseteq \Nat$, for every $\secp \in Q$, we have,
		$$
		\abs{
			\Pr[\Disting( \zkS_{\text{No-Fail}}^{(1)}(\zkmV_\secp, \rho_\secp) ) = 1] - \Pr[\Disting( \zkS_{\text{No-Fail}}^{(2)}(\zkmV_\secp, \rho_\secp) ) = 1]
		} \geq \epsilon(\secp).
		$$
		Consider two cases.
		\begin{itemize}
			\item There's an infinite subsequence $Q' \subseteq Q$ and a negligible function $\mu$ s.t. $1 - c(\rho_\secp) \leq \mu(\secp)$ for all $\secp \in Q'$.

			In that case, the contradiction follows directly from Claim \ref{claim:aborting_similarity}.

			\item  Otherwise, there's an infinite subsequence $Q' \subseteq Q$ where $1 - c(\rho_\secp)$ is noticeable for all indices inside $Q'$.
			This implies that for these indices we can sample from $S_{\prot{\zkP}{\zkmV}}$ in polynomial time and overwhelming probability of success in sampling.
			The last fact implies in turn that we can still use Claim \ref{claim:aborting_similarity} to get a contradiction in the following manner:
			We reduce distinguishability of aborting parts to distinguishability between $\zkS_{\text{No-Fail}}^{(1)}$ and $\zkS_{\text{No-Fail}}^{(2)}$, by getting a sample from either $\zkSA_\bot$ or $\view_{\zkmV}\prot{\zkP}{\zkmV}_{A}$, and if we got $\bot$, then we sample (with overwhelming probability of success) from $S_{\prot{\zkP}{\zkmV}}$.
			If the sample was from $\zkSA_\bot$, then the output sample of the reduction is from a distribution that's statistically indistinguishable from $\zkS_{\text{No-Fail}}^{(1)}$, and if the sample came from $\view_{\zkmV}\prot{\zkP}{\zkmV}_{A}$, then the reduction output is sample from a distribution which is statistically indistinguishable from $\zkS_{\text{No-Fail}}^{(2)}$.
		\end{itemize}

		\item $\zkS_{\text{No-Fail}}^{(2)} \approx_{s} \zkS_{\text{No-Fail}}^{(3)}:$
		These two distributions are also statistically indistinguishable, which follows from the fact that $a(\rho)$ and $c(\rho)$ are negligibly close (Corollary \ref{corollary:a_and_c_are_close}).
	\end{itemize}
\end{proof}

\section{Constant-Round Zero-Knowledge Quantum Arguments for QMA}\label{sec:qma}

In this section, we show how to use our constant-round ZK argument in order to construct constant-round ZK quantum arguments for QMA, that is, honest parties are efficient and quantum (prover is efficient given a quantum witness), and communication is also quantum.
In \cite{broadbent2016zero}, Broadbent, Ji, Song and Watrous construct a constant-round zero-knowledge quantum protocol for QMA with constant soundness.
They then perform a polynomial sequential repetition of that protocol to get a proof system (with negligible soundness) with polynomially many rounds.

The authors also note that a parallel repetition of their (core, constant-round) protocol can be used to obtain a constant-round zero-knowledge quantum protocol for QMA, given two tools:
\begin{itemize}
	\item
	A fully-simulatable constant-round coin-flipping protocol for polynomially-many bits.

	\item
	A constant-round zero-knowledge protocol for NP.
\end{itemize}

In section \ref{sec:const-round_qzk} we constructed a constant-round argument for NP and in this section (using our zero-knowledge protocol) we construct the required coin-flipping protocol.

Next, we formally define a zero-knowledge quantum argument system for QMA, and then state our result regarding QMA.

\begin{definition}[Zero-Knowledge Quantum Argument for QMA]\label{def:qma_zk}
	A quantum protocol $(\zkP, \zkV)$ with an honest \QPT prover $\zkP$ and an honest \QPT verifier $\zkV$ for a language $\lang \in\QMA$ is a quantum-secure zero-knowledge argument if it satisfies:

	\begin{enumerate}
		\item {\bf Statistical Completeness:}
		There is some negligible function $\mu(\cdot)$ s.t. for any $\secp \in\Nat,\ins \in \lang \cap \zo^\secp, w \in \mathcal{R}_{\lang}(x)$\footnote{For a language $\lang$ in QMA, for an instance $x \in \lang$ in the language, the set $\mathcal{R}_{\lang}(x)$ is the (possily infinite) set of quantum witnesses that make the BQP verification machine accept with some probability negligibly close to 1.},
		$$
		\Pr[ \view_{\zkV}\prot{\zkP(w)}{\zkV}(\ins) = 1 ] \geq 1 - \mu(\secp) \enspace.
		$$

		\item {\bf Quantum Computational Soundness:}
		For any non-uniform quantum polynomial-size prover $\zkmP = \set{\zkmP_\secp}_{\secp \in \Nat}$, there exists a negligible function $\mu(\cdot)$ such that for any security parameter $\secp\in \Nat$ and any $\ins \in \zo^\secp\setminus\lang$,
		\begin{align*}
			\Pr\left[ \view_{\zkV}\prot{\zkmP_\secp}{\zkV}(\ins) = 1 \right] \leq \mu(\secp)\enspace.
		\end{align*}

		\item {\bf Quantum Computational Zero-Knowledge:}
		There exists a quantum expected polynomial-time simulator $\zkS$, such that for any non-uniform quantum polynomial-size verifier $\zkmV = \set{\zkmV_\secp}_{\secp \in \Nat}$,
		$$
		\{ \view_{\zkmV_\secp}\prot{\zkP(w)}{\zkmV_\secp}(\ins)\}_{\substack{\secp\in\Nat,\\ \ins\in\lang\cap\zo^\secp,\\ w \in \mathcal{R}_{\lang}(x)}}
		\approx_{c}
		\{\zkS(\ins,\zkmV_\secp)\}_{\substack{\secp\in\Nat,\\ \ins\in\lang\cap\zo^\secp,\\ w \in \mathcal{R}_{\lang}(x)}}\enspace.
		$$
	\end{enumerate}
\end{definition}
We note that like in the case of NP, the stronger (quantumly-semi-composable) version of the zero-knowledge definition is proven by practically the same proof, but for the sake of simplicity (and because we don't actually use the ZK argument for QMA in this work, only construct it), we stay with the simpler definition.

We now turn to the definition of constant-round fully-simulatable coin-flipping protocol, where the simulation is in the same quantum-semi-composable sense as the zero-knowledge guarantee for the argument from section \ref{sec:const-round_qzk}.

\begin{definition}[2-Party Coin-Flipping Protocol with QSC Full Simulation of Party $\cfA$]\label{def:coin_flipping}
	A 2-party coin-flipping protocol (with full simulation of party $\cfA$) is given by two classical algorithms $(\cfA, \cfB)$ with joint input $1^\secp, 1^{k(\secp)}$, and joint output $r \in \{ 0,1 \}^{k} \cup \{ \bot \}$ (which can be efficiently computed from the protocol transcript), with the following randomness guarantee:
	\begin{itemize}
		\item {\bf Computational Randomness Guarantee for $\cfA$:}
		Let $\cfmB = \{ \cfmB_\secp, \rho_\secp \}_{\secp \in \Nat}$ be a polynomial-size quantum adversary.
		Let $p_\secp$ be the probability that the protocol ends with a non-$\bot$ output when $\cfA$ interacts with $\cfmB_\secp$, and let $(p, U_{k})$ be the distribution that with probability $1 - p$ outputs $\bot$ and with probability $p$ outputs a sample from $U_k$.
		Then, the protocol output $r$ is computationally indistinguishable from $\{ (p_\secp, U_{k(\secp)}) \}_{\secp \in \Nat}$ (where $k(\secp)$ is a polynomial).

		\item {\bf Strong Randomness Guarantee for $\cfB$ (Full QSC Simulation of Party $\cfA$):}
		There exists a quantum expected polynomial-time simulator $\cfS$, such that for any quantum polynomial-size adversary $\cfmA = \{ \cfmA_\secp, \rho_\secp \}_{\secp \in \Nat}$,
		$$
		\{
		\protView_{\cfmA_\secp}\prot{\cfmA(\rho_\secp)}{\cfB}(1^\secp, 1^{k(\secp)})
		\}_{\secp\in\Nat}
		\approx_{c}
		\{
		\cfS(r, \cfmA_{\secp}, O_{\rho_\secp})
		\; | \; r \gets U_{k(\secp)}
		\}_{\secp\in\Nat}\enspace,
		$$
		where,
		\begin{itemize}
			\item
			$\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}$ includes (1) the output $r \in \{ 0, 1 \}^k \cup \{ \bot \}$ of the protocol, (2) the protocol transcript, and (3) the inner quantum state of $\cfmA$ at the end of interaction (whether it ended successfully or not).

			\item
			For the "protocol output" part of its simulation output,
			$\cfS(r, \cfmA_{\secp}, O_{\rho_\secp})$ always outputs either $r$ or $\bot$.

			\item
			$O_{\rho}$ is an inputless oracle that upon activation returns a copy of the quantum state $\rho$.
		\end{itemize}
	\end{itemize}
\end{definition}

We now can state our result regarding QMA.
\begin{theorem}
	Given the existence of constant-round QSC zero-knowledge arguments for NP, and constant-round coin-flipping protocols with QSC Full Simulation, there exists constant-round zero-knowledge quantum arguments for QMA.
\end{theorem}

The construction and proof of the QMA protocol appear in \cite{broadbent2016zero} and are omitted here. The only change in the proof from \cite{broadbent2016zero} is that our coin-flipping and zero-knowledge NP protocols simulations are quantumly-semi-composable, rather then fully composable. This only makes the proof less modular. In our fully-simulatable coin-flipping protocol we demonstrate how to use the semi-composable definition.

\medskip\noindent
We move to present the fully-simulatable coin-flipping protocol.

\paragraph{Ingredients and notation:}
\begin{itemize}
	\item
	A non-interactive commitment scheme $\Com$.
	\item
	A 2-message function-hiding secure function evaluation scheme $(\sfeGen,$ $\sfeEnc,$ $\sfeEval,$ $\sfeD)$.
	\item
	A constant-round QSC zero-knowledge argument system $(\zkP_{\text{NP}}, \zkV_{\text{NP}})$ for NP.
\end{itemize}

\paragraph{Handling Aborts and Alikes.}
Like in previous sections, we set a convention to handle publicly checkable misbehaviors by the parties in the protocol.

\begin{itemize}
	\item
	For a security parameter $\secp$, for each message in the protocol, it is known (publicly) based on $\secp$, what is the length of each message (or upper and lower bounds on that length).
	If a party sends a message in an incorrect length, the receiving party fixes it locally and trivially; if the message is too long, it cuts the message in a suitable place, and if it's too short then pads with zeros.

	\item
	In the below protocol, whenever a party aborts, the other party ends communication, and the output of the protocol is $\bot$.
	The output of the protocol is $\bot$ also if either of the parties fail to prove their arguments in steps \ref{cf:B_argument} and \ref{cf:A_argument} below.
\end{itemize}

We describe the protocol in \figref{fig:const_round_cf}.

\protocol
{\proref{fig:const_round_cf}}
{A constant-round coin-flipping protocol with full simulation of party $\cfA$ and quantum security.}
{fig:const_round_cf}
{
	\begin{description}
		\item[Common Input:] A security parameter $\secp \in \Nat$ and a number $k \in \Nat$ of wanted random coins, both given in unary $1^\secp, 1^k$.
	\end{description}

	\begin{enumerate}
		\item {\bf Initial Commitment by $\cfB$:}\label{cf:B_commit}
		$\cfB$ sends a commitment to $0$: $\cmt_\cfB \gets \Com(1^\secp, 0)$.

		\item {\bf ZK Argument by $\cfB$:}\label{cf:B_argument}
		$\cfB$ interacts with $\cfA$ through $(\zkP_{\text{NP}}, \zkV_{\text{NP}})$ to give a ZK argument that $\cmt_\cfB$ is indeed a commitment to $0$, that is, there exists randomness $r_0 \in \{ 0, 1 \}^{\poly(\secp, 1)}$\footnote{Let $\poly(\secp, \ell)$ denote the polynomial that represents the amount of randomness the commitment algorithm $\Com(\cdot)$ needs for security parameter $\secp$ and message length $\ell$.} s.t. $\cmt_\cfB = \Com(1^\secp, 0; r_0)$.

		\item {\bf $\cfA$ Commits to Coins:}\label{cf:A_commit}
		$\cfA$ chooses $k$ random coins $a \gets U_k$ and sends a commitment for them $\cmt_\cfA \gets \Com(1^\secp, a)$.

		\item {\bf $\cfA$ Challenges $\cfB$:}\label{cf:A_challenge}
		The parties interact so that $\cfA$ can offer to send $a$ if $\cfB$ managed to trick $\cfA$ in the ZK argument.
		\begin{enumerate}
			\item \label{cf:B_sfe}
			$\cfB$ computes $\sfedk \gets \sfeGen(1^\secp)$ and sends $\ciph_{\cfB} \gets \sfeEnc_{\sfedk}(0^{\poly(\secp, 1)})$.

			\item \label{cf:A_response}
			$\cfA$ sends $\evciph \gets \sfeEval\Big( C_{1\rightarrow a}, \ciph_{\cfB} \Big)$, where $C_{1\rightarrow a}$ is the (canonical) circuit that for input $r_1 \in \{ 0, 1 \}^{\poly(\secp, 1)}$ s.t. $\cmt_\cfB = \Com(1^\secp, 1; r_1)$, outputs $a$, and for any other input outputs $\bot$.
		\end{enumerate}

		\item {\bf ZK Argument by $\cfA$:}\label{cf:A_argument}
		$\cfA$ interacts with $\cfB$ through $(\zkP_{\text{NP}}, \zkV_{\text{NP}})$ to give a ZK argument for the statement that its transcript until the end of step \ref{cf:A_response} is explainable.

		\item {\bf Both Parties Reveal Coins:}\label{cf:coin_reveal}
		$\cfB$ computes $b \gets U_k$ and sends it to $\cfA$.
		$\cfA$ responds with sending $a$ along with an opening of the commitment $\cmt_\cfA$.
		If the opening does not open $\cmt_\cfA$ to $a$, protocol output is $\bot$.

		\item {\bf Output:}
		The output of the protocol is $r = a \oplus b$.
	\end{enumerate}
}

\subsection{Randomness Guarantee for $\cfA$}
We prove the (computational) randomness guarantee for party $\cfA$, which basically says that for any efficient quantum attacker $\cfB$, the output distribution of the protocol is computationally indistinguishable from one where the protocol output is a truly random string (considering the aborting probability $1-p$ of the attacker).

\begin{claim}
	\proref{fig:const_round_cf} has a computational randomness guarantee for $\cfA$.
\end{claim}
\begin{proof}
	Let $\cfmB = \{ \cfmB_\secp, \rho_\secp \}_{\secp \in \Nat}$ be a quantum polynomial-size adversary (and let $k(\secp)$ be a polynomial that denotes the number of output bits in the protocol, for security parameter $\secp \in \Nat$), and denote by $r_\secp$ the random variable in $\{ 0, 1 \}^{k(\secp)} \cup \{ \bot \}$ that is the output of the interaction between $\cfA$ and $\cfmB(\rho_\secp)$, and by $p_\secp$ the probability the protocol ends with a non-$\bot$ output when $\cfA$ interacts with $\cfmB_\secp(\rho_\secp)$.
	We prove that
	$$
	\{ r_\secp \}_{\secp \in \Nat}
	\approx_{c}
	\{ (p_\secp, U_{k(\secp)}) \}_{\secp \in \Nat} \enspace .
	$$

	We can assume w.l.o.g. that $\cfmB(\rho)$ always sends the same first message, and the reason is as follows:
	Consider the distribution $D$ over the first message $\cmt_{\cfmB}$ of $\cfmB(\rho)$, and for a message $\cmt_{\cfmB}$ denote by $q_{\cmt_{\cfmB}}$ the probability that the protocol ends with a non-$\bot$ output when $\cfA$ interacts with $\cfmB$, when the first message of $\cfmB$ was $\cmt_{\cfmB}$.
	The reasoning is finished by the following steps:
	\begin{itemize}
		\item
		Recall that $\mathbb{E}_{\cmt_{\cfmB} \gets D}\left[ q_{\cmt_{\cfmB}} \right] = p$.

		\item
		Furthermore, note that the following distribution is identical to the distribution $(p, U_{k})$: Sample $\cmt_{\cfmB} \gets D$ and output a sample from $(q_{\cmt_{\cfmB}}, U_k)$.

		\item
		Denote by $\Disting$ a distinguisher that tells the difference between the protocol's output and $(p, U_k)$.
		Thus,
		\begin{gather*}
			\abs{ \Pr\left[\Disting(r) = 1\right] - \Pr\left[\Disting(p, U_k) = 1\right] } = \\
			\abs{ \mathbb{E}_{\cmt_{\cfmB} \gets D}\left[ \Pr\left[\Disting(r_{\cmt_{\cfmB}}) = 1\right] - \Pr\left[\Disting(q_{\cmt_{\cfmB}}, U_k) = 1\right] \right] } \enspace ,
		\end{gather*}
		where $r_{\cmt_{\cfmB}}$ is the random variable that denotes the protocol's output conditioned that the first message of $\cfmB$ is $\cmt_{\cfmB}$.

		\item
		Finally, we can consider the sample $\cmt_{\cfmB}'$ and inner quantum state $\rho^{(1)}$ s.t. the gap inside the expectation is maximized, and assume that $\cfmB$ always uses this pair (as $\cfmB$ can use n.u. quantum advice).
	\end{itemize}

	We furthermore add w.l.o.g. the assumption that the first message of $\cfmB$, $\cmt_{\cfmB}$, is not only deterministic, but indeed is a commitment to $0$.
	If it wasn't the case that $\cmt_{\cfmB}$ commits to $0$, then by the soundness of the argument that $\cfmB$ gives at step \ref{cf:B_argument} of the protocol, the argument will fail to convince $\cfA$ with overwhelming probability and protocol output $r$ is $\bot$, this means that $p$ is negligibly close to $1$ and that the distributions $r$ and $(p, U_k)$ are statistically indistinguishable, and our proof is finished.

	Now, note that the distribution $\{ r_\secp \}_{\secp}$ is exactly the distribution that's generated by the following process: $\cfA$ and $\cfmB(\rho)$ interact regularly (as usual, if there is an abort by $\cfmB$ or that it fails in its argument in step \ref{cf:B_argument}, output is $\bot$), and once $\cfmB$ sends $b$ at step \ref{cf:coin_reveal}, the process output is $a\oplus b$.

	We claim that the last process is computationally indistinguishable from the following: $\cfA(0^k)$\footnote{For a string $a'\in\{ 0, 1 \}^k$, $\cfA(a')$ denotes the process $\cfA$ s.t. the string $a$ that it commits to in step \ref{cf:A_commit} is $a'$.} and $\cfmB(\rho)$ interact regularly, and when $\cfmB$ sends its string $b$, the process chooses at random $a\gets U_k$ and outputs $a\oplus b$.

	In a nutshell, the reason that the last two distributions are computationally indistinguishable is that the string $a$ that $\cfA$ commits to in step \ref{cf:A_commit} is hidden from computationally bounded quantum adversaries.
	More precisely, the last informal claim is captured formally in Claim \ref{claim:cf_coins_are_hidden}.
	It's easy to verify that given Claim \ref{claim:cf_coins_are_hidden} and an averaging argument over $a$, the above indistinguishability is proved.

	We note that the last distribution is exactly $(p_{0}, U_{k})$, where $p_{0}$ is the probability that $\cfmB(\rho)$ aborts when interacting with $\cfA(0^k)$.
	Finally, observe that $(p_{0}, U_{k})$ is statistically indistinguishable from $(p, U_{k})$ (recall that $p$ is the probability for $\cfmB(\rho)$ to abort when interacting with $\cfA$), and this follows from the fact that $p$ and $p_0$ are negligibly close, which is also implied by Claim \ref{claim:cf_coins_are_hidden}.
\end{proof}

\begin{claim}[$\cfA$'s coins are hidden]\label{claim:cf_coins_are_hidden}
	For a string $s\in\{ 0,1 \}^k$, let $\protView_{\cfmB}\prot{\cfA(s)}{\cfmB(\rho)}$ be the distribution over the transcript and inner quantum state of $\cfmB$ at the end of step \ref{cf:A_argument}, generated in the process of interaction between $\cfA(s)$ and $\cfmB(\rho)$.
	Then, for every two $k(\secp)$-length strings $\{ s_{0, \secp} \}_{\secp \in \Nat}$, $\{ s_{1, \secp} \}_{\secp \in \Nat}$:
	$$
	\{ \protView_{\cfmB}\prot{\cfA(s_{0, \secp})}{\cfmB_\secp(\rho_\secp)}(1^\secp, 1^{k(\secp)}) \}_{\secp \in \Nat}
	\approx_{c}
	\{ \protView_{\cfmB}\prot{\cfA(s_{1, \secp})}{\cfmB_\secp(\rho_\secp)}(1^\secp, 1^{k(\secp)}) \}_{\secp \in \Nat} \enspace .
	$$
\end{claim}

\begin{proof}
	Define the following hybrid distributions on transcripts.
	\begin{itemize}
		\item $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}:$
		Acts like the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}$, except that in step \ref{cf:A_argument}, instead of $\cfA$ communicating with $\cfmB$ to give a ZK argument, we take the ZK simulator $\zkS_{\text{NP}}$ and use it to simulate the argument by $\cfA$.
		The instance-advice distribution $(x, \rho^{(x)})\gets \sigma$ that the simulator will have oracle access to, is the conditional distribution on protocol transcript ($x$) and inner state of $\cfmB$ that is generated by the interaction between $\cfA(s_0)$ and $\cfmB(\rho)$ until the end of step \ref{cf:A_response} ($\rho^{(x)}$), {\bf conditioned} that the transcript is successful so far (no aborts or argument fails from $\cfmB$).

		We further describe the operation of the process: It has oracle access $O_\rho$ to the quantum advice $\rho$ of $\cfmB$, and if it gets to step \ref{cf:A_argument} and needs to simulate, it will use the generated transcript as instance and inner state of $\cfmB$ as the advice, and every time the simulator needs another sample, the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$ restarts, samples from $O_{\rho}$ and generates a transcript and inner state of $\cfmB$ such that the transcript is successful - this might take many tries, but the process will keep on trying until it gets a successful transcript (if we managed to get to step \ref{cf:A_argument} once, the probability to sample a transcript that's successful until that step, is non-zero).

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}:$
		Acts like the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$, except that in step \ref{cf:A_response}, instead of actually performing an SFE evaluation of $C_{1\rightarrow s_0}$, the process performs an SFE evaluation of the circuit $C_\bot$ that always outputs $\bot$.

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(3)}:$
		Acts like the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}$, except that in step \ref{cf:A_commit}, instead of committing to $s_0$, $\cfA$ commits to $s_1$.

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(4)}:$
		Acts like the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(3)}$, except that in step \ref{cf:A_response}, the process performs an SFE evaluation of the circuit $C_{1\rightarrow s_1}$, and not of the circuit $C_\bot$.

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(5)}:$
		Acts like the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(4)}$, except that instead of using the ZK simulator for $\cfA$'s argument, the process is a regular communication between $\cfA(s_1)$ and $\cfmB$.
		Observe that this process is exactly $\protView_{\cfmB}\prot{\cfA(s_1)}{\cfmB(\rho)}$.
	\end{itemize}

	We now explain why $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}$ is computaionally indistinguishable from $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$, and why each consecutive pair of distributions are computationally indistinguishable.
	By the transitivity of computational indistinguisability, after we show the above, we are done.
	\begin{itemize}
		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)} \approx_c \protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}:$
		Follows from the quantumly-semi-composable (QSC) ZK property of definition \ref{def:qzk}.

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)} \approx_c \protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}:$
		As a short explanation, this indistinguishability follows from performing a cutoff on the ZK simulator's running time (which is expected polynomial time), together with the circuit privacy property of the SFE encryption (that's more easily captured by Claim \ref{claim:SFE_eval}).
		As a longer explanation, we give the full reasoning which will be used (but not written from scratch every time) in every of the following indistinguishabilities.

		Assume towards contradiction that these distributions are distinguishable, and we describe a process for distinguishing between SFE evaluations of $C_{1\rightarrow s_0}$ and SFE evaluations of $C_\bot$ which according to Claim \ref{claim:SFE_eval} are statistically indistinguishable because the two circuits have identical functionality (recall we know that the commitment of $\cfmB$ is to $0$, and because of its perfect binding, there is no opening of the commitment to $1$, and thus the circuit $C_{1\rightarrow s_0}$ always outputs $\bot$).

		\begin{itemize}
			\item {\bf Identifying the Processes Operation Exactly:}
			For clarity, we start with explicitly describing the operation processes of both $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$, $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}$.
			Any of the above processes start regularly, and if a process does not get to step \ref{cf:A_argument} on the first try and $\cfmB$ aborts somewhere along the way (or fails the ZK argument), the process terminates regularly.
			However, if a process does make it to the simulation at step \ref{cf:A_argument}, then every time the ZK simulator needs a fresh sample, the process "restarts": it erases the transcript so far, samples $\rho \gets O_{\rho}$ and tries to sample a new successful transcript - this might take a while, because $\cfmB$ can abort somewhere between the restarting point of the process and restarting point of simulation.

			\item {\bf Identifying Processes Expected Running Time as Polynomial:}
			We would now like to explain why both processes still run in expected polynomial time, even when the probability of $\cfmB$ to succeed is negligible.
			Let $p_1$ be the probability that $\cfmB$ succeeds to get to the simulation part in the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$, from the point that we sample $\rho \gets O_{\rho}$ (and let $p_2$ be the same probability for the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}$), then the average number of tries until getting a successful transcript in the setting of $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$ is $1/p_1$, which might be exponential.
			The catch is that we perform such repeated sampling only when we already gotten a successful transcript once, which happens with probability $p_1$.
			More specifically, the expected running time of the procedure $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$ is,
			$$
			(1-p_1) \cdot \poly(\secp) + p_1 \cdot q(|\cfmB|)\cdot \frac{1}{p_1} \cdot \poly(\secp) \leq \poly(\secp) + q(|\cfmB|)\cdot \poly(\secp) =: q'(\secp) \enspace ,
			$$
			where $\poly(\secp)$ is a polynomial that denotes the running time of the protocol interaction (executing the algorithms $\cfA$ and $\cfmB$ until the simulation part), and the number $\frac{1}{p_1} \cdot \poly(\secp)$ thus denotes the expected running time to get a fresh sample for the ZK simulator, which runs in expected time $q(|\cfmB|)$.
			By similar reasoning, we obtain that the expected running time of the process $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}$ is also bounded by the polynomial $q'(\secp)$.

			\item {\bf Using the Distinguisher's Advantage to Define Strinct Polynomial-Time Processes:}
			A distinguisher $\Disting$ that tells the difference between the two processes above, distinguishes with some noticeable probability $\epsilon(\secp)$ (for infinitely many security parameters).
			We will show how to turn the simulators to fixed polynomial-time ones that use a polynomial-size quantum advice.
			Now, in either of the processes (whether we get an evaluation of $C_{1\rightarrow s_0}$ or of $C_\bot$), the expectation of the running time of the process is $q'(\secp)$, where $q'(\cdot)$ is fixed polynomial.
			By Markov's inequality, the probability that the process's running time exceeds $m(\secp) := q'(\secp)\cdot 4\cdot \frac{1}{\epsilon}$ is bounded by $\frac{\epsilon}{4}$, and thus if we consider an alternative process that halts after exceeding this time bound (and in particular doesn't use oracle access $O_\rho$ to $\rho$ samples, but a fixed $m(\secp)$ samples of $\rho$), its output distribution has statistical distance bounded by $\frac{\epsilon}{4}$ to that of the original process.

			\item {\bf Observing that the Distinguisher Tells the Difference Between the Cutoff Processes:}
			For the distinguisher $\Disting$ that tells the difference between the two original processes (that take expected polynomial time to execute), the distinction advantage is at least $\epsilon$, and thus, because each of the cutoff processes is $\frac{\epsilon}{4}$-close to its original version, the distinction advantage of $\Disting$ between the two cutoff processes is at least $\frac{\epsilon}{2}$.

			\item {\bf Connecting the Processes with a Cryptographic Security Guarantee:}
			We now connect the distinguisher with the circuit privacy property of the SFE.
			Note that by Claim \ref{claim:SFE_eval} and by the fact that the circuits $C_{1\rightarrow s_0}$ and of $C_\bot$ have identical functionality, we can claim that for any distribution $D$ on $(\ket{\phi}, \ciph^*)$ where $\ket{\phi}$ is a quantum state and $\ciph^*$ is a possibly invalid ciphertext, the distributions $(\ket{\phi}, \ciph^*, \sfeEval(C_{1\rightarrow s_0}, \ciph^*))$ and $(\ket{\phi}, \ciph^*, \sfeEval(C_{\bot}, \ciph^*))$ are also statistically indistinguishable, this is true by a simple averaging argument.
			The above implies that for any polynomial number of independent samples of the abovementioned tuples, evaluations of $C_{1\rightarrow s_0}$ on samples from $D$ and evaluations of $C_\bot$ on samples from $D$ are still statistically indistinguishable, this can be verified by a hybrid argument.

			In particular, consider the distribution $D$ that samples a transcript and inner quantum state for $\cfmB$ generated at the end of step \ref{cf:B_sfe}, that is, $\ket{\phi}$ is the transcript and the inner quantum state of $\cfmB$, not including the message $\ciph_{\cfmB}$ from step \ref{cf:B_sfe}, and $\ciph^* := \ciph_{\cfmB}$, and if there was an abort before step \ref{cf:B_sfe} in the interaction of that sample, define $\ciph^* := 0$.
			$m(\secp)$ is a polynomial and such number of samples is statistically indistinguishable - we show that we can distinguish, in contradiction.

			\item {\bf Security Reduction:}
			We describe a distinguisher $\tilde{\Disting}$ that will use $\Disting$: it gets a sample $(z_1, z_2, \cdots, z_{m(\secp)})$ which is either $m(\secp)$ tuples of evaluations of $C_{1\rightarrow s_0}$ or of $C_\bot$.
			If the transcript in $z_1$ is aborting we just give $\Disting$ the transcript and inner state of $\cfmB$ (this corresponds to the scenario where $\cfmB$ aborted before we even got to the ZK simulation for the first time).
			Otherwise, we initiate the ZK simulator and when it needs new sample from its instance-advice oracle, then we use the rest of the samples $z_2, z_3, \cdots, z_{m(\secp)}$ to feed it.
			It can be verified that when the tuples come from evaluations of $C_{1 \rightarrow s_0}$ then the transcripts that $\tilde{\Disting}$ generates for $\Disting$ come from the output distribution of the cutoff process of $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)}$, and when tuples come from evaluations of $C_{\bot}$ then the transcripts that $\tilde{\Disting}$ generates for $\Disting$ come from the output distribution of the cutoff process of $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}$.
			Thus $\Disting$ tells the difference with advantage $\frac{\epsilon}{2}$ and so does $\tilde{\Disting}$, in contradiction.
		\end{itemize}

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)} \approx_c \protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(3)}:$
		Follows from performing a cutoff on the ZK simulator's running time, together with the hiding of the commitment $\Com(\cdot)$.

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(3)} \approx_c \protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(4)}:$
		Similarly to the indistinguishability $\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(1)} \approx_c \protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(2)}$, this one follows from performing a cutoff on the ZK simulator's running time, together with the circuit privacy property of the SFE encryption.

		\item
		$\protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(4)} \approx_c \protView_{\cfmB}\prot{\cfA(s_0)}{\cfmB(\rho)}^{(5)}:$
		Follows again from the QSC ZK property of definition \ref{def:qzk}.
	\end{itemize}
\end{proof}

\subsection{Full Simulation of Party $\cfA$}
We show a quantum expected polynomial-time simulator $\cfS$ s.t. for any polynomial-size quantum adversary $\cfmA = \{ \cfmA_\secp, \rho_\secp \}_{\secp \in \Nat}$, simulates the protocol as described in definition \ref{def:coin_flipping}.

\paragraph{Handling Aborts in Simulation.}
In the below simulation, if at any part of the simulation $\cfmA$ either aborts, or fails in its argument statement (for messages of incorrect length, the simulator acts like $\cfB$ and trivially corrects the length, as describe above the protocol) the simulator halts, outputs $\bot$ as the simulation coin-flipping output, the transcript so far as the simulation transcript output, and the inner state of $\cfmA$ as the simulation adversary state output.

\medskip
\paragraph{$\cfS(r, \cfmA, O_{\rho}):$}
\begin{enumerate}

	\item {\bf Simulation of Initial Commitment:}\label{cf_simulation:B_commit}
	$\zkS$ samples $\rho \gets O_{\rho}$ and sets $\rho$ to be the inner state of $\cfmA$.
	$\cfS$ then sends to $\cfmA$ a commitment to 1: $\cmt_{\cfS} = \Com(1^{\secp}, 1; r_1)$, where $r_1 \in \{ 0, 1 \}^{\poly(\secp, 1)}$ is the random string used as the randomness of the commitment algorithm.

	\item {\bf $\cfB$'s ZK Argument Simulation:}\label{cf_simulation:B_argument}
	$\cfS$ uses the argument's ZK simulator $\zkS_{\text{NP}}$ to simulate for $\cfmA$ the communication with $\cfB$.
	It executes $\zkS_{\text{NP}}(\cfmA, O_{\sigma})$, where $\sigma$ is the instance-advice distribution $(x, \rho^{(x)})$ that is generated s.t. $x$ is a commitment to $1$ by $\cfS$ (from step \ref{cf_simulation:B_commit} of the simulation), and $\rho_{(x)}$ is the inner state $\rho$ of $\cfmA$ at the beginning of the protocol.

	\item {\bf Extraction Attempt from $\cfmA$:}\label{cf_simulation:A_extraction}
	\begin{itemize}
		\item
		$\cfmA$ outputs $\cmt_{\cfmA}$.

		\item
		$\cfS$ computes $\sfedk \gets \sfeGen(1^\secp)$ and sends $\ciph_{\cfS}\gets \sfeEnc_{\sfedk}(r_1)$.

		\item
		$\cfmA$ outputs a response $\evciph$.
	\end{itemize}
	$\cfS$ then decrypts the evaluated ciphertext to get $a'$.

	\item {\bf ZK Argument by Malicious $\cfmA$:} \label{cf_simulation:A_argument}
	$\cfS$ takes the role of the honest $\cfB$ in the ZK argument $\cfmA$ gives.

	\item {\bf Matching $\cfB$'s Coins to $\cfmA$'s Coins:}
	$\cfS$ sends $b = a' \oplus r$ to $\cfmA$.
	$\cfmA$ sends back $a$ and $r_a$, $\cfS$ verifies that $r_a$ indeed opens $\cmt_{\cfmA}$ to $a$, and thus decides if the output of the protocol is $a\oplus b$ or $\bot$.
	Finally, $\cfS$ outputs the inner state of $\cfmA$ along with the protocol output (either $a\oplus b$ or $\bot$) and transcript.
\end{enumerate}

\medskip
It is clear that given oracle access to copies of $\rho$, the expected running time of the simulator is polynomial, as it performs polynomial-time computations plus executing the ZK argument simulator $\zkS_{\text{NP}}$, which also runs in expected polynomial time.
It remains to explain why the above simulation process yields an output that's computationally indistinguishable from what's generated in a real interaction between $\cfmA(\rho)$ and $\cfB$.

\begin{claim}[CF Simulator Output Validity]
	Let $\cfmA = \{ \cfmA_\secp, \rho_\secp \}_{\secp \in \Nat}$ be a polynomial-size quantum adversary, then,
	$$
	\{
	\protView_{\cfmA_\secp}\prot{\cfmA(\rho_\secp)}{\cfB}(1^\secp, 1^{k(\secp)})
	\}_{\secp\in\Nat}
	\approx_{c}
	\{
	\cfS(r, \cfmA_{\secp}, O_{\rho_\secp})
	\; | \; r \gets U_{k(\secp)}
	\}_{\secp\in\Nat}\enspace.
	$$
\end{claim}

\begin{proof}
	Define the following hybrid processes:
	\begin{itemize}
		\item
		$\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(1)}:$
		This process acts like the regular interaction $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}$, except that it has oracle access $O_{\rho}$ to the inner state $\rho$ of $\cfmA$, and in step \ref{cf:B_argument}, instead of executing the argument between the parties, we take the ZK simulator $\zkS_{\text{NP}}$ to simulate $\cfmA$'s view.
		To use the simulator we need to define what is the instance-advice distribution $(x, \rho^{(x)})\gets \sigma$, and let $\zkS_{\text{NP}}$ have oracle access to $O_{\sigma}$.
		\begin{itemize}
			\item
			The distribution $(x, \rho^{(x)})\gets \sigma$ is the distribution on protocol transcript ($x$) and inner state ($\rho^{(x)}$) of $\cfmA$ that is generated by the interaction between $\cfmA(\rho)$ and $\cfB$ until the end of step \ref{cf:B_commit}, that is, $x$ is a commitment to $0$ by $\cfB$, and $\rho^{(x)}$ is simply the inner state $\rho$ of $\cfmA$ before protocol starts.
		\end{itemize}

		\item
		$\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(2)}:$
		Acts like $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(1)}$, except that in step \ref{cf:B_commit}, $\cfB$ commits to $1$ instead of to $0$.

		\item
		$\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(3)}:$
		Acts like $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(2)}$, except that in step \ref{cf:B_sfe}, $\cfB$ sends an SFE encryption $\ciph_{\cfB}$ of the randomness that it used in step \ref{cf:B_commit} when it committed for $1$.

		\item
		$\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(4)}:$
		Acts like $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(3)}$, except that in step \ref{cf:coin_reveal}, $\cfB$ outputs $b = a' \oplus r$  for a random $r \gets U_{k(\secp)}$, instead of a random string $b \gets U_{k(\secp)}$.
		Observe that this distribution, given the fact the $r$ is sampled uniformly and is not used in the process before this last step, is exactly $\{
		\cfS(r, \cfmA_{\secp}, O_{\rho_\secp})
		\; | \; r \gets U_{k(\secp)}
		\}$.
	\end{itemize}

	We now explain why $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}$ is computationally indistinguishable from $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(1)}$, and why each consecutive pair of distributions are computationally indistinguishable.
	By the transitivity of computational indistinguisability, after we show the above, we are done.
	\begin{itemize}
		\item $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB} \approx_c \protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(1)}:$
		Follows from the ZK property of definition \ref{def:qzk}.

		\item $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(1)} \approx_c \protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(2)}:$
		Follows from performing a cutoff on the ZK simulator's running time (the full technical reasoning can be seen as part of the proof of Claim \ref{claim:cf_coins_are_hidden}), together with the hiding of the commitment algorithm $\Com(\cdot)$.

		\item $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(2)} \approx_c \protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(3)}:$
		Follows from the input privacy (encryption security) property of the SFE encryption.

		\item $\protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(3)} \equiv \protView_{\cfmA}\prot{\cfmA(\rho)}{\cfB}^{(4)}:$
		These two distributions in fact yield exactly the same distribution, because in both cases the random coins of $\cfB$ in step \ref{cf:coin_reveal} distribute exactly like $U_{k}$.
	\end{itemize}

\end{proof}

\subsubsection*{Acknowledgments}
We thank Zvika Brakerski for insightful discussions about Quantum Fully-Homomorphic Encryption.
We also thank Venkata Koppula for advice regarding the state of the art of Compute-and-Compare Obfuscation.

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv