$(\mathsf{sk},\mathsf{rt})$. If $V$ rejects then the commitment $\mathsf{rt}$
is rejected and the protocol ends.

    2. 2.

Otherwise, choose at random $c\leftarrow\\{0,1\\}$.

    3. 3.

If $c=0$ then go to the $\mathsf{OPEN}$ phase.

    4. 4.

If $c=1$ then run the $\mathsf{Test}$ protocol, where the prover
$P_{\mathsf{Test}}$ takes as input
$(\mathsf{pk},\mathsf{rt},\mathbf{y},\bm{\rho})$ and the verifier
$V_{\mathsf{Test}}$ takes as input $(\mathsf{sk},\mathsf{rt})$. If
$V_{\mathsf{Test}}$ rejects then the commitment $\mathsf{rt}$ is rejected and
otherwise it is accepted. At the end of the $\mathsf{Test}$ protocol the
commitment protocol ends (the $\mathsf{Open}$ phase is not executed).

  * •

$\mathsf{OPEN}$ phase:

    1. 1.

$[{\mathsf{C}}\leftarrow{\mathsf{V}}]$: ${\mathsf{V}}$ sends a subset
$J\subseteq[\ell]$ and an opening basis $\mathbf{b}_{J}\in\\{0,1\\}^{|J|}$ to
${\mathsf{C}}$.

    2. 2.

$[{\mathsf{C}}\rightarrow{\mathsf{V}}]$: ${\mathsf{C}}$ computes
$(\mathbf{z},\bm{\rho}^{\prime})\leftarrow\mathsf{Open}(\bm{\rho},(J,\mathbf{b}_{J}))$
and sends $\mathbf{z}$ to ${\mathsf{V}}$.

    3. 3.

$[{\mathsf{V}}]$: ${\mathsf{V}}$ checks that
$\mathsf{Ver}(\mathsf{sk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{z})=1$, and
if so outputs
$\mathbf{m}\leftarrow\mathsf{Out}(\mathsf{sk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{z})$
as the decommitment bit. Otherwise, it outputs $\bot$.

###  5.2 Properties

We require that a commitment scheme satisfies two properties, correctness and
binding, defined below.

####  5.2.1 Correctness

We define the correctness guarantee separately for the non-succinct and the
succinct setting, starting with the former.

######  Definition 5.4 (Correctness).

A (non-succinct) classical commitment scheme is correct if for any
$\ell$-qubit quantum state $\bm{\sigma}$, and any basis
$\mathbf{b}=(b_{1},\dots,b_{\ell})\in\\{0,1\\}^{\ell}$,

$\mathsf{Real}(1^{\lambda},\bm{\sigma},\mathbf{b})\equiv\bm{\sigma}(\mathbf{b}),$
(9)

where $\bm{\sigma}(\mathbf{b})$ is the distribution obtained by measuring each
qubit $j$ of $\bm{\sigma}$ in the basis specified by $b_{j}$ (standard if
$b_{j}=0$, Hadamard if $b_{j}=1$), and
$\mathsf{Real}(1^{\lambda},\bm{\sigma},\mathbf{b})$ is the distribution
resulting from the following experiment:

  1. 1.

Generate
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})$.

  2. 2.

Generate
$(\mathbf{y},\bm{\rho})\leftarrow\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.

  3. 3.

Compute
$(\mathbf{z},\bm{\rho}^{\prime})\leftarrow\mathsf{Open}(\bm{\rho},\mathbf{b})$.

  4. 4.

If $\mathsf{Ver}(\mathsf{sk},\mathbf{y},\mathbf{b},\mathbf{z})=0$ then output
$\bot$.

  5. 5.

Otherwise, output
$\mathsf{Out}(\mathsf{sk},\mathbf{y},\mathbf{b},\mathbf{z})$.

######  Definition 5.5 (Succinct Correctness).

A succinct classical commitment scheme is correct if for any $\ell$-qubit
quantum state $\bm{\sigma}$, any basis
$\mathbf{b}=(b_{1},\dots,b_{\ell})\in\\{0,1\\}^{\ell},$ and any subset
$J\subseteq[\ell]$, the following two conditions holds:

$\mathsf{Real}_{c=0}(1^{\lambda},\bm{\sigma},J,\mathbf{b}_{J})\equiv\bm{\sigma}(J,\mathbf{b}_{J})~{}~{}\mbox{and}~{}~{}\mathsf{Real}_{c=1}(1^{\lambda},\bm{\sigma},J,\mathbf{b}_{J})\equiv
1$ (10)

where:

  * •

$\bm{\sigma}(J,\mathbf{b}_{J})$ is the distribution obtained by measuring each
qubit $j\in J$ of $\bm{\sigma}$ in the basis specified by $b_{j}$ (standard if
$b_{j}=0$ and Hadamard if $b_{j}=1$).

  * •

$\mathsf{Real}_{c=0}(1^{\lambda},\bm{\sigma},J,\mathbf{b}_{J}$) is the
distribution resulting from the following experiment:

    1. 1.

Generate $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$.

    2. 2.

Generate
$(\mathsf{rt},\mathbf{y},\bm{\rho})\leftarrow\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.

    3. 3.

Run the protocol $\mathsf{Ver}.\mathsf{Commit}$ between $P$ with input
$(\mathsf{pk},\mathsf{rt},\mathbf{y})$ and $V$ with input
$(\mathsf{sk},\mathsf{rt})$. If $V$ rejects then then output $\bot$.

    4. 4.

Otherwise, compute
$(\mathbf{z},\bm{\rho}^{\prime})\leftarrow\mathsf{Open}(\bm{\rho},(J,\mathbf{b}_{J}))$.

    5. 5.

If $\mathsf{Ver}(\mathsf{sk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{z})=0$
then output $\bot$.

    6. 6.

Otherwise, output
$\mathsf{Out}(\mathsf{sk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{z})$.

  * •

$\mathsf{Real}_{c=1}(1^{\lambda},\bm{\sigma},J,\mathbf{b}_{J}$) is the
distribution resulting from the following experiment:

    1. 1.

Generate $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$.

    2. 2.

Generate
$(\mathsf{rt},\mathbf{y},\bm{\rho})\leftarrow\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.

    3. 3.

Run the protocol $\mathsf{Ver}.\mathsf{Commit}$ between $P$ with input
$(\mathsf{pk},\mathsf{rt},\mathbf{y})$ and $V$ with input
$(\mathsf{sk},\mathsf{rt})$. If $V$ rejects then then output $\bot$.

    4. 4.

Execute $\mathsf{Test}$ where the prover $P_{\mathsf{Test}}$ takes as input
$(\mathsf{pk},\mathsf{rt},\mathbf{y},\bm{\rho})$ and the verifier
$V_{\mathsf{Test}}$ takes as input $(\mathsf{sk},\mathsf{rt})$. If
$V_{\mathsf{Test}}$ rejects then output $\bot$ and if it accepts then output
$1$.

####  5.2.2 Binding

In what follows we define the binding condition. Intuitively, our binding
guarantee is that a cheating committer cannot change the way they open based
on _any_ information they learn after the commitment phase, and that the
opening distribution is consistent with the distribution of a qubit.

For simplicity, we consider only cheating algorithms that are accepted with
high probability. This can be ensured by repetition. Namely, for every
$\epsilon,\delta>0$ by repeating the commitment and opening protocol
$O\left(\frac{\log(1/\epsilon)}{\delta}\right)$ times, if a cheating
${\mathsf{C}}^{*}$ is accepted in all of executions with probability at least
$\epsilon$ then a random execution is accepted with probability at least
$1-\delta$.

We first define the binding property for the (non-succinct) commitment and
then define it for the succinct commitment.

######  Definition 5.6 (Binding).

A classical (non-succinct) commitment scheme to a multi-qubit quantum state is
said to be computationally binding if there exists a $\mathsf{QPT}$ oracle
machine $\mathsf{Ext}$ such that for any $\mathsf{QPT}$ algorithm
${\mathsf{C}}^{*}.\mathsf{Commit}$, any $\mathsf{poly}(\lambda)$-size quantum
state $\bm{\sigma}$, any polynomial $\ell=\ell(\lambda)$, any basis
$\mathbf{b}=(b_{1},\ldots,b_{\ell})$, and any $\mathsf{QPT}$ algorithms
${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and ${\mathsf{C}}^{*}_{2}.\mathsf{Open}$,
for every $i\in\\{1,2\\}$

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},{\mathsf{C}}^{*}_{i}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle\eta}}{{\approx}}\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Commit},{\mathsf{C}}^{*}_{i}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
(11)

and

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},{\mathsf{C}}^{*}_{1}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle\eta}}{{\approx}}\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},{\mathsf{C}}^{*}_{2}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
(12)

where $\eta=O\left(\sqrt{\delta}\right)$ and

$\delta=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})\\\
(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})\end{subarray}}\max_{\begin{subarray}{c}i\in\\{1,2\\},\\\
\mathbf{b}^{\prime}\in\\{\mathbf{b},{\bf 0},{\bf
1\\}}\end{subarray}}\Pr[\mathsf{Ver}(\mathsf{sk},\mathbf{y},\mathbf{b}^{\prime},{\mathsf{C}}_{i}^{*}.\mathsf{Open}(\bm{\rho},\mathbf{b}^{\prime}))=0].$
(13)

and where
$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
is defined as follows:

  * •

$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})$.

  * •

$(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.

  1. 1.

Compute
$(\mathbf{z},\bm{\rho}^{\prime})\leftarrow{\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho},\mathbf{b})$.

  2. 2.

If $\mathsf{Ver}(\mathsf{sk},\mathbf{y},\mathbf{b},\mathbf{z})=0$ then output
$\bot$.

  3. 3.

Otherwise, let
$\mathbf{m}=\mathsf{Out}(\mathsf{sk},\mathbf{y},\mathbf{b},\mathbf{z})$.

  4. 4.

Output $(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m})$.

$\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Commit},{{\mathsf{C}}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
is defined as follows:

  1. 1.

$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})$.

  2. 2.

$(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.

  3. 3.

Let $\bm{\tau}_{{\cal A},{\cal
B}}=\mathsf{Ext}^{{\mathsf{C}}^{*}.\mathsf{Open}}(\mathsf{sk},\mathbf{y},\bm{\rho})$.

  4. 4.

Measure $\bm{\tau}_{\cal A}$ in the basis $\mathbf{b}=(b_{1},\ldots,b_{\ell})$
to obtain $\mathbf{m}\in\\{0,1\\}^{\ell}$.

  5. 5.

Output $(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m})$.

######  Remark 5.7.

Throughout this write-up to avoid cluttering of notation we omit the
superscript ${\mathsf{C}}^{*}.\mathsf{Commit}$ from

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})~{}~{}\mbox{
and
}~{}~{}\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Commit},{{\mathsf{C}}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma}),$

and denote these by

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})~{}~{}\mbox{
and
}~{}~{}\mathsf{Ideal}^{\mathsf{Ext},{{\mathsf{C}}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma}),$

respectively.

######  Remark 5.8.

We prove that our commitment scheme is sound with $\eta\leq 10\sqrt{\delta}$.
Note that $\delta$ is a bound on the probability that the openings of
${\mathsf{C}}^{*}_{i}.\mathsf{Open}$ are rejected not only on basis
$\mathbf{b}$, but also on basis ${\bf 0}$ and ${\bf 1}$. We note that for
Equation 12 we do not need to bound the probability that
${\mathsf{C}}^{*}_{i}.\mathsf{Open}$ is rejected on basis ${\bf 0}$ and basis
${\bf 1}$, and indeed we do not bound these probabilities in the proof (see
Lemma 7.10). The reason we need to bound these probabilities to prove Equation
11 is that our extractor uses the openings of
${\mathsf{C}}^{*}_{i}.\mathsf{Open}$ on basis ${\bf 0}$ and ${\bf 1}$ to
extract the quantum state.

######  Remark 5.9.

We mention that we prove a stronger condition than the one given in Equation
12. This is done in Lemma 7.10. The strengthening is due to two reasons.
First, we prove Equation 12 by induction on $\ell$, and for the induction step
to go through we need to strengthen the induction hypothesis, and as a result
we prove a stronger guarantee. Second, we allow the cheating algorithm
${\mathsf{C}}^{*}.\mathsf{Open}$ to depend on a part of the secret key
$\mathsf{sk}$. This is needed to obtain our succinct interactive argument for
QMA in Section 8.1 and is needed for our applications in Section 8.

Definition 5.6 assumes that ${\mathsf{C}}^{*}.\mathsf{Open}$ opens all the
qubits of the committed state. Indeed, we use ${\mathsf{C}}^{*}.\mathsf{Open}$
to extract an $\ell$-qubit quantum state. In what follows we define the notion
of binding for a succinct commitment, where ${\mathsf{C}}^{*}.\mathsf{Open}$
may only open to a subset $J\subseteq[\ell]$ of the qubits, and hence cannot
be used to extract the entire state (as was done in Definition 5.6). While we
can extract a state consisting of $|I|$ qubits from
${\mathsf{C}}^{*}.\mathsf{Open}$, for our applications we will need to extract
the entire $\ell$-qubit state, even if ${\mathsf{C}}^{*}.\mathsf{Open}$ only
opens to the qubits in $J$ (without blowing up the communication). This is
precisely the purpose of the $\mathsf{Ver}.\mathsf{Commit}$ protocol; instead
of extracting from ${\mathsf{C}}^{*}.\mathsf{Open}$ we extract from the
(cheating) prover $P^{*}$ of the $\mathsf{Ver}.\mathsf{Commit}$ protocol. We
note that even though $\mathsf{Ver}.\mathsf{Commit}$ is a succinct protocol,
its interactive nature will allow us to extract the (non-succinct)
$\ell$-qubit state from $P^{*}$.

######  Definition 5.10 (Succinct Binding).

A succinct classical commitment scheme to a multi-qubit quantum state is said
to be computationally binding if there exists a $\mathsf{QPT}$ oracle machine
$\mathsf{Ext}$ such that for any $\mathsf{QPT}$ algorithm
${\mathsf{C}}^{*}.\mathsf{Commit}$, any $\mathsf{poly}(\lambda)$-size quantum
state $\bm{\sigma}$, any polynomial $\ell=\ell(\lambda)$, any $\mathsf{QPT}$
prover $P^{*}$ for the $\mathsf{Ver}.\mathsf{Commit}$ protocol, any
$\mathsf{QPT}$ prover $P^{*}_{\mathsf{Test}}$ for the $\mathsf{Test}$
protocol, any $J\subseteq[\ell]$ and $\mathbf{b}_{J}=(b_{j})_{j\in
J}\in\\{0,1\\}^{|J|}$, any $\epsilon>0$, and any $\mathsf{QPT}$ algorithms
${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and ${\mathsf{C}}^{*}_{2}.\mathsf{Open}$,
for every $i\in\\{1,2\\}$

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},P^{*},{\mathsf{C}}^{*}_{i}.\mathsf{Open}}(\lambda,(J,\mathbf{b}_{J}),\bm{\sigma})\stackrel{{\scriptstyle\zeta}}{{\approx}}\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Commit},P^{*},P^{*}_{\mathsf{Test}}}(\lambda,(J,\mathbf{b}_{J}),\bm{\sigma},\epsilon)$
(14)

and

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},P^{*},{\mathsf{C}}^{*}_{1}.\mathsf{Open}}(\lambda,(J,\mathbf{b}_{J}),\bm{\sigma})\stackrel{{\scriptstyle\eta}}{{\approx}}\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},P^{*},{\mathsf{C}}^{*}_{2}.\mathsf{Open}}(\lambda,(J,\mathbf{b}_{J}),\bm{\sigma})$
(15)

where
$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Commit},P^{*},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,(J,\mathbf{b}_{J}),\bm{\sigma})$
is defined as follows:

  1. 1.

Generate $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$.

  2. 2.

Compute
$(\mathsf{rt},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.272727Note
that a malicious ${\mathsf{C}}^{*}.\mathsf{Commit}$ may choose $\mathsf{rt}$
maliciously without a corresponding non-succinct commitment string
$\mathbf{y}$. We assume without loss of generality that all the auxiliary
information it has about $\mathsf{rt}$ is encoded in $\bm{\rho}$.

  3. 3.

Compute the $\mathsf{Ver}.\mathsf{Commit}$ protocol between
$P^{*}(\mathsf{pk},\mathsf{rt},\bm{\rho})$ and $V(\mathsf{sk},\mathsf{rt})$.
If $V$ rejects then output $\bot$. Denote the resulting quantum state of
$P^{*}$ at the end of this protocol by $\bm{\rho}_{\mathsf{post}}$.282828If
$P^{*}$ was honest then it would have been classical and hence $\bm{\rho}$
would have remained unchanged. But since we are considering a malicious
$P^{*}$ it may alter its quantum state during the
$\mathsf{Ver}.\mathsf{Commit}$ protocol.

  4. 4.

Compute
$(\mathbf{z}_{J},\bm{\rho}^{\prime})\leftarrow{\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho}_{\mathsf{post}},(J,\mathbf{b}_{J}))$.

  5. 5.

