text:
\section{Introduction}
\vspace{-0.5em}

Quantum computing and modern cryptography have enjoyed a highly
productive relationship for many decades ever since the conception of
both fields. On the one hand, (large-scale) quantum computers can be
used to break many widely used cryptosystems based on the hardness of
factoring and discrete logarithms, thanks to Shor's
algorithm~\cite{Shor94}. On the other hand, quantum information and
computation have helped us realize cryptographic tasks that are
otherwise impossible, for example quantum money~\cite{Wiesner} and generating certifiable randomness~\cite{Colbeck09,VV12,BCMVV18}.

Yet another crown jewel in quantum cryptography is the discovery, by Bennett and Brassard~\cite{BB84}, of a key exchange protocol whose security is unconditional. That is, they achieve information-theoretic security for a cryptographic task that classically necessarily has to rely on unproven computational assumptions. In a nutshell, they accomplish this using the uncloneability of quantum states, a bedrock principle of quantum mechanics. What's even more remarkable is the fact that their protocol makes minimalistic use of quantum resources, and consequently, has been implemented in practice over very large distances~\cite{Dixon_2008,Liao_2018}. This should be seen in contrast to large scale quantum {\em computation} whose possibility is still being actively debated.

Bennett and Brassard's groundbreaking work raised a {\em tantalizing} possibility for the field of cryptography:
\begin{quote}
\centering
  {\em Could {\em every} cryptographic primitive\\ be realized unconditionally using quantum information?}
\end{quote}

A natural next target is oblivious transfer (OT), a versatile cryptographic primitive which, curiously, had its origins in Wiesner's work in the 1970s on quantum information~\cite{Wiesner} before being rediscovered in cryptography by Rabin~\cite{Rabin81} in the 1980s. Oblivious transfer (more specifically, $1$-out-of-$2$ OT) is a two-party functionality where a receiver Bob wishes to obtain one out of two bits that the sender Alice owns. The OT protocol must ensure that Alice does not learn which of the two bits Bob received, and that Bob learns only one of Alice's bits and no information about the other.
Oblivious transfer lies at the foundation of secure computation, allowing us to construct protocols for the secure multiparty computation (MPC) of any polynomial-time computable function~\cite{STOC:GolMicWig87,STOC:Kilian88,C:IshPraSah08}.

Bennett, Brassard, Cr\'{e}peau and Skubiszewska\cite{C:BBCS91} constructed an OT protocol given an {\em ideal} bit commitment protocol and quantum communication. In fact, the only quantum communication in their protocol consisted of Alice sending several so-called ``BB84 states'' to Bob. Unfortunately, {\em unconditionally secure} commitment~\cite{Mayers97,LoChau97} and {\em unconditionally secure} OT~\cite{Lo97,CGS16} were soon shown to be impossible even with quantum resources.

However, given that bit commitment can be constructed from one-way functions (OWF{})~\cite{C:Naor89,HILL99}, the hope remains that OT, and therefore a large swathe of cryptography, can be based on only {\em OWF{}} together with (practically feasible) quantum communication. Drawing our inspiration from Impagliazzo's five worlds in cryptography~\cite{Imp95}, we call such a world, where post-quantum secure one-way functions (pqOWF{}) exist and quantum computation and communication are possible,  {Mini\textbf{\textcolor{blue}{Q}}Crypt}. The  question that motivates this paper is:
\begin{quote}
  \begin{center}
  {\em Do OT and MPC exist in MiniQCrypt?}
  \end{center}
\end{quote}

Without the quantum power, this is widely believed to be
impossible. That is, given only OWF{}s, there are no {\em
  black-box} constructions of OT or even key exchange
protocols~\cite{IR89,Rud91}. The fact that \cite{BB84} overcome this
barrier and construct a key exchange protocol with quantum
communication (even without the help of OWF{}s)
reinvigorates our hope to do the same for OT.

\paragraph{Aren't We Done Already?}
At this point, the reader may wonder why we do not have an affirmative
answer to this question already, by combining the OT protocol of \cite{C:BBCS91}
based on bit commitments, with a construction of bit commitments from
pqOWF{}~\cite{C:Naor89,HILL99}. Although this possibility was
mentioned already in \cite{C:BBCS91}, where they note that
``\ldots computational complexity based quantum cryptography is interesting
since it allows to build oblivious transfer around one-way
functions.'', attaining this goal remains elusive as we explain below.

First, proving the security of the \cite{C:BBCS91} OT protocol (regardless of the
assumptions) turns out to be a marathon.
After early proofs against {limited}
adversaries~\cite{MaySal94,STOC:Yao95}, it is relatively recently that we have a
clear picture with formal
proofs against arbitrary quantum polynomial-time adversaries~\cite{DFR+07,DFL+09,C:BouFeh10,EC:Unruh10}.
Based on these results, we
can summarize the state of the art as follows.

\begin{itemize}
\item \highlight{Using Ideal Commitments:}
  If we assume an \emph{ideal} commitment protocol, formalized as
  universally composable (UC) commitment, then the quantum OT
  protocol can be proven secure in strong
  {simulation}-based models, in particular the quantum UC model
  that admits sequential
  composition or even concurrent composition in a network setting~\cite{DFL+09,FS09,C:BouFeh10,EC:Unruh10}.
  However, UC commitments, in contrast to
  vanilla computationally-hiding and statistically-binding commitments,
  are powerful objects that do not live in Minicrypt. In particular,
  UC commitments give us key exchange protocols and are therefore
  black-box separated from Minicrypt.\footnote{The
  key exchange protocol between Alice and Bob works as follows. Bob, playing
  the simulator for a malicious
  sender in the UC commitment protocol, chooses a common reference string (CRS)
  with a trapdoor $TD$ and sends
  the CRS to Alice. Alice, playing the sender in the commitment scheme,
  chooses a random $K$ and runs the
  committer algorithm. Bob runs the straight-line
  simulator-extractor (guaranteed by UC simulation)
  using the $TD$ to get $K$, thus ensuring that Alice and Bob have a
  common key. An eavesdropper Eve should not
  learn $K$ since the above simulated execution is indistinguishable from
  an honest execution, where $K$ is hidden.}

\item \highlight{Using Vanilla Commitments:}
    If in the \cite{C:BBCS91} quantum OT protocol we use a {\em vanilla}
    statistically-binding and computationally hiding commitment scheme, which
    exists assuming a pqOWF{}, the
    existing proofs, for example \cite{C:BouFeh10}, fall short in two respects.

    First, for a malicious receiver, the proof of \cite{C:BouFeh10}
    constructs only an {\em in}efficient simulator. Roughly speaking,
    this is because the OT receiver in \cite{C:BBCS91} acts as a
    committer, and vanilla commitments are not extractable. Hence, we
    need an inefficient simulator to extract the committed value by
    brute force. Inefficient simulation makes it hard, if not
    impossible, to use the OT protocol to build other protocols (even
    if we are willing to let the resulting protocol have inefficient
    simulation). Our work will focus on achieving the standard
    ideal/real notion of security~\cite{Golbook} with efficient
    simulators.

    Secondly, it is unclear how to construct a simulator (even
    ignoring efficiency) for a malicious sender. Roughly speaking, the
    issue is that simulation seems to require that the commitment
    scheme used in \cite{C:BBCS91} be secure against selective opening
    attacks, which vanilla commitments do not
    guarantee~\cite{EC:BelHofYil09}.

  \item \highlight{Using Extractable Commitments:} It turns out that the
    first difficulty above can be addressed if we assume a commitment
    protocol that allows \emph{efficient extraction} of the committed
    value -- called extractable commitments.
    %
    %
    %
    %
    Constructing extractable commitments is surprisingly challenging
    in the quantum world because of the hardness of
    rewinding. Moreover, to plug into the quantum OT protocol, we need
    a strong version of extractable commitments from which the
    committed values can be extracted efficiently {\em without
      destroying or even disturbing the quantum states of the
      malicious committer,\footnote{This is because when using
        extractable commitment in a bigger protocol, the proof needs
        to extract the committed value and continue the execution with
        the adversary.}} a property that is at odds with quantum
    unclonability and rules out several extraction techniques used for
    achieving arguments of knowledge such as
    in~\cite{EC:Unruh12}.\rachelm{add citation to quantum AOK.} In
    particular, we are not aware of a construction of such extractable
    commitments without resorting to strong assumptions such as
    LWE~\cite{STOC:BitShm20,AnaPla19}, which takes us out of
    minicrypt.  Another standard way to construct extractable
    commitments is using public-key encryption in the CRS model, which
    unfortunately again takes us out of minicrypt.
\end{itemize}

To summarize, we would like to stress that before our work, the claims that quantum OT protocols can be constructed from pqOWF{}s~\cite{C:BBCS91,FangUWYZ20} were rooted in misconceptions. \agnotem{Gave another shot}\vnotem{Controversial sentence?}

\paragraph{Why MiniQCrypt.}
Minicrypt is one of five Impagliazzo's worlds~\cite{Imp95} where OWF{}s exist,
but public-key encryption schemes do not. In Cryptomania, on the other hand, public-key
encryption schemes do exist.

Minicrypt is robust {\em and} efficient. It is robust because there is
an abundance of candidates for OWF{}s that draw from a
variety of sources of hardness, and most do not fall to quantum
attacks. Two examples are (OWF{}s that can be constructed
from) the advanced encryption standard (AES) and the secure hash
standard (SHA). They are ``structureless'' and hence typically do not
have any subexponential attacks either. In contrast, cryptomania seems
fragile and, to some skeptics, even endangered due to the abundance of
subexponential and quantum attacks, except for a handful of
candidates. It is efficient because the operations are combinatorial
in nature and amenable to very fast implementations; and the key
lengths are relatively small owing to OWF{}s against which
the best known attacks are essentially brute-force key search.  We
refer the reader to a survey by Barak~\cite{baraksurvey} for a deeper
perspective.

Consequently, much research in (applied) cryptography has been devoted
to minimizing the use of public-key primitives in advanced
cryptographic protocols~\cite{Beaver96,IKNP03}.  However, complete
elimination seems hard.  In the classical world, in the absence of
quantum communication, we can construct pseudorandom generators and
digital signatures in Minicrypt, but not key exchange, public-key
encryption, oblivious transfer or secure computation protocols. With
quantum {\em communication} becoming a reality not just
academically~\cite{Dixon_2008,Hiskett_2006,Pugh_2017} but also
commercially~\cite{Liao_2018}, we have the ability to reap the
benefits of robustness and efficiency that Minicrypt affords us, {\em
  and} construct powerful primitives such as oblivious transfer and
secure computation that were so far out of reach.

\paragraph{Our results.}
In this paper, we finally show that the longstanding (but previously unproved) claim is true.
\begin{theorem}[Informal]
  Oblivious transfer protocols in the plain model that are simulation-secure
  against malicious quantum polynomial-time adversaries
  exist assuming that post-quantum one-way functions exist and that quantum communication is possible.
\end{theorem}
Our main technical contribution consists of showing a construction of
an extractable commitment scheme based solely on pqOWF{}s and using quantum communication. Our construction involves
three ingredients.  The first is vanilla post-quantum commitment
schemes which exist assuming that pqOWF{}s
exist~\cite{C:Naor89}.  The second is post-quantum zero-knowledge
protocols which also exist assuming that pqOWF{}s exist~\cite{Watrous09}.  The third and final ingredient is a
special multiparty computation protocol called conditional disclosure
of secrets (CDS) constructing which in turns requires OT.  This might
seem circular as this whole effort was to construct an OT protocol to
begin with!  Our key observation is that the CDS protocol is only
required to have a mild type of security, namely {\em unbounded
  simulation}, which {\em can} be achieved with a slight variant of
the \cite{C:BBCS91} protocol.  Numerous difficulties arise in our
construction, and in particular proving consistency of a protocol
execution involving quantum communication appears difficult: how do we
even write down an statement (e.g., NP or QMA) that encodes
consistency?  Overcoming these difficulties constitutes the bulk of
our technical work. We provide a more detailed discussion on the
technical contribution of our work in \Cref{sec:technical}.

We remark that understanding our protocol requires only limited knowledge of
quantum computation. Thanks to the composition theorems for (stand-alone) simulation-secure
quantum protocols~\cite{HSS15}, much of our protocol can be viewed as a
{\em classical} protocol in the
(unbounded simulation) OT-hybrid model. The only quantumness resides in the
instantiation of the OT hybrid
with %
\cite{C:BBCS91}.%

We notice that just as in \cite{BB84,C:BBCS91}, the honest execution
of our protocols does not need strong quantum computational power,
since one only needs to create, send and measure ``BB84'' states,
which can be performed with current quantum technology. \footnote{A
  BB84 state is a single-qubit state that is chosen uniformly at
  random from $\{\ket{0},\ket{1},\ket{+},\ket{-}\}$. Alternatively, it
  can be prepared by computing $H^hX^x \ket{0}$ where $X$ is the
  bit-flip gate, $H$ is the Hadamard gate, and $h,x\in\{0,1\}$ are
  random bits.}  Most notably, creating the states does not involve
creating or maintaining long-range correlations between qubits.

In turn, plugging our OT protocol into the protocols
of \cite{C:IshPraSah08,EC:Unruh10,DNS12,EC:DGJMS20} (and using the sequential
composition theorem~\cite{HSS15}) gives us secure two-party computation
and multi-party computation (with a dishonest majority) protocols, even for
quantum channels.

\begin{theorem}[Informal]
  Assuming that post-quantum one-way functions exist and quantum communication
  is possible, for every
  classical two-party and multi-party functionality $\mathcal{F}$, there is
  a quantum protocol in the plain model that is simulation-secure
  against malicious quantum polynomial-time adversaries.
  Under the same assumptions, there is a quantum two-party and multi-party
  protocol for any
  quantum circuit $Q$.
\end{theorem}

Finally, we note that our OT protocol runs in $\mathsf{poly}(\secpar)$ number
of rounds, where $\secpar$ is a security parameter, and that is only because
of the zero-knowledge proof. Watrous' ZK proof system~\cite{Watrous09} involves
repeating a classical ZK proof (such as that graph coloring ZK proof~\cite{C:GolMicWig86}
or the Hamiltonicity proof~\cite{Blum86}) {\em sequentially}. A recent work
of Bitansky and Shmueli~\cite{STOC:BitShm20} for the first time constructs a
{\em constant-round} quantum ZK protocol (using only classical resources) but
they rely on a strong assumption, namely learning with errors, which
 does not
live in minicrypt. Nevertheless, in the common random string (CRS) model,
we can instantiate the zero-knowledge protocol using a WI protocol and a Pseudo-Random Generator (PRG) with additive $\lambda$ bit stretch as follows: To prove a statement $x$, the prover proves using the WI protocol that either $x$ is in the language or the common random string is in the image of the PRG. To simulate a proof, the simulator samples the CRS as a random image of the PRG, and proves using the WI protocol that it belongs to the image in a straight-line.
Moreover, this modification allows us to achieve {\em straight-line simulators}, leading to {\em universally-composable} (UC) security~\cite{Can01}.
Therefore, this
modification would give us the following statement.

\begin{theorem}[Informal]
  Constant-round oblivious transfer protocols in the common random string (CRS) model that are  UC-simulation-secure
  against malicious quantum poly-time adversaries
  exist assuming that post-quantum one-way functions exist and that quantum communication is possible.
\end{theorem}
Plugging the above UC-simulation-secure OT into the protocol of~\cite{C:IshPraSah08} gives constant-round multi-party computation protocols for classical computation in the common random string model that are UC-simulation-secure against malicious quantum poly-time adversaries.
\rachel{Rachel: 11/29 added the above sentence for constant round pq MPC.}

  %
  %

\rnotem{if ZK in the CRS model from OWF works, which is simply PRG in
  CRS + WI, we can write two theorems, one in the plain model and
  anohter in the CRS model}

\agnotem{Maybe we should sell our result a bit more here}

\paragraph{Going Below MiniQCrypt?}
We notice that all of the primitives that we implement in our work {\em cannot} be implemented unconditionally, even in the quantum setting~\cite{Mayers97,LoChau97,Lo97,CGS16}. Basing their construction on pqOWF{}s seems to be the next best thing, but it does leave with the intriguing question if they could be based on weaker assumptions.
More concretely, assume a world with quantum communication as we do in this paper. Does the existence of quantum OT protocols imply the existence of pqOWF{}s? Or, does a weaker {\em quantum} notion of one-way functions suffice? We leave the exploration of other possible cryptographic worlds below MiniQCrypt to future work.

\paragraph{Other Related Work.}
Inspired by the quantum OT protocol~\cite{C:BBCS91}, a family of
primitives, named \emph{$k$-bit cut-and-choose}, has been shown to be
sufficient to realize OT statistically by quantum
protocols~\cite{FKSZZ13,DFLS16} which is provably impossible by
classical protocols alone~\cite{MPR10}. These offer further examples
demonstrating the power of quantum cryptographic protocols.

There has also been extensive effort on designing quantum protocols OT
and the closely related primitive of \emph{one-time-memories} under
\emph{physical} rather than \emph{computational} assumptions, such as
the bounded-storage model, noisy-storage model, and isolated-qubit
model, which restrict the quantum memory or admissible operations of
the
adversary~\cite{Salvail98,Liu14_itcs,Liu14_crypto,DFR+07,DFSS08,KWW12}. They
provide important alternatives, but the composability of these
protocols are not well understood. Meanwhile, there is strengthening
on the impossibility for quantum protocols to realize secure
computation statistically from scratch~\cite{BCS12,SSS15}.

Finally, we note that there exist classical protocols for two-party
and multi-party computation that are quantum-secure assuming strong
assumptions such as post-quantum dense encryption and superpolynomial
quantum hardness of the learning-with-errors
problem~\cite{HSS15,LN11,ABGKM20}. And prior to the result
in~\cite{EC:DGJMS20}, there is a long line of work on secure multi-party
\emph{quantum} computation (Cf.~\cite{CGS02,BCGHS06,DNS10,DNS12}).

\subsection{Technical Overview}
\label{sec:technical}

We give an overview of our construction of post-quantum OT protocol in
the plain model from post-quantum one-way functions.
In this overview, we assume some familiarity with post-quantum MPC in the
stand-alone, sequential composition, and UC models, and basic
functionalities such as $\funct{\ot}$ and $\funct{\com}$.  We will also consider
{\em parallel versions} of them, denoted as $\funct{\pot}$ and $\funct{\socom}$. The
parallel OT functionality $\funct{\pot}$ enables the sender to send some
polynomial number of pairs of strings $\smallset{s^i_0, s^i_1}_i$ and the receiver to choose one per pair to obtain
$s^i_{c_i}$ in
parallel. The commitment with selective opening functionality
$\funct{\socom}$ enables a sender to commit to a string $m$ while hiding it,
and a receiver to request opening of a subset of bits at locations
$T \subseteq[|m|]$ and obtain $m_T = (m_i)_{i \in T}$. We
refer the reader to Section~\ref{sec:model} for formal definitions of
these functionalities.

\paragraph{BBCS OT in the $\funct{\socom}$-Hybrid Model.} We start by
describing the
quantum OT protocol of \cite{C:BBCS91} in the $\funct{\socom}$ hybrid model.

\begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
  \small
{\bf BBCS OT protocol:} The sender $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}$ has strings $s_0,s_1 \in \{0,1\}^\ell$, the receiver
$\otR$ has a choice bit $c \in \{0,1\}$.
\begin{enumerate}
\item {\bf Preamble.} $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}$ sends $n \gg \ell$ BB94 qubits
  $\ket{x^A}_{ \theta^A}$ prepared using random bits
  $ x^A\in_R \{0,1\}^n$ and random basis
  $ \theta^A\in_R \{+,\times\}^n$.

  $\otR$ measures these qubits in randomly chosen bases
  $ \theta^B\in_R \{+,\times\}^n$ and commits to the measured bits
  together with the choice of the bases, that is $\smallset{ \theta_i^B,  x_i^B}_i$,
  using
  $\funct{\socom}$.