If $\mathsf{Ver}(\mathsf{sk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{z}_{J})=0$
then output $\bot$.

  6. 6.

Otherwise, let
$\mathbf{m}_{J}=\mathsf{Out}(\mathsf{sk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{z})$.

  7. 7.

Output $(\mathsf{pk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{m}_{J})$.

Let $\delta_{0}$ be the probability that at the end of the protocol
$\mathsf{Ver}.\mathsf{Commit}$ the verifier rejects. Namely, $\delta_{0}$ is
the probability that Item 3 above outputs $\bot$. Denote by
$\bm{\rho}_{\mathsf{post}}$ the state of $P^{*}$ after the
$\mathsf{Ver}.\mathsf{Commit}$ protocol. Let $\delta^{\prime}_{0}$ be the
probability that the verifier $V_{\mathsf{Test}}(\mathsf{sk},\mathsf{rt})$
outputs $\bot$ in the $\mathsf{Test}$ protocol when interacting with
$P^{*}_{\mathsf{Test}}(\mathsf{pk},\mathsf{rt},\bm{\rho}_{\mathsf{post}})$.
Let

$\delta=\max_{i\in\\{1,2\\}}\Pr[\mathsf{Ver}(\mathsf{sk},\mathsf{rt},\mathbf{b}_{J},\mathbf{z}_{J})=0]~{}~{}\mbox{
and
}~{}\mathbf{z}={\mathsf{C}}^{*}_{i}.\mathsf{Open}(\bm{\rho}_{\mathsf{post}},\mathbf{b}_{J}),$
(16)

and let

$\eta=O\left(\sqrt{\delta_{0}+\delta}\right)~{}~{}\mbox{ and
}~{}~{}\zeta=O\left(\sqrt{\delta_{0}+\delta^{\prime}_{0}+\delta}\right)+\epsilon.$
(17)

$\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Commit},P^{*},P^{*}_{\mathsf{Test}}}(\lambda,(J,\mathbf{b}_{J}),\bm{\sigma},\epsilon)$
is defined as follows:

  1. 1.

Generate $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$.

  2. 2.

Compute
$(\mathsf{rt},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.

  3. 3.

Let $\bm{\tau}_{{\cal A},{\cal
B}}=\mathsf{Ext}^{P^{*},P^{*}_{\mathsf{Test}}}(\mathsf{sk},\mathsf{rt},\bm{\rho},1^{\lceil
1/\epsilon\rceil})$.

  4. 4.

Measure the $J$ qubits of $\bm{\tau}_{\cal A}$ in the basis $\mathbf{b}_{J}$
to obtain $\mathbf{m}_{J}\in\\{0,1\\}^{|J|}$.

  5. 5.

Output $(\mathsf{pk},\mathsf{rt},(J,\mathbf{b}_{J}),\mathbf{m}_{J})$.

######  Remark 5.11.

In the succinct soundness definition above we assume that $\ell=\ell(\lambda)$
is polynomial in the security parameter. We could also consider $\ell$ that is
super-polynomial in $\lambda$, in which case we will obtain binding assuming
the post-quantum $\ell$-security of the $\mathsf{LWE}$ assumption; i.e.,
assuming that a $\mathsf{poly}(\ell)$ size quantum circuit cannot break the
$\mathsf{LWE}$ assumption. The proof for a general (super-polynomial) $\ell$
is exactly the same as the one where $\ell=\mathsf{poly}(\lambda)$, the only
difference is that now we consider adversaries that run in
$\mathsf{poly}(\ell)$ time.

##  6 Constructions

In this section we present our constructions. We first construct a classical
commitment scheme for committing to a single qubit state. This can be found in
Section 6.1. Then, we show a generic transformation that converts any single-
qubit commitment scheme into a multi-qubit commitment scheme. This can be
found in Section 6.2. In this scheme the size of the public key and the size
of the commitments grow with the length of the quantum state committed to.
Finally, in Section 6.3 we show how to construct a succinct multi-qubit
commitment scheme, where the size of the public key as well as the size of the
commitment grows only with the security parameter (and poly-logarithmically
with the length of the quantum state committed to). We analyze these schemes
in Section 7.

###  6.1 Construction for Single Qubit States

In this subsection, we describe our commitment scheme for a quantum state that
consists of a single qubit, denoted by $\alpha_{0}\ket{0}+\alpha_{1}\ket{1}$.
We use as a building block the commitment algorithm $\mathsf{Commit_{\text{\em
W}}}$ from [Mah18] for the multi-qubit case. This algorithm makes use of a
$\mathsf{NTCF}$ family

$(\mathsf{Gen}_{\mathsf{NTCF}},\mathsf{Eval}_{\mathsf{NTCF}},\mathsf{Invert}_{\mathsf{NTCF}},\mathsf{Check}_{\mathsf{NTCF}},\mathsf{Good}_{\mathsf{NTCF}}).$

The public key $\mathsf{pk}$ used by $\mathsf{Commit_{\text{\em W}}}$ to
commit to an $\ell$-qubit state is of the form
$\mathsf{pk}=(\mathsf{pk}_{1},\ldots,\mathsf{pk}_{\ell})$ where each
$\mathsf{pk}_{j}$ is a public key generated by
$\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$.292929We mention that [Mah18] used
a dual mode $\mathsf{NTCF}$ family, where each $\mathsf{pk}_{i}$ is generated
either in an injective mode in a two-to-one mode, depending on the opening
basis which is assumed to fixed ahead of time. The $\mathsf{QPT}$ algorithm

$\mathsf{Commit_{\text{\em
W}}}\left((\mathsf{pk}_{1},\ldots,\mathsf{pk}_{\ell}),\sum_{\mathbf{s}\in\\{0,1\\}^{\ell}}\alpha_{\mathbf{s}}\ket{\mathbf{s}}_{\cal
S}\right)$

outputs the following:

  1. 1.

A measurement outcome $\mathbf{y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{\ell})$,
where each $\mathbf{y}_{j}\in\mathsf{R_{\mathsf{pk}_{j}}}$.

  2. 2.

A state $\ket{\varphi}$ such that

$\ket{\varphi}\equiv\sum_{\mathbf{s}\in\\{0,1\\}^{\ell}}\alpha_{\mathbf{s}}\ket{\mathbf{s}}_{\cal
S}\ket{\mathbf{x}_{\mathbf{s}}}_{\cal Z},$ (18)

where
$\mathbf{x}_{\mathbf{s}}=(\mathbf{x}_{s_{1}}\dots,\mathbf{x}_{s_{\ell}})$
where each $\mathbf{x}_{s_{j}}\in\mathsf{D_{\mathsf{pk}_{j}}}$ and is such
that

$\mathbf{y}_{j}\in\mathsf{Supp}(\mathsf{Eval}(\mathsf{pk}_{j},s_{j},\mathbf{x}_{s_{j}})).$

######  Construction 6.1 (Commitment Scheme).

Our construction uses a noisy trapdoor claw-free ($\mathsf{NTCF}$) function
family
$(\mathsf{Gen}_{\mathsf{NTCF}},\mathsf{Eval}_{\mathsf{NTCF}},\mathsf{Invert}_{\mathsf{NTCF}},\mathsf{Check}_{\mathsf{NTCF}},\mathsf{Good}_{\mathsf{NTCF}})$
and the algorithm $\mathsf{Commit_{\text{\em W}}}$ defined above. Our
algorithms are defined as follows:

  * •

$\mathsf{Gen}(1^{\lambda}):$

    1. 1.

For every $i\in\\{0,1,\ldots,n+1\\}$ sample
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$,
where $n=n(\lambda)$ is such that the domain of each trapdoor claw-free
function is a subset of $\\{0,1\\}^{n}$.

    2. 2.

Let $\mathsf{pk}=(\mathsf{pk}_{0},\mathsf{pk}_{1},\ldots,\mathsf{pk}_{n+1})$
and $\mathsf{sk}=(\mathsf{sk}_{0},\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1})$.

    3. 3.

Output $(\mathsf{pk},\mathsf{sk})$.

  * •

$\mathsf{Commit}(\mathsf{pk},\alpha_{0}\ket{0}+\alpha_{1}\ket{1}):$

    1. 1.

Parse $\mathsf{pk}=(\mathsf{pk}_{0},\mathsf{pk}_{1},\ldots,\mathsf{pk}_{n+1})$

    2. 2.

Compute $(\mathbf{y}_{0},\ket{\varphi_{0}})\leftarrow\mathsf{Commit_{\text{\em
W}}}(\mathsf{pk}_{0},\alpha_{0}\ket{0}+\alpha_{1}\ket{1})$, where

$\ket{\varphi_{0}}_{{\cal S},{\cal
Z}}\equiv\sum_{s\in\\{0,1\\}}\alpha_{s}\ket{s}_{{\cal
S}}\ket{\mathbf{x}_{s}}_{{\cal Z}}$

Here, $\mathbf{x}_{s}\in\\{0,1\\}^{n}$ and
$\mathbf{y}_{0}\in\mathsf{Supp}(\mathsf{Eval}_{\mathsf{NTCF}}(\mathsf{pk}_{0},s,\mathbf{x}_{s}))$
for every $s\in\\{0,1\\}$. Note that register ${\cal S}$ consists of $1$ qubit
and ${\cal Z}$ consists of $n$ qubits.

    3. 3.

Apply the Hadamard unitary $H^{\otimes(n+1)}$ to $\ket{\varphi_{0}}$ to obtain

$\displaystyle\ket{\varphi_{1}}_{{\cal S},{\cal Z}}$
$\displaystyle=H^{\otimes(n+1)}\ket{\varphi_{0}}$
$\displaystyle\equiv\frac{1}{\sqrt{2^{n+1}}}\sum_{\mathbf{d}\in\\{0,1\\}^{n+1}}\underbrace{(-1)^{\mathbf{d}\cdot(0,\mathbf{x}_{0})}(\alpha_{0}+(-1)^{\mathbf{d}\cdot(1,\mathbf{x}_{0}\oplus\mathbf{x}_{1})}\alpha_{1})}_{\beta_{\mathbf{d}}}\ket{\mathbf{d}}_{{\cal
S},{\cal Z}}$

    4. 4.

Apply the algorithm $\mathsf{Commit_{\text{\em W}}}$ with $\mathsf{pk}_{1}$ to
register ${\cal S}$ of $\ket{\varphi_{1}}_{{\cal S},{\cal Z}}$, and for every
$i\in\\{2,\ldots,n+1\\}$ apply $\mathsf{Commit_{\text{\em W}}}$ with
$\mathsf{pk}_{i}$ to register ${\cal Z}_{i}$ of $\ket{\varphi_{1}}_{{\cal
S},{\cal Z}}$. Denote the output by $(\mathbf{y}_{1},\ldots,\mathbf{y}_{n+1})$
and the resulting state by

$\ket{\varphi_{2}}_{{\cal S},{\cal Z},{\cal
Z}^{\prime}}\equiv\frac{1}{\sqrt{2^{n+1}}}\sum_{\mathbf{d}\in\\{0,1\\}^{n+1}}\beta_{\mathbf{d}}\ket{\mathbf{d}}_{{\cal
S},{\cal
Z}}\ket{\mathbf{x}^{\prime}_{1,d_{1}},\mathbf{x}^{\prime}_{2,d_{2}},\ldots,\mathbf{x}^{\prime}_{n+1,d_{n+1}}}_{{\cal
Z}^{\prime}}$

where for every $i\in\\{1,\ldots,n+1\\}$ and every $d_{i}\in\\{0,1\\}$,

$\mathbf{y}_{i}\in\mathsf{Supp}(\mathsf{Eval}_{\mathsf{NTCF}}(\mathsf{pk}_{i},d_{i},\mathbf{x}^{\prime}_{i,d_{i}})).$

Note that the ${\cal Z}^{\prime}$ register consists of $n\cdot(n+1)$ qubits,
and we partition these qubits to registers ${\cal Z}^{\prime}_{1},\ldots,{\cal
Z}^{\prime}_{n+1}$, each consisting of $n$ qubits.

    5. 5.

Rename the register ${\cal S}$ to ${\cal Z}_{1}$ and split the register ${\cal
Z}$ into registers ${\cal Z}_{2},\dots,{\cal Z}_{n+1}$ of $1$ qubit each.
Permute the registers to obtain a state $\ket{\varphi_{3}}$ such that

$\ket{\varphi_{3}}\equiv\frac{1}{\sqrt{2^{n+1}}}\sum_{\mathbf{d}\in\\{0,1\\}^{n+1}}\beta_{\mathbf{d}}\ket{d_{1}}_{{\cal
Z}_{1}}\ket{\mathbf{x}^{\prime}_{1,d_{1}}}_{{\cal
Z}^{\prime}_{1}}\dots\ket{d_{n+1}}_{{\cal
Z}_{n+1}}\ket{\mathbf{x}^{\prime}_{n+1,d_{n+1}}}_{{\cal Z}^{\prime}_{n+1}}$

    6. 6.

Output $(\mathbf{y}_{0},\mathbf{y}_{1},\ldots,\mathbf{y}_{n+1})$ and
$\ket{\varphi_{3}}$.

  * •

$\mathsf{Open}(\ket{\varphi},b)$:

If $b=1$ (corresponding to an opening in the Hadamard basis) then output the
measurement of $\ket{\varphi}$ in the standard basis, and if $b=0$
(corresponding an opening in the standard basis) then output the measurement
of $\ket{\varphi}$ in the Hadamard basis.

  * •

$\mathsf{Ver}(\mathsf{sk},\mathbf{y},b,\mathbf{z})$:

    1. 1.

Parse
$\mathsf{sk}=(\mathsf{sk}_{0},\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1})$.

    2. 2.

Parse $\mathbf{y}=(\mathbf{y}_{0},\mathbf{y}_{1},\ldots,\mathbf{y}_{n+1})$.

    3. 3.

If $b=1$ then do the following:

      1. (a)

Parse
$\mathbf{z}=(d_{1},\mathbf{x}^{\prime}_{1},\dots,d_{n+1},\mathbf{x}^{\prime}_{n+1})$
and let $\mathbf{d}=(d_{1},\ldots,d_{n+1})$.

      2. (b)

Compute
$((0,\mathbf{x}_{0}),(1,\mathbf{x}_{1}))=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{0},\mathbf{y}_{0})$.

      3. (c)

Verify that

         * –

$\mathsf{Check}_{\mathsf{NTCF}}({\mathsf{pk}_{i},d_{i},\mathbf{x}^{\prime}_{i},\mathbf{y}_{i}})=1$
for every $i\in\\{1,\ldots,n+1\\}$.

         * –

$\mathbf{d}\in\mathsf{Good}_{\mathbf{x}_{0},\mathbf{x}_{1}}$.

If any of these checks does not hold output $0$ and otherwise output $1$.

    4. 4.

If $b=0$ then do the following:

      1. (a)

Parse $\mathbf{z}=(\mathbf{z}_{1},\ldots,\mathbf{z}_{n+1})$ where each
$\mathbf{z}_{i}\in\\{0,1\\}^{n+1}$.

      2. (b)

For every $i\in\\{1,\ldots,n+1\\}$ compute
$((0,\mathbf{x}^{\prime}_{i,0}),(1,\mathbf{x}^{\prime}_{i,1}))=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{i},\mathbf{y}_{i})$.

      3. (c)

If there exists $i\in[n+1]$ such that
$\mathbf{z}_{i}\notin\mathsf{Good}_{\mathbf{x}^{\prime}_{i,0},\mathbf{x}^{\prime}_{i,1}}$
then output $0$.

      4. (d)

Else, for every $i\in[n+1]$ let
$m_{i}=\mathbf{z}_{i}\cdot(1,\mathbf{x}^{\prime}_{i,0}\oplus\mathbf{x}^{\prime}_{i,1})$.

      5. (e)

If
$\mathsf{Check}_{\mathsf{NTCF}}(\mathsf{pk}_{0},m_{1},(m_{2},\dots,m_{n+1}),\mathbf{y}_{0})\neq
1$, output $0$. Else, output $1$

  * •

$\mathsf{Out}(\mathsf{sk},\mathbf{y},b,\mathbf{z})$:

    1. 1.

Parse
$\mathsf{sk}=(\mathsf{sk}_{0},\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1})$.

    2. 2.

Parse $\mathbf{y}=(\mathbf{y}_{0},\mathbf{y}_{1},\ldots,\mathbf{y}_{n+1})$.

    3. 3.

If $b=1$:

      1. (a)

Compute
$((0,\mathbf{x}_{0}),(1,\mathbf{x}_{1}))=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{0},\mathbf{y}_{0})$.

      2. (b)

Parse
$\mathbf{z}=(d_{1},\mathbf{x}^{\prime}_{1},\dots,d_{n+1},\mathbf{x}^{\prime}_{n+1})$
and let $\mathbf{d}=(d_{1},\ldots,d_{n+1})$.

      3. (c)

Output $m=\mathbf{d}\cdot(1,\mathbf{x}_{0}\oplus\mathbf{x}_{1})$.

    4. 4.

If $b=0$:

      1. (a)

Parse $\mathbf{z}=(\mathbf{z}_{1},\ldots,\mathbf{z}_{n+1})$.

      2. (b)

Compute
$((0,\mathbf{x}^{\prime}_{1,0}),(1,\mathbf{x}^{\prime}_{1,1}))=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{1},\mathbf{y}_{1})$.

      3. (c)

Output
$m_{1}=\mathbf{z}_{1}\cdot(1,\mathbf{x}^{\prime}_{1,0}\oplus\mathbf{x}^{\prime}_{1,1})$.

###  6.2 Construction of Commmitments for Multi-Qubit States

There are two ways one can extend our single-qubit commitment scheme to the
multi-qubit setting. The first is to commit to an $\ell$-qubit state qubit-by-
qubit by generating $\ell$ key pairs and using the $i$’th key pair to commit
and open to the $i$’th qubit. This construction results with key size and
commitment size that grow linearly with $\ell$, and is presented below. The
second approach is to extend our single qubit commitment scheme to a succinct
multi-qubit commitment scheme. This is done in two steps. First, we construct
a semi-succinct multi-qubit commitment scheme, which is the same as the non-
succinct one, except that we generate a single key pair
$(\mathsf{pk},\mathsf{sk})$ and commit to each of the $\ell$ qubits using the
same public key $\mathsf{pk}$. This results with a commitment string
$(\mathbf{y}_{1},\ldots,\mathbf{y}_{\ell})$. Then we show how to convert the
semi-succinct commitment scheme into a succinct one. We elaborate on this
approach in Section 6.3.

######  Construction 6.2 (Scheme for Multi-Qubit States).

Given any single-qubit commitment scheme
$(\mathsf{Gen}_{1},\mathsf{Commit}_{1},\mathsf{Open}_{1},\mathsf{Ver}_{1},\mathsf{Out}_{1})$
we construct a multi-qubit commitment scheme consisting of algorithms

$(\mathsf{Gen},\mathsf{Commit},\mathsf{Open},\mathsf{Ver},\mathsf{Out})$

defined as follows, where we define
$(\mathsf{Open},\mathsf{Ver},\mathsf{Out})$ to operate one qubit at a time
(see Remark 5.2):

  * •

$\mathsf{Gen}(1^{\lambda},1^{\ell})$:

    1. 1.

For every $i\in[\ell]$ sample
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}_{1}(1^{\lambda})$.

    2. 2.

Let $\mathsf{pk}=(\mathsf{pk}_{1},\dots,\mathsf{pk}_{\ell})$ and
$\mathsf{sk}=(\mathsf{sk}_{1},\dots,\mathsf{sk}_{\ell})$.

    3. 3.

Output $(\mathsf{pk},\mathsf{sk})$.

  * •

$\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$:

    1. 1.

Parse $\mathsf{pk}=(\mathsf{pk}_{1},\dots,\mathsf{pk}_{\ell})$.

    2. 2.

We assume that $\bm{\sigma}$ is an $\ell$-qubit state, and we denote the
$\ell$ registers of $\bm{\sigma}$ by ${\cal S}_{1},\ldots,{\cal S}_{\ell}$.

    3. 3.

Execute the following steps:

      1. (a)

Let $\bm{\rho}_{0}=\bm{\sigma}$.

      2. (b)

For every $j\in\\{1,\ldots,\ell\\}$, apply $\mathsf{Commit}_{1}$ with key
$\mathsf{pk}_{j}$ to register ${\cal S}_{j}$ of the state $\bm{\rho}_{j-1}$,
obtaining an outcome $\mathbf{y}_{j}$ and a post-measurement state
$(\bm{\rho}_{j})_{{\cal S}_{1},\dots,{\cal S}_{\ell},{\cal Z}_{1}\dots,{\cal
Z}_{j}}$.

    4. 4.

Output $(\mathbf{y},(\bm{\rho}_{\ell})_{{\cal S}_{1}\dots\cal S_{\ell},{\cal
Z}_{1},\dots\cal Z_{\ell}})$, where
$\mathbf{y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{\ell})$.

  * •

$\mathsf{Open}(\bm{\rho}_{{\cal S}_{1}\dots\cal S_{\ell},{\cal
Z}_{1},\dots\cal Z_{\ell}},(j,b_{j}))$:

    1. 1.

Apply $\mathsf{Open}_{1}$ with basis $b_{j}$ to registers $\\{{\cal
S}_{j},{\cal Z}_{j}\\}$ of $\bm{\rho}_{{\cal S}_{1}\dots\cal S_{\ell},{\cal
Z}_{1},\dots\cal Z_{\ell}}$, obtaining an outcome $\mathbf{z}_{j}$ and post-
measurement state $\bm{\rho}^{\prime}_{j}$ .

    2. 2.

Output $(\mathbf{z}_{j},\bm{\rho}^{\prime}_{j})$.

  * •

$\mathsf{Ver}(\mathsf{sk},\mathbf{y},(j,b_{j}),\mathbf{z}_{j})$:

    1. 1.

Parse $\mathsf{sk}=(\mathsf{sk}_{1},\dots,\mathsf{sk}_{\ell})$ and
$\mathbf{y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{\ell})$.

    2. 2.

Output
$\mathsf{Ver}_{1}(\mathsf{sk}_{j},\mathbf{y}_{j},b_{j},\mathbf{z}_{j})$.

  * •

$\mathsf{Out}(\mathsf{sk},\mathbf{y},(j,b_{j}),\mathbf{z}_{j})$:

    1. 1.

Parse $\mathsf{sk}=(\mathsf{sk}_{1},\dots,\mathsf{sk}_{\ell})$,
$\mathbf{y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{\ell})$.

    2. 2.

Output
$m_{j}\leftarrow\mathsf{Out}_{1}(\mathsf{sk}_{j},\mathbf{y}_{j},b_{j},\mathbf{z}_{j})$.

We consider a semi-succinct version of the commitment scheme described above,
which is used as a stepping stone for proving soundness of the fully succinct
commitment scheme constructed in Section 6.3, below.

######  Definition 6.3.

A semi-succinct classical commitment scheme to quantum states is a commitment
scheme obtained from a single qubit commitment scheme by applying the
algorithms qubit-by-qubit, as in Construction 6.2, but with a single public
key $\mathsf{pk}$. Namely, it is similar to Construction 6.2 but where
$\mathsf{Gen}$ generates a single key pair
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}_{1}(1^{\lambda})$ (as opposed
to $\ell$ such pairs), and sets
$(\mathsf{pk}_{i},\mathsf{sk}_{i})=(\mathsf{pk},\mathsf{sk})$ for every
$i\in[\ell]$.

######  Remark 6.4.

In Section 7.2, when we prove that our (non-succinct and semi-succinct) multi-
qubit commitment scheme satisfies the binding property, we assume that
${\mathsf{C}}^{*}.\mathsf{Open}$ successfully opens all the $\ell$ qubits in
the standard basis with high probability, and successfully opens all the
$\ell$ qubits in the Hadamard basis with high probability $1-\delta$. Namely,
we assume that for every $b\in\\{0,1\\}$,
${\mathsf{C}}^{*}.\mathsf{Open}\left(\bm{\rho},b^{\ell}\right)$ generates an
accepting opening with probability $1-\delta$. To ensure that this assumption
holds, we repeat the commitment phase $O(\lfloor{1/\delta\rfloor})$
times.303030We assume that ${\mathsf{C}}.\mathsf{Commit}$ can generate
$\bm{\sigma}^{\otimes\lfloor{1/\delta}\rfloor}$. For each of these
commitments, we ask ${\mathsf{C}}^{*}.\mathsf{Open}$ with probability $1/3$ to
open all the qubits in the standard basis, with probability $1/3$ to open all
the qubits in the Hadamard basis, and with probability $1/3$ to open in
desired basis $\mathbf{b}\in\\{0,1\\}^{\ell}$.

We emphasize that even if ${\mathsf{C}}^{*}.\mathsf{Open}$ opens only a small
subset of the qubits, we still require that
${\mathsf{C}}^{*}.\mathsf{Open}\left(\bm{\rho},b^{\ell}\right)$ generates a
valid opening for every $b\in\\{0,1\\}$. The reason is that our binding
property states that there exists an extractor ${\cal E}$ that uses any
${\mathsf{C}}^{*}.\mathsf{Open}$ to extract a state $\bm{\tau}$. We want the
guarantee that even if ${\mathsf{C}}^{*}.\mathsf{Open}$ only opens a small
subset, still the extractor can extract an $\ell$-qubit state $\bm{\tau}$.
This is important in some applications, such as compiling any quantum $X/Z$
$\mathsf{PCP}$ into a succinct interactive argument (see Section 8.2).
Importantly, we need to do this without increasing the communication
complexity in the opening phase, and in particular it should not grow with
$\ell$. In what follows we show how this can be done succinctly.

###  6.3 Construction of Succinct Multi-Qubit Commitments

Before we present our construction of a succinct multi-qubit commitment
scheme, we define one of the main building blocks used in our construction.

##### State-Preserving Succinct Arguments of Knowledge

Our scheme uses a state-preserving succinct argument of knowledge system,
defined and constructed in [LMS22].

######  Definition 6.5.

[LMS22] A publicly verifiable argument system $\Pi$ for an $\mathsf{NP}$
language ${\cal L}$ (with witness relation $\mathcal{R}$) is an
$\epsilon$-state-preserving succinct argument-of-knowledge if it satisfies the
following properties.

  * •

Succinctness: when invoked on a security parameter $\lambda$, instance size
$n$, and a relation $\mathcal{R}$ decidable in time $T$, the communication
complexity of the protocol is $\mathsf{poly}(\lambda,\log T)$. The verifier
computational complexity is $\mathsf{poly}(\lambda,\log T)+\tilde{O}(n)$.

  * •

State-Preserving Extraction. There exists an extractor ${\cal E}$, with oracle
access to a cheating prover $P^{*}$ and a corresponding quantum state
$\bm{\rho}$, with the following properties:

    * –

Efficiency: ${\cal E}$ on input $(\mathbf{x},1^{\lambda},\epsilon)$ runs in
time $\mathsf{poly}(|\mathbf{x}|,\lambda,1/\epsilon)$, and outputs a classical
transcript $\mathbb{T}_{\mathsf{Sim}}$, a classical string $\mathbf{w}$, and a
residual state $\bm{\rho}_{\mathsf{Sim}}$.

    * –

State-preserving: The following two games are $\varepsilon$-indistinguishable
to any $\mathsf{QPT}$ distinguisher:

      * *

Game 0 (Real): Generate a transcript $\mathbb{T}$ by running
$P^{*}(\bm{\rho},\mathbf{x})$ with the honest verifier $V$. Output
$\mathbb{T}$ along with the residual state $\bm{\rho}^{\prime}$.

      * *

Game 1 (Simulated): Generate
$((\mathbb{T}_{\mathsf{Sim}},\mathbf{w}),\bm{\rho}_{\mathsf{Sim}})\leftarrow{\cal
E}^{P^{*},\bm{\rho}}(\mathbf{x},1^{\lambda},\epsilon)$. Output
$(\mathbb{T}_{\mathsf{Sim}},\bm{\rho}_{\mathsf{Sim}})$.

    * –

Extraction correctness: for any $P^{*}$ as above, the probability that
$\mathbb{T}_{\mathsf{Sim}}$ is an accepting transcript but $\mathbf{w}$ is
_not_ in $\mathcal{R}_{\mathbf{x}}$ is at most
$\epsilon+\mathsf{negl}(\lambda)$.

The following is an immediate corollary.

######  Corollary 6.6.

An $\epsilon$-state-preserving succinct argument-of-knowledge protocol for an
$\mathsf{NP}$ language ${\cal L}$ (with witness relation $\mathcal{R}$) and
extractor ${\cal E}$ satisfies that for every cheating prover $P^{*}$ and a
corresponding quantum state $\bm{\rho}$, and every $\mathbf{x}$, if
$P^{*}(\bm{\rho},\mathbf{x})$ convinces the verifier $V$ to accept with
probability $1-\delta$ then for

$((\mathbb{T}_{\mathsf{Sim}},\mathbf{w}),\bm{\rho}_{\mathsf{Sim}})\leftarrow{\cal
E}^{P^{*},\bm{\rho}}(\mathbf{x},1^{\lambda},\epsilon),$

$\Pr[(\mathbf{x},\mathbf{w})\in{\cal R}]\geq
1-\delta-2\epsilon-\mathsf{negl}(\lambda)$.

######  Theorem 6.7 ([LMS22]).

Assuming the post-quantum $\mathsf{poly}(\lambda,1/\epsilon)$ hardness of
learning with errors, there exists a (4-message, public coin) $\epsilon$-state
preserving succinct argument of knowledge for $\mathsf{NP}$.

####  6.3.1 Construction

We are now ready to present our construction of a succinct classical
commitment for multi-qubit quantum states. Our construction uses the following
ingredients:

  * •

Collapsing hash family with local opening
$(\mathsf{Gen}_{\mathsf{H}},\mathsf{Eval}_{\mathsf{H}},\mathsf{Open}_{\mathsf{H}},\mathsf{Ver}_{\mathsf{H}})$,
as defined in Definitions 3.4 and 3.6.

  * •

A semi-succinct commitment scheme
$(\mathsf{Gen}_{\mathbf{ss}},\mathsf{Commit}_{\mathbf{ss}},\mathsf{Open}_{\mathbf{ss}},\mathsf{Ver}_{\mathbf{ss}},\mathsf{Out}_{\mathbf{ss}})$,
as defined in Definition 6.3, corresponding to an underlying single-qubit
commitment scheme

$(\mathsf{Gen}_{1},\mathsf{Commit}_{1},\mathsf{Open}_{1},\mathsf{Ver}_{1},\mathsf{Out}_{1})$

  * •

An $\epsilon$-state-preserving succinct argument of knowledge protocol
$(P,V)$, as defined in Definition 6.5, for the $\mathsf{NP}$ languages ${\cal
L}^{*}$ and ${\cal L}^{**}$ with a corresponding $\mathsf{NP}$ relations
$\mathcal{R}_{{\cal L}^{*}}$ and $\mathcal{R}_{{\cal L}^{**}}$, respectively,
defined as follows:

$((\mathsf{hk},\mathsf{rt}),\mathbf{y})\in\mathcal{R}_{{\cal L}^{*}}~{}\mbox{
if and only if
}~{}\mathsf{Eval}_{\mathsf{H}}(\mathsf{hk},\mathbf{y})=\mathsf{rt}$ (19)

and

$((\mathsf{sk}_{1},\mathsf{hk},\mathsf{rt},\mathsf{rt}^{\prime},b),(\mathbf{y},\mathbf{z}))\in\mathcal{R}_{{\cal
L}^{**}}$

if and only if

$\mathsf{Eval}_{\mathsf{H}}(\mathsf{hk},\mathbf{y})=\mathsf{rt}~{}\wedge~{}\mathsf{Eval}_{\mathsf{H}}(\mathsf{hk},\mathbf{z})=\mathsf{rt}^{\prime}~{}\wedge~{}\mathsf{Ver}_{\mathbf{ss}}\left(\mathsf{sk}_{1},\mathbf{y},b^{\ell},\mathbf{z}\right)=1.$

######  Construction 6.8 (Succinct Commitment to Multi-Qubit Quantum States).

In what follows we use the ingredients above to construct a succinct
commitment scheme to multi-qubit quantum states.

  * •

$\mathsf{Gen}(1^{\lambda})$:

    1. 1.

Sample
$(\mathsf{pk}_{1},\mathsf{sk}_{1})\leftarrow\mathsf{Gen}_{1}(1^{\lambda})$.

    2. 2.

Sample $\mathsf{hk}\leftarrow\mathsf{Gen}_{\mathsf{H}}(1^{\lambda})$.

    3. 3.

Let $\mathsf{pk}=(\mathsf{pk}_{1},\mathsf{hk})$ and
$\mathsf{sk}=(\mathsf{sk}_{1},\mathsf{hk})$.

    4. 4.

Output $(\mathsf{pk},\mathsf{sk})$.

  * •

$\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$:

    1. 1.

Parse $\mathsf{pk}=(\mathsf{pk}_{1},\mathsf{hk})$.

    2. 2.

Compute
$(\mathbf{y},\bm{\rho})\leftarrow\mathsf{Commit}_{\mathbf{ss}}(\mathsf{pk}_{1},\bm{\sigma})$.

    3. 3.

Let $\mathsf{rt}=\mathsf{Eval}_{\mathsf{H}}(\mathsf{hk},\mathbf{y})$.

    4. 4.

Output $(\mathsf{rt},\mathbf{y},\bm{\rho})$.

  * •

$\mathsf{Ver}.\mathsf{Commit}$ runs the $\epsilon$-state-preserving succinct
argument of knowledge protocol for the $\mathsf{NP}$ language ${\cal L}^{*}$,
where $P$ and $V$ take as input the instance $(\mathsf{hk},\mathsf{rt})$ and
$P$ takes an additional input the witness $\mathbf{y}$.313131Note that in this
protocol both the prover and the verifier are classical. If $V$ rejects then
this commitment string $\mathsf{rt}$ is declared invalid, and the protocol
aborts.

  * •

$\mathsf{Test}$ is an interactive protocol between $P_{\mathsf{Test}}$ with
input $(\mathsf{pk},\mathsf{rt},\mathbf{y},\bm{\rho})$ and $V_{\mathsf{Test}}$
with input $(\mathsf{sk},\mathsf{rt})$ that proceeds as follows:

    1. 1.

$V_{\mathsf{Test}}$ samples a uniformly random bit $b\leftarrow\\{0,1\\}$, and
sends $b$ to $P_{\mathsf{Test}}$.

    2. 2.

$P_{\mathsf{Test}}$ generates
$\mathbf{z}\leftarrow\mathsf{Open}_{\mathbf{ss}}\left(\bm{\rho},b^{\ell}\right)$
and sends
$\mathsf{rt}^{\prime}=\mathsf{Eval}_{\mathsf{H}}(\mathsf{hk},\mathbf{z})$ to
$V_{\mathsf{Test}}$.

    3. 3.

Run the $\epsilon$-state-preserving succinct argument of knowledge protocol
for the $\mathsf{NP}$ language ${\cal L}^{*}$, where $P$ and $V$ take as input
the instance $(\mathsf{hk},\mathsf{rt}^{\prime})$ and $P$ takes the additional
input $\mathbf{z}$. If $V$ rejects then this commitment is declared invalid
and the protocol aborts.

    4. 4.

$V_{\mathsf{Test}}$ sends $\mathsf{sk}_{1}$ to the prover.

    5. 5.

Run the $\epsilon$-preserving succinct argument of knowledge protocol $(P,V)$
for the $\mathsf{NP}$ language ${\cal L}^{**}$, where $P$ and $V$ take as
input the instance
$(\mathsf{sk}_{1},\mathsf{hk},\mathsf{rt},\mathsf{rt}^{\prime},b)$ and $P$
takes as additional input the witness $(\mathbf{y},\mathbf{z})$. If $V$
rejects then this commitment is declared invalid.

    6. 6.

If $V$ accepts in both steps 2 and 4 above then $V_{\mathsf{Test}}$ outputs
$1$, and otherwise it outputs $0$.

######  Remark 6.9.

Note that the $\mathsf{Test}$ protocols runs the $\epsilon$-state-preserving
succinct argument of knowledge twice: once to prove knowledge of $\mathbf{z}$
and once to prove knowledge of $(\mathbf{y},\mathbf{z})$. It may seem that it
suffices to run this protocol once, since there is no need to prove knowledge
of $\mathbf{z}$ twice. However, in the first protocol the cheating prover does
not know $\mathsf{sk}_{1}$ and hence the $\mathbf{z}$ that is extracted, using
the extractor from Definition 6.5, can be efficiently computed without knowing
$\mathsf{sk}_{1}$. Then we use the security guarantee of the underlying
collision resistant hash family to argue that the vector $\mathbf{z}$
extracted from the second protocol is identical to that extracted from the
first protocol, and hence can be computed efficiently without knowing
$\mathsf{sk}_{1}$. This fact is crucial for the soundness proof to go through.

  * •

$\mathsf{Open}((\bm{\rho},\mathsf{hk},\mathbf{y}),(j,b_{j}))$:

    1. 1.

Parse $\mathbf{y}=(\mathbf{y}_{1},\ldots,\mathbf{y}_{\ell})$.

    2. 2.

Compute
$\mathbf{o}_{j}=\mathsf{Open}_{\mathsf{H}}(\mathsf{hk},\mathbf{y},j)$.323232$\mathsf{Open}_{\mathsf{H}}(\mathsf{hk},\mathbf{y},j)$
denotes an opening to the $j$’th chunk of the preimage $\mathbf{y}$,
consisting of $\mathbf{y}_{j}$ which is the commitment to the $j$’th qubit.

    3. 3.

Compute
$(\mathbf{z}_{j},\bm{\rho}^{\prime})\leftarrow\mathsf{Open}_{\mathbf{ss}}(\bm{\rho},(j,b_{j}))$.

    4. 4.

Output $((\mathbf{y}_{j},\mathbf{o}_{j},\mathbf{z}_{j}),\bm{\rho}^{\prime})$.

  * •

$\mathsf{Ver}(\mathsf{sk},\mathsf{rt},(j,b_{j}),(\mathbf{y}_{j},\mathbf{o}_{j},\mathbf{z}_{j}))$:

    1. 1.

Parse $\mathsf{sk}=(\mathsf{sk}_{1},\mathsf{hk})$.

    2. 2.

Let
$v_{0}=\mathsf{Ver}_{\mathsf{H}}(\mathsf{hk},\mathsf{rt},j,\mathbf{y}_{j},\mathbf{o}_{j})$.333333
$\mathsf{Ver}_{\mathsf{H}}(\mathsf{hk},\mathsf{rt},j,\mathbf{y}_{j},\mathbf{o}_{j})$
denotes the verification of the opening for $\mathbf{y}_{j}$, which is the
$j$’th chunk of the hashed preimage.

    3. 3.

Let
$v_{1}=\mathsf{Ver}_{1}(\mathsf{sk}_{1},\mathbf{y}_{j},b_{j},\mathbf{z}_{j})$.

    4. 4.

Output $v_{0}~{}\wedge~{}v_{1}$.

  * •

$\mathsf{Out}(\mathsf{sk},\mathsf{rt},(j,b_{j}),(\mathbf{y}_{j},\mathbf{o}_{j},\mathbf{z}_{j}))$:

    1. 1.

Parse $\mathsf{sk}=(\mathsf{sk}_{1},\mathsf{hk})$.

    2. 2.

Output
$m_{j}=\mathsf{Out}_{1}(\mathsf{sk}_{1},\mathbf{y}_{j},b_{j},\mathbf{z}_{j})$.

##  7 Analysis of the Multi-Qubit Commitment Schemes from Section 6

###  7.1 Correctness

In this section we prove the correctness of Construction 6.2 and Construction
6.8.

######  Theorem 7.1.

The multi-qubit commitment scheme described in Construction 6.2 satisfies the
correctness property given in Definition 5.4.

Section 6.2 commits to each qubit of a multi-qubit state independently by
using the single-qubit protocol given in construction Construction 6.1 as a
black-box. Therefore, to prove Theorem 7.1 it suffices to prove the following
theorem.

######  Theorem 7.2.

The single-qubit commitment scheme described in Construction 6.1 satisfies the
correctness property given in Definition 5.4.

We make use of the following lemma about $\mathsf{Commit_{\text{\em W}}}$
throughout the proof.

######  Lemma 7.3 (Correctness of $\mathsf{Commit_{\text{\em W}}}$).

For any $\ell$-qubit quantum state
$\ket{\varphi}=\sum_{\mathbf{s}\in\\{0,1\\}^{\ell}}\alpha_{\mathbf{s}}\ket{\mathbf{s}}_{\cal
S}$ and any basis
$\mathbf{b}=(b_{1},\dots,b_{\ell})\in\\{0\\}^{\ell}\cup\\{1\\}^{\ell}$,

$\mathsf{Real}_{W}(1^{\lambda},\ket{\varphi},\mathbf{b})\stackrel{{\scriptstyle\mathsf{negl}(\lambda)}}{{\equiv}}\bm{\sigma}(\mathbf{b})$
(20)

where $\bm{\sigma}(\mathbf{b})$ is the distribution obtained by measuring each
qubit $j$ of $\ket{\varphi}$ in the basis specified by $b_{j}$ (standard if
$b_{j}=0$, Hadamard if $b_{j}=1$), and
$\mathsf{Real}_{W}(1^{\lambda},\ket{\varphi},\mathbf{b})$ is the distribution
resulting from honestly opening the commitment. Specifically,
$\mathsf{Real}_{W}(1^{\lambda},\ket{\varphi},\mathbf{b})$ is defined by:

  1. 1.

For every $i\in\\{0,1,\dots,\ell\\}$, sample
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$.

  2. 2.

Compute
$(\mathbf{y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{\ell}),\ket{\varphi^{\prime}})\leftarrow\mathsf{Commit_{\text{\em
W}}}((\mathsf{pk}_{1},\dots,\mathsf{pk}_{\ell}),\ket{\varphi})$, where
$\ket{\varphi^{\prime}}$ is of the same form as Equation 18.

  3. 3.

If $\mathbf{b}=\\{0\\}^{\ell}$:

    1. (a)

Measure $\ket{\varphi^{\prime}}$ in the standard basis to get
$\mathbf{z}=(\mathbf{z}_{1},\dots,\mathbf{z}_{\ell})$. Parse each
$\mathbf{z}_{i}=(s_{i},\mathbf{x}_{i,s_{i}})$. If
$\mathsf{Check}_{\mathsf{NTCF}}(\mathsf{pk}_{i},s_{i},\mathbf{x}_{i,s_{i}},\mathbf{y}_{i})\neq
1$ for some $i\in[\ell]$, output $\bot$. Otherwise, output
$\mathbf{s}=(s_{1},s_{2},\dots,s_{\ell})$.

  4. 4.

If $\mathbf{b}=\\{1\\}^{\ell}$:

    1. (a)

Measure $\ket{\varphi^{\prime}}$ in the Hadamard basis to get
$\mathbf{d}=(\mathbf{d}_{1},\dots,\mathbf{d}_{\ell})\in\\{0,1\\}^{\ell(n+1)}$.
For each $j\in[\ell]$, compute
$((0,\mathbf{x}_{j,0}),(1,\mathbf{x}_{j,1}))=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{j},\mathbf{y}_{j})$.
If $\mathbf{d}_{j}\notin\mathsf{Good}_{\mathbf{x}_{j,0},\mathbf{x}_{j,1}}$ for
some $j\in[\ell]$, output $\bot$. Otherwise, output
$\mathbf{m}=(m_{1},\dots,m_{\ell})$, where each
$m_{j}=\mathbf{d}_{j}\cdot(1,\mathbf{x}_{j,0}\oplus\mathbf{x}_{j,1})$.

###### Proof.

This follows directly from the proof of Lemma 5.3 in [Mah18], where the
$\mathbf{b}=\\{0\\}^{\ell}$ case corresponds to the _Test_ round and the
$\mathbf{b}=\\{1\\}^{\ell}$ case corresponds to the _Hadamard_ round. ∎

Recall that in Construction 6.1, the final state $\ket{\phi_{3}}$ is the
result of applying $\mathsf{Commit_{\text{\em W}}}$ to the state

$\ket{\phi_{2}}=\frac{1}{\sqrt{2^{n+1}}}\sum_{\mathbf{d}\in\\{0,1\\}^{n+1}}\beta_{\mathbf{d}}\ket{\mathbf{d}}.$

in the commitment procedure (pre-measurement)

We now show that the outcome of opening $\ket{\varphi_{3}}$ in a basis
$b\in\\{0,1\\}$ is statistically indistinguishable from measuring the initial
state, $\ket{\psi}$, in the basis $b$. We proceed with the proof for pure
states, which extends to the case of mixed and entangled states by linearity,
and show correctness for each basis separately. We treat the correctness of
$\mathsf{Commit_{\text{\em W}}}$ as a black-box. Namely, we make use of Lemma
7.3 throughout the proof.

######  Lemma 7.4 (Opening in the Hadamard basis, $b=1$).

For any pure single-qubit quantum state
$\ket{\psi}=\alpha_{0}\ket{0}+\alpha_{1}\ket{1}$ and any $\mathsf{NTCF}$
family, the distribution over the outcomes of the following two experiments
are statistically indistinguishable under Construction 6.1:

  * •

Experiment 1. Measure $\ket{\psi}$ in the Hadamard basis and report the
outcome.

  * •

Experiment 2. Execute $\mathsf{Real}(1^{\lambda},\ket{\psi},b_{1}=1)$, as
described in Definition 5.4.

###### Proof.

By inspection, it can be seen that the distribution of outcomes obtained from
$\mathsf{Real}(1^{\lambda},\ket{\psi},b_{1}=1)$ here is the same as the
outcome obtained from the following procedure:

  1. 1.

Generate keys $(\mathsf{sk}_{0},\mathsf{pk}_{0})$.

  2. 2.

Apply the weak commitment once to get
$\mathbf{y}_{0},\ket{\phi_{1}}\leftarrow\mathsf{Commit}_{W}(\mathsf{pk}_{0},\ket{\psi})$.

  3. 3.

Apply a Hadamard transform to the state to get
$\ket{\phi_{2}}=H^{\otimes(n+1)}\ket{\phi_{1}}$.

  4. 4.

Execute $\mathsf{Real}_{W}(1^{\lambda},\ket{\phi_{2}},0^{n+1})$ to obtain an
outcome $\mathbf{d}=(d_{0},\dots,d_{n+1})$.

  5. 5.

Report an outcome $\mathbf{d}\cdot(1,\mathbf{x}_{0}\oplus\mathbf{x}_{1})$,
where
$\\{(b,\mathbf{x}_{b})\\}_{b=0,1}=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{0},\mathbf{y}_{0})$.

By Lemma 7.3 for standard basis openings, the distribution over $\mathbf{d}$
statistically close to the distribution obtained by measuring $\ket{\phi_{2}}$
in the standard basis. This, in turn, by construction is equal to the
distribution obtained by measuring $\ket{\phi_{1}}$ in the Hadamard basis.
Finally, by applying Lemma 7.3 again, this time for Hadamard basis openings,
this implies that the distribution of
$\mathbf{d}\cdot(1,\mathbf{x}_{0}\oplus\mathbf{x}_{1})$ is statistically close
to the distribution obtained by measuring $\ket{\psi}$ in the Hadamard basis.

∎

######  Lemma 7.5 (Opening in the standard basis, $b=0$).

For any pure single-qubit quantum state
$\ket{\psi}=\alpha_{0}\ket{0}+\alpha_{1}\ket{1}$ and any $\mathsf{NTCF}$
family, the distribution over the outcomes of the following two experiments
are statistically indistinguishable under Construction 6.1:

  * •

Experiment 1. Measure $\ket{\psi}$ in the standard basis and report the
outcome.

  * •

Experiment 2. Execute $\mathsf{Real}(1^{\lambda},\ket{\psi},b_{1}=0)$, as
described in Definition 5.4.

###### Proof.

By inspection, it can be seen that the distribution of outcomes obtained from
$\mathsf{Real}(1^{\lambda},\ket{\psi},b_{1}=1)$ here is the same as the
outcome obtained from the following procedure:

  1. 1.

Generate keys $(\mathsf{sk}_{0},\mathsf{pk}_{0})$.

  2. 2.

Apply the weak commitment once to get
$\mathbf{y}_{0},\ket{\phi_{1}}\leftarrow\mathsf{Commit}_{W}(\mathsf{pk}_{0},\ket{\psi})$.

  3. 3.

Apply a Hadamard transform to the state to get
$\ket{\phi_{2}}=H^{\otimes(n+1)}\ket{\phi_{1}}$.

  4. 4.

Execute $\mathsf{Real}_{W}(1^{\lambda},\ket{\phi_{2}},1^{n+1})$ to obtain an
outcome $\mathbf{m}=(m_{0},\dots,m_{n})$.

  5. 5.

If
$\mathsf{Check}_{\mathsf{NTCF}}(\mathsf{pk}_{0},m_{0},(m_{1},\dots,m_{n}),\mathbf{y}_{0})=1$,
output $m_{0}$; else, output $\bot$.

By Lemma 7.3, applied in the Hadamard basis case, the outcome $\mathbf{m}$ has
a distribution that is statistically close to the outcome of a Hadamard basis
measurement of $\ket{\phi_{2}}$. By construction, this is equal to the
distribution of the outcome of a standard basis measurement of
$\ket{\phi_{1}}$. Finally, by Lemma 7.3, applied in the standard basis case,
the distribution of a standard outcome of $\ket{\phi_{1}}$ will pass the check
$\mathsf{Check}_{\mathsf{NTCF}}(\mathsf{pk}_{0},m_{0},(m_{1},\dots,m_{n}),\mathbf{y}_{0})$
with probability negligibly close to $1$, and the bit $m_{0}$ will be
distributed close to the distribution obtained by measuring $\ket{\psi}$ in
the standard basis.

∎

###### Proof of Theorem 7.2.

The theorem follows immediately from Lemma 7.4 and Lemma 7.5. ∎

We now proceed with the proof of correctness for the succinct commitment
scheme.

######  Theorem 7.6.

The succinct multi-qubit commitment scheme described in Construction 6.8
satisfies the correctness property given in Definition 5.5.

###### Proof.

By correctness of the state-preserving succinct argument of knowledge protocol
[LMS22], $\mathsf{Ver}.\mathsf{Commit}$ in Construction 6.8 accepts with
probability $1-\mathsf{negl}(\lambda)$. The $\mathsf{Commit}$ algorithm in
that construction uses $\mathsf{Commit}_{\mathbf{ss}}$ as a black box, which
consists of applying the $\mathsf{Commit}_{1}$ procedure to each qubit of
$\bm{\sigma}$ under the same public key $\mathsf{pk}_{1}$. Therefore, for the
$c=0$ case in Definition 5.5, correctness holds by Theorem 7.2. The $c=1$ case
follows from the correctness of the state-preserving argument of knowledge
[LMS22]. ∎

###  7.2 Binding

In this section we prove the following two theorems.

######  Theorem 7.7.

The non-succinct commitment scheme described in Section 6.2 satisfies the
binding property given in Definition 5.6 (assuming the existence of a
$\mathsf{NTCF}$ family).

######  Theorem 7.8.

The semi-succinct multi-qubit commitment scheme described in Section 6.2
(Definition 6.3) satisfies the binding property given in Definition 5.6 if the
underlying single qubit commitment scheme is the one from Section 6.1 and the
underlying $\mathsf{NTCF}$ family is the one from [BCM+18] and assuming it
satisfies the distributional strong adaptive hardcore bit property (see
Definition 4.1).343434We recall that [BCM+18] satisfies the distributional
strong adaptive hardcore bit property under $\mathsf{LWE}$ (see Claim 4.4).

To prove the above two theorems we need to prove that both the non-succinct
and the semi-succinct commitment schemes described in Section 6.2 satisfy
Equation 11 and Equation 12 of the binding property (Definition 5.6).

######  Remark 7.9.

We note that Equation 12 only relies on the fact that the underlying
$\mathsf{NTCF}$ family is collapsing (as defined in Claim 3.12), whereas
Equation 11 relies on the adaptive hardcore bit property for the non-succinct
scheme and on the specific properties of the $\mathsf{NTCF}$ family from
[BCM+18] (specifically, the distributional strong adaptive hardcore bit
property) for the semi-succinct scheme.

We start by proving that both the non-succinct and the semi-succinct
commitment schemes satisfy Equation 12. We actually prove a stronger version
of Equation 12, stated below.

######  Lemma 7.10.

[Stronger version of Equation 12] For any $\mathsf{QPT}$ algorithm
${\mathsf{C}}^{*}.\mathsf{Commit}$ and quantum state $\bm{\sigma}$, any
purification $\ket{\varphi}$ of $\bm{\sigma}$, any $\mathsf{QPT}$ algorithms
${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and ${\mathsf{C}}^{*}_{2}.\mathsf{Open}$,
any $\mathbf{b}\in\\{0,1\\}^{\ell}$, and any efficient unitaries $V_{1}$ and
$V_{2}$ there exists a negligible function $\mu=\mu(\lambda)$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U_{1}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{1}V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}-U_{2}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{2}V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}\|_{2}\leq$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\eta+\epsilon+\mu}$

where

  * •

$\epsilon=\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|V_{1}\ket{\psi}-V_{2}\ket{\psi}\|_{2}$.

  * •

$\eta=\sum_{j=1}^{\ell}2\sqrt{\delta_{j}}$ for

$\delta_{j}\triangleq\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\\\
(\mathbf{z}_{i},\bm{\rho}^{\prime}_{i})\leftarrow{\mathsf{C}}^{*}_{i}.\mathsf{Open}(\bm{\rho},\mathbf{b})\end{subarray}}\max_{i\in\\{1,2\\}}\Pr[\mathsf{Ver}(\mathsf{sk},\mathbf{y},(j,b_{j}),\mathbf{z}_{i,j})=0~{}|~{}\mathsf{Ver}(\mathsf{sk},\mathbf{y},(k,b_{k}),\mathbf{z}_{i,k})=1~{}\forall
k\in[j-1]]$

where $\mathbf{z}_{i}=(\mathbf{z}_{i,j})_{j=1}^{\ell}$.

  * •

$\ket{\psi_{\mathsf{ext}}}=\ket{0^{\ell}}_{\mathsf{copy}}\otimes\ket{0^{\ell}}_{\mathsf{out}}\otimes\ket{\mathbf{b}}_{\mathsf{basis}}\otimes\ket{\psi}$.

  * •

For every $i\in\\{1,2\\}$, $V_{\mathsf{ext},i}=I_{\mathsf{copy}}\otimes
I_{\mathsf{out}}\otimes I_{\mathsf{basis}}\otimes V_{i}$.

  * •

For every $i\in\\{1,2\\}$, $U_{i}$ is the unitary defined by applying
${\mathsf{C}}^{*}_{i}.\mathsf{Open}$ to the registers $\mathsf{open}$ and
$\mathsf{basis}$.

  * •

$U_{\mathsf{Out}}$ is the unitary defined by first applying the unitary
corresponding to $\mathsf{Ver}(\mathsf{sk},\mathbf{y},\cdot,\cdot)$ to
registers $\mathsf{open}$ and $\mathsf{basis}$, and controlled on
$\mathsf{Ver}$ accepting, applying the unitary corresponding to
$\mathsf{Out}(\mathsf{sk},\mathbf{y},\cdot,\cdot)$ to registers
$\mathsf{open}$ and $\mathsf{basis}$, and writing the output on the register
$\mathsf{out}$.

  * •

$\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}$ applies a $\mathsf{CNOT}$ to
registers $\mathsf{copy}$ and $\mathsf{out}$ (i.e., it copies register
$\mathsf{out}$ to register $\mathsf{copy}$).

Moreover, ${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and
${\mathsf{C}}^{*}_{2}.\mathsf{Open}$ can be $\mathsf{QPT}$ given
$\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1}$ when opening in the standard basis
and $\mathsf{QPT}$ when opening in the Hadamard basis.353535This
generalization is needed to obtain Corollary 7.11. Alternatively, they can be
$\mathsf{QPT}$ given $\mathsf{sk}_{0}$ when opening in the Hadamard basis and
$\mathsf{QPT}$ when opening in the standard basis.

######  Corollary 7.11.

For any $\mathsf{QPT}$ algorithm ${\mathsf{C}}^{*}.\mathsf{Commit}$ and
quantum state $\bm{\sigma}$, any $\mathsf{QPT}$ algorithms
${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and ${\mathsf{C}}^{*}_{2}.\mathsf{Open}$,
and any $\mathbf{b}\in\\{0,1\\}^{\ell}$,

$\mathsf{Real}^{{\mathsf{C}}^{*}_{1}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle
2(\sqrt{\delta_{0}}+\sqrt{\delta_{1}})}}{{\approx}}\mathsf{Real}^{{\mathsf{C}}^{*}_{2}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$

where denoting by $I_{b}=\\{i\in[\ell]:\mathbf{b}_{i}=b\\}$,

$\delta_{b}=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})\\\
\mathbf{z}_{i}\leftarrow{\mathsf{C}}^{*}_{i}.\mathsf{Open}(\bm{\rho},\mathbf{b})\end{subarray}}\max_{i\in\\{1,2\\}}\Pr[\mathsf{Ver}\left(\mathsf{sk},\mathbf{y},(I_{b},b^{|I_{b}|}),\mathbf{z}_{i,I_{b}}\right)=0]$

where $\mathbf{z}_{i,I_{b}}=(\mathbf{z}_{i,j})_{j\in I_{b}}$.

Moreover, ${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and
${\mathsf{C}}^{*}_{2}.\mathsf{Open}$ can be $\mathsf{QPT}$ given
$\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1}$ when opening in the standard basis
and $\mathsf{QPT}$ when opening in the Hadamard basis.

##### Proof of Corollary 7.11

Fix any $\mathsf{QPT}$ algorithm ${\mathsf{C}}^{*}.\mathsf{Commit}$ and
quantum state $\bm{\sigma}$, any algorithms
${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and ${\mathsf{C}}^{*}_{2}.\mathsf{Open}$
as in the statement of Corollary 7.11, and any basis $\mathbf{b}$. For every
$i\in\\{1,2\\}$ we slightly change ${\mathsf{C}}^{*}_{i}.\mathsf{Open}$ to
${\mathsf{C}}^{**}_{i}.\mathsf{Open}$, as follows:
${\mathsf{C}}^{**}_{i}.\mathsf{Open}(\bm{\rho},(j,b))$ coherently computes
$\mathbf{z}\leftarrow{\mathsf{C}}^{*}_{i}.\mathsf{Open}(\bm{\rho},\mathbf{b})$
and outputs $\mathbf{z}_{j}$ if
$\mathsf{Ver}(\mathsf{sk},\mathbf{y},(I_{b},\mathbf{b}_{I_{b}}),\mathbf{z})=1$,
and otherwise it outputs $\bot$.363636Note that
$\mathbf{b}_{I_{b}}=b^{|I_{b}|}$ Note that
${\mathsf{C}}^{**}_{i}.\mathsf{Open}$ remains a $\mathsf{QPT}$ algorithm when
opening in the Hadamard basis since $\mathsf{Ver}$ does not use $\mathsf{sk}$
when verifying a Hadamard basis opening, whereas it uses
$\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1}$ when opening in the standard basis.
Thus ${\mathsf{C}}^{**}_{1}.\mathsf{Open}$ and
${\mathsf{C}}^{**}_{2}.\mathsf{Open}$ satisfy the efficiency conditions of
Lemma 7.10. In addition, note that for every $i\in\\{1,2\\}$,

$\mathsf{Real}^{{\mathsf{C}}^{*}_{i}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})\equiv\mathsf{Real}^{{\mathsf{C}}^{**}_{i}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma}).$

where $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$ and
$(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$.
By Lemma 7.10 for any purification $\ket{\varphi}$ of $\bm{\sigma}$ there
exists a negligible function $\mu$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U_{1}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{1}\ket{\psi_{\mathsf{ext}}}-U_{2}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{2}\ket{\psi_{\mathsf{ext}}}\|_{2}$
$\displaystyle\leq~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\eta+\mu}$

where $U_{i}$ is the unitary defined by ${\mathsf{C}}^{**}_{i}.\mathsf{Open}$,
and $U_{\mathsf{Out}}$ and $\eta$ are as defined in Lemma 7.10. It remains to
observe that $\eta\leq 2\sqrt{\delta_{0}}+2\sqrt{\delta_{1}}$, which follows
from the the definition of ${\mathsf{C}}^{**}_{i}.\mathsf{Open}$, which
asserts that $\delta_{j}=0$ if there exists $k\in\\{1,\ldots,j-1\\}$ for which
$b_{j}=b_{k}$. ∎

##### Proof of Lemma 7.10

We prove this lemma for the semi-succinct variant of the multi-qubit
commitment scheme described in Section 6.2. The proof for the non-succinct
variant is identical. The proof is by induction on $\ell$.

##### Base case: $\ell=1$.

Fix any $\mathsf{QPT}$ algorithm ${\mathsf{C}}^{*}.\mathsf{Commit}$, a quantum
state $\bm{\sigma}$, algorithms ${\mathsf{C}}^{*}_{1}.\mathsf{Open}$ and
${\mathsf{C}}^{*}_{2}.\mathsf{Open}$, basis $b\in\\{0,1\\}$, and efficient
unitaries $V_{1}$ and $V_{2}$, as in the lemma statement. Also fix a
purification $\ket{\varphi}$ of $\bm{\sigma}$. Suppose for the sake of
contradiction that there exists a non-negligible $\xi=\xi(\lambda)$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U_{1}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{1}V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}-U_{2}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{2}V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}\|_{2}\geq$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\eta+\epsilon+\xi}$

We construct a $\mathsf{QPT}$ adversary $\mathsf{A}$ that uses the
$\mathsf{QPT}$ committer ${\mathsf{C}}^{*}.\mathsf{Commit}$, its purified
state $\ket{\varphi}$, and the unitaries
$U_{1},U_{2},V_{1},V_{2},U_{\mathsf{Out}}$ to break the collapsing property of
the underlying $\mathsf{NTCF}$ family (Definition 3.10). We break the
collapsing property as formulated in Remark 3.11. We distinguish between the
case that $b=0$ and the case that $b=1$.

##### Case 1: $b=0$.

The adversary $\mathsf{A}$ operates as follows:

  1. 1.

Advserary: Upon receiving a public key $\mathsf{pk}_{0}$ from the challenger,
where
$(\mathsf{pk}_{0},\mathsf{sk}_{0})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$:

    1. (a)

For every $i\in[n+1]$ generate
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$.

    2. (b)

Let $\mathsf{pk}=(\mathsf{pk}_{0},\mathsf{pk}_{1},\ldots,\mathsf{pk}_{n+1})$.

    3. (c)

Compute
$(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})$.

    4. (d)

Parse $\mathbf{y}=(\mathbf{y}_{0},\mathbf{y}_{1},\ldots,\mathbf{y}_{n+1})$

    5. (e)

Let
$\ket{\psi^{\prime}}=U\left(\ket{+}_{\mathsf{coin}}\otimes\ket{\psi_{\mathsf{ext}}}\right)$,
where

$U=\ket{0}\bra{0}_{\mathsf{coin}}\otimes
U_{\mathsf{Out}}U_{1}V_{\mathsf{ext},1}+\ket{1}\bra{1}_{\mathsf{coin}}\otimes
U_{\mathsf{Out}}U_{2}V_{\mathsf{ext},2}$

Recall that $U_{\mathsf{Out}}$ first computes $\mathsf{Ver}$ which in Item 4d
computes $\mathbf{m}\in\\{0,1\\}^{n+1}$. $U_{\mathsf{Out}}$ stores in register
$\mathsf{out}$ the output, which is the first bit of $\mathbf{m}$. We denote
by $\mathsf{preimage}$ the registers that store the last $n$ bits of
$\mathbf{m}$.

    6. (f)

Send to the challenger the string $\mathbf{y}_{0}$ and the registers
$\mathsf{out}$ and $\mathsf{preimage}$ of $\ket{\psi^{\prime}}$.

Notice that since $b=0$, $U_{\mathsf{Out}}$ (as possibly $U_{1}$ and $U_{2}$)
use only the secret keys $(\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1})$, which
$\mathsf{A}$ knows, and thus $\mathsf{A}$ can efficiently apply the unitary
$U$ to the state $\ket{+}_{\mathsf{coin}}\otimes\ket{\psi_{\mathsf{ext}}}$.

  2. 2.

Challenger: Recall that the challenger applies in superposition the algorithm
$\mathsf{Check}_{\mathsf{NTCF}}$ to the state it receives w.r.t. public key
$\mathsf{pk}_{0}$ and the image string $\mathbf{y}_{0}$, and measures the bit
indicating whether the output of $\mathsf{Check}_{\mathsf{NTCF}}$ is $1$. If
this is not the case it sends $\bot$. Otherwise, it chooses a random bit
$u\leftarrow\\{0,1\\}$ and measures this state if and only if $u=1$. It then
sends the resulting state to the adversary.

Note that by the two-to-one nature of the underlying $\mathsf{NTCF}$ family,
measuring the entire state is equivalent to measuring only the first qubit of
the state, i.e., register $\mathsf{out}$. Thus, we can assume that the
challenger measures only register $\mathsf{out}$ if and only if $u=1$.

In addition, note that conditioned on the challenger not outputting $\bot$,
the state is projected to $\Pi_{\mathsf{Ver}}\ket{\psi^{\prime}}$ (up to
normalization), where $\Pi_{\mathsf{Ver}}\ket{\psi^{\prime}}$ is the state
$\ket{\psi^{\prime}}$ projected to the challenger accepting the state.
Consider the state
$\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}\ket{\psi^{\prime}}$.
Note that this state, with the $\mathsf{copy}$ register excluded, is
indistinguishable from the state returned from the challenger conditioned on
choosing the random bit $u$. Thus we think of the adversary as receiving this
state.

  3. 3.

Adversary: If the adversary receives $\bot$ from the challenger, then it
outputs a uniformly random $u^{\prime}$. Note that this occurs with
probability at most $\delta$.

Otherwise, the adversary $\mathsf{A}$ receives the registers $\mathsf{out}$
and $\mathsf{preimage}$ from the challenger (either measured or not, depending
on $u$). The joint state of the adversary and challenger at this point is
$\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}\ket{\psi^{\prime}}$,
where all registers except $\mathsf{copy}$ are held by the adversary. The
adversary does the following:

    1. (a)

Let

$U^{\prime}=\ket{0}\bra{0}_{\mathsf{Coin}}\otimes
U_{1}^{\dagger}U_{\mathsf{out}}^{\dagger}+\ket{1}\bra{1}_{\mathsf{Coin}}\otimes
U_{2}^{\dagger}U_{\mathsf{out}}^{\dagger}.$

    2. (b)

Apply $U^{\prime}$ to the adversary’s system, resulting in the joint state

$\displaystyle
U^{\prime}\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}\ket{\psi^{\prime}}=$
$\displaystyle
U^{\prime}\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}U\ket{\psi_{\mathsf{ext}}}=$
$\displaystyle(\ket{0}\bra{0}_{\mathsf{Coin}}U^{\dagger}_{1}U_{\mathsf{out}}^{\dagger}\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{1}V_{\mathsf{ext},1}+\ket{1}\bra{1}_{\mathsf{Coin}}U^{\dagger}_{2}U_{\mathsf{out}}^{\dagger}\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{2}V_{\mathsf{ext},2})\ket{\psi_{\mathsf{ext}}}$

    3. (c)

Output the measurement of the $\mathsf{Coin}$ register in the Hadamard basis,
denoted by $u^{\prime}$ (i.e., $u^{\prime}=0$ if the measurement is $\ket{+}$
and is $u^{\prime}=0$ if the measurement is $\ket{-}$).

Consider the states

$U^{\dagger}_{1}U_{\mathsf{out}}^{\dagger}\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{1}V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}~{}~{}\mbox{
and
}~{}~{}U^{\dagger}_{2}U_{\mathsf{out}}^{\dagger}\mathsf{CNOT}^{u}_{\mathsf{copy},\mathsf{out}}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{2}V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}$

Note that for $u=0$, these states are $(2\sqrt{\delta}+\epsilon)$-close in
$\|\cdot\|_{2}$ distance. This follows from the fact that by Lemma 3.1,
together with the assumption that the probability that
$\ket{\psi_{\mathsf{ext}}}$ opens successfully is $\geq 1-\delta$, it holds
that for every $i\in\\{1,2\\}$:

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U^{\dagger}_{i}U_{\mathsf{out}}^{\dagger}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{i}V_{\mathsf{ext},i}\ket{\psi_{\mathsf{ext}}}-U^{\dagger}_{i}U_{\mathsf{out}}^{\dagger}U_{\mathsf{out}}U_{i}V_{\mathsf{ext},i}\ket{\psi_{\mathsf{ext}}}\|_{2}\leq\sqrt{\delta},$

and from our assumption that

$\displaystyle\epsilon=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}-V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}\|_{2}.$

This implies that there exists a negligible function $\mu$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U_{1}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{1}V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}-U_{2}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{2}V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}\|_{2}\leq$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{2\sqrt{\delta}+\epsilon+\mu}$

On the other hand, by our contradiction assumption, for $u=1$, these two
states are $(2\sqrt{\delta}+\epsilon)$-far. This, together with Claim 7.12
below, implies that $\mathsf{A}$ indeed breaks the collapsing property of the
underlying $\mathsf{NTCF}$ family.

######  Claim 7.12.

For any two states $\ket{\psi_{0}}$ and $\ket{\psi_{1}}$ such that
$\left\|\ket{\psi_{0}}-\ket{\psi_{1}}\right\|=\epsilon$, and for
$\ket{\varphi}=\frac{1}{\sqrt{2}}\ket{0}\ket{\psi_{0}}+\frac{1}{\sqrt{2}}\ket{1}\ket{\psi_{1}}$,
it holds that

$\Pr[H[\varphi]\rightarrow 1]=\frac{\epsilon^{2}}{4}.$

###### Proof.

We calculate

$\displaystyle\Pr[H[\varphi]\mapsto 1]$ $\displaystyle=\norm{(\bra{1}\otimes
I)H\ket{\varphi}}^{2}$ $\displaystyle=\norm{(\bra{1}\otimes
I)\left(\frac{1}{\sqrt{2}}\ket{+}\ket{\psi_{0}}+\frac{1}{\sqrt{2}}\ket{-}\ket{\psi_{1}}\right)}^{2}$
$\displaystyle=\left\|\frac{1}{2}\ket{\psi_{0}}-\frac{1}{2}\ket{\psi_{1}}\right\|^{2}$
$\displaystyle=\frac{1}{4}\epsilon^{2}.\qed$

##### Case 2: $b=1$.

We show how to use the adversary $\mathsf{A}$ to break the extended collapsing
game (see Claim 3.13). The adversary $\mathsf{A}$ operates as follows:

  1. 1.

Upon receiving public keys $(\mathsf{pk}_{1},\ldots,\mathsf{pk}_{n+1})$ from
the challenger, where
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$
for every $i\in[n+1]$, do the following:

    1. (a)

Generate
$(\mathsf{pk}_{0},\mathsf{sk}_{0})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$.

    2. (b)

Let $\mathsf{pk}=(\mathsf{pk}_{0},\mathsf{pk}_{1},\ldots,\mathsf{pk}_{n+1})$.

    3. (c)

Compute
$(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})$.

    4. (d)

Parse $\mathbf{y}=(\mathbf{y}_{0},\mathbf{y}_{1},\ldots,\mathbf{y}_{n+1})$.

    5. (e)

Compute
$((0,\mathbf{x}_{0}),(1,\mathbf{x}_{1}))=\mathsf{Invert}_{\mathsf{NTCF}}(\mathsf{sk}_{0},\mathbf{y}_{0})$.

    6. (f)

Let $J=\\{j\in\\{2,\ldots,n+1\\}:x_{0,j-1}\oplus x_{1,j-1}=1\\}\cup\\{1\\}$.

    7. (g)

As in the $b=0$ case, define

$U=\ket{0}\bra{0}_{\mathsf{coin}}\otimes
U_{\mathsf{Out}}U_{1}V_{\mathsf{ext},1}+\ket{1}\bra{1}_{\mathsf{coin}}\otimes
U_{\mathsf{Out}}U_{2}V_{\mathsf{ext},2}$

and prepare the state
$\ket{\psi^{\prime}}=U(\ket{+}_{\mathsf{coin}}\otimes\ket{\psi_{\mathsf{ext}}})$.

Note that since $b=1$ it holds that $\ket{\psi^{\prime}}$ can be computed
efficiently given $\mathsf{sk}_{0}$

    8. (h)

For every $j\in[J]$, denote by ${\cal X}_{j}$ and ${\cal Z}_{j}$ the registers
in $\bm{\rho}^{\prime}$ corresponding to $d_{j}$ and $x^{\prime}_{j}$,
respectively.

    9. (i)

Send $J$, $\\{\mathbf{y}_{j}\\}_{j\in J}$ and the registers $\\{{\cal
X}_{j},{\cal Z}_{j}\\}_{j\in J}$ of $\ket{\psi^{\prime}}$.

  2. 2.

Recall that the challenger applies in superposition the algorithm
$\mathsf{Check}$ to the state it received w.r.t. the image strings
$\\{\mathbf{y}_{j}\\}_{j\in J}$, where the $j$’th check is w.r.t
$\mathsf{pk}_{j}$, and measures the bit indicating whether the output of
$\mathsf{Check}$ is $1$. If any of the outputs of $\mathsf{Check}$ are $0$,
the challenger immediately halts and sends $\bot$ to the adversary. Otherwise,
it chooses a random bit $u\leftarrow\\{0,1\\}$ and applies $Z^{u}$ to every
${\cal X}_{j}$ register. It then sends the resulting state to the adversary.

  3. 3.

If the adversary receives $\bot$, it returns a uniformly random $u^{\prime}$.
Otherwise, observe that once the adversary receives the state from the
challenger, it is in possession of all the quantum registers. At this point,
they are, up to normalization, in the state
$Z^{u}_{J}\Pi_{\mathsf{Ver},J}\ket{\psi^{\prime}}$, where $Z_{J}=\prod_{j\in
J}Z_{{\cal X}_{j}}$ and $\Pi_{\mathsf{Ver},J}\ket{\psi^{\prime}}$ is the state
$\ket{\psi^{\prime}}$ projected to an accepting state.

It then does the following:

    1. (a)

Let

$U^{\prime}=\ket{0}\bra{0}_{\mathsf{Coin}}\otimes
U_{1}^{\dagger}U_{\mathsf{out}}^{\dagger}+\ket{1}\bra{1}_{\mathsf{Coin}}\otimes
U_{2}^{\dagger}U_{\mathsf{out}}^{\dagger}.$

    2. (b)

Apply $U^{\prime}$ to its registers, resulting in the state

$\displaystyle U^{\prime}Z^{u}_{J}\Pi_{\mathsf{Ver},J}\ket{\psi^{\prime}}=$
$\displaystyle\left(\ket{0}\bra{0}_{\mathsf{Coin}}\otimes
U^{\dagger}_{1}U_{\mathsf{out}}^{\dagger}Z^{u}_{J}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{1}V_{\mathsf{ext,1}}+\ket{1}\bra{1}_{\mathsf{Coin}}\otimes
U^{\dagger}_{2}U_{\mathsf{out}}^{\dagger}Z^{u}_{J}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{2}V_{\mathsf{ext,2}}\right)(\ket{+}_{\mathsf{Coin}}\otimes\ket{\psi_{\mathsf{ext}}})$

    3. (c)

Output the measurement of the first register of this state in the Hadamard
basis, denoted by $u^{\prime}$.

Consider the states

$U^{\dagger}_{1}U_{\mathsf{out}}^{\dagger}Z^{u}_{J}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{1}V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}~{}~{}\mbox{
and
}~{}~{}U^{\dagger}_{2}U_{\mathsf{out}}^{\dagger}Z^{u}_{J}\Pi_{\mathsf{Ver}}U_{\mathsf{out}}U_{2}V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}$

Note that similarly to the $b=0$ case, for $u=0$ these states are
$(2\sqrt{\delta}+\epsilon)$-close in $\|\cdot\|_{2}$ distance. On the other
hand, by our contradiction assumption, together with Lemma 3.3, for $u=1$,
these two states are $(2\sqrt{\delta}+\epsilon)$-far in $\|\cdot\|_{2}$
distance. This together with Claim 7.12, implies that indeed $\mathsf{A}$
breaks the collapsing property of the underlying $\mathsf{NTCF}$ family.

##### Induction step:

Suppose that the multi-qubit commitment scheme is sound for $\ell-1$ and we
prove that it is sound for $\ell$. We need to prove that there exists a
negligible function $\mu=\mu(\lambda)$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U_{1}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{1}V_{\mathsf{ext},1}\ket{\psi_{\mathsf{ext}}}-U_{2}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{2}V_{\mathsf{ext},2}\ket{\psi_{\mathsf{ext}}}\|_{2}\leq$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\eta+\epsilon+\mu}$

for $\eta=\sum_{j=1}^{\ell}2\sqrt{\delta_{j}}$ and
$\epsilon=\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|V_{1}\ket{\psi}-V_{2}\ket{\psi}\|_{2}$.

To this end, note that for every $i\in\\{1,2\\}$

$\displaystyle
U_{i}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy},\mathsf{out}}U_{\mathsf{Out}}U_{i}V_{\mathsf{ext},i}\ket{\psi_{\mathsf{ext}}}=$
$\displaystyle
U_{i}^{\dagger}U_{\mathsf{Out}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{\ell},\mathsf{out}_{\ell}}\mathsf{CNOT}_{\mathsf{copy}_{[1,\ell-1]},\mathsf{out}_{[1,\ell-1]}}U_{\mathsf{Out}}U_{i}V_{\mathsf{ext},i}\ket{\psi_{\mathsf{ext}}}=$
$\displaystyle
U_{i}^{\dagger}U_{\mathsf{Out}_{\ell}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{\ell},\mathsf{out}_{\ell}}U_{\mathsf{Out}_{\ell}}U_{i}V_{\mathsf{ext},i}V_{\mathsf{ext},i}^{\dagger}U_{i}^{\dagger}U_{\mathsf{Out}_{[1,\ell-1]}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{[1,\ell-1]},\mathsf{out}_{[1,\ell-1]}}U_{\mathsf{Out}_{[1,\ell-1]}}U_{i}V_{\mathsf{ext},i}\ket{\psi_{\mathsf{ext}}}=$
$\displaystyle
U_{i}^{\dagger}U_{\mathsf{Out}_{\ell}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{\ell},\mathsf{out}_{\ell}}U_{\mathsf{Out}_{\ell}}U_{i}\underbrace{U_{i}^{\dagger}U_{\mathsf{Out}_{[1,\ell-1]}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{[1,\ell-1]},\mathsf{out}_{[1,\ell-1]}}U_{\mathsf{Out}_{[1,\ell-1]}}U_{i}V_{\mathsf{ext},i}}_{V_{i}^{\prime}}\ket{\psi_{\mathsf{ext}}}$

For every $i\in\\{1,2\\}$, denote by

$\ket{\psi^{\prime}_{i}}=V_{i}^{\prime}\ket{\psi_{\mathsf{ext}}}$

By the induction hypothesis, there exists a negligible function
$\mu=\mu(\lambda)$ such that

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|\ket{\psi^{\prime}_{1}}-\ket{\psi^{\prime}_{2}}\|_{2}\leq\eta^{\prime}+\mu$

where $\eta^{\prime}=\sum_{j=1}^{\ell-1}2\sqrt{\delta_{j}}+\epsilon$. Denoting
by $\epsilon^{\prime}=\eta^{\prime}$, our base case implies that there exists
a negligible function $\nu=\nu(\lambda)$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathbf{y},\ket{\psi})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\ket{\varphi})\end{subarray}}\|U_{1}^{\dagger}U_{\mathsf{Out}_{\ell}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{\ell},\mathsf{out}_{\ell}}U_{\mathsf{out}_{\ell}}U_{1}V^{\prime}_{1}\ket{\psi_{\mathsf{ext}}}-U_{1}^{\dagger}U_{\mathsf{Out}_{\ell}}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{\ell},\mathsf{out}_{\ell}}U_{\mathsf{out}_{\ell}}U_{1}V_{2}^{\prime}\ket{\psi_{\mathsf{ext}}}\|_{2}\leq$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}2\sqrt{\delta_{\ell}}+\eta^{\prime}+\nu$

as desired.

∎

We next prove that both the non-succinct and the semi-succinct commitment
schemes from Section 6.2 satisfy Equation 11.

######  Lemma 7.13.

The non-succinct commitment scheme described in Section 6.2 satisfies Equation
11 from Definition 5.6 assuming the underlying $\mathsf{NTCF}$ family has the
adaptive hardcore bit property.

######  Lemma 7.14.

The semi-succinct commitment scheme described in Section 6.2 (Definition 6.3)
satisfies Equation 11 from Definition 5.6 assuming the underlying
$\mathsf{NTCF}$ family is the one from [BCM+18] and assuming it has the
distributional strong adaptive hardcore bit property (which is the case under
$\mathsf{LWE}$).

##### Proof of Lemmas 7.13 and 7.14

We prove these two lemmas jointly since much of the proof is identical. In
both cases we think of the public and secret keys as being

$\mathsf{pk}=(\mathsf{pk}_{1},\ldots,\mathsf{pk}_{\ell})~{}~{}\mbox{ and
}~{}~{}\mathsf{sk}=(\mathsf{sk}_{1},\ldots,\mathsf{sk}_{\ell})$

where in the non-succinct commitment each
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$
and in the semi-succinct commitment
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}_{\mathsf{NTCF}}(1^{\lambda})$,
and for every $i\in[\ell]$

$\mathsf{sk}_{i}=\mathsf{sk}~{}~{}\mbox{ and
}~{}~{}\mathsf{pk}_{i}=\mathsf{pk}$

Fix any $\mathsf{QPT}$ cheating committer ${\mathsf{C}}^{*}.\mathsf{Commit}$
with auxiliary quantum state $\bm{\sigma}$ that commits to an $\ell$-qubit
state. Denote by

$(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma}),$

where $\mathbf{y}=(\mathbf{y}_{1},\ldots,\mathbf{y}_{\ell})$, each
$\mathbf{y}_{i}=(\mathbf{y}_{i,0},\mathbf{y}_{1},\ldots,\mathbf{y}_{i,n+1})$
and each $\mathbf{y}_{i,j}$ is in $\mathsf{R}_{\mathsf{pk}_{j}}$ which is the
range of the $\mathsf{NTCF}$ function $\mathsf{Eval}(\mathsf{pk}_{j},\cdot)$.
Fix any $\mathsf{QPT}$ algorithm ${\mathsf{C}}^{*}.\mathsf{Open}$. We start by
defining the $\mathsf{QPT}$ extractor
$\mathsf{Ext}^{{\mathsf{C}}^{*}.\mathsf{Open}}(\mathsf{sk},\mathbf{y},\bm{\rho})$.
We do so in two steps:

  1. 1.

First, we define $2\ell$ “operational observables”
$\\{P_{X_{i}},P_{Z_{i}}\\}_{i\in\ell]}$ such that for every $i\in[\ell]$ and
$b\in\\{0,1\\}$,

$(\mathsf{pk},\mathbf{y},\mathbf{m}_{\mathsf{ideal},i,b})\equiv(\mathsf{pk},\mathbf{y},\mathbf{m}_{i,b})$

where
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})$,373737In
the semi-succinct setting
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$.
$(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$,
$\mathbf{m}_{\mathsf{ideal},i,b}$ is obtained by measuring $\bm{\rho}$ in the
$P_{X_{i}}$ basis if $b=1$ and measuring it in the $P_{Z_{i}}$ basis if $b=0$,
and $\mathbf{m}_{i,b}$ is obtained by computing
$\mathbf{z}\leftarrow{\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho},b^{\ell})$ and
setting
$\mathbf{m}_{i,b}=\mathsf{Out}(\mathsf{sk},\mathbf{y},(i,b),\mathbf{z}_{i})$.

  2. 2.

We then use these operational observables to extract a state $\bm{\tau}$. This
is done following the approach of [Mah18, Vid20, BKL+22],

##### Defining the operational observables
$\\{P_{X_{i}},P_{Z_{i}}\\}_{i\in[\ell]}$.

To define these operational observables formally, we add
$L=\ell\cdot\left((n+1)^{2}+1\right)$ ancilla registers to $\bm{\rho}$, which
we initialize to $0$. We denote by

$\bm{\rho}_{\mathsf{Ext}}=\bm{\rho}\otimes\ket{0^{L}}\bra{0^{L}},$

where the first $\ell\cdot(n+1)^{2}$ ancilla registers are denoted by
$\mathsf{open}=(\mathsf{open}_{1},\ldots,\mathsf{open}_{\ell})$, and these
registers store the output $(\mathbf{z}_{1},\ldots,\mathbf{z}_{\ell})$
generated by $\mathsf{Open}$, where $\mathbf{z}_{i}\in\\{0,1\\}^{(n+1)^{2}}$
is stored in $\mathsf{open}_{i}$. The last $\ell$ ancilla registers are
denoted by $\mathsf{out}=(\mathsf{out}_{1},\ldots,\mathsf{out}_{\ell})$, and
these registers store the output $(v_{1},\ldots,v_{\ell})$ generated by
$\mathsf{Out}$, where $v_{i}\in\\{0,1\\}$ is stored in register
$\mathsf{out}_{i}$.

######  Definition 7.15.

For any $(\mathsf{sk},\mathbf{y})$ and any $\mathsf{QPT}$ algorithm
${\mathsf{C}}^{*}.\mathsf{Open}$ we define the operational observables
$(P_{X_{i}},P_{Z_{i}})_{i\in[\ell]}$ to be

$P_{X_{i}}=U_{1}^{\dagger}\mathsf{Out}_{i,1}^{\dagger}Z_{\mathsf{out}_{i}}\mathsf{Out}_{i,1}U_{1}$

and

$P_{Z_{i}}=U_{0}^{\dagger}\mathsf{Out}_{i,0}^{\dagger}Z_{\mathsf{out}_{i}}\mathsf{Out}_{i,0}U_{0}$

where for every $i\in[\ell]$ and every $b\in\\{0,1\\}$,

  * •

$U_{b}$ is the unitary corresponding to
${\mathsf{C}}^{*}.\mathsf{Open}(\cdot,(b,\ldots,b))$. The output is recorded
in registers $\mathsf{open}$.

  * •

$\mathsf{Out}_{i,b}$ computes
$\mathsf{Out}(\mathsf{sk},\mathbf{y},(i,b),\cdot)$ and records the output in
the ancilla register $\mathsf{out}_{i}$.

  * •

$Z_{\mathsf{out},i}$ is the Pauli $Z$ operator applied only on the register
$\mathsf{out}_{i}$.

We next define the extractor $\mathsf{Ext}$ which uses the operational
observables $\\{P_{X_{i}},P_{Z_{i}}\\}_{i\in[\ell]}$, defined above. For the
sake of simplicity, we define $\mathsf{Ext}$ to operate on pure states. The
definition easily generalizes to mixed states by linearity.

#####
$\mathsf{Ext}^{{\mathsf{C}}^{*}.\mathsf{Open}}(\mathsf{sk},\mathbf{y},{\ket{\varphi}})$
operates as follows:

  1. 1.

Consider the operational observables $\\{P_{X_{i}},P_{Z_{i}}\\}_{i\in[\ell]}$
corresponding to $(\mathsf{sk},\mathbf{y})$.

  2. 2.

Prepare the state

$\frac{1}{2^{\ell}}\sum_{\mathbf{r},\mathbf{s}\in\\{01\\}^{\ell}}\ket{\mathbf{r},\mathbf{s}}_{\mathsf{Coin}}\otimes\ket{0^{\ell}}_{\cal
A}\otimes\ket{\varphi}_{\cal B}.$

  3. 3.

Denote by

$\mathbf{X}^{\mathbf{r}}=X_{\ell}^{r_{\ell}}\ldots X_{1}^{r_{1}}~{}\mbox{ and
}\mathbf{Z}^{\mathbf{s}}=Z_{\ell}^{s_{\ell}}\ldots Z_{1}^{s_{1}}.$

Similarly, denote by

$P_{\mathbf{X}}^{\mathbf{r}}=P_{X_{\ell}}^{r_{\ell}}\ldots
P_{X_{1}}^{r_{1}}~{}\mbox{ and
}P_{\mathbf{Z}}^{\mathbf{s}}=P_{Z_{\ell}}^{s_{\ell}}\ldots P_{Z_{1}}^{s_{1}}.$

  4. 4.

Controlled on the values $\mathbf{r},\mathbf{s}$ of the $\mathsf{Coin}$
register, apply $\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}$ to the ${\cal
A}$ register and apply
$P_{\mathbf{X}}^{\mathbf{r}}P_{\mathbf{Z}}^{\mathbf{s}}$ to the ${\cal B}$
register to obtain the state

$\frac{1}{2^{\ell}}\sum_{\mathbf{r},\mathbf{s}\in\\{0,1\\}^{\ell}}\ket{\mathbf{r},\mathbf{s}}_{\mathsf{Coin}}\otimes\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{0^{\ell}}_{\cal
A}\otimes
P_{\mathbf{X}}^{\mathbf{r}}P_{\mathbf{Z}}^{\mathbf{s}}\ket{\varphi}_{\cal B}$

  5. 5.

Apply Hadamard gates $H^{\otimes 2\ell}$ to the $\mathsf{Coin}$ register in
the to obtain the state

$\frac{1}{4^{\ell}}\sum_{\mathbf{r},\mathbf{s},\mathbf{r}^{\prime},\mathbf{s}^{\prime}\in\\{0,1\\}^{\ell}}(-1)^{\mathbf{r}\cdot\mathbf{r}^{\prime}+\mathbf{s}\cdot\mathbf{s}^{\prime}}\ket{\mathbf{r}^{\prime},\mathbf{s}^{\prime}}_{\mathsf{Coin}}\otimes\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{r}\ket{0^{\ell}}_{\cal
A}\otimes
P_{\mathbf{X}}^{\mathbf{r}}P_{\mathbf{Z}}^{\mathbf{s}}\ket{\varphi}_{\cal B}$

where

$\mathbf{r}\cdot\mathbf{r}^{\prime}=\sum_{i=1}^{\ell}r_{i}\cdot
r^{\prime}_{i}~{}\mathsf{mod}~{}2~{}~{}\mbox{ and
}~{}~{}\mathbf{s}\cdot\mathbf{s}^{\prime}=\sum_{i=1}^{\ell}s_{i}\cdot
s^{\prime}_{i}~{}\mathsf{mod}~{}2.$

  6. 6.

Apply $\mathbf{X}^{\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{r}^{\prime}}$ to
the ${\cal A}$ register. Note that

$\displaystyle\mathbf{X}^{\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{r}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{0^{\ell}}=$
$\displaystyle\mathbf{X}^{\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{Z}^{\mathbf{r}^{\prime}}\mathbf{X}^{\mathbf{r}}\ket{0^{\ell}}=$
$\displaystyle(-1)^{\mathbf{r}\cdot\mathbf{r}^{\prime}}\mathbf{X}^{\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\mathbf{Z}^{\mathbf{r}^{\prime}}\ket{0^{\ell}}=$
$\displaystyle(-1)^{\mathbf{r}\cdot\mathbf{r}^{\prime}}\mathbf{X}^{\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{0^{\ell}}=$
$\displaystyle(-1)^{\mathbf{r}\cdot\mathbf{r}^{\prime}+\mathbf{s}\cdot\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{s}^{\prime}}\mathbf{X}^{\mathbf{r}}\ket{0^{\ell}}=$
$\displaystyle(-1)^{\mathbf{r}\cdot\mathbf{r}^{\prime}+\mathbf{s}\cdot\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\mathbf{X}^{\mathbf{s}^{\prime}}\ket{0^{\ell}}=$
$\displaystyle(-1)^{\mathbf{r}\cdot\mathbf{r}^{\prime}+\mathbf{s}\cdot\mathbf{s}^{\prime}}\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{\mathbf{s}^{\prime}}.$

Therefore the state obtained is

$\frac{1}{4^{\ell}}\sum_{\mathbf{r},\mathbf{s},\mathbf{r}^{\prime},\mathbf{s}^{\prime}\in\\{0,1\\}^{\ell}}\ket{\mathbf{r}^{\prime},\mathbf{s}^{\prime}}_{\mathsf{Coin}}\otimes\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{\mathbf{s}^{\prime}}_{\cal
A}\otimes
P_{\mathbf{X}}^{\mathbf{r}}P_{\mathbf{Z}}^{\mathbf{s}}\ket{\varphi}_{\cal B}$

which is equal to the state

$\left(\frac{1}{\sqrt{2}^{\ell}}(\ket{0}+\ket{1})^{\otimes\ell}\right)\otimes\frac{1}{(2\sqrt{2})^{\ell}}\sum_{\mathbf{r},\mathbf{s},\mathbf{s}^{\prime}\in\\{0,1\\}^{\ell}}\ket{\mathbf{s}^{\prime}}\otimes\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{\mathbf{s}^{\prime}}_{\cal
A}\otimes
P_{\mathbf{X}}^{\mathbf{r}}P_{\mathbf{Z}}^{\mathbf{s}}\ket{\varphi}_{\cal B}.$

  7. 7.

Discard the first $\ell$ registers to obtain the state

$\frac{1}{({2\sqrt{2}})^{\ell}}\sum_{\mathbf{r},\mathbf{s},\mathbf{s}^{\prime}\in\\{0,1\\}^{\ell}}\ket{\mathbf{s}^{\prime}}\otimes\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{\mathbf{s}^{\prime}}_{\cal
A}\otimes
P_{\mathbf{X}}^{\mathbf{r}}P_{\mathbf{Z}}^{\mathbf{s}}\ket{\varphi}_{\cal B}.$

  8. 8.

Output the state $\bm{\tau}_{{\cal A},{\cal B}}$ that is the reduced state of
the above on registers ${\cal A},{\cal B}$.

We next prove that

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle
10\sqrt{\delta}}}{{\approx}}\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma}).$
(21)

To this end, for a given $\mathbf{b}\in\\{0,1\\}^{\ell}$, denote by

$I=\\{i\in[\ell]:\mathbf{b}_{i}=0\\}~{}\mbox{ and
}~{}J=\\{j\in[\ell]:\mathbf{b}_{j}=1\\},$

so that $I$ and $J$ partition $[\ell]$.

Next we define a new opening algorithm
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$. We first give a “buggy” definition
of ${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$, and then show how to fix it in
Remark 7.16. ${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$ on input
$(\bm{\rho},\mathbf{b})$ does the following:

  1. 1.

Compute
$\bm{\rho}_{1}=U_{0}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{I},\mathsf{open}_{I}}U_{0}[\bm{\rho}]$,
where $\mathsf{open}_{I}$ is the register that contains the openings
$\\{\mathbf{z}_{i}\\}_{i\in I}$, and
$\mathsf{CNOT}_{\mathsf{copy}_{I},\mathsf{open}_{I}}$ copies the content of
this register to a fresh register denoted by $\mathsf{copy}_{I}$.

  2. 2.

Measure the registers $\mathsf{copy}_{I}$ of $\bm{\rho}_{1}$ to obtain
$\\{\mathbf{z}_{i}\\}_{i\in I}$ and denote the resulting state by
$\bm{\rho}_{2}$.

  3. 3.

Compute
$\bm{\rho}_{3}=U_{1}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{J},\mathsf{open}_{J}}U_{1}[\bm{\rho}_{2}]$,
where $\mathsf{open}_{J}$ is the register that contains the openings
$\\{\mathbf{z}_{j}\\}_{j\in J}$, and
$\mathsf{CNOT}_{\mathsf{copy}_{J},\mathsf{open}_{J}}$ copies the content of
this register to a fresh register denoted by $\mathsf{copy}_{J}$.

  4. 4.

Measure the registers $\mathsf{copy}_{J}$ of $\bm{\rho}_{3}$ to obtain
$\\{\mathbf{z}_{j}\\}_{j\in J}$ and denote the resulting state by
$\bm{\rho}_{4}$.

  5. 5.

Output $((\mathbf{z}_{1},\ldots,\mathbf{z}_{\ell}),\bm{\rho}_{4})$.

######  Remark 7.16.

We remark that as written,
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(\bm{\rho},\mathbf{b})$ may be
rejected with high probability. The reason is that, while the standard basis
openings of ${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$ and
${\mathsf{C}}^{*}.\mathsf{Open}$ are identical,
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$ can completely fail to open in the
Hadamard basis, since after computing the standard basis openings its state
becomes
$U_{0}^{\dagger}\mathsf{CNOT}_{\mathsf{copy}_{I},\mathsf{open}_{I}}U_{0}[\bm{\rho}]$,
with the $\mathsf{copy}_{I}$ registers measured. This is a disturbed state and
it is no longer clear that computing the Hardamard basis opening on it will
give an accepting opening.

To ensure that ${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(\bm{\rho},\mathbf{b})$
is accepted with the same probability as
${\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho},\mathbf{b})$, up to negligible
factors, we need to ensure that the state after computing the standard basis
openings remains undisturbed, or at least that this disturbance is undetected
by the algorithms that compute the Hadamard basis opening and verify whether
this opening is valid. To achieve this we slightly modify
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$ and allow it to compute the standard
basis opening using $(\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1})$. We note that
such opening algorithms are allowed in Corollary 7.11 (which we will later use
in our analysis).

Specifically, ${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$, rather than placing
the output of $U_{0}$ in the $\mathsf{open}_{I}$ registers, which when
measured may disturb the state, we use
$(\mathsf{sk}_{1},\ldots,\mathsf{sk}_{n+1})$ to apply the following post-
opening unitary to each $\mathsf{open}_{i}$ register, to ensure that when
measured the disturbance will not be noticed. Recall that $\mathsf{open}_{i}$
contains a vector
$\mathbf{z}=(\mathbf{z}_{1},\ldots,\mathbf{z}_{n+1})\in\\{0,1\\}^{(n+1)^{2}}$
where each $\mathbf{z}_{j}\in\\{0,1\\}^{n+1}$. The post-opening unitary does
the following:

  1. 1.

Coherently compute for every $j\in[n+1]$ the bit
$m_{j}=\mathbf{z}_{j}\cdot(1,\mathbf{x}^{\prime}_{j,0}\oplus\mathbf{x}^{\prime}_{j,1})$,
where $\mathbf{x}^{\prime}_{j,0}$ and $\mathbf{x}^{\prime}_{j,1}$ are the two
preimages of $\mathbf{y}_{i,j}$ that are computed using $\mathsf{sk}_{j}$.

  2. 2.

Let $\mathbf{m}=(m_{1},\ldots,m_{n+1})\in\\{0,1\\}^{n+1}$.

Note that if $\mathbf{z}$ is a successful opening (i.e., it is accepted) then
$\mathbf{m}$ is a preimage of $\mathbf{y}_{i,0}$, and whether a preimage is
measured or not is undetectable without knowing $\mathsf{sk}_{0}$, due to the
collapsing property of the underlying $\mathsf{NTCF}$ family.

  3. 3.

On an ancila register, compute a super-position over all
$\mathbf{z}^{\prime}=(\mathbf{z}^{\prime}_{1},\ldots,\mathbf{z}^{\prime}_{n+1})\in\\{0,1\\}^{(n+1)^{2}}$
such that for every $j\in[n+1]$
$m_{j}=\mathbf{z}^{\prime}_{j}\cdot(1,\mathbf{x}^{\prime}_{j,0}\oplus\mathbf{x}^{\prime}_{j,1})$.

  4. 4.

Swap register $\mathsf{open}_{i}$ with the ancila register above, so that now
$\mathbf{z}^{\prime}=(\mathbf{z}^{\prime}_{1},\ldots,\mathbf{z}^{\prime}_{n+1})$
is in register $\mathsf{open}_{i}$.

Now we can argue that the residual state after computing the standard basis
opening seems undisturbed for anyone who does not know $\mathsf{sk}_{0}$ due
to the collapsing property of the underlying $\mathsf{NTCF}$ family, and
computing the Hadamard opening and verification of it does not use
$\mathsf{sk}_{0}$ (and is done publicly given only $\mathsf{pk})$.

Note that since

$\delta=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})\\\
(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})\end{subarray}}\max_{\mathbf{b}^{\prime}\in\\{\mathbf{b},{\bf
0},{\bf
1\\}}}\Pr[\mathsf{Ver}(\mathsf{sk},\mathbf{y},\mathbf{b}^{\prime},{\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho},\mathbf{b}^{\prime}))=0].$

it holds that

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},1^{\ell})\\\
(\mathbf{y},\bm{\rho})\leftarrow{\mathsf{C}}^{*}.\mathsf{Commit}(\mathsf{pk},\bm{\sigma})\end{subarray}}\max_{\mathbf{b}^{\prime}\in\\{\mathbf{b},{\bf
0},{\bf
1\\}}}\Pr[\mathsf{Ver}(\mathsf{sk},\mathbf{y},\mathbf{b}^{\prime},{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(\bm{\rho},\mathbf{b}^{\prime}))=0]\leq
2\delta.$ (22)

This is the case since the probability that
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(\bm{\rho},\mathbf{b})$ is rejected is
bounded by the sum of the probabilities that
${\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho},0^{\ell})$ is rejected and
${\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho},1^{\ell})$ is rejected.

By Corollary 7.11, we conclude that for every $\mathbf{b}\in\\{0,1\\}^{\ell}$,

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle
6\sqrt{\delta}}}{{\approx}}\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
(23)

This implies that to prover Equation 21 it suffices to prove

$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle
4\sqrt{\delta}}}{{\approx}}\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
(24)

To this end, we first compute the distribution of measurement outcomes on the
extracted state. While in general the input to the extractor is a mixed state
$\bm{\rho}$, we will perform the calculations for a general pure state
$\ket{\varphi}$ instead. The results we obtain will hold for any pure state
$\ket{\varphi}$. Thus, they will extend by convexity to the post-commitment
state $\bm{\rho}$ as well, since we can always write
$\bm{\rho}=\sum_{k}p_{k}\ket{\varphi_{k}}\bra{\varphi_{k}}$ for some
collection of pure states $\\{\ket{\varphi_{k}}\\}$.

As a first step in the computation, we remark that for every $i,j\in[\ell]$,
it holds that $P_{Z_{i}}$ and $P_{Z_{j}}$ commute and $P_{X_{i}}$ and
$P_{X_{j}}$ commute. This follows from the fact that we defined all the
$P_{Z_{i}}$ with respect to the same unitary $U_{0}$ and defined all the
$P_{X_{i}}$ with respect to the same unitary $U_{1}$. Thus, for an input state
$\ket{\varphi}$, the output of the extractor can be written as

$\frac{1}{{(2\sqrt{2})^{\ell}}}\sum_{\mathbf{r},\mathbf{s},\mathbf{s}^{\prime}\in\\{0,1\\}^{\ell}}\ket{\mathbf{s}^{\prime}}_{\mathsf{Coin}}\otimes\mathbf{Z}^{\mathbf{s}}\mathbf{X}^{\mathbf{r}}\ket{\mathbf{s}^{\prime}}_{\cal
A}\otimes
P_{\mathbf{X}_{I}}^{\mathbf{r}_{I}}P_{\mathbf{X}_{J}}^{\mathbf{r}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}P_{\mathbf{Z}_{I}}^{\mathbf{s}_{I}}\ket{\varphi}_{\cal
B}.$

##### Measuring the $I$ registers of ${\cal A}$ in the standard basis.

Now, we imagine measuring the $I$ registers of ${\cal A}$ in the standard
basis; we denote these registers by ${\cal A}_{I}$. When we measure them we
obtain an outcome which we will denote $\mathbf{a}_{I}$. The unnormalized
post-measurement state is obtained by applying the projector
$I\otimes\ket{\mathbf{a}_{I}}\bra{\mathbf{a}_{I}}_{{\cal A}_{I}}$ to the
state, where the factor of identity acts on all registers other than ${\cal
A}_{I}$. To calculate what happens, let us examine what happens when we apply
the projector $\ket{\mathbf{a}_{I}}\bra{\mathbf{a}_{I}}$ to
$\mathbf{Z}^{\mathbf{s}_{I}}_{I}\mathbf{X}^{\mathbf{r}_{I}}_{I}\ket{\mathbf{s}^{\prime}_{I}}$.
Note that

$\displaystyle\bra{\mathbf{a}_{I}}\mathbf{Z}_{I}^{\mathbf{s}_{I}}\mathbf{X}_{I}^{\mathbf{r}_{I}}\ket{\mathbf{s}^{\prime}_{I}}=$
$\displaystyle\prod_{i\in
I}\bra{a_{i}}Z_{i}^{s_{i}}X_{i}^{r_{i}}\ket{s^{\prime}_{i}}=$
$\displaystyle\prod_{i\in I}\bra{a_{i}}Z_{i}^{s_{i}}\ket{s^{\prime}_{i}\oplus
r_{i}}=$ $\displaystyle\prod_{i\in I}\bra{a_{i}}(-1)^{s_{i}\cdot
a_{i}}\ket{s^{\prime}_{i}\oplus r_{i}}=$ $\displaystyle\prod_{i\in
I}(-1)^{s_{i}\cdot a_{i}}\bra{a_{i}}\ket{s^{\prime}_{i}\oplus r_{i}},$

where for every $i\in I$, $\bra{a_{i}}\ket{s^{\prime}_{i}\oplus r_{i}}$ is $1$
if $a_{i}\oplus r_{i}=s^{\prime}_{i}$, and $0$ otherwise. This means that if
we obtain an outcome $\mathbf{a}_{I}$, then we force the
$\mathbf{s}^{\prime}_{I}$ register to be $\mathbf{a}_{I}\oplus\mathbf{r}_{I}$.
This means that the sum over $\mathbf{s}^{\prime}$ collapses to a sum over
$\mathbf{s}^{\prime}_{J}$, since $J$ is the complement of $I$. Thus, we obtain
the unnormalized post-measurement state

$\frac{1}{({2\sqrt{2}})^{\ell}}\sum_{\mathbf{r},\mathbf{s}\in\\{0,1\\}^{\ell},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}(-1)^{\mathbf{s}_{I}\cdot\mathbf{a}_{I}}\ket{\mathbf{a}_{I}\oplus\mathbf{r}_{I}}_{\mathsf{Coin}_{I}}\ket{\mathbf{s}^{\prime}_{J}}_{\mathsf{Coin}_{J}}\otimes\ket{\mathbf{a}_{I}}_{{\cal
A}_{I}}\otimes
Z_{J}^{\mathbf{s}_{J}}X_{J}^{\mathbf{r}_{J}}\ket{\mathbf{s}^{\prime}_{J}}_{{\cal
A}_{J}}\otimes
P_{\mathbf{X}_{I}}^{\mathbf{r}_{I}}P_{\mathbf{X}_{J}}^{\mathbf{r}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}P_{\mathbf{Z}_{I}}^{\mathbf{s}_{I}}\ket{\varphi}_{\cal
B}$

Note that

$\frac{1}{2^{|I|}}\sum_{\mathbf{s}_{I}\in\\{0,1\\}^{|I|}}(-1)^{\mathbf{s}_{I}\cdot\mathbf{a}_{I}}P_{Z_{I}}^{\mathbf{s}_{I}}=\frac{1}{2^{|I|}}\prod_{i\in
I}\sum_{s_{i}\in\\{0,1\\}}(-1)^{s_{i}\cdot a_{i}}P_{Z_{i}}^{s_{i}}=\prod_{i\in
I}\frac{I+(-1)^{a_{i}}P_{Z_{i}}}{2}$

and thus the state we obtain after the projection is equal to

$\frac{1}{2^{|J|}\cdot{2}^{\ell/2}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}_{J},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\ket{\mathbf{a}_{I}\oplus\mathbf{r}_{I}}\otimes\ket{\mathbf{s}^{\prime}_{J}}\otimes\ket{\mathbf{a}_{I}}_{{\cal
A}_{I}}\otimes
Z_{J}^{\mathbf{s}_{J}}X_{J}^{\mathbf{r}_{J}}\ket{\mathbf{s}^{\prime}_{J}}_{{\cal
A}_{J}}\otimes
P_{\mathbf{X}_{I}}^{\mathbf{r}_{I}}P_{\mathbf{X}_{J}}^{\mathbf{r}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\prod_{i\in
I}\left(\frac{I+(-1)^{a_{i}}P_{Z_{i}}}{2}\right)\ket{\varphi}_{\cal B}.$

Denoting by $\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}=\prod_{i\in
I}\frac{I+(-1)^{a_{i}}P_{Z_{i}}}{2}$, the above projected state is equal to

$\ket{\Psi_{\mathbf{a}_{I}}}=\frac{1}{2^{|J|}\cdot{2}^{\ell/2}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}_{J},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\ket{\mathbf{a}_{I}\oplus\mathbf{r}_{I}}_{\mathsf{Coin}_{I}}\otimes\ket{\mathbf{s}^{\prime}_{J}}_{\mathsf{Coin}_{J}}\otimes\ket{\mathbf{a}_{I}}_{{\cal
A}_{I}}\otimes
Z_{J}^{\mathbf{s}_{J}}X_{J}^{\mathbf{r}_{J}}\ket{\mathbf{s}^{\prime}_{J}}_{{\cal
A}_{J}}\otimes
P_{\mathbf{X}_{I}}^{\mathbf{r}_{I}}P_{\mathbf{X}_{J}}^{\mathbf{r}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}.$ (25)

The square norm of this unnormalized state is the probability that the
measurement returns outcome $\mathbf{a}_{I}$. We now calculate this:

$\displaystyle\Pr[\mathbf{a}_{I}]$ $\displaystyle=\frac{1}{2^{2|J|}\cdot
2^{\ell}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\|\sum_{\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}Z^{\mathbf{s}_{J}}_{J}X^{\mathbf{r}_{J}}_{J}\ket{\mathbf{s}^{\prime}_{J}}_{{\cal{A}}_{J}}\otimes
P^{\mathbf{r}_{I}}_{\mathbf{X}_{I}}P^{\mathbf{r}_{J}}_{\mathbf{X}_{J}}P^{\mathbf{s}_{J}}_{\mathbf{Z}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{{\cal
B}}\|^{2}$ $\displaystyle=\frac{1}{2^{2|J|}\cdot
2^{\ell}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\|\sum_{\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}(-1)^{\mathbf{s}_{J}\cdot(\mathbf{s}^{\prime}_{J}+\mathbf{r}_{J})}\ket{\mathbf{s}^{\prime}_{J}+\mathbf{r}_{J}}_{{\cal{A}}_{J}}\otimes
P^{\mathbf{r}_{I}}_{\mathbf{X}_{I}}P^{\mathbf{r}_{J}}_{\mathbf{X}_{J}}P^{\mathbf{s}_{J}}_{\mathbf{Z}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{{\cal
B}}\|^{2}$ $\displaystyle=\frac{1}{2^{2|J|}\cdot
2^{\ell}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\sum_{\mathbf{s}_{J},\mathbf{s}^{\prime\prime}_{J}\in\\{0,1\\}^{|J|}}(-1)^{(\mathbf{s}_{J}+\mathbf{s}^{\prime\prime}_{J})\cdot(\mathbf{s}^{\prime}_{J}+\mathbf{r}_{J})}\bra{\varphi}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}P^{\mathbf{s}^{\prime\prime}_{J}}_{\mathbf{Z}_{J}}P^{\mathbf{s}_{J}}_{\mathbf{Z}_{J}}\Pi_{P_{{\mathbf{Z}_{I},\mathbf{a}_{I}}}}\ket{\varphi}_{{\cal
B}}$
$\displaystyle=\frac{1}{2^{2|J|}}\sum_{\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\sum_{\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}\bra{\varphi}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\Pi_{P_{{\mathbf{Z}_{I},\mathbf{a}_{I}}}}\ket{\varphi}_{{\cal
B}}$
$\displaystyle=\bra{\varphi}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\Pi_{P_{{\mathbf{Z}_{I},\mathbf{a}_{I}}}}\ket{\varphi}_{{\cal
B}}.$ (26)

Thus, we have shown that the outcome distribution from the extracted state is
identical to the outcome distribution from measuring the original state
$\ket{\varphi}$.

##### Measuring the $J$ registers of ${\cal A}$ in the Hadamard basis.

Now, we imagine taking the standard basis post-measurement state
$\ket{\Psi_{\mathbf{a}_{I}}}$, and then further measuring the $J$ registers of
${\cal A}$ in the Hadamard basis. We denote these registers by ${\cal A}_{J}$
and the outcome by $\mathbf{a}_{J}$. To obtain the unnormalized post-
measurement state after this measurement, we apply the projector
$H^{\otimes|J|}\ket{\mathbf{a}_{J}}\bra{\mathbf{a}_{J}}H^{\otimes|J|}$ to the
$J$ registers of ${\cal A}$. Note that

$\displaystyle\bra{\mathbf{a}_{J}}H^{\otimes|J|}Z_{J}^{\mathbf{s}_{J}}X_{J}^{\mathbf{r}_{J}}\ket{\mathbf{s}^{\prime}_{J}}=$
$\displaystyle\prod_{j\in
J}\bra{a_{j}}HZ_{j}^{s_{j}}X_{j}^{r_{j}}\ket{s^{\prime}_{j}}=$
$\displaystyle\prod_{j\in J}\bra{a_{j}}HZ_{j}^{s_{j}}\ket{s^{\prime}_{j}\oplus
r_{j}}=$ $\displaystyle\prod_{j\in
J}\bra{a_{j}}H(-1)^{s_{j}\cdot(s^{\prime}_{j}\oplus
r_{j})}\ket{s^{\prime}_{j}\oplus r_{j}}=$ $\displaystyle\prod_{j\in
J}\frac{(-1)^{s_{j}\cdot(s^{\prime}_{j}\oplus
r_{j})}}{\sqrt{2}}\bra{a_{j}}(\ket{0}+(-1)^{s^{\prime}_{j}\oplus
r_{j}}\ket{1})=$ $\displaystyle\frac{1}{2^{|J|/2}}\prod_{j\in
J}(-1)^{(s_{j}\oplus a_{j})\cdot(s^{\prime}_{j}\oplus
r_{j})}\triangleq\beta_{J}^{\mathbf{s}^{\prime}_{J}}$

Thus we obtain the state

$\frac{1}{2^{|J|}\cdot{2}^{\ell/2}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}_{J},\mathbf{s}^{\prime}_{J}\in\\{0,1\\}^{|J|}}\ket{\mathbf{a}_{I}\oplus\mathbf{r}_{I}}\otimes\beta_{J}^{\mathbf{s}^{\prime}_{J}}\ket{\mathbf{s}^{\prime}_{J}}\otimes\ket{\mathbf{a}_{I}}_{{\cal
A}_{I}}\otimes H^{\otimes|J|}\ket{\mathbf{a}_{J}}_{{\cal A}_{J}}\otimes
P_{\mathbf{X}_{I}}^{\mathbf{r}_{I}}P_{\mathbf{X}_{J}}^{\mathbf{r}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}.$

Next, we observe that

$\displaystyle\sum_{\mathbf{s}^{\prime}_{J}}\beta_{J}^{\mathbf{s}^{\prime}_{J}}\ket{\mathbf{s}^{\prime}_{J}}$
$\displaystyle=\frac{1}{\sqrt{2^{|J|}}}\sum_{\mathbf{s}^{\prime}_{J}}(-1)^{(\mathbf{s}_{J}\oplus\mathbf{a}_{J})\cdot(\mathbf{s}^{\prime}_{J}\oplus\mathbf{r}_{J})}\ket{\mathbf{s}^{\prime}_{J}}$
(27)
$\displaystyle=(-1)^{(\mathbf{s}_{J}\oplus\mathbf{a}_{J})\cdot\mathbf{r}_{J}}H^{\otimes|J|}\ket{\mathbf{s}_{J}\oplus\mathbf{a}_{J}}$
(28)

Thus, applying Equation 28 to simplify the sum over $\mathbf{s}^{\prime}_{J}$,
we can write this as

$\displaystyle\ket{\Psi_{\mathbf{a}_{I},\mathbf{a}_{J}}}=\frac{1}{2^{\ell/2}2^{|J|}}\sum_{\mathbf{r}\in\\{0,1\\}^{\ell},\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}(-1)^{(\mathbf{s}_{J}\oplus\mathbf{a}_{J})\cdot\mathbf{r}_{J}}$
$\displaystyle\ket{\mathbf{a}_{I}\oplus\mathbf{r}_{I}}_{\mathsf{Coin}_{I}}\otimes
H^{\otimes|J|}\ket{\mathbf{s}_{J}\oplus\mathbf{a}_{J}}_{\mathsf{Coin}_{J}}$
$\displaystyle\otimes\ket{\mathbf{a}_{I}}_{{\cal A}_{I}}\otimes
H^{\otimes|J|}\ket{\mathbf{a}_{J}}_{{\cal A}_{J}}\otimes
P^{\mathbf{r}_{I}}_{\mathbf{X}_{I}}P^{\mathbf{r}_{J}}_{\mathbf{X}_{J}}P^{\mathbf{s}_{J}}_{\mathbf{Z}_{j}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}.$

Note that

$\frac{1}{2^{|J|}}\sum_{\mathbf{r}_{J}\in\\{0,1\\}^{|J|}}(-1)^{(\mathbf{s}_{J}\oplus\mathbf{a}_{J})\cdot\mathbf{r}_{J}}P_{\mathbf{X}_{J}}^{\mathbf{r}_{J}}=\prod_{j\in
J}\frac{I+(-1)^{s_{j}\oplus a_{j}}P_{X_{j}}}{2}.$

Let us define

$\Pi_{P_{\mathbf{X}_{j}},\mathbf{s}_{J}\oplus\mathbf{a}_{J}}=\prod_{j\in
J}\frac{I+(-1)^{s_{j}\oplus a_{j}}P_{X_{j}}}{2}.$

Then we can rewrite $\ket{\Psi_{\mathbf{a}_{I},\mathbf{a}_{J}}}$ as

$\displaystyle\ket{\Psi_{\mathbf{a}_{I},\mathbf{a}_{J}}}=\frac{1}{{2}^{\ell/2}}\sum_{\mathbf{r}_{I}\in\\{0,1\\}^{|I|},\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}\ket{\mathbf{a}_{I}\oplus\mathbf{r}_{I}}_{\mathsf{Coin}_{I}}$
$\displaystyle\otimes
H^{\otimes|J|}\ket{\mathbf{s}_{J}\oplus\mathbf{a}_{J}}_{\mathsf{Coin}_{J}}\otimes\ket{\mathbf{a}_{I}}_{{\cal
A}_{I}}\otimes H^{\otimes|J|}\ket{\mathbf{a}_{J}}_{{\cal A}_{J}}$
$\displaystyle\otimes
P_{\mathbf{X}_{I}}^{\mathbf{r}_{I}}\Pi_{P_{\mathbf{X}_{J}},\mathbf{a}_{J}\oplus\mathbf{s}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}.$

The square norm of this unnormalized state is the probability that the
measurement returns outcome $\mathbf{a}_{J}$. We now calculate this:

$\displaystyle\Pr[\mathbf{a}_{I},\mathbf{a}_{J}]$
$\displaystyle=\frac{2^{|I|}}{2^{\ell}}\left\|\sum_{\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}H^{\otimes|J|}\ket{\mathbf{s}_{J}\oplus\mathbf{a}_{J}}_{\mathsf{Coin}_{J}}\otimes\Pi_{P_{\mathbf{X}_{J}},\mathbf{a}_{J}\oplus\mathbf{s}_{J}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}\right\|^{2}$
$\displaystyle=\frac{1}{2^{|J|}}\sum_{\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}\|\Pi_{P_{\mathbf{X}_{j},\mathbf{a}_{J}\oplus\mathbf{s}_{J}}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}\|^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mathbf{s}_{J}\in\\{0,1\\}^{|J|}}\|\Pi_{P_{\mathbf{X}_{j},\mathbf{a}_{J}\oplus\mathbf{s}_{J}}}P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}\Pi_{P_{\mathbf{Z}_{I},\mathbf{a}_{I}}}\ket{\varphi}_{\cal
B}\|^{2}.$ (29)

This equation can be interpreted operationally as follows: the probability of
obtaining an outcome $(\mathbf{a}_{I},\mathbf{a}_{J})$ by measuring the
extracted state is _equal_ to the probability of obtaining this outcome by the
following procedure acting on $\ket{\varphi}$:

  1. 1.

First, measure the observables $P_{Z_{i}}$ for every $i\in I$ on
$\ket{\varphi}$, obtaining an outcome $\mathbf{a}_{I}$.

  2. 2.

Next, sample a string $\mathbf{s}_{J}\in\\{0,1\\}^{|J|}$ uniformly at random
and apply $P_{\mathbf{Z}_{J}}^{\mathbf{s}_{J}}$ to the state.

  3. 3.

Next, measure the observables $P_{X_{j}}$ for every $j\in J$ on the state,
obtaining an outcome $\mathbf{u}_{J}$.

  4. 4.

Set $\mathbf{a}_{J}=\mathbf{u}_{J}\oplus\mathbf{s}_{J}$ and return
$(\mathbf{a}_{I},\mathbf{a}_{J})$.

##### The proof of Equation 24

We first define a new distribution, which we denote by
$\widehat{\mathsf{Real}}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})$.
This distribution is identical to
$\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})$
except that it does not run the $\mathsf{Ver}$ algorithm (i.e., it does not
run Item 2 of the definition of $\mathsf{Real}$ in Definition 5.6), and simply
sets $\mathbf{m}=\mathsf{Out}(\mathsf{sk},\mathbf{y},\mathbf{b},\mathbf{z})$.
We note that by Lemma 3.2,

$\widehat{\mathsf{Real}}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle\sqrt{2\delta}}}{{\approx}}\mathsf{Real}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})$
(30)

where recall $2\delta$ is the probability that $\mathsf{Ver}$ rejects
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(\lambda,\mathbf{b},\bm{\sigma})$ (see
Equation 22). Therefore to prove Equation 24 it suffices to prove that

$\widehat{\mathsf{Real}}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})\stackrel{{\scriptstyle
2\sqrt{\delta}}}{{\approx}}\mathsf{Ideal}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$
(31)

To this end, we first claim that

$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{\mathsf{Sim},I})\equiv(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{\widehat{\mathsf{Real}},I})$

where $(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{\mathsf{Sim},I})$ is
distributed by generating

$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m})\leftarrow{\mathsf{Ideal}}^{\mathsf{Ext},{\mathsf{C}}^{*}.\mathsf{Open}}(\lambda,\mathbf{b},\bm{\sigma})$

and outputting $(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I})$, and
$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{\widehat{\mathsf{Real}},I})$
is distributed by generating

$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m})\leftarrow\widehat{\mathsf{Real}}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})$

and outputting $(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I})$. To see
why this is true, recall that Equation 26 implies that for a given
$\mathsf{pk},\mathbf{y},\mathbf{b}$, the outcome
$\mathbf{m}_{\mathsf{Sim},I}$, which is equal to $\mathbf{a}_{I}$ in the
notation used in that equation, is distributed according to the outcome of
measuring $P_{Z_{i}}$ on the qubits $i\in I$ qubits of the post-commitment
state. Moreover, $P_{Z_{i}}$ is defined so that it exactly matches the action
of $\widehat{\mathsf{Real}}$ since both do not run $\mathsf{Ver}$.

######  Remark 7.17.

We note that the observable $P_{Z_{i}}$ was defined with respect to the
opening algorithm ${\mathsf{C}}^{*}.\mathsf{Open}$ and we are considering
$\widehat{\mathsf{Real}}$ with respect to the opening algorithm
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$. The observable $P_{Z_{i}}$
corresponding to ${\mathsf{C}}^{*}.\mathsf{Open}$, when viewed as a unitary,
is different from observable corresponding to
${\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}$, denoted by $P^{\prime}_{Z_{i}}$,
when viewed as a unitary. In particular, recall that

$P_{Z_{i}}=U_{0}^{\dagger}\mathsf{Out}_{i,0}^{\dagger}Z_{\mathsf{out}_{i}}\mathsf{Out}_{i,0}U_{0}$

whereas

$P^{\prime}_{Z_{i}}=U_{0}^{\dagger}U_{\mathsf{post}}^{\dagger}\mathsf{Out}_{i,0}^{\dagger}Z_{\mathsf{out}_{i}}\mathsf{Out}_{i,0}U_{\mathsf{post}}U_{0},$

where $U_{\mathsf{post}}$ is the unitary that does some post-processing to the
$\mathsf{open}_{i}$ register to ensure that measuring it will not disturb the
state in a detectable way. Despite the fact that $P_{Z_{i}}$ and
$P^{\prime}_{Z_{i}}$ are different unitaries, on the subspace where the ancila
registers are initialized to $\ket{0}$, they are identical operators. In
particular, $P^{\prime}_{Z_{i}}$ preserves the subspace where the ancila
registers are initialized to $\ket{0}$.

To avoid cluttering of notation, from now on we denote
$\mathbf{m}_{\widehat{\mathsf{Real}},I}$ and $\mathbf{m}_{\mathsf{Sim},I}$ by
$\mathbf{m}_{I}$. Denote by

$\bm{\rho}^{\prime}_{I}=\Pi_{P_{\mathbf{Z}_{I}},\mathbf{m}_{I}}[\bm{\rho}]$

where $\bm{\rho}$ is post-commitment state and $\mathbf{m}_{I}$ is distributed
as $\mathbf{m}_{\mathsf{Sim},I}$. We note in the experiment
$\widehat{\mathsf{Real}}^{{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}}(\lambda,\mathbf{b},\bm{\sigma})$,
the post state after measuring $\mathbf{m}_{I}$ is $\bm{\rho}^{\prime}_{I}$.
This follows from Remark 7.17. We prove that

$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{\widehat{\mathsf{Real}},J})\stackrel{{\scriptstyle
2\sqrt{\delta}}}{{\approx}}(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{\mathsf{Sim},J})$
(32)

where $\mathbf{m}_{\widehat{\mathsf{Real}},J}$ is obtained as follows:

  1. 1.

Compute
$\mathbf{z}_{J}\leftarrow{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(\bm{\rho}^{\prime}_{I},(J,\mathbf{b}_{J}))$.

  2. 2.

For every $j\in J$ let
$\mathbf{m}_{\widehat{\mathsf{Real}},j}=\mathsf{Out}(\mathsf{sk},\mathbf{y},(j,1),\mathbf{z}_{j})$

  3. 3.

Output
$\mathbf{m}_{\widehat{\mathsf{Real}},J}=\\{\mathbf{m}_{\widehat{\mathsf{Real}},j}\\}_{j\in
J}$.

To describe how $\mathbf{m}_{\mathsf{Sim},J}$ is obtained, we take the
procedure obtained immediately below Equation 29, and apply the definitions of
the operational observable $P_{X}$, to obtain the following:

  1. 1.

Sample at random $\mathbf{s}_{J}\leftarrow\\{0,1\\}^{|J|}$.

  2. 2.

Compute
$\mathbf{z}_{J}\leftarrow{\mathsf{C}}^{*}.\mathsf{Open}_{[\ell]}(P_{Z_{J}}^{\mathbf{s}_{J}}[\bm{\rho}^{\prime}_{I}],(J,\mathbf{b}_{J}))$.

  3. 3.

For every $j\in J$ let
$u_{j}=\mathsf{Out}(\mathsf{sk},\mathbf{y},(j,1),\mathbf{z}_{j})$.

  4. 4.

For every $j\in J$ let
$\mathbf{m}_{\mathsf{Sim},j}=u_{j}\oplus\mathbf{s}_{j}$.

  5. 5.

Output $\mathbf{m}_{\mathsf{Sim},J}=(\mathbf{m}_{\mathsf{Sim},j})_{j\in J}$.

We prove Equation 32 separately for the non-succinct and the semi-succinct
versions. For the non-succinct version we rely on the adaptive hardcore bit
property and for the semi-succinct version we rely on the distributional
strong adaptive hardcore bit property. In both cases, we assume without loss
of generality that $\mathsf{Open}_{[\ell]}$ opens in the Hadamard basis
honestly, by measuring the relevant qubits in the standard basis. For every
$j\in J$, we denote by ${\cal O}_{j}$ the $n+1$ registers that are measured to
obtain the opening of the $j$’th committed qubit in the Hadamard basis.

##### Proof of Equation 32 in the non-succinct setting.

Let $\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$ denote the state
$\bm{\rho}^{\prime}_{I}$ projected to

$\mathsf{Ver}(\mathsf{sk},\mathbf{y},(J,1^{|J|}),\mathsf{Open}(\bm{\rho}^{\prime}_{I},(J,1^{|J|})))=1.$

By Lemma 3.2,

$\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]\stackrel{{\scriptstyle\sqrt{\delta}}}{{\equiv}}\bm{\rho}^{\prime}_{I}.$

Therefore to prove Equation 32 it suffices to prove that

$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*}_{{\mathsf{Real}},J})\approx(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*}_{\mathsf{Sim},J})$
(33)

where $\mathbf{m}^{*}_{{\mathsf{Real}},J}$ is distributed as
$\mathbf{m}_{\widehat{\mathsf{Real}},J}$ except that $\bm{\rho}^{\prime}_{I}$
is replaced with $\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$. Similarly,
$\mathbf{m}^{*}_{\mathsf{Sim},J}$ is distributed as
$\mathbf{m}_{\mathsf{Sim},J}$ except that $\bm{\rho}^{\prime}_{I}$ is replaced
with $\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$.

To prove Equation 33 it suffices to prove that

$\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\\{\mathbf{m}_{j,0}\\}_{j\in
J}\right)\approx\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\\{\mathbf{m}_{j,1}\oplus
1\\}_{j\in J}\right)$ (34)

where for every $j\in J$ and $u\in\\{0,1\\}$,

$(\mathbf{z}_{j,u},\bm{\rho}^{\prime}_{j,u})={\mathsf{C}}^{*}.\mathsf{Open}(P^{u}_{Z_{j}}\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}],(j,1))~{}~{}\mbox{
and
}~{}~{}\mathbf{m}_{j,u}=\mathsf{Out}(\mathsf{sk},\mathbf{y},(j,1),\mathbf{z}_{j,u}).$

We prove that for every $j\in J$,

$\displaystyle\left(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,0},\bm{\rho}^{\prime}_{j,0}\right)\approx\left(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,1}\oplus
1,\bm{\rho}^{\prime}_{j,1}\right),$ (35)

where $\mathsf{sk}_{-(j,0)}$ denotes all the secret keys except
$\mathsf{sk}_{j,0}$. Namely,

$\mathsf{sk}_{-(j,0)}\triangleq\left(\mathsf{sk}_{[\ell],1},\ldots,\mathsf{sk}_{[\ell],n+1},\mathsf{sk}_{[\ell]\setminus\\{j\\},0}\right).$

We next argue that Equation 35 implies Equation 34. To this end, we first
notice that $P_{Z_{j}}$ and ${\mathsf{C}}^{*}.\mathsf{Open}(\cdot,(j,1))$ only
touch the registers corresponding to the $j$’th committed qubit. This follows
from our assumption that ${\mathsf{C}}^{*}.\mathsf{Open}$ behaves honestly
when opening in the Hadamard basis. This in turn implies that for every
$u\in\\{0,1\\}$ it holds that $\bm{\rho}^{\prime}_{j,u}$ and
$\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$ are distributed identically on
the registers that do not correspond to the $j$’th committed qubit. Thus,
Equation 35 implies that

$\displaystyle\left(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,0},\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]_{\\{{\cal
O}_{j}\\}_{j\in
J\setminus\\{j\\}}}\right)\approx\left(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,1}\oplus
1,\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]_{\\{{\cal O}_{j}\\}_{j\in
J\setminus\\{j\\}}}\right).$ (36)

We next note that $\mathbf{m}_{j,u}$ is a $\mathsf{QPT}$ function of
$\Pi_{\mathsf{Ver}}[{\bm{\rho}^{\prime}_{I}}]_{{\cal O}_{j}}$ and
$\mathsf{sk}_{j}$. This, together with a hybrid argument implies that indeed
Equation 36 implies Equation 34, as desired.

Thus, we focus on proving Equation 35. Fix $j\in J$ and consider the mixed
state

$\bm{\rho}_{\mathsf{mix,j}}=\frac{1}{2}\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]+\frac{1}{2}P_{Z_{j}}\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$

Note that this state can be generated efficiently, with probability
$1-\delta$, from $\bm{\rho}$ given
$(\mathsf{sk}_{[\ell],1},\ldots,\mathsf{sk}_{[\ell],n+1})$. In addition, note
that $\bm{\rho}_{\mathsf{mix,j}}$ is identical to the state
$\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$ after measuring it in the
$P_{Z_{j}}$ basis. Recall that we assume that ${\mathsf{C}}^{*}.\mathsf{Open}$
behaves honestly on the Hadamard basis. Thus, the $(n+1)^{2}$ qubits of this
projected state $\bm{\rho}_{\mathsf{mix,j}}$ corresponding to the $j$’th
committed qubit are in superposition over
$\ket{d_{1},\mathbf{x}^{\prime}_{1}}\ldots\ket{d_{n+1},\mathbf{x}^{\prime}_{n+1}}$
such that for every $i\in[n+1]$,
$\mathbf{y}_{j,i}=\mathsf{Eval}(\mathsf{pk}_{j,i},d_{i},\mathbf{x}^{\prime}_{i})$.

Let

$(\mathbf{z}^{*},\bm{\rho}^{*})\leftarrow{\mathsf{C}}^{*}.\mathsf{Open}\left(\bm{\rho}_{\mathsf{mix,j}},(j,1)\right).$

By the adaptive hardcore bit property (w.r.t. $\mathsf{pk}_{j,0}$), letting
$m^{*}=\mathsf{Out}(\mathsf{sk},\mathbf{y},(j,1),\mathbf{z}^{*})$,

$(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},m^{*},\bm{\rho}^{*})\approx(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},U,\bm{\rho}^{*})$
(37)

where $U$ is the uniform distribution over $\\{0,1\\}$. Note that $m^{*}$ is a
random variable that with probability $\frac{1}{2}$ is distributed identically
to $\mathbf{m}_{j,0}$ and with probability $\frac{1}{2}$ is distributed
identically to $\mathbf{m}_{j,1}$. We next argue that Equation 37 implies that

$\displaystyle(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,0},\bm{\rho}^{\prime}_{j,0})\approx$
$\displaystyle(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,1}\oplus
1,\bm{\rho}^{\prime}_{j,1}),$

as desired. To this end, suppose for contradiction that there exists a
$\mathsf{QPT}$ algorithm $\mathsf{A}$ and a non-negligible $\epsilon>0$ such
that

$\displaystyle\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,1}\oplus
1,\bm{\rho}^{\prime}_{j,1})=1]-$
$\displaystyle\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,0},\bm{\rho}^{\prime}_{j,0})=1]\geq\epsilon.$

Denote by

$p_{u}=\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,u},\bm{\rho}^{\prime}_{j,u})=1]$

and denote by

$p^{\prime}_{1}=\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}_{j,1}\oplus
1,\bm{\rho}^{\prime}_{j,1})=1]$

Note that

$\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*},\bm{\rho}^{*})=1]=\frac{1}{2}p_{0}+\frac{1}{2}p_{1}.$

On the other hand

$\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},U,\bm{\rho}_{j,1}^{\prime})=1]=\frac{1}{2}p^{\prime}_{1}+\frac{1}{2}p_{1},$

which by the collapsing property implies that there exists a negligible
function $\mu$ such that

$\Pr[\mathsf{A}(\mathsf{pk},\mathsf{sk}_{-(j,0)},\mathbf{y},\mathbf{b},\mathbf{m}_{I},U,\bm{\rho}^{*})=1]=\frac{1}{2}p^{\prime}_{1}+\frac{1}{2}p_{1}\pm\mu$

This contradicts Equation 37 since

$\left(\frac{1}{2}p^{\prime}_{1}+\frac{1}{2}p_{1}\pm\mu\right)-\left(\frac{1}{2}p_{0}+\frac{1}{2}p_{1}\right)=\frac{1}{2}(p^{\prime}_{1}-p_{0})-\mu\geq\frac{\epsilon}{2}\pm\mu,$

which is non-negligible.

##### The proof of Equation 32 for the semi-succinct version.

We prove Equation 32 holds if the underlying $\mathsf{NTCF}$ family satisfies
the strong adaptive hardcore bit property (see Definition 3.8) and the
distributional strong adaptive hardcore bit property (Definition 4.1). Let
$\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$ denote the state
$\bm{\rho}^{\prime}_{I}$ projected to

$\mathsf{Ver}(\mathsf{sk},\mathbf{y},(J,0^{|J|}),{\mathsf{C}}^{*}.\mathsf{Open}(\bm{\rho}^{\prime}_{I},(J,0^{|J|})))=1.$

By Lemma 3.2,

$\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]\stackrel{{\scriptstyle\sqrt{\delta}}}{{\equiv}}\bm{\rho}^{\prime}_{I}.$

Therefore to prove Equation 32 it suffices to prove that

$(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*}_{{\mathsf{Real}},J})\approx(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*}_{\mathsf{Sim},J})$
(38)

where $\mathbf{m}^{*}_{{\mathsf{Real}},J}$ is distributed as
$\mathbf{m}_{\widehat{\mathsf{Real}},J}$ except that $\bm{\rho}^{\prime}_{I}$
is replaced with $\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$. Similarly,
$\mathbf{m}^{*}_{\mathsf{Sim},J}$ is distributed as
$\mathbf{m}_{\mathsf{Sim},J}$ except that $\bm{\rho}^{\prime}_{I}$ is replaced
with $\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]$.
We prove Equation 38 via a hybrid argument. Namely, denoting by $k=|J|$, we
prove that for every $\alpha\in[k]$,

$\displaystyle\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{(\alpha-1)}_{J}\right)\approx\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{(\alpha)}_{J}\right)$
(39)

where $\mathbf{m}^{(\beta)}_{J}$ is distributed exactly as
$\mathbf{m}_{\mathsf{Sim},J}$ accept that rather than choosing
$\mathbf{s}_{J}\leftarrow\\{0,1\\}^{|J|}$ at random, we only choose the first
$\beta$ coordinates randomly and the rest we set to zero. Namely, we choose
$\mathbf{s}_{1},\ldots,\mathbf{s}_{\beta}\leftarrow\\{0,1\\}$ and set
$\mathbf{s}_{\beta+1}=\ldots=\mathbf{s}_{k}=0$. Equation 39 implies that

$\displaystyle\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{(0)}_{J}\right)\approx\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{(k)}_{J}\right)$

thus proving Equation 34 since

$\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{(0)}_{J}\right)\equiv\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*}_{\widehat{\mathsf{Real}},J}\right)~{}~{}\mbox{
and
}~{}~{}\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{(k)}_{J}\right)\equiv\left(\mathsf{pk},\mathbf{y},\mathbf{b},\mathbf{m}_{I},\mathbf{m}^{*}_{\mathsf{Sim},J}\right).$

Fix any $\alpha\in[k]$ and we prove Equation 39 for this $\alpha$. Denote by
$J=\\{j_{1},\ldots,j_{k}\\}\subseteq[\ell]$. For every
$\mathbf{s}_{[\alpha-1]}=(s_{1},\ldots,s_{\alpha-1})\in\\{0,1\\}^{\alpha-1}$
consider the states

$\bm{\rho}_{\mathbf{s}_{[\alpha-1]}}=\prod_{i=1}^{\alpha-1}P^{s_{i}}_{Z_{j_{i}}}\Pi_{\mathsf{Ver}}[\bm{\rho}^{\prime}_{I}]~{}~{}\mbox{
and