\item {\bf Cut and Choose.}  $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}$ requests to open a random
  subset $T$ of locations, of size say $n/2$, and
  gets $\{  \theta_i^B,  x_i^B\}_{i\in T}$ from
  $\funct{\socom}$.

  Importantly, it aborts if for any $i$
  $\theta^B_i = \theta^A_i$ but
  $ x^B_i\neq  x^A_i$. Roughly speaking, this is because it's
  an indication that the receiver has not reported honest
  measurement outcomes.

  %
  %
  %
  %

\item {\bf Partition Index Set.}  $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}$ reveals
  ${\theta}^A_{\bar T}$ for the unchecked locations $\bar T$. $\otR$ partitions $\bar T$ into a subset of locations where it
  measured in the same bases as the sender
  $I_c := \{i \in \bar T: {\theta}_i^A ={\theta}_i^B\}$ and
  the rest $I_{1-c} := \bar T - I_c$, and sends $(I_0, I_1)$ to the sender.
    %

\item {\bf Secret Transferring}. $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}$ hides the two strings
  $s_i$ for $i = 0, 1$ using randomness extracted from
  $ x^A_{I_i}$ via a universal hash function $f$ and sends
  $m_i := s_i \oplus f( x^A_{I_i})$, from which $\otR$
  recovers $s := m_c \oplus f( x^B_{I_c})$.

\end{enumerate}
\end{mdframed}

Correctness follows from that for every $i\in I_c$, $\theta_i^A = \theta_i^B$ and
  $x^A_{I_c} = x^B_{I_c}$, hence the receiver decodes
  $s_c$ correctly.

The security of the BBCS OT protocol relies crucially on two important
properties of the $\funct{\socom}$ commitments, namely extractability and
equivocability, which any protocol implementing the $\funct{\socom}$ functionality must
satisfy.

\medskip
\noindent\highlight{Equivocability:} To show the receiver's privacy, we need
  to efficiently simulate the execution with a malicious sender
  $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}^*$ without knowing the choice bit $c$ and extract both
  sender's strings $s_0, s_1$. To do so, the simulator $\mathsf{ot.SimS}$ would
  like to measure at these unchecked locations $\bar T$ using exactly
  the same bases $\theta^A_{\bar T}$ as $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}^*$ sends in Step 3. In
  an honest execution, this is impossible as the receiver must commit
  to its bases $\theta^B$ and pass the cut-and-choose step. However,
  in simulation, this can be done by invoking the equivocability of
  $\funct{\socom}$. In particular, $\mathsf{ot.SimS}$ can {\em simulate} the
  receiver's commitments in
  the preamble phase without committing to any value. When it is
  challenged to open locations at $T$, it measures qubits at $T$ in
  random bases, and {\em equivocates} commitments at $T$ to the
  measured outcomes and bases. Only after $\mathsf{ot.S}} \newcommand{\otR}{\mathsf{ot.R}^*$ reveals its bases
  $\theta^A_{\bar T}$ for the unchecked locations, does $\mathsf{ot.SimS}$
  measure qubits at $\bar T$ in exactly these bases. This ensures that
  it learns both $x^A_{I_0}$ and $x^A_{I_1}$ and hence can recover
  both $s_0$ and $s_1$.

  \smallskip
\noindent\highlight{Extractability:} To show the sender's privacy, we need to
  efficiently extract the choice bit $c$ from a malicious receiver
  $\otR^*$ and simulate the sender's messages using only
  $s_c$. To do so, the simulator $\mathsf{ot.SimR}$ needs to extract
  efficiently from the $\funct{\socom}$ commitments all the bases $\theta^B$,
  so that, later given $I_0, I_1$ it can figure out which subset $I_c$
  contains more locations $i$ where the bases match
  $\theta^B_i=\theta^A_i$, and use the index of that set as the
  extracted choice bit. Observe that it is important that extraction
  does not ``disturb'' the quantum state of $\otR^*$ at all, so that
  $\mathsf{ot.SimR}$ can continue simulation with $\otR^*$. This is easily
  achieved using $\funct{\socom}$ as extraction is done in a straight-line
  fashion, but challenging to achieve in the plain model as rewinding
  a quantum adversary is tricky. Indeed, the argument of knowledge
  protocol of~\cite{EC:Unruh12} can extract a witness but disturbs the
  state of the quantum adversary due to measurement. To the best of
  our knowledge, such strong extractable commitment is only known
  assuming post-quantum FHE in the
  plain model~\cite{STOC:BitShm20,AnaPla19}\agnotem{Is the second citation the one you meant?}
  using non-black-box simulation techniques, or assuming public key
  encryption in the CRS model.
\medskip

It turns out that equivocability {\em can} be achieved
using zero-knowledge protocols, which gives a post-quantum OT protocol
with an inefficient simulator $\mathsf{ot.SimR}$ against malicious receivers
(and efficient $\mathsf{ot.SimS}$). Our main technical contribution lies in
achieving efficient extractability while assuming only post-quantum one-way
functions. In particular, we will use the OT with unbounded simulation
as a tool for this. We proceed to describing these steps in more detail.

\paragraph{Achieving Equivocability Using Zero-Knowledge.} The idea is
to let the committer commit $c = \text{\tt com}(\mu; \rho)$ to a string
$\mu \in \{0,1\}^n$ using any statistically binding computationally hiding commitment scheme
$\text{\tt com}$ whose decommitment can be verified classically, for instance, Naor's commitment scheme~\cite{C:Naor89} from post-quantum one-way functions. For now in this overview, think of $\text{\tt com}$ as non-interactive.
(Jumping ahead, later we will also instantiate this commitment with a multi-round extractable commitment scheme that we construct.)

Any computationally hiding commitment can be simulated by simply committing to zero,
$\tilde c = \text{\tt com}(0; \rho)$. The question is how to equivocate
$\tilde c$ to any string $\mu'$ later in the decommitment phase.
With a
post-quantum ZK protocol, instead of asking the committer to reveal
its randomness $\rho$ which would statistically bind $\tilde c$ to the
zero string, we can ask the committer to send $\mu'$ and give a
zero-knowledge proof that $\tilde c$ indeed commits to $\mu'$. As such,
the simulator can cheat and successfully open to any value $\mu'$ by
simulating the zero-knowledge argument to the receiver.

\begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
  \small
{\bf Equivocable Commitment:} The sender $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}$ has a string $\mu \in \{0,1\}^n$, the receiver
$\comR$ has a subset $T \subseteq [n]$.
\begin{enumerate}
\item {\bf Commit Phase.} $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}$ commits to $\mu$ using a statistically
  binding commitment scheme $\text{\tt com}$ using randomness $\rho$. Let $c$ be
  the produced commitment.

  \Note{Simulation against malicious receivers commits to $0^n$.
    Simulation against malicious senders is inefficient to extract
    $\mu$ by brute force.}

\item {\bf Decommit Phase.}  Upon $\comR$ requesting to open a subset
  $T$ of locations, $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}$ sends $\mu'$ and gives a single zero
  knowledge argument that $c$ commits to $\mu$ such that $\mu' = \mu_T$.

  \Note{To equivocate to $\mu' \neq \mu_T$, the simulator sends $\mu'$ and
    simulates the zero-knowledge argument (of the false statement).}
\end{enumerate}
\end{mdframed}
The above commitment protocol implements $\funct{\socom}$ with efficient
simulation against malicious receivers, but inefficient simulation
against malicious senders. Plugging it into BBCS OT protocol, we
obtain the following corollary:
\begin{corollary}[Informal]
  Assume post-quantum one-way functions. In the plain model, there is:
  \begin{itemize}
  \item a protocol that securely implements the OT functionality $\funct{\ot}$, and
  \item a protocol that securely implements the parallel OT
    functionality $\funct{\pot}$,
\end{itemize}
in the sequential composition setting, and with efficient
simulation against malicious senders but inefficient simulation
against malicious receivers. \rnotem{CRS model}
\end{corollary}
The second bullet requires some additional steps, as parallel
composition does not automatically apply in the stand-alone  (as opposed to UC) setting
(e.g., the ZK protocol of~\cite{Watrous09} is not
simulatable in parallel due to rewinding). Instead, we first observe that the BBCS OT
UC-implements $\funct{\ot}$ in the $\funct{\socom}$ hybrid model, and hence parallel
invocation of BBCS OT UC-implements $\funct{\pot}$ in the $\funct{\socom}$ hybrid
model. Note that parallel invocation of BBCS OT invokes $\funct{\socom}$ in
parallel, which in fact can be merged into a single invocation to
$\funct{\socom}$.
 Therefore,
plugging in the above commitment protocol gives an OT protocol that
implements $\funct{\pot}$. In particular, digging deeper into the protocol, this ensures that
we are invoking a {\em single} ZK protocol for all the parallel copies of the parallel OT, binding
the executions together.

\paragraph{Achieving Extractability Using OT with Unbounded
  Simulation.} Interestingly, we show that OT with (even 2-sided)
unbounded simulation plus zero-knowledge is sufficient for
constructing extractable commitments, which when combined with
zero-knowlege again as above gives an implementation of $\funct{\socom}$ in
the sequential composition setting in the plain model.

The initial idea is to convert the power of simulation into the power
of extraction via two-party computation, and
sketched below. \vnotem{The ref here is probably wrong.}\rnotem{let's just not cite.}
\begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
  \small
{\bf Initial Idea for Extractable Commitment:} The sender $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}$ has $\mu \in \{0,1\}^n$.

\begin{enumerate}
\item {\bf Trapdoor setup:}
  The receiver $\comR$ sends a commitment $c$ of a statistically
  binding commitment scheme $\text{\tt com}$, and gives a zero-knowledge proof
  that $c$ commits to 0.

  %
  %

\item {\bf Conditional Disclosure of Secret (CDS):}
  $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}$ and $\comR$ run a two-party computation protocol implementing
  the CDS functionality $\funct{\cds}$ for the language
  $\mathcal{L}_\text{\tt com} = \smallset{(c', b') : \exists r' \text{ s.t. } c' =
    \text{\tt com}(b'; r')}$, where the CDS functionality $\funct{\cds}$ for $\mathcal{L}_\text{\tt com}$ is defined as below:
  \begin{align*}
    \funct{\cds} \ :&  \text{ Sender input } (x, \mu), \text{ Receiver
    input } w\\
  & \text{ Sender has no output}, \text{Receiver outputs } x \mbox{ and } \mu'
                                     =\begin{cases}
                                       \mu & \mbox{if } \mathcal{R}_{\mathcal{L}_\text{\tt com}}(x, w) = 1\\
                                       \perp & \text{otherwise}
                                     \end{cases}
  \end{align*}
  $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}$ acts as the CDS sender using
  input $(x=(c, 1), \mu)$ while $\comR$ acts as the CDS receiver using
  witness $w = 0$.
  %
  %
  %
\end{enumerate}
\end{mdframed}
It may seem paradoxical that we try to implement commitments using the
much more powerful tool of two-party computation. The {\em key observation} is
that the hiding and extractability of the above commitment protocol
 only relies on the {\em input-indistinguishability property} of the CDS
protocol, which is {\em implied by unbounded simulation}.
\begin{itemize}
\item \highlight{Hiding:} A commitment to $\mu$ can be simulated by
  simply commiting to $0^n$ honestly, that is, using $(x=(c, 1), 0^n)$
  as the input to the CDS. The simulation is
  indistinguishable as the soundness of ZK argument guarantees that $c$
  must be a commitment to $0$ and hence the CDS statement $(c, 1)$ is
  false and should always produce $\mu' = \bot$. Therefore, the
  unbounded-simulation security of the CDS protocol implies that it is
  indistinguishable to switch the sender's input from $\mu$ to $0^n$.

\item \highlight{Extraction:} To efficiently extract from a malicious
  sender $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}^*$, the idea (which however suffers from a problem
  described below) is to let the simulator-extractor $\mathsf{com.SimS}$ set
  up a trapdoor by committing to 1 (instead of 0) and simulate the ZK
  argument; it can then use the decommitment (call it $r$) to 1 as a valid witness
  to obtain the committed value from the output of the CDS
  protocol. Here, the unbounded-simulation security of CDS again
  implies that interaction with an honest receiver who uses $w = 0$ is
  indistinguishable from that with $\mathsf{com.SimS}$ who uses $w = r$ as
  $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}^*$ receives no output via CDS.
\end{itemize}
The advantage of CDS with unbounded simulation is that it can be
implemented using OT with unbounded simulation: Following the work
of~\cite{STOC:Kilian88,C:IshPraSah08,EC:Unruh10}, post-quantum MPC protocols exist in the
$\funct{\ot}$-hybrid model, and instantiating them with the unbounded-simulation
OT yields unbounded simulation MPC and therefore CDS.

\subparagraph{NP-Verifiability and the Lack of It.} Unfortunately, the above
attempt  has several problems: how do we show that the commitment is binding?
how to decommit? and how to guarantee that the extracted value agrees
with the value that can be decommitted to? %
We can achieve binding by having the sender additionally commit to
$\mu$ using a statistically binding commitment scheme $\text{\tt com}$, and send
the corresponding decommitment in the decommitment phase. However, to
guarantee that the extractor would extract the same string $\mu$ from
CDS, we need a way to verify that the same $\mu$ is indeed used by the CDS
sender.
Towards this, we formalize a verifiability property of a CDS protocol:

\smallskip\noindent{\em A CDS protocol is verifiable if}\vspace{-1mm}
\begin{itemize}
\item The honest CDS sender $\mathsf{cds.S}$ additionally outputs $(x,\mu)$ and a
  ``proof'' $\pi$ (on a special output tape) at the end of the execution.
\item There is an efficient {\em classical} verification algorithm
  $\mathsf{Ver}(\tau, x,\mu, \pi)$ that verifies the proof, w.r.t.\ the
  transcript $\tau$ of the {\em classical} messages exchanged in the CDS protocol.
\item \highlight{Binding:} No malicious sender $\mathsf{cds.S}^*$ after
  interacting with an honest receiver $\mathsf{cds.R}(w)$ can output
  $(x,\mu,\pi)$, such that the following holds simultaneously: (a)
  $\mathsf{Ver}(\tau, x, \mu, \pi) = 1$, (b) $\mathsf{cds.R}$ did not abort, and (c)
  $\mathsf{cds.R}$ outputs $\mu'$ inconsistent with the inputs $(x,\mu)$ and $w$,
  that is,
$      \mu' \ne
      \begin{cases}
        \mu & \text{ if } \mathcal{R}_\mathcal{L}(x, w) = 1  \\
        \bot & \text{ otherwise }
      \end{cases}
$
\end{itemize}

We observe first that classical protocols with perfect correctness have
verifiability for free: The proof $\pi$ is simply the sender's
random coins $r$, and the verification checks if the honest sender
algorithm with input $(x, \mu)$ and random coins $r$ produces the same
messages as in the transcript $\tau$. If so, perfect correctness
guarantees that the output of the receiver must be consistent with
$x, \mu$. However, verifiability cannot be taken for granted in the
$\funct{\ot}$ hybrid model or in the quantum setting. In the $\funct{\ot}$ hybrid
model, it is difficult to write down an NP-statement that captures
consistency as the OT input is {\em not} contained in the protocol
transcript and is unconstrained by it. In the quantum setting,
protocols use quantum communication, and consistency cannot be
expressed as an NP-statement.  %
Take the BBCS protocol as an example, the OT receiver receives from
the sender $\ell$ qubits and measures them locally; there is no way to
"verify" this step in NP.

\paragraph{Implementing Verifiable CDS.} To overcome the above
challenge, we implement a verifiable CDS protocol in the $\funct{\pot}$
hybrid model assuming only post-quantum one-way functions. We develop
this protocol in a few steps below.

Let's start by understanding why the standard two-party comptuation
protocol is not verifiable. The protocol proceeds as follows:
First, the sender $\mathsf{cds.S}$ locally garbles a circuit computing the
following function into $\hat G$ with labels
$\smallset{\ell^j_b}_{j \in [m], b\in\{0,1\}}$ where $m = |w|$.
\begin{align}
  G_{x,\mu}(w) =  \mu' = \begin{cases}
    \mu & \text{ if } \mathcal{R}_\mathcal{L}(x, w) = 1  \\
    \bot & \text{ otherwise }
  \end{cases}
  \label{eq:G}
\end{align}
Second, $\mathsf{cds.S}$ sends the pairs of labels $\smallset{\ell^j_0, \ell^j_1}_j$
via $\funct{\pot}$. The receiver $\mathsf{cds.R}$ on the other hand chooses $\smallset{w_j}_{j}$ to
obtain $\smallset{\tilde \ell^j_{w_j}}_j$, and  evaluates
$\hat G$ with these labels to obtain $\mu'$.  This protocol is not
NP-verifiable because consistency between the labels of the garbled
circuit and the sender's inputs to $\funct{\pot}$ cannot be expressed as a NP
statement.

To fix the problem, we devise a way for the receiver to verify the OT
sender's strings. Let $\mathsf{cds.S}$ additionally commit to all the labels
$\smallset{c_b^j = \text{\tt com}(\ell^j_b ; r^j_b)}_{j,b}$ and the message
$c = \text{\tt com}(\mu; r)$ and prove in ZK that $\hat G$ is consistent with the labels and message committed in
the commitments, as well as the statement $x$. Moreover, the sender sends both
the labels and decommitments
$\smallset{(\ell^j_0, r^j_0),(\ell^j_1, r^j_1)}_j$ via $\funct{\pot}$.
The receiver after receiving
$\smallset{\tilde \ell^j_{w_j}, \tilde r^j_{w_j}}_j$ can now verify
their correctness by verifying the decommitment w.r.t.\ $c_{w_j}^j$,
and aborts if verification fails. This gives the following new
protocol:

\begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
  \small
{\bf A Verifiable but Insecure CDS Protocol:} The sender $\mathsf{cds.S}$ has
$(x, \mu)$ and the receiver $\mathsf{cds.R}$ has $w$.

\begin{enumerate}
\item {\bf Sender's Local Preparation:} $\mathsf{cds.S}$ generate a
  garbled circuits $\hat G$ for the
  circuit computing $G_{x,\mu}$ (Equation~\eqref{eq:G}), with labels
  $\smallset{\ell^{i,j}_b}_{j, b}$. Moreover, it generates commitments $c = \text{\tt com}(\mu, r)$ and
$c^{j}_b = \text{\tt com}(\ell^{j}_b; r^{j}_b)$ for every $j,b$.

\item {\bf OT:} $\mathsf{cds.S}$ and $\mathsf{cds.R}$ invoke $\funct{\pot}$. For every $j$, the
  sender sends $(\ell^{j}_0, r^{j}_0), (\ell^{j}_1, r^{j}_1)$, and the
  receiver chooses $w_j$ and obtains
  $(\tilde \ell^{j}_{w_{j}}, \tilde r^{j}_{w_{j}})$.

  %
  %
\item {\bf Send Garbled Circuit and Commitments:} $\mathsf{cds.S}$ sends
  $\hat G$, $c$, and $\smallset{c^j_b}_{j,b}$ and proves via a ZK
  protocol that they are all generated consistently w.r.t.\ each other
  and $x$.

\item {\bf Receiver's Checks:} $\mathsf{cds.R}$ aborts if ZK is not accepting,
  or if for some $j$,
  $c^j_{w_j} \ne \text{\tt com}(\tilde \ell^{j}_{w_{j}}, \tilde
  r^{j}_{w_{j}})$. Otherwise, it evaluates $\hat G$ with the labels
  and obtain $\mu' = G_{x,\mu}(w)$.
\end{enumerate}
\end{mdframed}
We argue that this protocol is NP-verifiable. The sender's proof
is simply the decommitment $r$ of $c$, and
$\mathsf{Ver}(\tau, (x, \mu), r) = 1$ iff $r$ is a valid decommitment to $\mu$ of the commitment $c$ contained
in the transcript $\tau$. To show the binding property, consider an
interaction between a cheating sender $\mathsf{cds.S}^*$ and
$\mathsf{cds.R}(w)$. Suppose $\mathsf{cds.R}$ does not abort, it means that 1) the ZK
argument is accepting and hence $\hat G$ must be consistent with
$x, \smallset{c_b^j}, c$, and 2) the receiver obtains the labels
committed in $c_{w_j}^j$'s. Therefore, evaluating the garbled circuit
with these labels must produce $\mu'= G_{x,\mu}(w)$ for the $\mu$
committed to in $c$.

Unfortunately, the checks that the receiver performs render the protocol
insecure. A malicious sender $\mathsf{com.S}} \newcommand{\comR}{\mathsf{com.R}^*$ can launch the so-called
selective abort attack to learn information of $w$. For instance, to
test if $w_1 = 0$ or not, it replaces $\ell^1_0$ with
zeros.  If $w_1 = 0$ the honest receiver would abort; otherwise, it
proceeds normally.

\subparagraph{The Final Protocol} To circumvent the selective abort
attack, we need a way to check the validity of sender's strings that
is independent of $w$. Our idea is to use a variant of cut-and-choose. Let $\mathsf{cds.S}$
create $2\lambda$ copies of garbled circuits and commitments to their
labels, $\smallset{\hat G^i}_{i \in [2\lambda]}$ and
$\smallset{c^{i,j}_b = \text{\tt com}(\ell^{i,j}_b; r^{i,j}_b)}_{i,j,b}$ and
prove via a ZK protocol that they are all correctly generated w.r.t.\
the same $c$ and $x$. Again, $\mathsf{cds.S}$ sends the labels and decommitment
via $\funct{\pot}$, but $\mathsf{cds.R}$ does not choose $w$ universally in all
copies. Instead, it secretly samples a random subset
$\Lambda \in [2\lambda]$ by including each $i$ with probability 1/2; for
copy $i \in \Lambda$, it chooses random string $s^i \gets \{0,1\}^m$ and obtains $\smallset{\tilde \ell^{i,j}_{s^i_j}, \tilde r^{i,j}_{s^i_j}}_j$,
whereas for copy $i \not \in \Lambda$, it choose $w$ and obtains $\smallset{\tilde \ell^{i,j}_{w_j}, \tilde r^{i,j}_{w_j}}_j$.  Now, in the
checking step, $\mathsf{cds.R}$ only verifies the validity of $\smallset{\tilde \ell^{i,j}_{s^i_j}, \tilde r^{i,j}_{s^i_j}}_{i \in \Lambda, j}$  received in copies in $\Lambda$. Since the check is
now completely independent of $w$, it circumvents the selective abort attack.

Furthermore, NP-verifiability still holds. The key point is that if
the decommitments $\mathsf{cds.R}$ receives in copies in $\Lambda$ are all
valid, with overwhelming probability, the number of {\em bad copies}
where the OT sender's strings are not completely valid is bounded by
$\lambda/4$. Hence, there must exist a copy $i \not\in \Lambda$ where
$\mathsf{cds.R}$ receives the right labels $\ell^{i,j}_{w_j}$ committed to in
$c^{i,j}_{w_j}$. $\mathsf{cds.R}$ can then evaluate $\hat G^i$ to obtain
$\mu'$. By the same argument as above, $\mu'$ must be consistent with
the $(x,\mu)$ and $w$, for $\mu$ committed in $c$, and
NP-verifiability follows. The final protocol is described in Figure~\ref{fig:cdsprot}.

\rachelm{Another angle is what is the right primitive for defining minicrypt for qcrypt? Is it classical OWF or something weaker?}
\vnotem{Good question. I think it depends on what we can prove :) We could have miniQcrypt (quantum OWF with quantum input/output -- is this well-defined -- or microQcrypt (quantum OWF with classical input/output) or nanoQcrypt (classical OWF)}\agnotem{I am not sure if we should not invert the definitions of mini/micro/nano... Intuitively, it seems that it is easier to have a OWF with quantum input/outputs... The point is that they might be incomparable}

\iffalse
\begin{figure}[!ht]
\centering
\[
  \begin{matrix}
& \ovalbox{$\text{\tt p-ot}^*$} &
\overset{\text{Theorem~\ref{thm:vercds}}}{\underset{\text{C}}\longrightarrow}
& \ovalbox{$\mathsf{cds}$}
&\overset{\text{Theorem~\ref{thm:ecom}}}{\underset{\text{C}}\longrightarrow}
& \ovalbox{$\text{\tt so-com}$} & \\
\text{\footnotesize C, Theorem~\ref{thm:pot}} & \big\uparrow & & & &
\big\downarrow & \text{\footnotesize Q, Theorem~\ref{thm:ot}} \\
& \ovalbox{$\text{\tt ot}^*$} & & & & \ovalbox{$\text{\tt ot}$} & \\
\text{\footnotesize Q, Theorem~\ref{thm:ot}} & \big\uparrow & & & &
\big\downarrow & \text{\footnotesize C, Theorem~\ref{thm:mpc} }\\
& \ovalbox{$\text{\tt so-com}^*$} & & & & \ovalbox{$\mathsf{pqMPC}$} & \\
\text{\footnotesize C, Theorem~\ref{thm:socom}} & \big\uparrow & & & &
\big\downarrow & \text{\footnotesize Q, Theorem~\ref{thm:mpqc}} \\
& \ovalbox{$\mathsf{pqOWF}$} &&\Longrightarrow&& \ovalbox{$\mathsf{qMPC}$} &
\end{matrix}
\]
\label{fig:diagram}
\caption{Road map of the constructions. ``C/Q'' indicates if the protocol
  is classical or quantum respectively. ``*'' indicates secure
  emulation with unbounded simulation on one side. The top line bears
  our main contributions.}
\end{figure}

\begin{figure}[!ht]
\centering
\[
  \begin{matrix}
& \ovalbox{$\text{\tt p-ot}^*$} &
\overset{\text{\Cref{sec:cdsprot}}}{\underset{\text{C}}\longrightarrow}
& \ovalbox{$\mathsf{cds}$}
&\overset{\text{\Cref{sec:cds-to-extcom}}}{\underset{\text{C}}\longrightarrow}
& \ovalbox{$\text{\tt so-com}$} & \\
\text{\footnotesize C, \Cref{sec:parallel-composition}} & \big\uparrow & & & &
\big\downarrow & \text{\footnotesize Q, \Cref{sec:qot}} \\
& \ovalbox{$\text{\tt ot}^*$} & & & & \ovalbox{$\text{\tt ot}$} & \\
\text{\footnotesize Q, \Cref{sec:qot}} & \big\uparrow & & & &
\big\downarrow & \text{\footnotesize C, \Cref{sec:mpc} }\\
& \ovalbox{$\text{\tt so-com}^*$} & & & & \ovalbox{$\mathsf{pqMPC}$} & \\
\text{\footnotesize C, \Cref{sec:socom}} & \big\uparrow & & & &
\big\downarrow & \text{\footnotesize Q, \Cref{sec:mpc}} \\
& \ovalbox{$\mathsf{pqOWF}$} &&\Longrightarrow&& \ovalbox{$\mathsf{qMPC}$} &
\end{matrix}
\]
\caption{Road map of the constructions. ``C/Q'' indicates if the protocol
  is classical or quantum respectively. ``*'' indicates secure
  emulation with unbounded simulation on one side. The top line bears
  our main contributions.
  }
\label{fig:diagram}
\end{figure}
\fi

\subsubsection{Organization of the Paper.}
We review the quantum stand-alone security model introduced by \cite{HSS15} in \Cref{sec:model}. In section~\Cref{sec:parallel-ot}, we construct a quantum parallel-OT protocol with one-sided, unbounded simulation. In more detail, we review in \Cref{sec:qot}  the quantum OT protocol from \cite{C:BBCS91} based on ideal commitments with selective opening security. Then in \Cref{sec:parallel-composition}, we show how to boost it to construct a {\em parallel} OT protocol from the same assumptions. And finally, we provide a classical implementation of the commitment scheme with selective opening security in \Cref{sec:socom} which gives us ideal/real security except with unbounded receiver simulation. This result will be fed into our main technical contribution in \Cref{sec:ecom} where we show how to construct extractable commitments from unbounded-simulation parallel-OT. In \Cref{sec:cdsprot}, we show how to construct (the intermediate primitive of) CDS from parallel-OT and one-way functions, and then in \Cref{sec:cds-to-extcom} we construct extractable commitments from CDS.
Finally, in \Cref{sec:mpc} we lift our results to achieve quantum protocols for multi-party (quantum) computation from one-way functions.

Throughout work, we assume familiarity with  basic notions in quantum computation and cryptography. For completeness,  we provide a brief review on the relevant concepts in~\Cref{sec:prelim}.

\section{Quantum Stand-alone Security Model}
\label{sec:model}

We adopt the quantum stand-alone security model from the work of Hallgren, Smith and Song~\cite{HSS15}, tailored to the two-party setting.

Let $\mathcal{F}$ denote a \emph{functionality}, which is a
classical \vnotem{``or quantum'': do we need it? aren't all our $\mathcal{F}$ classical?} interactive machine specifying the instructions
to realize a cryptographic task. A two-party protocol $\Pi$ consists
of a pair of quantum interactive machines $(A,B)$. We call a protocol
{\em efficient} if $A$ and $B$ are both quantum poly-time machines. If we want to
emphasize that a protocol is classical, i.e., all computation and all
messages exchanged are classical, we then use lower-case letters
(e.g., $\pi$). Finally, an adversary $\adv$ is another quantum interactive
machine that intends to attack a protocol.

When a protocol $\Pi=(A,B)$ is executed under the presence of an
adversary $\adv$, the state registers are initialized by a security
parameter $1^\secpar$ and a joint quantum state $\sigma_\secpar$.
Adversary $\adv$ gets activated first, and may either \textbf{deliver}
a message, i.e., instructing some party to read the proper segment of
the network register, or \textbf{corrupt} a party. We assume all
registers are authenticated so that $\adv$ cannot modify them, but
otherwise $\adv$ can schedule the messages to be delivered in any
arbitrary way. If $\adv$ corrupts a party, the party passes all of its
internal state to $\adv$ and follows the instructions of $\adv$. Any
other party, once receiving a message from $\adv$, gets activated and
runs its machine. At the end of one round, some message is generated
on the network register. Adversary $\adv$ is activated again and
controls message delivery. At some round, the party generates some
output and terminates.

We view $\Pi$ and $\adv$ as a whole and model the composed system as
another QIM, call it $\mac_{\Pi, \adv}$. Then executing $\Pi$ in the
presence of $\adv$ is just running $\mac_{\Pi, \adv}$ on some input
state, which may be entangled with a reference system available to a
distighuisher.

\paragraph{Protocol emulation and secure realization of a
  functionality.} A secure protocol is supposed to ``emulate'' an
idealized protocol. Consider two protocols $\Pi$ and $\Gamma$, and let
$\mac_{\Pi,\adv}$ be the composed machine of $\Pi$ and an adversary
$\adv$, and $\mac_{\Gamma,\simulator}$ be that of $\Gamma$ and another
adversary $\simulator$. Informally, $\Pi$ emulates $\Gamma$ if the two
machines $\mac_{\Pi,\adv}$ and $\mac_{\Gamma,\simulator}$ are
indistinguishable.

Given the general form of protocol emulation, it is of particular
interest to emulate the so-called \emph{ideal-world} protocol
$\tilde \Pi_\mathcal{F}$ for a functionality $\mathcal{F}$ which captures the
security properties we desire. In this protocol, two (dummy) parties
$\tilde A$ and $\tilde B$ have access to an additional ``trusted''
party that implements $\mathcal{F}$. We abuse notation and call the trusted
party $\mathcal{F}$ too. Basically $\tilde A$ and $\tilde B$ invoke $\mathcal{F}$
with their inputs, and then $\mathcal{F}$ runs on the inputs and sends the
respective outputs back to $\tilde A$ and $\tilde B$. An execution of
$\tilde \Pi$ with an adversary $\simulator$ is as before, except that
$\mathcal{F}$ cannot be corrupted. We denote the composed machine of $\mathcal{F}$
and $\tilde \Pi_\mathcal{F}$ as $\mac_{\mathcal{F}, \simulator}$.

\begin{definition}[Computationally Quantum-Stand-Alone Emulation]\label{def:cqsa}
  Let
  $\Pi$ and $\Gamma$ be two poly-time protocols. We say $\Pi$
  \emph{computationally quantum-stand-alone} (\text{\tt C-QSA}) emulates
  $\Gamma$, if for any poly-time QIM $\adv$ there exists a poly-time
  QIM $\mathcal{S}$ such that $\mac_{\Pi,\adv} \qc
    \mac_{\Gamma,\simulator} $.
\label{def:qcsa}
\end{definition}

\begin{definition}[\text{\tt C-QSA}~Realization of a Functionality] Let $\mathcal{F}$
  be a poly-time two-party functionality and $\Pi$ be a poly-time
  two-party protocol. We say $\Pi$ {\em computationally
    quantum-stand-alone} realizes $\mathcal{F}$, if $\Pi$ \text{\tt C-QSA}~emulates
  $\tilde \Pi_\mathcal{F}$. Namely, for any poly-time $\adv$, there is a
  poly-time $\simulator$ such that $\mac_{\Pi, \adv} \qc \mac_{\mathcal{F},
    \simulator}$.
\label{def:qsae}
\end{definition}

\vspace{-3ex}

\begin{figure}[ht!]
    \begin{center}
    \begin{tikzpicture}[scale=0.38,
        turn/.style={draw, minimum height=15mm, minimum width=10mm,
          fill = ChannelColor, text=ChannelTextColor},
        smallturn/.style={draw, minimum height=8mm, minimum width=8mm,
          fill = ChannelColor, text=ChannelTextColor},
        >=latex]
      \node (A) at (-8,0) [turn] {$\adv$};
      \node (B) [right of = A, xshift = 1cm, turn] {$B_\Pi$};
      \node (ina) [above of=A, yshift=1cm, minimum width = 0mm] {};
      \node (inb) [above of=B, yshift=1cm, minimum width = 0mm] {};
      \node (outa) [below of=A, yshift=-0.5cm, minimum width = 0mm] {};
      \node (outb) [below of=B, yshift=-0.5cm, minimum width = 0mm]
      {};
      \node (M) [above of = A, xshift = 1cm, yshift=2mm, minimum width = 0mm] {$M_{\Pi, \adv}$};
      \node (ML) [left of = A, xshift = 2cm, yshift = 0.3cm, draw, densely dotted, minimum height= 25 mm,
        minimum width = 3.6cm] {};
      \draw[<->] (A.east) -- (B.west) node {};
      \draw[->] (ina.south) -- (A.north) node {};
      \draw[->] (inb.south) -- (B.north) node {};
      \draw[->] (A.south) -- (outa.north) node {};
      \draw[->] (B.south) -- (outb.north) node {};

      \node (QC) [right of = B, xshift=.2cm] {$\qc$};

      \node (A2) [right of =QC, xshift = .2cm, turn] {$\simulator$};
      \node (B2) [right of = A2, xshift = 1cm, turn] {$B_\Gamma$};
      \node (ina2) [above of=A2, yshift=1cm, minimum width = 0mm] {};
      \node (inb2) [above of=B2, yshift=1cm, minimum width = 0mm] {};
      \node (outa2) [below of=A2, yshift=-0.5cm, minimum width = 0mm] {};
      \node (outb2) [below of=B2, yshift=-0.5cm, minimum width = 0mm]
      {};
      \node (M2) [above of = A2, xshift = 1cm, yshift=2mm, minimum width = 0mm] {$M_{\Gamma, \simulator}$};
      \node (ML2) [left of = A2, xshift = 2cm, yshift = 0.3cm, draw, densely dotted, minimum height= 25 mm,
        minimum width = 3.6cm] {};
      \draw[<->] (A2.east) -- (B2.west) node {};
      \draw[->] (ina2.south) -- (A2.north) node {};
      \draw[->] (inb2.south) -- (B2.north) node {};
      \draw[->] (A2.south) -- (outa2.north) node {};
      \draw[->] (B2.south) -- (outb2.north) node {};

      %
      \node (A3) at (-8,-12) [turn] {$\adv$};
      \node
      (B3) [right of = A3, xshift = 1cm, turn] {$B_\Pi$}; \node (ina3)
      [above of=A3, yshift=1cm, minimum width = 0mm] {}; \node (inb3)
      [above of=B3, yshift=1cm, minimum width = 0mm] {}; \node (outa3)
      [below of=A3, yshift=-0.5cm, minimum width = 0mm] {}; \node
      (outb3) [below of=B3, yshift=-0.5cm, minimum width = 0mm] {};
      \node (M3) [above of = A3, xshift = 1cm, yshift=2mm, minimum
      width = 0mm] {$M_{\Pi, \adv}$}; \node (ML3) [left of = A3,
      xshift = 2cm, yshift = 0.3cm, draw, densely dotted, minimum
      height= 25 mm, minimum width = 3.6cm] {}; \draw[<->] (A3.east)
      -- (B3.west) node {}; \draw[->] (ina3.south) -- (A3.north) node
      {}; \draw[->] (inb3.south) -- (B3.north) node {}; \draw[->]
      (A3.south) -- (outa3.north) node {}; \draw[->] (B3.south) --
      (outb3.north) node {};

      \node (QC2) [right of = B3, xshift=.2cm] {$\qc$};

      \node (A4) [right of =QC2, xshift = .2cm, turn] {$\simulator$};
      \node (B4) [right of = A4, xshift = 1cm, turn] {$\tilde B$};
      \node (ina4) [above of=A4, yshift=2cm, minimum width = 0mm] {};
      \node (inb4) [above of=B4, yshift=2cm, minimum width = 0mm] {};
      \node (outa4) [below of=A4, yshift=-0.5cm, minimum width = 0mm] {};
      \node (outb4) [below of=B4, yshift=-0.5cm, minimum width = 0mm]
      {};
      \node (F2) [above of = A4, xshift = 1cm, yshift=5mm, smallturn] {{\color{blue}$\mathcal{F}$}};
      \node (M4) [above of = F2, yshift=-2mm, minimum width = 0mm] {$M_{\mathcal{F}, \simulator}$};
      \node (ML4) [left of = A4, xshift = 2cm, yshift = 0.8cm, draw, densely dotted, minimum height= 35 mm,
        minimum width = 3.6cm] {};
      \draw[<->] (A4.east) -- (B4.west) node {};
      \draw[->] (ina4.south) -- (A4.north) node {};
      \draw[->] (inb4.south) -- (B4.north) node {};
      \draw[->] (A4.south) -- (outa4.north) node {};
      \draw[->] (B4.south) -- (outb4.north) node {};
      \draw[<->] ([yshift=12mm]A4.east) -- ([xshift=-5mm]F2.south) node
      {};
      \draw[<->] ([yshift=12mm]B4.west) -- ([xshift=5mm]F2.south) node {};

    \end{tikzpicture}
  \end{center}
\vspace{-2ex}
\caption{Quantum stand-alone emulation between protocols (above) and
  realization of a functionality (below).
  } \label{fig:emuprot}
\end{figure}

 \begin{definition}[Statistically Quantum-Stand-Alone Emulation] Let
   $\Pi$ and $\Gamma$ be two poly-time protocols. We say $\Pi$
   \emph{statistically quantum-stand-alone} (\text{\tt S-QSA}) emulates $\Gamma$,
   if for any QIM $\adv$ there exists an QIM $\simulator$ that runs in
   poly-time of that of $\adv$, such that
   $\mac_{\Pi, \adv} \dmm \mac_{\Gamma, \simulator}$.
 \label{def:qssa}
 \end{definition}

  We assume \emph{static} corruption only in this work, where the
  identities of corrupted parties are determined before protocol
  starts. The definitions above consider computationally bounded
  (poly-time) adversaries, including simulators. Occasionally, we will
  work with \emph{inefficient} simulators, which we formulate as
  unbounded simulation of corrupted party $P$.

  \begin{definition}[Unbounded Simulation of Corrupted $P$] Let $\Pi$
    and $\Gamma$ be two poly-time protocols. For any poly-time QIM
    $\adv$ corrupting party $P$, we say that $\Pi$ \text{\tt C-QSA}-emulates
    $\Gamma$ against corrupted $P$ with unbounded simulation, if there
    exists a QIM $\mathcal{S}$ possibly unbounded such that
    $ \mac_{\Pi,\adv} \qc \mac_{\Gamma,\simulator}$.
\label{def:uqcsa}
\end{definition}

\subsection{Modular Composition Theorem}
\label{sec:sacomposition}
It's shown that protocols satisfying the definitions of stand-alone
emulation admit a modular composition~\cite{HSS15}. Specifically, let
$\Pi$ be a protocol that uses another protocol $\Gamma$ as a
subroutine, and let $\Gamma'$ be a protocol that QSA emulates
$\Gamma$. We define the \emph{composed} protocol, denoted
$\cprot{\Pi}{\Gamma}{\Gamma'}$, to be the protocol in which each
invocation of $\Gamma$ is replaced by an invocation of $\Gamma'$. We
allow multiple calls to a subroutine and also using multiple
subroutines in a protocol $\Pi$. \textbf{However, quite importantly, we require that at any
point, only one subroutine call be in progress}. This is more
restrictive than the ``network'' setting, where many instances and
subroutines may be executed \emph{concurrently}.

In a \emph{hybrid} model, parties can make calls to an ideal-world
protocol $\tilde\Pi_{\funcG}$ of some functionality
$\funcG$\footnote{In contrast, we call it the \emph{plain model} if no
  such trusted set-ups are available.}. We call such a protocol a
\emph{$\funcG$-hybrid} protocol, and denote it $\Pi^{\funcG}$. The
execution of a hybrid-protocol in the presence of an adversary $\adv$
proceeds in the usual way. Assume that we have a protocol $\Gamma$
that realizes $\funcG$ and we have designed a $\funcG$-hybrid protocol
$\Pi^{\funcG}$ realizing another functionality $\mathcal{F}$. Then the
composition theorem allows us to treat sub-protocols as equivalent to
their ideal versions.

If the secure emulation involves unbounded simulation against a party,
the proof in~\cite{HSS15} can be extended to show that the composed
protocol also emulates  with unbounded simulation against
the corresponding corrupted party.

\begin{theorem}[Modular Composition] All of the following holds.
  \begin{itemize}
  \item Let $\Pi$, $\Gamma$ and $\Gamma'$ be two-party protocols such
    that $\Gamma'$ \text{\tt C-QSA}-emulates $\Gamma$, then
    $\cprot{\Pi}{\Gamma}{\Gamma'}$ \text{\tt C-QSA}~emulates
    $\Pi$. If $\Gamma'$ \text{\tt C-QSA}~emulates $\Gamma$ against corrupted $P$
    with unbounded simulation, then   $\cprot{\Pi}{\Gamma}{\Gamma'}$
    \text{\tt C-QSA}~emulates against corrupted $P$
    with unbounded simulation.

  \item Let $\mathcal{F}$ and $\funcG$ be poly-time functionalities. Let
    $\Pi^{\funcG}$ be a $\funcG$-hybrid protocol that \text{\tt C-QSA}~realizes
    $\mathcal{F}$, and $\Gamma$ be a protocol that \text{\tt C-QSA}~realizes $\funcG$,
    then $\cprot{\Pi}{\funcG}{\Gamma}$ \text{\tt C-QSA}~realizes $\mathcal{F}$.  If
    $\Gamma$ \text{\tt C-QSA}~realizes $\funcG$ against corrupted $P$ with
    unbounded simulation then $\cprot{\Pi}{\funcG}{\Gamma}$
    \text{\tt C-QSA}~realizes $\mathcal{F}$ against corrupted $P$ with unbounded
    simulation.
  \end{itemize}
\label{thm:sacomposition}
\end{theorem}

\begin{figure}[ht!]
    \begin{center}
    \begin{tikzpicture}[scale=0.38,
        turn/.style={draw, minimum height=15mm, minimum width=10mm,
          fill = ChannelColor, text=ChannelTextColor},
        smallturn/.style={draw, minimum height=8mm, minimum width=8mm,
          fill = ChannelColor, text=ChannelTextColor},
        >=latex]
      \node (A) at (-8,0) [smallturn] {$\Gamma$};
      \node (inl) [above of=A, xshift=-.5cm, minimum width = 0mm] {};
      \node (inr) [above of=A, xshift=.5cm,  minimum width = 0mm] {};
      \node (outl) [below of=A, xshift=-.5cm, minimum width = 0mm]
      {};
      \node (outr) [below of=A, xshift=.5cm,  minimum
      width = 0mm] {};
      \node (omitt) [above of = A, minimum width
            = 0mm] {$\vdots$};
      \node (omitb) [below of = A, minimum width
      = 0mm] {$\vdots$};
      \node (P) [above of = A, yshift = 4mm, minimum width
      = 0mm] {$\Pi$};
      \node (ML) [left of = A, xshift=1cm, yshift = 2mm, , draw, densely dotted, minimum height= 32 mm,
        minimum width =1.8 cm] {};
      \draw[->] (inl.south) -- ([xshift=-5mm]A.north) node {};
      \draw[->] (inr.south) -- ([xshift=5mm]A.north) node {};
      \draw[->] ([xshift=-5mm]A.south) -- (outl.north) node {};
      \draw[->] ([xshift=5mm]A.south) -- (outr.north) node {};

      \node (App) [right of = A, xshift = .5cm] {$\approx$};

      %

      \node (A1) [right of = App, xshift = .5cm, smallturn] {$\Gamma'$};
      \node (inl1) [above of=A1, xshift=-.5cm, minimum width = 0mm] {};
      \node (inr1) [above of=A1, xshift=.5cm,  minimum width = 0mm] {};
      \node (outl1) [below of=A1, xshift=-.5cm, minimum width = 0mm]
      {};
      \node (outr1) [below of=A1, xshift=.5cm,  minimum
      width = 0mm] {};
      \node (omitt) [above of = A1, minimum width
            = 0mm] {$\vdots$};
      \node (omitb) [below of = A1, minimum width
      = 0mm] {$\vdots$};
      \node (P1) [above of = A1, yshift = 4mm, minimum width
      = 0mm] {$\Pi^{\Gamma/{\Gamma'}}$};
      \node (ML1) [left of = A1, xshift=1cm, yshift = 2mm, , draw, densely dotted, minimum height= 32 mm,
        minimum width =1.8 cm] {};
      \draw[->] (inl1.south) -- ([xshift=-5mm]A1.north) node {};
      \draw[->] (inr1.south) -- ([xshift=5mm]A1.north) node {};
      \draw[->] ([xshift=-5mm]A1.south) -- (outl1.north) node {};
      \draw[->] ([xshift=5mm]A1.south) -- (outr1.north) node {};

      \node (L) [above of = A, yshift=1.5cm, smallturn] {$\Gamma$};
      \node (E) [right of = L, xshift=.5cm] {$\approx$};
      \node (R) [right of = E, xshift=.5cm, smallturn] {$\Gamma'$};
      \node (I) [below of = E] {$\Downarrow$};

      %

      \node (A2) [right of = A1, xshift = 2.5cm, smallturn] {$\funcG$};
      \node (inl2) [above of=A2, xshift=-.5cm, minimum width = 0mm] {};
      \node (inr2) [above of=A2, xshift=.5cm,  minimum width = 0mm] {};
      \node (outl2) [below of=A2, xshift=-.5cm, minimum width = 0mm]
      {};
      \node (outr2) [below of=A2, xshift=.5cm,  minimum
      width = 0mm] {};
      \node (omitt2) [above of = A2, minimum width
            = 0mm] {$\vdots$};
      \node (omitb2) [below of = A2, minimum width
      = 0mm] {$\vdots$};
      \node (P2) [above of = A2, yshift = 4mm, minimum width
      = 0mm] {$\Pi$};
      \node (ML2) [left of = A2, xshift=1cm, yshift = 2mm, , draw, densely dotted, minimum height= 32 mm,
        minimum width =1.8 cm] {};
      \draw[->] (inl2.south) -- ([xshift=-5mm]A2.north) node {};
      \draw[->] (inr2.south) -- ([xshift=5mm]A2.north) node {};
      \draw[->] ([xshift=-5mm]A2.south) -- (outl2.north) node {};
      \draw[->] ([xshift=5mm]A2.south) -- (outr2.north) node {};

      \node (App2) [right of = A2, xshift = .5cm] {$\approx$};

      \node (A3) [right of = App2, xshift = .5cm, smallturn] {$\Gamma$};
      \node (inl3) [above of=A3, xshift=-.5cm, minimum width = 0mm] {};
      \node (inr3) [above of=A3, xshift=.5cm,  minimum width = 0mm] {};
      \node (outl3) [below of=A3, xshift=-.5cm, minimum width = 0mm]
      {};
      \node (outr3) [below of=A3, xshift=.5cm,  minimum
      width = 0mm] {};
      \node (omitt3) [above of = A3, minimum width
            = 0mm] {$\vdots$};
      \node (omitb3) [below of = A3, minimum width
      = 0mm] {$\vdots$};
      \node (P3) [above of = A3, yshift = 4mm, minimum width
      = 0mm] {$\Pi^{\funcG/{\Gamma}}$};
      \node (ML3) [left of = A3, xshift=1cm, yshift = 2mm, , draw, densely dotted, minimum height= 32 mm,
        minimum width =1.8 cm] {};
      \draw[->] (inl3.south) -- ([xshift=-5mm]A3.north) node {};
      \draw[->] (inr3.south) -- ([xshift=5mm]A3.north) node {};
      \draw[->] ([xshift=-5mm]A3.south) -- (outl3.north) node {};
      \draw[->] ([xshift=5mm]A3.south) -- (outr3.north) node {};

      \node (L2) [above of = A2, yshift=1.5cm, smallturn] {$\funcG$};
      \node (E2) [right of = L2, xshift=.5cm] {$\approx$};
      \node (R2) [right of = E2, xshift=.5cm, smallturn] {$\Gamma$};
      \node (I2) [below of = E2] {$\Downarrow$};

    \end{tikzpicture}
  \end{center}
\label{fig:modcomp}
\caption{Illustration of modular composition theorem: the general case (left) and in hybrid model (right).}
\end{figure}

\iffalse

\subsection{Statistically Binding Commitment Schemes}
\rachel{I suggest that we use $\text{\tt com}$ to denote the classical SB com, and $\langle \mathcal{C}, \mathcal{R} \rangle$ to denote more interactive commitments}

\subsection{Simulation Security of Multiparty Computation Protocols}

\subsubsection{Explain the setup here -- environment and adversary and how they interact}

\rachel{Choice for terminology: shall we say simulation security against $\mathcal{P}$? That means there is a simulator for malicious party $\mathcal{P}^*$. The other choice is simulation-security for $\mathcal{P}'$, where $\mathcal{P}' \ne \mathcal{P}$. This works for 2PC, but does not work for MPC. We should just stick to one choice. }

\subsubsection{Commitments implementing $\mathcal{F}_{com}$}

\rachel{Directly define string commitment with local opening.}

\agnote{Do we need multiple parties here for future applications or 2 are sufficient?}
\begin{definition}[Ideal commitment functionality $\mathcal{F}_{com}$]
The functionality $\mathcal{F}_{com}$ is parametrized by a security parameter $\lambda$. This functionality interacts with an adversary $\mathcal{A}$ \agnote{I saw that some definitions do not have this $\mathcal{A}$. Should we keep it?} and parties $P_1,...,P_n$ via the following queries:
\begin{description}
    \item[Commit phase:] $\mathcal{F}_{com}$ receives a query $(\text{Commit},sid,ssid,P_i,P_j,b)$ from party $P_i$, records $(sid,ssid,P_i,P_j,b)$ and send the message $(\text{Receipt},sid,ssid,P_i,P_j)$ to $P_j$ and $\mathcal{A}$.  $\mathcal{F}_{com}$ ignore further commit messages from $P_i$.
    \item[Decommit phase:] $\mathcal{F}_{com}$ receives a query $(\text{Reveal},sid,ssid,P_i,P_j)$ and either ignores the message
    if no $(sid,ssid,P_i,P_j,b)$ recorded; otherwise $\mathcal{F}_{com}$
    marks $(sid,ssid,P_i,P_j,b)$ as revealed and send a message
    $(\text{Open},sid,ssid,P_i,P_j,b)$ to $P_j$ and $\mathcal{A}$.
\end{description}
\end{definition}
\rachel{NOte: statistical binding translates to unbounded simulation based receiver-security. Extractability translates to efficient simulation based receiver security. Hiding to efficient simulation based committer security. }

\subsubsection{Zero Knowledge implementing $\mathcal{F}_{zk}$}

\begin{definition}[Ideal Zero-knowledge functionality $\mathcal{F}_{zk}^R$ for relation $R$]
The functionality $\mathcal{F}_{zk}^R$, is parametrized by some relation $R$ and a security parameter $\lambda$. This functionality interacts with an adversary $\mathcal{A}$, prover $P$ and verifier $V$ via the following query:
\begin{description}
    \item[Proof:] $\mathcal{F}_{zk}^R$ receives a query $(\text{ZK-prover},sid,x,w)$ from $P$, and if $R(x,w) = 1$, sends the message $(\text{ZK-proof},sid,x)$ to $\mathcal{A}$ and $V$ and halts; otherwise, it just halts.
\end{description}
\end{definition}

\rachel{NOte:  Soundness translates to unbounded simulation based verifier-security. POK translates to efficient simulation based verifier security. ZK to efficient simulation based prover security. }

\subsubsection{Coin-Toss implementing $\mathcal{F}_{coin\text{-}toss}$ with One-sided Simulation}

\begin{definition}[Ideal coin-toss functionality $\mathcal{F}_{coin\text{-}toss}$]
The functionality $\mathcal{F}_{coin\text{-}toss}^R$, is parametrized by a security parameter $\lambda$. This functionality interacts with an adversary $\mathcal{A}$, $P_1$ and $P_2$ via the following query:
\begin{description}
    \item[Coin toss:] After $\mathcal{F}_{coin\text{-}toss}$ receives a query $(\text{START},sid)$ from $P_1$ and $P_2$, $\mathcal{F}_{coin\text{-}toss}$ sends an uniformly random bit $(COIN,b)$ to $P_1$ and waits $P_1$ to answer with $(OK)$ or $(FAIL)$. If the answer is $(OK)$, $\mathcal{F}_{coin\text{-}toss}$ sends $(COIN,b)$ to $P_2$ and halts, and if it is $(FAIL)$, it just halts.
\end{description}
\end{definition}

\subsubsection{Oblivious Transfer implementing $\mathcal{F}_{ot}$}

\begin{definition}[Ideal Oblivious-transfer functionality $\mathcal{F}_{ot}$]
The functionality $\mathcal{F}_{ot}$ is parametrized by a security parameter $\lambda$. This functionality interacts with an adversary $\mathcal{A}$, the sender $S$ and the receiver $R$ via the following queries:
\begin{description}
    \item[Sender query:] $\mathcal{F}_{ot}$ receives a query $(\text{Sender},sid,x_0,x_1)$ from $S$, records $(sid,x_0,x_1)$.
    \item[Receiver query:] $\mathcal{F}_{ot}$ receives a query $(\text{Receiver},sid,b)$ from and either ignores the message
    if no $(x_0,x_1)$ is recorded; otherwise $\mathcal{F}_{ot}$
    sends
    $(\text{Reveal},sid,x_b)$ to $R$ and $\mathcal{A}$.
\end{description}
\end{definition}

\fi

\section{Parallel OT  with Unbounded Simulation from OWF{}}
\label{sec:BBCS}
\label{sec:parallel-ot}

The goal of this section is to prove the following theorem.

\begin{theorem}
  Assuming the existence of pqOWF{}, there exists a protocol $\Pi_{\text{\tt p-ot}}$ that $\text{\tt C-QSA}$-emulates $\funct{\pot}$ with unbounded simulation against a malicious receiver.
\end{theorem}

We prove this theorem as follows. In \Cref{sec:bbcsot}, we review the protocol of \cite{C:BBCS91} that implies stand-alone-secure OT in $\funct{\socom}$-hybrid model. Then, in \Cref{sec:parallel-composition}, we show how to build $\funct{\pot}$ from $\funct{\socom}$. Finally in \Cref{sec:socom}, we construct $\funct{\socom}$ with unbounded simulation against malicious sender.

\subsection{Stand-Alone-secure OT in $\funct{\socom}$-hybrid model}

\label{sec:bbcsot}\label{sec:qot}
In this section we present the quantum OT protocol assuming a selective opening-secure commitment scheme, that is, in the $\funct{\socom}$~hybrid model. We would like to stress that the results in this section are not novel; they consist of a straightforward adaptation of previous results~\cite{C:BBCS91,DFL+09,EC:Unruh10} to our setting/language, and our goal in this presentation is to to provide a self-contained proof of its security.
We describe the protocol  $\Pi_{\tt QOT}$  in \Cref{sec:technical} and we have the following.

\iffalse
\begin{figure}[!ht]
  \begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
    {\sf Parameters:} Security parameter $\secpar$, $n, \ell \geq
    \secpar$, $\alpha \in (1/4,1/2) $. A family $\mathbf{F}=\big\{f:\{0,1\}^n\rightarrow\{0,1\}^\ell\big\}$ of universal
hash functions.\\
{\sf Parties:} The sender $S$ and the recipient $R$.\\
{\sf Inputs:} $S$ gets two $\ell$-bit strings $s_0$ and $s_1$, $R$ gets a bit $c$.

\begin{enumerate}
\item {\bf Preamble.} $S$ chooses $\tilde x^A=(\tilde x^A_1,\ldots,\tilde x^A_n)\in_R \{0,1\}^n$ and $\tilde \theta^A =(\tilde \theta^A_1,\ldots,\tilde\theta^A_n)\in_R \{+,\times\}^n$ uniformly at random and sends $|\tilde x^A\rangle_{\tilde
    \theta^A}$ to $R$ who denotes the received state by $\ket{\psi}$.

$R$ chooses $\tilde \theta^B
  =(\tilde \theta^B_1,\ldots,\tilde\theta^B_n)\in_R \{+,\times\}^n$ uniformly at random and measures
the qubits of $|\psi\rangle$ in the bases $\tilde \theta^B$; denote
the result by $\tilde x^B :=(\tilde x_1^B,\ldots,\tilde x_n^B)$. $R$
then invokes $\funct{\socom}$ and commits to each $(\tilde \theta_i^B, \tilde x_i^B)$.
\item {\bf Checking.}
   $S$ picks a subset $T \subseteq [n]$ of size $\alpha
    n$ uniformly at random, inputs $T$ to $\funct{\socom}$ and receives
    $\{ \tilde \theta_i^B, \tilde x_i^B\}_{i\in T}$.

  If there is any $i$ such that
    $\tilde\theta^B_i = \tilde\theta^A_i$ but
    $\tilde x^B_i\neq \tilde x^A_i$, then $S$ aborts.

  Let $\hat{x}^A$ be the string by removing in $\tilde x^A$ the
    positions in the checking set $T$. Define $\hat{\theta}^A$,
    $\hat{x}^B$, $\hat{\theta}^B$ analogously.
\item {\bf Partition Index Set.} $S$ sends $\hat{\theta}^A$ to $R$. $R$ sets $I_c := \{i : \hat{\theta}_i^A =\hat{\theta}_i^B\}$ and $I_{1-c} := \{i : \hat{\theta}_i^A \ne \hat{\theta}_i^B\}$, and  sends $(I_0, I_1)$ to $S$.
    %
\item {\bf Secret Transferring}.
 $S$ samples $f\in_R\mathbf{F}$; for $i = 0,1:$ $S$ computes
  $m_i := s_i \oplus f(x_i')$, where $x_i'$ is the $n$-bit string that
  consists of $\hat x^A|_{I_i}$ padded with zeros, and sends
  $(f,m_0,m_1)$ to $R$.

$R$ outputs $s := m_c \oplus f(x'_B)$, where  ${x'_B}$ is the $n$-bit string that
consists of $\hat x^B|_{I_c}$ padded with zeros.
\end{enumerate}
\caption{Quantum OT protocol $\Pi_{\tt QOT}$ in $\funct{\socom}$~hybrid model.}\label{fig:bbcs-com}
\end{mdframed}
\end{figure}
\fi

\begin{theorem}
\label{thm:ot}
$\Pi_{\tt QOT}$ $\text{\tt C-QSA}$-realizes $\funct{\ot}$ in the $\funct{\socom}$ hybrid model.
\end{theorem}

Due to space restrictions and since it closely follows the proof in previous results, we defer the proof of \Cref{thm:ot} to \Cref{ap:qot}.

 %
\subsection{Parallel Repetition for Protocols with Straight-Line Simulation}
\label{sec:parallel-composition}

\def\mathcal{G}{\mathcal{G}}

We show now that if $\pi$ implements $\mathcal{F}$ in the $\mathcal{G}$-hybrid model with an (efficient/unbounded) {\em straight-line} simulator, then a parallel repetition of $\pi$, denoted $\pi^{||}$ implements $\mathcal{F}^{||}$ in the $\mathcal{G}^{||}$-hybrid model with an (efficient/unbounded) simulator. As a corollary, we get that a parallel repetition of the $\mathcal{F}_{ot}$ protocol from the previous section is a secure implementation of parallel OT in the $\mathcal{F}_{\text{\tt so-com}}$ hybrid model.

\begin{theorem}[Parallel Repetition]\label{thm:parallel}
  Let $\mathcal{F}$ and $\mathcal{G}$ be two-party functionalities and let $\pi$
  be a secure implementation of $\mathcal{F}$ in the $\mathcal{G}$-hybrid model
  with a {\em straight-line} simulator.  Then, $\pi^{||}$ is a secure
  implementation of $\mathcal{F}^{||}$ in the $\mathcal{G}^{||}$-hybrid model
  with straight-line simulation as well.
\end{theorem}

The proof of \Cref{thm:parallel} is deferred to \Cref{ap:parallel}.  We
immediately get the following by observing that parallel-$\funct{\socom}$ is
exactly $\funct{\socom}$.

\begin{corollary}
  The parallel repetition of any protocol that  $\text{\tt C-QSA}$-realizes $\mathcal{F}_{ot}$ in the $\mathcal{F}_{\text{\tt so-com}}$-hybrid model with a straight-line simulator achieves $\funct{\pot}$ in the $\mathcal{F}_{\text{\tt so-com}}$-hybrid model.
\end{corollary}

\subsection{Implementing $\mathcal{F}_{\text{\tt so-com}}$ with unbounded Simulation}
\label{sec:comm-unbounded}
\label{sec:socom}

In this section we provide an implementation of $\funct{\socom}$ from Naor's commitment scheme and ZK protocols. Our protocol $\Pi_{\text{\tt so-com}}$ is described in \Cref{fig:prot-ext-com} and we prove the following result.

\begin{theorem}\label{thm:socom}
Assuming the existence of pqOWF{}, $\Pi_{\text{\tt so-com}}$ $\text{\tt C-QSA}$-realizes $\funct{\socom}$. with unbounded simulation against malicious committer.
\end{theorem}
\vspace{-3ex}
\begin{figure}[!ht]
  \begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
    %
{\sf Parties:} The committer $C$ and the receiver $R$.\\
{\sf Inputs:} $C$ gets $k$ $\ell$-bit strings $m_1$,...$m_k$ and $R$ gets a subset $I \subseteq [k]$ of messages to be decommited%

\begin{center}
\underline{\textsf{Commitment Phase}}
\end{center}
\begin{enumerate}
    \item $R$ sends $\rho$ for Naor's commitment scheme
    \item For $i \in [k]$, $C$ generates the commitments $c_i = \text{\tt com}_\rho(m_i,r_i)$, where $r_i$ is some private randomness.
    \item $C$ sends $c_1,...,c_k$ to $R$
\end{enumerate}

\begin{center}
\underline{\textsf{Decommitment Phase}}
\end{center}
\begin{enumerate}
   \item  $R$ sends $I$ to $C$
   \item $C$ sends $(m_i)_{i \in I}$ to $R$ and they run a ZK protocol to prove that there exists $\left((\tilde{m}_i)_{i \not\in I},(r_i)_{i \in [k]})\right)$ such that  $c_i = \text{\tt com}_{\rho}(\tilde{m}_i,r_i)$
\end{enumerate}
\vspace{-2ex}
\caption{Protocol for selective-opening commitment scheme $\Pi_{\text{\tt so-com}}$.}\label{fig:prot-ext-com}
\end{mdframed}
\vspace{-3ex}
\end{figure}

We prove \Cref{thm:socom} by showing security against malicious committer with unbounded simulator in \Cref{lem:socom-sender} and security against malicious receiver in \Cref{lem:socom-receiver}.

\begin{lemma}\label{lem:socom-sender}
Assuming the existence of pqOWF{},
$\Pi_{\text{\tt so-com}}$ \text{\tt C-QSA}-emulates
    $\funct{\socom}$ against corrupted committer $\adv$ with unbounded simulation.
\end{lemma}
\begin{proof}
The unbounded simulator $\simulator$ works as follows:
\begin{enumerate}
\item In the commitment phase, $\simulator$ runs the honest protocol with $\adv$ and when receives the commitments $\hat{c}_1,...,\hat{c}_k$ from $\adv$ and $\simulator$ finds the messages $\hat{m}_1,...,\hat{m}_k$ by brute force. If there is a $\hat{c}_i$ that does not decommit to any message or decommits to more than one message $\simulator$ aborts. Finally, $\simulator$ inputs $\hat{m}_1,...,\hat{m}_k$ to $\mathcal{F}_{\text{\tt so-com}}$
\item In the Decommitment phase,
   $\simulator$ receives $I$ from  $\mathcal{F}_{\text{\tt so-com}}$, forwards it to $\adv$. $\simulator$ receives $(\tilde{m}_i)_{i \in I}$ from $\adv$ runs the honest verifier in the ZK protocol with $\adv$, and rejects iff the ZK rejects or if for any $i \in I$, $\hat m_i \ne \tilde m_i$.
\end{enumerate}

The proof follows the statistically-binding property of Naor's commitment scheme, so we can ignore commitments that open to more than one message, and by the ZK soundness property, which ensures that, up to negligible probability, if the commitments are not well-formed or if the sender tries to open then to a different value, both the simulator and the original receiver abort.

Due to space restrictions, we leave the details to \Cref{ap:proof-sender-socom}
\end{proof}

We now show security against malicious receiver.

\begin{lemma}\label{lem:socom-receiver}
Assuming the existence of pqOWF{},
$\Pi_{\text{\tt so-com}}$ \text{\tt C-QSA}-realizes
    $\funct{\socom}$ against corrupted receiver $\adv$.
\end{lemma}
\begin{proof}
The simulator $\simulator$ works as follows:
\begin{enumerate}
\item In the commitment phase,  $\simulator$ sends $c_i = \text{\tt com}_\rho(0,r_i)$ to $\adv$
\item In the decommitment phase, $\simulator$ receives $I$ from  $\adv$, uses it as input of $\mathcal{F}_{\text{\tt so-com}}$. $\simulator$ receives back the messages $(m_i)_{i \in I}$, sends them to $\adv$ and runs the ZK simulator of the proof that $(c_i)_{i \in I}$ open to $(m_i)_{i \in I}$ and that $(c_i)_{i \not\in I}$ are valid commitments.
\end{enumerate}

The fact that $ M_{\Pi_{\text{\tt so-com}},\adv} \qc M_{\funct{\socom}, \simulator}$
follows from the computational zero-knowledge of the protocol and the
computatinally-hiding property of Naor's commitment scheme. We defer
the details of the proof to \Cref{ap:proof-receiver-socom}

\end{proof}

\fsnotem{I noticed several protocols are described in FZK
  hybrid. Strictly speaking, we cannot apply composition later since
  we don't have fully-simulatable ZK protocols assuming OWFs alone. I
  suppose we can just say "run ZK protocols" instead. Incidentally,
  Watrous proved quantum ZK for NP using a non-interactive commitment,
  and his theorem didn't claim quantum-secure ZK from OWFs. I don't
  see any issue plugging in Naor's commitment though.}

\section{Extractable Commitment from Unbounded Simulation OT}
\label{sec:ecom}

In this section, we construct an extractable commitment scheme using the
unbounded simulation OT from section~\ref{sec:BBCS}.
We do this in two steps. First, we define a new primitive, namely {\em verifiable}
conditional disclosure of secrets (vCDS) in section~\ref{sec:cdsdef}, and we
construct a (unbounded simulation)
vCDS protocol in section~\ref{sec:cdsprot} from the unbounded simulation OT. We then show how to use
vCDS to construct an extractable commitment protocol that implements
$\funct{\socom}$ with efficient simulators in section~\ref{sec:cds-to-extcom}.

\subsection{Verifiable Conditional Disclosure of Secrets (vCDS)}
\label{sec:cdsdef}

\agnotem{Is it necessary to define $\mathcal{F}_{CDS}$? I am not sure that we are using it in the later proof, since we need to use concrete protocol and we don't use the ideal functionality.}

\rachelm{I think we do implement $\mathcal{F}_{CDS}$ with unbounded
  simulation for both malicious sender and receiver. In the case of
  malicious receiver, we can simulate OT to get all the input it is
  using in each copy of OT. The simulator can test if any of them is a
  valid witness of $x$. If so, it sends that witness to the ideal
  functionality to get $m$ and then simulate the garbled circuits
  accordingly. So it seems we are fine, am I missing anything?}

\rachelm{Defined the above only w.r.t.\ 2 party and only has sid.}
\vnotem{need to ref for CDS. Who?}

We define the primitive of (verifiable) conditional disclosure of secrets.
Conditional disclosure of secrets~\cite{GIKM98} (CDS) for an $\NP$-language $\mathcal{L}$
is a two-party protocol where a sender (denoted $\mathsf{cds.S}$) and a receiver
(denoted $\mathsf{cds.R}$) have a common input $x$, the sender has a message $\mu$,
and the receiver (purportedly) has a witness $w$ for the $\NP$-relation $R_{\mathcal{L}}$.
At the end of the protocol, $\mathsf{cds.R}$ gets $\mu$ if $R_{\mathcal{L}}(x,w)=1$
and $\bot$ otherwise, and the sender gets nothing. In a sense, this can be
viewed as a {\em conditional} version of oblivious transfer, or as an interactive
version of witness encryption.

The CDS functionality is defined in Figure~\ref{fig:fcds}. We will
construct a protocol $\Pi = \inter{\mathsf{cds.S}, \mathsf{cds.R}}$ that securely
realizes the CDS functionality in the quantum stand-alone model. We
will consider protocols with either efficient or unbounded simulators.

\begin{figure}[!ht]
  \begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
  \begin{center}
    \textbf{The Conditional Disclosure of Secret (CDS) Functionality}
    $\mathcal{F}_{CDS}$ for an NP language $\mathcal{L}$.
  \end{center}
  \
  \\
  \textsf{Security Parameter:} $\lambda$.  \\
    \textsf{Parties:} Sender $S$ and Receiver $R$, adversary $\adv$.

  \begin{description}
  \item[Sender Query:] $\mathcal{F}_{CDS}$ receives
    $(\text{Send},sid,(x,\mu))$ from $S$, where
    $x \in \mathcal{L} \cap \{0,1\}^{n_1(\secpar)}$ and
    $m \in\{0,1\}^{n_2(\secpar)}$ for polynomials $n_1$ and $n_2$,
    records $(sid,(x, \mu))$
    and sends $(\text{Input},sid,x)$ to $R$ and $\mathcal{A}$.
    %

    $\mathcal{F}_{CDS}$ ignores further send messages from $S$ with $sid$.
  \item[Receiver Query:] $\mathcal{F}_{CDS}$ receives
    $(\text{Witness},sid, w)$ from party $R$, where
    $w \in\{0,1\}^{m(\secpar)}$ for a polynomial $m$.  $\mathcal{F}_{CDS}$
    ignores the message if no $(sid,\star)$ was recorded. Otherwise
    $\mathcal{F}_{CDS}$ sends $(\text{Open},sid, x, \mu')$ to $R$ where
    $$\mu' = \left\{ \begin{array}{cc}
    \mu & \mbox{if $\mathcal{R}_\mathcal{L}(x, w) = 1$} \\
    \bot & \mbox{if $\mathcal{R}_\mathcal{L}(x, w) = 0$} \end{array} \right.$$
    $\mathcal{F}_{CDS}$ sends
    $(\text{Open},sid, x)$ to $\adv$ and ignores further
    messages from $R$ with $sid$.
\end{description}
\end{mdframed}
\caption{The Conditional Disclosure of Secrets (CDS) Functionality}
\label{fig:fcds}
\vspace{-3ex}
\end{figure}

\paragraph{Verifiability.}
We will, in addition, also require the CDS protocol to be {\em verifiable}.
Downstream, when constructing our extractable commitment protocol in Section~\ref{sec:cds-to-extcom},
we want to be able to prove consistency of the transcript of a
CDS sub-protocol. It is not a-priori
clear how to do this since the CDS
protocol we construct will either live in the OT-hybrid model, in which case
the OT input is {\em not} contained in the protocol transcript and is
unconstrained by it; or it uses quantum communication, in which case,
again consistency cannot be expressed as an NP-statement.

\rachelm{it would be more general to define verifiability w.r.t.\ SFE,
  but that would require defining the ideal functionality F
  for computing a function f, which we did not define.}

\begin{definition}[Verifiability]
  \label{def:ver}
  Let $\mathcal{L}$ be an $\NP$ language, and $\Pi = \inter{\mathsf{cds.S}, \mathsf{cds.R}}$ be a
  CDS protocol between a sender $\mathsf{cds.S}$ and a receiver $\mathsf{cds.R}$. $\Pi$ is
  {\em verifiable} (w.r.t.\ $\mathsf{cds.S}$) if there is a polynomial time
  classical algorithm $\mathsf{Ver}$, such that, the following properties are
  true:
  \begin{description}
  \item[Correctness:] For every
    $(x,\mu)$ and every $w$, $\mathsf{cds.S}(x,\mu)$ after interacting with $\mathsf{cds.R}(w)$,
    outputs on a special output tape a proof $\pi$, such that,
    $\mathsf{Ver}(\tau,x,\mu,\pi) = 1$ where $\tau$ is the transcript of classical
    messages exchanged in the interaction.

  \item[Binding:] For every $\secpar \in \mathbb{N}$, every
    (potentially unbounded) adversary
    $\adv = \set{\adv_\secpar}_{\secpar\in\mathbb{N}}$, every sequence of
    witnesses $\set{w_\secpar}_\secpar$,
    the probability that $\adv_\secpar$ wins in the following experiment is
    negligible.

  \begin{itemize}
  \item $\adv_\secpar$ after interacting with $\mathsf{cds.R}(1^\secpar, w)$,
    outputs $(x,\mu,\pi)$. Let $\tau$ be the transcript of classical
    messages exchanged in the interaction.

  \item $\adv_\secpar$ wins if (a) $\mathsf{Ver}(\tau, x, \mu, \pi) = 1$, (b) $\mathsf{cds.R}$ did
    not abort, and (c) $\mathsf{cds.R}$ outputs $\mu'$ inconsistent with inputs $(x,\mu)$ and
    $w$, that is,
    \begin{align*}
      \mu' \ne
      \begin{cases}
        \mu & \text{ if } \mathcal{R}_\mathcal{L}(x, w) = 1  \\
        \bot & \text{ otherwise }
      \end{cases}
    \end{align*}
  \end{itemize}
  \end{description}
\end{definition}

\begin{definition}[Verifiable CDS]
  Let $\mathcal{L}$ be an $\NP$ language, and $\Pi = \inter{\mathsf{cds.S}, \mathsf{cds.R}}$ be a
  protocol between a sender $\mathsf{cds.S}$ and a receiver $\mathsf{cds.R}$. $\Pi$ is a
  {\em verifiable CDS} protocol if (a) it $\text{\tt C-QSA}$-emulates $\funct{\cds}$ with
  an efficient simulator; and (b) it is verifiable according to Definition~\ref{def:ver}.
\end{definition}

\subsection{CDS Protocol from Unbounded Simulation OT}
\label{sec:cdsprot}

\begin{theorem}\label{thm:vercds}
  Assume the existence of pqOWF{}.  For
  every $\NP$ language $\mathcal{L}$, there is a verifiable CDS protocol
  $\Pi = \inter{\mathsf{cds.S}, \mathsf{cds.R}}$ that \text{\tt C-QSA}-emulates $\funct{\cds}$ for
  $\mathcal{L}$ in the $\funct{\pot}$ hybrid model.
\end{theorem}

\begin{corollary}
  Assume the existence of pqOWF{}, and a
  protocol that \text{\tt C-QSA}-emulates $\funct{\pot}$ with unbounded
  simulation. Then, for every $\NP$ language $\mathcal{L}$, there is a
  verifiable CDS protocol $\Pi = \inter{\mathsf{cds.S}, \mathsf{cds.R}}$ that
  \text{\tt C-QSA}-emulates $\funct{\cds}$ for $\mathcal{L}$ with unbounded simulation.
\end{corollary}

 \paragraph{Proof of Theorem~\ref{thm:vercds}.}
 The verifiable CDS protocol is described in Figure~\ref{fig:cdsprot}.
 The protocol uses Naor's classical statistically binding commitment
   protocol, Yao's garbled circuits, and post-quantum zero knowledge proofs, all
   of which can be implemented from pqOWF{}. For a more
   detailed description of these ingredients, see Section~\ref{sec:cryptoprelims}.

 In lemma~\ref{lem:rcvrsim}, we show that the protocol has an efficient simulator for a corrupted receiver,
 and in lemma~\ref{lem:sendsim}, an efficient simulator for a corrupted sender (both in the OT hybrid model).
 Lemma~\ref{lem:verifiability} shows that the protocol is verifiable.
 %
 %
 \qed

    %
\begin{figure}[htpb]
{\small
 \begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
 %
 \textsf{Parties:} The sender $\mathsf{cds.S}$ and the receiver $\mathsf{cds.R}$. \hfill \textsf{Inputs:} $\mathsf{cds.S}$ has input $(x,\mu)$ and $\mathsf{cds.R}$ has input $w$.
 %
  \begin{enumerate}
  \item \textbf{\textcolor{blue}{Preamble}}:
  $\mathsf{cds.R}$ sends a random string $\rho$ as the first message of
    Naor's commitment scheme to $\mathsf{cds.S}$ and $\mathsf{cds.S}$ sends $x$ to $\mathsf{cds.R}$
    %
    %
    %

   \item \textbf{Compute Garbled Circuits:}
   $\mathsf{cds.S}$ generates $2\secpar$ garbled circuits, for the circuit
     computing
     \begin{align*}
       G_{x,\mu}(w) =  \mu' = \begin{cases}
          \mu & \text{ if } \mathcal{R}_\mathcal{L}(x, w) = 1  \\
          \bot & \text{ otherwise }
        \end{cases}
     \end{align*}
     That is, for every $i \in [2\secpar]$,
     $$(\hat G^i,
     \smallset{\ell^{i,j}_b}_{j \in [m], b \in \{0,1\}}) = \mathsf{Garb}(G_{x,\mu};
     \gamma_i)$$
    where $m$ is the length of the witness, $\hat G^i$ are
     the garbled circuits, and $\ell$'s are its associated labels.

  \item \textbf{Cut-and-Choose:}
     $\mathsf{cds.R}$ samples a random subset $\Lambda \subseteq [2\secpar]$, by
       including each $i \in [2\secpar]$ with probability 1/2. For every
       $i \in [2\secpar]$, set
       %
       %
       \begin{align*}
        \sigma^i =
          \begin{cases}
            s^i \gets \{0,1\}^m & i \in \Lambda \\
            w & i \not\in \Lambda
          \end{cases}
       \end{align*}

   \item \textbf{\textcolor{blue}{OT}:}
   For every $i \in [2\secpar], j\in [m], b \in \{0,1\}$, $\mathsf{cds.S}$ samples
   $r^{i,j}_b$, the random coins for
   committing to the labels $\ell^{i,j}_b$ via Naor's commitment scheme.

   $\mathsf{cds.S}$ and $\mathsf{cds.R}$ invokes $\funct{\pot}$ for $2\secpar \times m$
     parallel OT, where the $(i,j)$'th OT for
     $i \in [2\secpar], j \in [m]$ has sender's input strings
     $(\ell^{i,j}_0, r^{i,j}_0)$ and $(\ell^{i,j}_1, r^{i,j}_1)$, and
     receiver's choice bit $\sigma^{i,j}$ (which is the $j$-th bit of $\sigma^{i}$) and $\mathsf{cds.R}$ receives
     $(\tilde \ell^{i,j}, \tilde r^{i,j})$.

     We refer to the OTs with index $(i, \star)$ as the $i$'th batch.
     as they transfer labels of the $i$'th garbled circuit $\hat G_i$.

   %
    %
    %
    %

  \item \textbf{\textcolor{blue}{Send Garbled Circuits and Commitments to the Labels and $\mu$}:}
         $\mathsf{cds.S}$ samples $r^*$ and computes $c^* = \text{\tt com}_{\rho}(\mu; r^*)$ and
         $c^{i,j}_b = \text{\tt com}_{\rho}(\ell^{i,j}_b; r^{i,j}_b)$.

         Send $\smallset{\hat G^i}_{i \in [2\secpar]}$ and
         $(c^*, \smallset{c^{i,j}_b}_{i\in [2\secpar], j \in [m], b \in \{0,1\}})$ to the receiver $\mathsf{cds.R}$.

    %
     %
     %
     %

   \item \textbf{\textcolor{blue}{Proof of Consistency}:}
   $\mathsf{cds.S}$ proves via ZK protocol that (a) $c^*$ is a valid commitment to
     $\mu$, (b) every $\hat G^i$ is a valid garbling of $G_{x,\mu}$ with labels
     $\smallset{\ell^{i,j}_b}_{j \in [m], b \in \{0,1\}}$, and (c) $c^{i,j}_b$ is a
     valid commitment to $\ell^{i,j}_b$.

   \item \textbf{Checks:} $\mathsf{cds.R}$ performs the following checks:
     \begin{itemize}
     \item If the ZK proof in the previous step is not accepting, $\mathsf{cds.R}$
       aborts.

     \item If there is $i \in \Lambda$ and $j \in [m]$, such that,
       $c^{i,j}_{\sigma^{i,j}} \ne \text{\tt com}_{\rho}(\tilde \ell^{i,j}, \tilde
       r^{i,j})$, $\mathsf{cds.R}$ aborts and outputs $\mathsf{err}_1$.

     \item If for every $i \not\in \Lambda$, there exists $j \in [m]$, such
       that, $c^{i,j}_{\sigma^{i,j}} \ne \text{\tt com}_{\rho}(\tilde \ell^{i,j},
       \tilde r^{i,j})$, $\mathsf{cds.R}$ aborts and outputs $\mathsf{err}_2$.
     \end{itemize}

   \item \textbf{Output:} If $\mathsf{cds.R}$ does not abort, there must exist $i \not \in \Lambda$
     such that, for all $j \in [m]$,
     $c^{i,j}_{\sigma^{i,j}} = \text{\tt com}_{\rho}(\tilde \ell^{i,j}, \tilde
     r^{i,j})$. Evaluate the $i$'th garbled circuit $\hat G^i$ to get
      $\mu' = \mathsf{GEval}(\hat G^i, \smallset{\tilde \ell^{i,j}}_{j\in[m]})$,
     and output $x',\mu'$. %

 \end{enumerate}

 \caption{\small The verifiable CDS Scheme in $\funct{\pot}$-hybrid model. The steps in color involve communication while the others only involve local computation. }\label{fig:cds-scheme}\label{fig:cdsprot}
 \end{mdframed}
 }
 \end{figure}

\begin{lemma}\label{lem:rcvrsim}
  There is an efficient simulator against a malicious receiver.
\end{lemma}

\begin{proof}
  The simulator $\simulator$ interacts with $\mathsf{cds.R}^*$, receives a string $\rho$ from
  $\mathsf{cds.R}^*$ in Step $1$, and intercepts
  the OT queries $(\sigma^{1},\ldots,\sigma^{2\secpar})$ in Step $4$.
  \begin{itemize}
    \item \textbf{Case $1$. $R_{\mathcal{L}}(x,\sigma^{i})=1$ for some $i$.}
    Send $(\text{Witness},sid, \sigma^{i})$ to the CDS functionality and receive
    $\mu$. Simulate the rest of the protocol honestly using the CDS sender input
    $(x,\mu)$.
    \item  \textbf{Case $2$. $R_{\mathcal{L}}(x,\sigma^{i})=0$ for all $i$.}
    Simulate the rest of the protocol honestly using the CDS sender input
    $(x,0)$.
  \end{itemize}

  We now show, through a sequence of hybrids, that this simulator produces a view that is computationally
  indistinguishable from
  that in the real execution of $\mathsf{cds.S}(x,\mu)$ with $\mathsf{cds.R}^*$.

  \medskip\noindent
  \textit{Hybrid $0$.} This corresponds to the real execution of the protocol where the
  sender has input $(x,m)$. The view of $\mathsf{cds.R}^*$ consists of
  $$ \bigg[ \rho,
           \smallset{\hat G^i, \tilde \ell^{i,j}, \tilde r^{i,j}, c^{i,j}_b}_{i\in[2\secpar],j\in[m],b\in\{0,1\}},
           c^*,
           \tau_{\mathsf{ZK}}    \bigg]$$
  where $\rho$ is the message sent by $\mathsf{cds.R}^*$ in Step $1$, the strings $\tilde \ell^{i,j}$ and $\tilde r^{i,j}$
  are received by $\mathsf{cds.R}^*$ from the OT functionality in Step $4$, the garbled circuits $\hat G^i$ and
  the commitments $c^{i,j}_b$ and $c^*$ in Step $5$, and $\tau_{\mathsf{ZK}}$ is the transcript of the ZK
  protocol between $\mathsf{cds.S}$ and $\mathsf{cds.R}^*$ in Step $6$. (See the protocol in Figure~\ref{fig:cdsprot}).

  \medskip \noindent
  \textit{Hybrid $1$.}
  This is identical to hybrid $0$ except that we run the simulator to intercept the OT queries
  $(\sigma^{1},\ldots,\sigma^{2\secpar})$ of $\mathsf{cds.R}^*$.
  The rest of the execution remains the same. Of course, the transcript produced is identical to that in
  hybrid $0$.

  \medskip \noindent
  \textit{Hybrid $2$.}
  In this hybrid, we replace the transcript $\tau_{\mathsf{ZK}}$ of the zero-knowledge
  protocol with a simulated transcript. This is indistinguishable from hybrid $1$ by
  (post-quantum) computational zero-knowledge. Note that generating this hybrid does not require
  us to use the randomness underlying the commitments $c^{i,j}_{1-\sigma^{i,j}}$ and $c^*$.
  (The randomness underlying $c^{i,j}_{\sigma^{i,j}}$ {\em are} revealed as part of the
  OT responses to $\mathsf{cds.R}^*$.)

  \medskip \noindent
  \textit{Hybrid $3$.}
  In this hybrid, we replace half the commitments, namely $c^{i,j}_{1-\sigma^{i,j}}$, as well as
  $c^*$ with commitments of $0$. This is indistinguishable from hybrid $2$ by
  (post-quantum) computational hiding of Naor commitments.

  \medskip \noindent
  \textit{Hybrid $4$.}
  In this hybrid, we proceed as follows.
  If the simulator is in case $1$, that is $R_{\mathcal{L}}(x,\sigma^i) = 1$ for some $i$,
  proceed as in hybrid $3$ with no change. On the other hand,
  if the simulator is in case $2$,  that is $R_{\mathcal{L}}(x,\sigma^i) = 0$ for all $i$,
  replace the garbled circuits with simulated garbled circuits that always output $\bot$ and
  let the commitments $c^{i,j}_{\sigma^{i,j}}$ be commitments of the simulated labels.
  This is indistinguishable from hybrid $3$ where the garbled circuits are an honest
  garbling of $G_{x,\mu}$ because of the fact that all the garbled evaluations output $\bot$ in hybrid $3$,
  and because of the post-quantum security of the
  garbling scheme.

  Hybrids $5$--$7$ undo the effects of hybrids $2$--$4$ in reverse.
  %

  \medskip \noindent
  \textit{Hybrid $5$.}
  In this hybrid, we replace the simulated garbled circuit with the real garbled circuit for the circuit $G_{x,0}$.
  This is indistinguishable from hybrid $4$ because of the fact that all the garbled evaluations output $\bot$ in this hybrid,
  and because of the post-quantum security of the
  garbling scheme.

  \medskip \noindent
  \textit{Hybrid $6$.}
  In this hybrid, we let all commitments be to the correct labels and messages. This is indistinguishable from hybrid $5$ by
  (post-quantum) computational hiding of Naor commitments.

  \medskip \noindent
  \textit{Hybrid $7$.}
  In this hybrid, we replace the simulated ZK transcript
  with the real ZK protocol transcript. This is indistinguishable from hybrid $7$ by
  (post-quantum) computational zero-knowledge.

  This final hybrid matches exactly the simulator. This finishes the
  proof.
\end{proof}
\begin{lemma}\label{lem:sendsim}
  There is an inefficient statistical simulator against a malicious sender.
\end{lemma}
\begin{proof}
  The simulator $\simulator$ interacts with $\mathsf{cds.S}^*$ as follows:
  \begin{itemize}
    \item Sending a string $\rho$ to $\mathsf{cds.S}^*$ in Step $1$, as in the protocol;
    \item {\em Intercept} the OT messages $(\ell^{i,j}_0,r^{i,j}_0)$ and $(\ell^{i,j}_1,r^{i,j}_1)$
    from $\mathsf{cds.S}^*$ in Step $4$.
    \item Run the rest of the protocol as an honest receiver $\mathsf{cds.R}$ would. If the
  verifier of the ZK proof rejects, send $(x,\bot)$ to the ideal functionality and halt.
    \item  Label the $i$-th
  garbled instance {\em bad} if for some $j \in [m]$ and $b\in \{0,1\}$,
  the label $\ell^{i,j}_b$  together with the decommitment $r^{i,j}_b$ is not
  consistent with the commitment $c^{i,j}_b$.
  \begin{itemize}
    \item If more than $\secpar$ garbled instances are bad, send $(x,\bot)$ to the ideal functionality and halt.
    \item If not, extract $\mu$ from $c^*$ using unbounded time, and send $(x,\mu)$ to the ideal functionality and halt.
  \end{itemize}
  \end{itemize}
  The transcript generated by $\simulator$ is identical to the one generated in
  the real world where $\mathsf{cds.R}$ on input $w$ interacts with $\mathsf{cds.S}^*$. It remains to
  analyze the output distribution of $\mathsf{cds.R}$ in the simulation vis-a-vis the real world.

  We split the analysis into two cases.
  \begin{enumerate}
    \item If more than $\secpar$ garbled instances are bad, $\simulator$ will send
    $(x,\bot)$ to the ideal functionality; on the other hand, the receiver will also output $\bot$ except
    with probability at most $2^{-\secpar/2}$, since the expected number of bad garbled circuits in $\Lambda$ is
    at least $\secpar/2$ and the probability that all of them check out is $(1/2)^{\secpar/2}$.
    \item If
    fewer than $\secpar$ garbled instances are bad, $\simulator$ will extract $\mu$ and send
    $(x,\mu)$ to the ideal functionality; on the other hand, in the real world, (1) at least
    one garbled instance is not bad; (2) since the ZK proof checked out,
    we know that all garbled circuits contain the same circuit $G_{x,\mu}$ with the correct
    labels committed in $c^{i,j}_b$; and (3) if all the commitment checks pass, the output of the garbled
    evaluation must be $\mu$.
  \end{enumerate}
 Thus, we have that the output distributions of the receiver are negligibly close between the
 simulation and the real world, finishing up the proof.
\end{proof}

\iffalse
\agnote{Do we need this?}
 \begin{claim}
   In an interaction between an (unbounded) adversary and $\mathsf{cds.R}$, the
   probability that $\mathsf{cds.R}$ does not output $\mathsf{err}_1$ but outputs $\mathsf{err}_2$
   is negligible.
 \end{claim}
 \begin{proof}
 Let $E_1$ ($E_2$) be the event when the condition to output $\mathsf{err}_1$ (resp. $\mathsf{err}_2$) is satisfied.

 For $i \in [2\lambda]$, let $M_i = \{(j,b) : c^{i,j}_{b} \ne \text{\tt com}_r(\tilde \ell^{i,j}_b,\tilde d^{i,j}_b)\}$ be the set of the commitments for the labels $\ell^{i,j}_b$ that are not correct.
 Let also $B = \{i \in [2\lambda] : |M_i| \geq 1\}$, the subset of $[2\lambda]$ where there is at least one commitment that is not correct.

Notice that the
\begin{align*}
    Pr[\overline{E_1}]  &= Pr[\Lambda \cap B = \emptyset \; \vee \; \forall i \in \Lambda \cap B, j \in [m], (j,\rho^i_j) \ne  M_i] \\
    &\leq
Pr[\Lambda \cap B = \emptyset] +  Pr[\forall i \in \Lambda \cap B, j \in [m], (j,\rho^i_j) \ne  M_i].
\end{align*}
We have that
$ Pr[\Lambda \cap B = \emptyset] \leq \frac{1}{2^{|B|}}$
since each $i \in B$ is in $\Lambda$ w.p. $\frac{1}{2}$ and,
$ Pr[\forall i \in \Lambda \cap B, j \in [m], (j,\rho^i_j) \ne  M_i] \leq \frac{1}{2^{|B|}}$ since for every $(b,j) \in M_i$, $\rho^i_j = b$ w.p. $\frac{1}{2}$. Thus, it follows that
\[Pr[\overline{E_1}]  \leq  \frac{1}{2^{|B|-1}}.\]

We also have that
\[\Pr[E_2] \leq Pr[\overline{\Lambda} \setminus B = \emptyset] \leq \frac{1}{2^{2\lambda - |B|}},\]
since each $i \not\in B$ is not in $\Lambda$ with probability $\frac{1}{2}$.

Therefore we have that
\[
Pr[ \mathsf{cds.R} \text{ does not output } \mathsf{err}_1 \text{ but outputs } \mathsf{err}_2 ] \leq
Pr[\overline{E_1} \wedge E_2] \leq \min\{Pr[\overline{E_1}], Pr[E_2] \} \leq \negl(\lambda),
\]
where in the last inequality we optimize over $0 \leq |B| \leq 2\lambda$.
 \end{proof}
\fi

 \begin{lemma}\label{lem:verifiability}
    The protocol is verifiable.
 \end{lemma}
 \begin{proof}
   We first construct a verification algorithm $\mathsf{Ver}$.
   \begin{itemize}
    \item The transcript $\tau$ of classical messages consists of $\rho,
      x, \smallset{\hat G^i}_{i \in [2\secpar]}, c^*,
      \smallset{c^{i,j}_b}_{i \in [2\secpar], j\in[m], b \in \{0,1\}}$.
      \fsnotem{what is $r_S$? Sender's randomness? how to define when
      sender is quantum?} \vnotem{we are talking here of the honest sender who is classical}
      %

    \item At the end of the protocol, $\mathsf{cds.S}$ outputs $(x, \mu, r^*)$ on its special output tape.

    \item The verification algorithm $\mathsf{Ver}(\tau, x, \mu', r') = 1$ iff $c^*=\text{\tt com}_{\rho}(\mu'; r')$.
   \end{itemize}

 We first claim that for honest $\mathsf{cds.S}$ and $\mathsf{cds.R}$ with $(x,w) \in \mathcal{R}_{\mathcal{L}}$, we have that $\mathsf{Ver}(\tau,x,\mu,r) = 1$.
 Since all parties in the protocol are honest the input $x$ in $\tau$ is the same as the one output by $\mathsf{cds.S}$ and we have that $c^*$ is the commitment to the honest message using the correct randomness, so $\mathsf{Ver}$ outputs $1$.

 To show binding, assume that the verification passes and the receiver does not abort. Then, we know that there is at least
 one $i \notin \Lambda$ such that the $i$-th garbled circuit+input pair is correct and the circuit is the garbling of $G_{x,\mu}$. The verifier will evaluate the circuit on input $w$ and obtain either $\bot$ when $R_{\mathcal{L}}(x,w) = 0$ or $\mu$ when $R_{\mathcal{L}}(x,w)=1$, exactly as required.
 \end{proof}

\subsection{Extractable Commitment from CDS}
\label{sec:cds-to-extcom}

\begin{theorem}\label{thm:ecom}
  Assume the existence of pqOWF{}.
  There is a commitment protocol $\inter{C, R}$ that
  \text{\tt C-QSA}-emulates $\funct{\socom}$ with efficient simulators.%
 \end{theorem}
\begin{proof}
The construction of our extractable commitment scheme is given in Figure~\ref{fig:ext-com-scheme}.
The protocol uses Naor's classical statistically binding commitment
  protocol and a verifiable CDS protocol $\Pi = \inter{\mathsf{cds.S}, \mathsf{cds.R}}$ that
    \text{\tt C-QSA}-emulates
    $\funct{\cds}$ (with unbounded simulation) for $\mathcal{L}_\text{\tt com}$, the
    language consisting of all Naor's commtiments $(\rho,c)$ to a bit $b$:
    \begin{align*}
      \mathcal{R}_{\mathcal{L}_\text{\tt com}} ((\rho,c,b), r) = 1 \text{ iff } c = \text{\tt com}_{\rho}(b;r) ~.
    \end{align*}
  For a more
  detailed description of these ingredients, see Section~\ref{sec:cryptoprelims} and \ref{sec:cdsprot}.

In~\Cref{lem:commsim} (resp.~\Cref{lem:commrcvrsim}, we show that the protocol has an efficient simulator for a corrupted sender (resp. receiver).  %
\end{proof}
\vspace{-3ex}
\begin{figure}[!h]
\begin{mdframed}[style=figstyle,innerleftmargin=10pt,innerrightmargin=10pt]
\textsf{Parties:} The committer $C$ and the receiver $R$.\\
\textsf{Inputs:} $C$ gets a message vector $\vec{\mu}=(\mu_1,\ldots,\mu_{\ell(n)})$ and $R$ gets $1^n$.
\begin{center}
\underline{\textsf{Commitment Phase}}
\end{center}
 \begin{enumerate}
 \item \textbf{Preamble.} $C$ sends a random string $\rho$ to $R$, and $R$ sends a random string $\rho^*$ to $C$, as the first message of the Naor commitment scheme.
 \item \textbf{Set up a Trapdoor Statement.}
 \begin{itemize}
   \item
   $R$ sends a Naor commitment $c = \text{\tt com}_{\rho}(0;r)$.
   \item
   $R$ proves to $C$ using a ZK protocol that $c$ is a commitment to $0$, that is,
   $((c,\rho,0), r) \in \mathcal{R}_{\mathcal{L}_{\mathsf{com}}}$.
   If the ZK verifier rejects, $C$ aborts.
 \end{itemize}

 \item \textbf{CDS.}
 $C$ and $R$ run the CDS protocol $\inter{\mathsf{cds.S}, \mathsf{cds.R}}$ for the language $\mathcal{L}_{\text{\tt com}}$ where $C$ acts as
 $\mathsf{cds.S}$ with input $x = (c,\rho, 1)$ and message $\vec{\mu}$, and $R$ acts as $\mathsf{cds.R}$ with input $0$. %

 $C$ aborts if $\mathsf{cds.S}$ aborts, else $C$ obtains the protocol transcript $\tau$ and $\mathsf{cds.S}$'s proof $\pi$.
 $R$ aborts if $\mathsf{cds.R}$ aborts, or if $\mathsf{cds.R}$
 outputs $(x', \vec{\mu}')$ but $x'\ne (\rho, c, 1)$.

 \item \textbf{Commit and Prove Consistency.}
 \begin{itemize}
   \item $C$ sends a Naor commitment $c^* = \text{\tt com}_{\rho^*}(\vec{\mu};r^*)$.
   \item $C$ proves to $R$ using a ZK protocol there exists a $\vec{\mu}$ such that $(x=(\rho, c, 1), \vec{\mu})$ is the input that $C$ used in the CDS protocol and $\vec{\mu}$ is committed in $c^*$, that is:
   $$\mathsf{Ver}(\tau, x, \vec{\mu}, \pi) = 1 \mbox{ and } c^* = \text{\tt com}_{\rho^*}(\vec{\mu}, r^*)$$
 \end{itemize}

 \item $R$ accepts this commitment if the ZK proof is accepting.
\end{enumerate}
\begin{center}
\underline{\textsf{Decommitment Phase}}
\end{center}

\begin{enumerate}
\item $R$ sends $I \subseteq [\ell]$.
 \item $C$ sends $\vec{\mu}|_I$ and proves via a ZK protocol that
   $c^*|_I$ commits to $\vec{\mu}|_I$.

 \item $R$ accepts this decommitment if the ZK proof is accepting.

 \end{enumerate}
\vspace{-3ex}
\caption{Extractable Selective-Opening-Secure Commitment Scheme}\label{fig:ext-com-scheme}
\end{mdframed}
\end{figure}

\begin{lemma}\label{lem:commsim}
There is an efficient simulator against a malicious sender. %
\end{lemma}
\begin{proof}
  The simulator $\simulator$ against a malicious committer $C^*$ works as follows.
  \begin{enumerate}
  \item In step $1$, proceed as an honest receiver would.
  \item In step $2$, send a Naor commitment $c = \text{\tt com}_{\rho}(1;r)$ (instead of $0$)
  and simulate the ZK proof.
  \item In step $3$, run the honest CDS protocol with $r$ as witness, gets $\vec{\mu}$ and sends it
  to the ideal functionality $\funct{\socom}$.
  \item Run the rest of the protocol as an honest receiver would.
    \end{enumerate}

We now show, through a sequence of hybrids, that this simulator produces a joint distribution of a view
of $C^*$ together with an output of $R$ that is computationally
        indistinguishable from that in the real execution of $C^*$ with $R$.
In order to show this we consider the following sequence of  hybrids.

\medskip\noindent
\textit{Hybrid 0.} This corresponds to the protocol  $\Pi_{\tt H_0}^{\ecom}$, where $\simulator_0$ sits between $C^*$ and the honest receiver in the real protocol and just forwards their messages. It follows trivially that
$M_{\Pi_{\mathsf{ECom}},C^*} \qc
    M_{\Pi_{\tt H_0}^{\ecom}, \simulator_0}$.

\medskip\noindent
\textit{Hybrid 1.}
 $\simulator_1$ interacts with $C^*$ following the protocol $\Pi_{\tt H_1}^{\ecom}$, which is the same as $\Pi_{\tt H_0}^{\ecom}$ except that $\simulator_1$ uses the ZK simulator instead of the the proof that
 $((c,\rho,0), r) \in \mathcal{R}_{\mathcal{L}_{\mathsf{com}}}$.
From the computational zero-knowledge property of the protocol, we have that
$    M_{\Pi_{\tt H_0}^{\ecom}, \simulator_0} \qc
    M_{\Pi_{\tt H_1}^{\ecom}, \simulator_1}$.

\medskip\noindent
\textit{Hybrid 2.}
$\simulator_2$ interacts with $C^*$ following the protocol $\Pi_{\tt H_2}^{\ecom}$, which is the same as $\Pi_{\tt H_1}^{\ecom}$ except that $\simulator_2$ sends $c' = \text{\tt com}_{\rho}(1;r)$ instead of the (honest) commitment of $0$. When $\simulator_2$ simulates $\funct{\zk}$, she still sends a message that $c'$ is a valid input. It follows from computationally hiding property of Naor's commitment scheme that $M_{\Pi_{\tt H_1}^{\ecom}, \simulator_1} \qc
    M_{\Pi_{\tt H_2}^{\ecom}, \simulator_2}$.

\medskip\noindent
\textit{Hybrid 3.}
$\simulator_3$ interacts with $C^*$ following the protocol $\Pi_{\tt H_3}^{\ecom}$, which is the same as $\Pi_{\tt H_2}^{\ecom}$ except that $\simulator_3$ now uses the private randomness $r$ as a witness that $c'$ is a commitment of $1$.

Since our protocol realizes $\mathcal{F}_{CDS}$, $\mathsf{cds.S}^*$ (controlled by $C^*$) does not behave differently depending on the input of $\mathsf{cds.R}$, so the probability of abort in step $3$ does not change. Notice also that  $\mathsf{Ver}(\tau,x,\vec{\mu},\pi)$ is independent of $\mathsf{cds.R}$'s message, so the acceptance probability of the ZK proof does not change either.

Then, if the ZK proof leads to acceptance, by the soundness of the protocol, we know that $\mathsf{Ver}(\tau,x,\vec{\mu},\pi) = 1$ and
by the binding of the commitment $c^*$, such a $\vec{\mu}$ is uniquely determined.

Finally, by the verifiability of the CDS protocol, we know that the receiver either aborts or outputs the specified $\vec{\mu}$. Thus, the outputs of the receiver $R$ in the simulated execution and the real execution must be the same in this case.

\end{proof}

\begin{lemma}\label{lem:commrcvrsim}
  There is an efficient simulator against a malicious receiver.
 %
\end{lemma}
\begin{proof}
  The simulator $\simulator$ against a malicious receiver $R^*$ proceeds as follows.
  \begin{itemize}
    \item In steps $1$ and $2$, proceed as an honest sender would.
    \item In step $3$, run the CDS protocol using a message vector $\vec{\mu} = \vec{0}$ of all zeroes.
    \item In step $4$, commit to the all-$0$ vector and produce a simulated ZK proof.
    \item During decommitment, send $I \subseteq [\ell]$ to the ideal functionality and receive $\vec{\mu}|_I$.
    Send $\vec{\mu}|_I$ to $R^*$, and simulate the ZK proof.
    \end{itemize}

  We now show, through a sequence of hybrids, that this simulator produces a view that is computationally
    indistinguishable from that in the real execution of $C(\vec{\mu})$ with $R^*$.

    \medskip\noindent
    \textit{Hybrid $0$.} This corresponds to the protocol  $\Pi_{\tt H_0}^{\ecom}$, where $\simulator_0$ sits between the honest commiter $C$ and $R^*$, and it just forwards their messages. It follows trivially that
$M_{\Pi_{\mathsf{ECom}},C^*} \qc
    M_{\Pi_{\tt H_0}^{\ecom}, \simulator_0}$.

    \medskip\noindent
    \textit{Hybrid $1$.}
     $\simulator_1$ interacts with $R^*$ following the protocol $\Pi_{\tt H_1}^{\ecom}$, which is the same as $\Pi_{\tt H_0}^{\ecom}$ except that $\simulator_1$ uses the ZK simulator in Step $4$ and the decommitment phase.
From the computational zero-knowledge property, we have that
$    M_{\Pi_{\tt H_0}^{\ecom}, \simulator_0} \qc
    M_{\Pi_{\tt H_1}^{\ecom}, \simulator_1}$.

    \medskip\noindent
    \textit{Hybrid $2$.}
     $\simulator_2$ interacts with $R^*$ following the protocol $\Pi_{\tt H_2}^{\ecom}$, which is the same as $\Pi_{\tt H_1}^{\ecom}$ except that $\simulator_2$  sets $c^*$ to be a commitment to $0$.
It follows from the computationally-hiding property of the commitment scheme that
$    M_{\Pi_{\tt H_1}^{\ecom}, \simulator_1} \qc
    M_{\Pi_{\tt H_2}^{\ecom}, \simulator_2}$.

    \medskip\noindent
    \textit{Hybrid $3$.}  $\simulator_3$ interacts with $R^*$ following the protocol $\Pi_{\tt H_3}^{\ecom}$, which is the same as $\Pi_{\tt H_2}^{\ecom}$ except that $\simulator_3$ uses $\vec{\mu} = 0^{\ell}$ as the $\mathsf{cds.S}$ message.

    From the soundness of the ZK proof in Step $2$, we have that $c$ is not a commitment of $1$. In this case, by the security of CDS, $R^*$ does not receive $\vec{\mu}$, so the change of the message cannot be distinguished.

    Notice that Hybrid $3$ matches the description of the  simulator $\simulator$, and therefore
    $    M_{\Pi_{\tt H_2}^{\ecom}, \simulator_2} \qc
    M_{\funct{\socom}, \simulator}$.
    and this
    finishes the proof of the first part of our lemma.

\end{proof}

\newcommand{\textsf{MiniQCrypt}}{\textsf{MiniQCrypt}}

\section{Multiparty (Quantum) Computation in MiniQCrypt}
\label{sec:mpc}
Our quantum protocol realizing $\funct{\socom}$ from quantum-secure OWF allows us to combine existing results and realize
secure computation of any two-party or multi-party classical
functionality as well as quantum circuit in MiniQCrypt.

\begin{theorem}\label{thm:mpc}
  Assuming that post-quantum secure one-way functions exist, for every
  classical two-party and multi-party functionality $\mathcal{F}$, there is
  a quantum protocol \text{\tt C-QSA}-emulates $\mathcal{F}$.
\end{theorem}

\begin{proof}
  By Theorem~\ref{thm:ot}, we readily realize $\funct{\ot}$ in
  \textsf{MiniQCrypt}. In the $\funct{\ot}$-hybrid model, any classical functionality
  $\mathcal{F}$ can be realized statistically by a classical protocol in the
  universal-composable model~\cite{C:IshPraSah08}. The security can be
  lifted to the quantum universal-composable model as shown by
  Unruh~\cite{EC:Unruh10}. As a result, we also get a classical
  protocol in the $\funct{\ot}$-hybrid model that \text{\tt S-QSA} emulates
  $\mathcal{F}$. Plugging in the quantum protocol for $\funct{\ot}$, we obtain a
  quantum protocol that \text{\tt C-QSA}-emulates $\mathcal{F}$ assuming existence of
  quantum-secure one-way functions.
\end{proof}

Now that we have a protocol that realizes any classical functionality
in \textsf{MiniQCrypt}, we can instantiate $\mathcal{F}_{mpc}$ used in the work of
\cite{EC:DGJMS20} to achieve a protocol for secure multi-party quantum
computation where parties can jointly evaluate an arbitrary quantum
circuit on their private quantum input states. Specifically consider a
quantum circuit $Q$ with $k$ input registers. Let $\mathcal{F}_Q$ be the
ideal protocol where a trusted party receives private inputs from $k$
parties, evaluate $Q$, and then send the outputs to respective
parties. We obtain the following.

\begin{theorem}\label{thm:mpqc}
  Assuming that post-quantum secure one-way functions exist, for any
  quantum circuit $Q$, there is a quantum protocol that
  $\text{\tt C-QSA}$-emulates the $\mathcal{F}_Q$.
\end{theorem}

\bigskip

\paragraph{Acknowledgements.}
We thank the Simons Institute for the Theory of Computing for providing a meeting
place where the seeds of this work were planted. VV thanks Ran Canetti for
patiently answering his questions regarding universally composable commitments.

Most of this work was done when AG was affiliated to CWI and QuSoft.
HL was supported by NSF grants CNS-1528178, CNS-1929901, CNS-1936825 (CAREER), CNS-2026774, a Hellman Fellowship, a JP Morgan AI Research Award, the Defense Advanced Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No.\ W911NF-15-C-0236, and a subcontract No.\ 2017-002 through Galois. FS was supported by NSF grants CCF-2041841, CCF-2042414, and CCF-2054758 (CAREER). VV was supported by DARPA under Agreement No. HR00112020023, a grant from the MIT-IBM Watson AI, a grant from Analog Devices, a Microsoft Trustworthy AI grant, and a DARPA Young Faculty Award. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, DARPA, the National Science Foundation, or the U.S.\ Government.

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv