# Succinct Classical Verification of Quantum Computation

James Bartusek UC Berkeley. Email<EMAIL_ADDRESS>Yael Tauman Kalai
Microsoft Research and MIT. Email<EMAIL_ADDRESS>Alex Lombardi MIT.
Email<EMAIL_ADDRESS>Fermi Ma Simons Institute and UC Berkeley. Email:
<EMAIL_ADDRESS>Giulio Malavolta Max Planck Institute for Security and
Privacy. Email<EMAIL_ADDRESS>Vinod Vaikuntanathan MIT. Email:
<EMAIL_ADDRESS>Thomas Vidick Caltech. Email<EMAIL_ADDRESS>Lisa Yang
MIT. Email<EMAIL_ADDRESS>
###### Abstract

We construct a classically verifiable _succinct_ interactive argument for
quantum computation (BQP) with communication complexity and verifier runtime
that are poly-logarithmic in the runtime of the BQP computation (and
polynomial in the security parameter). Our protocol is secure assuming the
post-quantum security of indistinguishability obfuscation (iO) and Learning
with Errors (LWE). This is the first succinct argument for quantum computation
_in the plain model_ ; prior work (Chia-Chung-Yamakawa, TCC ’20) requires both
a long common reference string and non-black-box use of a hash function
modeled as a random oracle.

At a technical level, we revisit the framework for constructing classically
verifiable quantum computation (Mahadev, FOCS ’18). We give a self-contained,
modular proof of security for Mahadev’s protocol, which we believe is of
independent interest. Our proof readily generalizes to a setting in which the
verifier’s first message (which consists of many public keys) is _compressed_.
Next, we formalize this notion of compressed public keys; we view the object
as a generalization of constrained/programmable PRFs and instantiate it based
on indistinguishability obfuscation.

Finally, we compile the above protocol into a fully succinct argument using a
(sufficiently composable) succinct argument of knowledge for NP. Using our
framework, we achieve several additional results, including

  * •

Succinct arguments for QMA (given multiple copies of the witness),

  * •

Succinct _non-interactive_ arguments for BQP (or QMA) in the quantum random
oracle model, and

  * •

Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without
iO).

###### Contents

  1. 1 Introduction
  2. 2 Technical Overview
    1. 2.1 Recap: Mahadev’s Measurement Protocol
    2. 2.2 Defining a (Succinct) Measurement Protocol
    3. 2.3 Constructing a Verifier-Succinct Measurement Protocol
    4. 2.4 Proof of Soundness
    5. 2.5 From a Verifier-Succinct Measurement Protocol to Succinct Arguments for BQP
  3. 3 Preliminaries
    1. 3.1 Quantum Information
    2. 3.2 Black-Box Access to Quantum Algorithms
    3. 3.3 Interactive Arguments
    4. 3.4 Computational Indistinguishability
    5. 3.5 Mahadev Randomized TCFs
    6. 3.6 Collapsing Hash Functions
    7. 3.7 Fully Homomorphic Encryption
    8. 3.8 Indistinguishability Obfuscation
    9. 3.9 Puncturable PRFs
  4. 4 Commit-and-Measure Protocols
    1. 4.1 Defining Commit-and-Measure Protocols
  5. 5 A Measurement Protocol Template
    1. 5.1 Measurement Protocol Description
  6. 6 Soundness of Mahadev’s Protocol
    1. 6.1 The Verifier’s Output Distribution
    2. 6.2 The Protocol Observables
    3. 6.3 The Extracted State
    4. 6.4 Indistinguishability of Measurement Outcomes
  7. 7 Succinct Key Generation from iO
    1. 7.1 Batch Key Generation: Definition and Construction
    2. 7.2 Combining Succinct Key Generation with Mahadev rTCFs
  8. 8 A Verifier-Succinct Protocol
    1. 8.1 Quantum commit-challenge-response protocols
    2. 8.2 Non-Interactive Post Hoc Verification of QMA
    3. 8.3 Semi-Succinct Delegation for QMA
  9. 9 The Fully Succinct Protocol
    1. 9.1 State-Preserving Succinct Arguments of Knowledge
    2. 9.2 The QMA Protocol, Version 1
    3. 9.3 The QMA Protocol, Version 2
  10. 10 Additional Results
    1. 10.1 Succinct Non-interactive Arguments in the QROM
    2. 10.2 Batch Arguments for QMA
    3. 10.3 Zero Knowledge
  11. A Proofs from Section 8
  12. B Proof of 6.4
  13. C Proof of 6.7

##  1 Introduction

Efficient verification of computation is one of the most fundamental and
intriguing concepts in computer science, and lies at the heart of the
$\mathrm{P}$ vs. $\mathrm{NP}$ question. It has been studied in the classical
setting for over three decades, giving rise to beautiful notions such as
interactive proofs [GMR85], multi-prover interactive proofs [BGKW88],
probabilistically checkable proofs [BFL90, ALM+92, AS92], and culminating with
the notion of a _succinct_ (interactive and non-interactive) _argument_
[Kil92, Mic94]. Roughly speaking, a succinct argument for a $T$-time
computation enables a prover running in $\mathsf{poly}(T)$ time to convince a
$\mathsf{polylog}(T)$-time verifier of the correctness of the computation
using only $\mathsf{polylog}(T)$ bits of communication, with soundness against
all polynomial-time cheating provers.

In a breakthrough result in 2018, Mahadev [Mah18] presented an interactive
argument system that enables a classical verifier to check the correctness of
an arbitrary _quantum_ computation. Mahadev’s protocol represents a different
kind of interactive argument — unlike the traditional setting in which the
prover simply has more _computational resources_ (i.e., running time) than the
verifier, the prover in Mahadev’s protocol works in a qualitatively more
powerful _computational model_. More precisely, for any $T$-time quantum
computation, Mahadev’s protocol enables a quantum prover running in time
$\mathsf{poly}(T)$ to convince a classical $\mathsf{poly}(T)$-time verifier
with $\mathsf{poly}(T)$ bits of classical communication. Soundness holds
against all quantum polynomial-time cheating provers under the post-quantum
hardness of the learning with errors (LWE) problem.

A fundamental question is whether we can get the best of both worlds: can the
prover have _both_ a more powerful computational model _and_ significantly
greater computational resources? Namely, we want an interactive argument
system for $T$-time quantum computation in which the quantum prover runs in
$\mathsf{poly}(T)$ time and convinces a $\mathsf{polylog}(T)$-time classical
verifier with $\mathsf{polylog}(T)$ bits of classical communication.

We answer this question affirmatively, both for $\mathsf{poly}(T)$-time
quantum computations, corresponding to the complexity class $\mathbf{BQP}$,
and also for the non-deterministic analog $\mathbf{QMA}$.

######  Theorem 1.1 (Succinct Arguments for $\mathbf{BQP}$).

Let $\lambda$ be a security parameter. Assuming the existence of a post-
quantum secure indistinguishability obfuscation scheme (iO) and the post-
quantum hardness of the learning with errors problem (LWE), there is an
interactive argument system for any $T$-time quantum computation on input
$x$,111A $T$-time quantum computation is a _language_ $L$ decidable by a
bounded-error $T$-time quantum Turing machine [BV97]. We leave it to future
work to address more complex tasks such as _sampling_ problems (as in
[CLLW20]). where

  * •

the prover is quantum and runs in time $\mathsf{poly}(T,\lambda)$,

  * •

the verifier is classical and runs in time $\mathsf{poly}(\log
T,\lambda)+\tilde{O}(|x|)$,222As in the classical setting, some dependence on
$|x|$ is necessary at least to read the input; as in [Kil92], we achieve a
fairly minimal $|x|$-dependence. and

  * •

the protocol uses $\mathsf{poly}(\log T,\lambda)$ bits of classical
communication.

######  Theorem 1.2 (Succinct Arguments for $\mathbf{QMA}$).

Assuming the existence of a post-quantum secure indistinguishability
obfuscation scheme (iO) and the post-quantum hardness of the learning with
errors problem (LWE), there is an interactive argument system for any $T$-time
quantum computation on input $x$ and a $\mathsf{poly}(T)$-qubit witness, where

  * •

the prover is quantum and runs in time $\mathsf{poly}(T,\lambda)$, using
polynomially many copies of the witness,333We inherit the need for
polynomially-many copies of the witness from prior works. This is a feature
common to all previous classical verification protocols, and even to the
quantum verification protocol of [FHM18].

  * •

the verifier is classical and runs in time $\mathsf{poly}(\log
T,\lambda)+\tilde{O}(x)$, and

  * •

the protocol uses $\mathsf{poly}(\log T,\lambda)$ bits of classical
communication.

##### A New Proof of Security for the [Mah18] Protocol.

One might hope to prove Theorems 1.1 and 1.2 by treating the Mahadev result as
a “black box” and showing that _any_ (classical) interactive argument for
quantum computations can be compressed into a succinct protocol via a suitable
cryptographic compiler. This is especially appealing given the extremely
technical nature of Mahadev’s security proof. Unfortunately, for reasons that
will become clear in the technical overview, this kind of generic compilation
seems unlikely to be achievable in our setting. Even worse, there does not
appear to be any easily formalized property of the Mahadev protocol that would
enable such a compilation.

Instead, our solution consists of two steps.

  1. (1)

We build a modified variant of the [Mah18] protocol and give an entirely self-
contained proof of security. This modified protocol satisfies a few technical
conditions that the original [Mah18] does not; most prominently, the _first
verifier message_ of our modified protocol is already succinct.

  2. (2)

We give a generic compiler that converts the protocol from Step (1) into a
succinct argument system.

Our Step (1) also results in a self-contained proof of security of the
original [Mah18] protocol that is more modular and amenable to further
modification and generalization, which we believe will be useful for future
work. Our analysis builds upon [Mah18] itself as well as an alternative
approach described in Vidick’s (unpublished) lecture notes [Vid20]. A concrete
consequence of our new proof is that one of the two “hardcore bit” security
requirements of the main building block primitive (“extended noisy trapdoor
claw-free functions”) in [Mah18] is not necessary.

##### Additional Results.

Beyond our main result of succinct arguments for $\mathbf{BQP}$ and
$\mathbf{QMA}$, we explore a number of extensions and obtain various new
protocols with additional properties.

  * •

Non-Interactive: Although our protocols are not public-coin, we show how to
modify them in order to apply the Fiat-Shamir transformation and round-
collapse our protocols. As a result, we obtain designated-verifier non-
interactive arguments for $\mathbf{BQP}$ (and the non-deterministic analog
$\mathbf{QMA}$) with security in the quantum random oracle model (QROM).

  * •

Zero-Knowledge: We show how to lift both variants of our protocol (interactive
and non-interactive) to achieve zero-knowledge. We show a generic
transformation based on classical two-party computation for reactive
functionalities that makes our protocols simulatable. This transformation does
not add any new computational assumption to the starting protocol.

  * •

Batch Arguments from LWE: For the case of batch arguments, i.e., where the
parties engage in the parallel verification of $n$ statements, we show a
succinct protocol that only assumes the post-quantum hardness of LWE (without
iO). In this context, succinctness requires that the verifier’s complexity
scales with the size of a _single instance_ , but is independent of $n$.

##### Prior Work.

As discussed above, Mahadev [Mah18] constructs a _non-succinct_ argument
system for BQP/QMA under LWE. The only prior work addressing _succinct_
classical arguments for quantum computation is the recent work of Chia, Chung
and Yamakawa [CCY20]. [CCY20] constructs a classically verifiable argument
system for quantum computation in the following setting:

  * •

The prover and verifier share a $\mathsf{poly}(T)$-bits long, structured
reference string (which requires a trusted setup to instantiate) along with a
hash function $h$ (e.g. SHA-3).

  * •

The “online communication” of the protocol is succinct ($\mathsf{poly}(\log
T)$).

  * •

Security is heuristic: it can be proved when $h$ is modeled as a random
oracle, but the _protocol description itself_ explicitly requires the code of
$h$ (i.e. uses $h$ in a non-black-box way).

We specifically note that when viewed in the _plain model_ (i.e., without
setup), the verifier must send the structured reference string to the prover,
resulting in a protocol that is _not succinct_. We note that [CCY20] was
specifically optimizing for a _two-message_ protocol, but their approach seems
incapable of achieving succinctness in the plain model even if further
interaction is allowed.

By contrast, our succinct interactive arguments are in the plain model and are
secure based on well-formed cryptographic assumptions, and our succinct
$2$-message arguments are proved secure in the QROM (and do not require a long
common reference string).

Finally, we remark that our approach to achieving succinct arguments
fundamentally (and likely necessarily) differs from [CCY20] because we
manipulate the “inner workings” of the [Mah18] protocol; by contrast [CCY20]
makes “black-box” use of a specific soundness property of the [Mah18] protocol
(referred to as “computational orthogonality” by [ACGH20]) and is otherwise
agnostic to how the protocol is constructed.

##### Acknowledgments.

AL is supported in part by a Charles M. Vest fellowship. GM is partially
supported by the German Federal Ministry of Education and Research BMBF (grant
16K15K042, project 6GEM). TV is supported by AFOSR YIP award number
FA9550-16-1-0495, a grant from the Simons Foundation (828076, TV), MURI Grant
FA9550-18-1-0161, the NSF QLCI program through grant number OMA-2016245 and
the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support
of the Gordon and Betty Moore Foundation (GBMF-12500028). AL, VV, and LY are
supported in part by DARPA under Agreement No. HR00112020023, a grant from
MIT-IBM Watson AI, a grant from Analog Devices, a Microsoft Trustworthy AI
grant and the Thornton Family Faculty Research Innovation Fellowship. Any
opinions, findings and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views
of the United States Government or DARPA. LY was supported in part by an NSF
graduate research fellowship.

##  2 Technical Overview

Our starting point is Mahadev’s protocol for classical verification of quantum
computation [Mah18], the core ingredient of which is a measurement protocol.

###  2.1 Recap: Mahadev’s Measurement Protocol

We begin by reviewing Mahadev’s $N$-qubit measurement protocol. In Mahadev’s
protocol, a quantum prover holding an $N$-qubit quantum state $\bm{\rho}$
interacts with a classical verifier, who wants to obtain the result of
measuring $\bm{\rho}$ according to measurement bases $h\in\\{0,1\\}^{N}$
($h_{i}$ specifies a basis choice for the $i$th qubit, with $h_{i}=1$
corresponding to the Hadamard basis and $h_{i}=0$ corresponding to the
standard basis).

##### Trapdoor Claw-Free Functions.

At the heart of the protocol is a cryptographic primitive known as an
_injective/claw-free trapdoor function_ (a variant of lossy trapdoor functions
[PW08, PVW08, GVW15]), which consists of two trapdoor function families
$\mathsf{Inj}$ (for injective) and $\mathsf{Cf}$ (for claw-free), with the
following syntactic requirements:444The actual syntactic requirements,
described in Section 3.5, are somewhat more complex due to the fact that the
functions in question are probabilistic.

  * •

Each function in $\mathsf{Cf}\cup\mathsf{Inj}$ is indexed by a public-key
$\mathsf{pk}$, where functions $f_{\mathsf{pk}}\in\mathsf{Inj}$ are injective
and functions $f_{\mathsf{pk}}\in\mathsf{Cf}$ are two-to-one. Moreover,
$\mathsf{pk}$ can be sampled along with a secret key $\mathsf{sk}$ that
enables computing $f^{-1}_{\mathsf{pk}}$ (i.e., $f^{-1}_{\mathsf{pk}}(y)$
consists of a single pre-image if $f_{\mathsf{pk}}\in\mathsf{Inj}$, and two
pre-images if $f_{\mathsf{pk}}\in\mathsf{Cf}$).

  * •

All functions in $\mathsf{Inj}$ and $\mathsf{Cf}$ have domain
$\\{0,1\\}^{\ell+1}$ (for some $\ell$) and the two pre-images of $y$ under
$f_{\mathsf{pk}}\in\mathsf{Cf}$ are of the form $(0,x_{0})$ and $(1,x_{1})$
for some $x_{0},x_{1}\in\\{0,1\\}^{\ell}$.

An injective/claw-free trapdoor function must satisfy the following security
properties:555In fact, Mahadev’s proof relies on two different hardcore bit
properties, but we show in this work that only the adaptive hardcore bit
property is needed.

  1. 1.

Claw-Free/Injective Indistinguishability. A random function in
$f_{\mathsf{pk}}\leftarrow\mathsf{Cf}$ is computationally indistinguishable
from a random function $f_{\mathsf{pk}}\leftarrow\mathsf{Inj}$.

  2. 2.

Adaptive Hardcore Bit. Given $f_{\mathsf{pk}}\leftarrow\mathsf{Cf}$, it is
computationally infeasible to output both (1) a pair $(x,y)$ satisfying
$f_{\mathsf{pk}}(x)=y$ and (2) a non-zero string $d\in\\{0,1\\}^{\ell+1}$ such
that $d\cdot(1,x_{0}\oplus x_{1})=0$, where $(0,x_{0})$ and $(1,x_{1})$ are
the two preimages of $y$.666The full definition places a slightly stronger
restriction on $d$ than simply being non-zero. However, this simplified
version will suffice for this overview.

To build some intuition about the usefulness of such function families, notice
that they can be used to commit to a single classical bit quite easily. The
commitment key is a function $f_{\mathsf{pk}}\in\mathsf{Inj}$, and commitment
to a bit $b$ is $y=f_{\mathsf{pk}}(b,x)$ for a random $x\in\\{0,1\\}^{n}$. It
is not hard to verify that this is a statistically binding and computationally
hiding commitment of $b$. On the other hand, if
$f_{\mathsf{pk}}\in\mathsf{Cf}$, it is a statistically hiding and
computationally binding commitment of $b$.777In particular,
$f_{\mathsf{pk}}\in\mathsf{Cf}$ satisfies Unruh’s definition of _collapse-
binding_ [Unr16b].

##### Protocol Description.

With this intuition in mind, we now describe a (slightly simplified version
of) the Mahadev measurement protocol. Mahadev’s protocol is a many-fold
sequential repetition of the following one-bit challenge protocol.

$\mathbf{V}\rightarrow\mathbf{P}$:

The verifier samples $N$ pairs of functions and their trapdoors: for every
$i\in[\ell]$, he samples
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Inj}$ if $h_{i}=0$ and
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Cf}$ if $h_{i}=1$. He
sends the $N$-tuple of public keys (function descriptions)
$(\mathsf{pk}_{1},\ldots,\mathsf{pk}_{N})$ to the prover.

$\mathbf{P}\rightarrow\mathbf{V}$:

The prover holds an $N$-qubit state $\bm{\rho}$ on register
$\mathcal{B}=\mathcal{B}_{1}\otimes\cdots\mathcal{B}_{N}$. She initializes
registers $\mathcal{X}=\mathcal{X}_{1}\otimes\cdots\mathcal{X}_{N}$ so that
each $\mathcal{X}_{i}$ is an $\ell$-qubit register in uniform superposition.
Then she evaluates each $f_{\mathsf{pk}_{i}}$ on the $\ell+1$ qubit register
$\mathcal{B}_{i}\otimes\mathcal{X}_{i}$ and measures the output to obtain
$y_{i}$. Finally, she sends $\underline{(y_{1},\ldots,y_{N})}$ to the
verifier, keeping the registers $\mathcal{B},\mathcal{X}$ for herself.

$\mathbf{V}\rightarrow\mathbf{P}$:

The verifier picks a random challenge bit $c\leftarrow\\{0,1\\}$ and sends it
to the prover. $c=0$ indicates a “test round” and $c=1$ indicates a
“measurement round”.

$\mathbf{P}\rightarrow\mathbf{V}$:

If $c=0$ (“test”), the prover measures each
$\mathcal{B}_{i}\otimes\mathcal{X}_{i}$ in the standard basis, obtaining
$(b_{i},x_{i})\in\\{0,1\\}\times\\{0,1\\}^{\ell}$, and sends
$(b_{i},x_{i})_{i=1}^{N}$ to the verifier.

If $c=1$ (“measure”), she measures each
$\mathcal{B}_{i}\otimes\mathcal{X}_{i}$ in the Hadamard basis (i.e., she
applies the Hadamard gate $H$ on each qubit and then measures in the standard
basis), obtaining $d_{i}\in\\{0,1\\}^{\ell+1}$, and sends $(d_{i})_{i=1}^{N}$
to the verifier.

$\mathbf{V}$ (output):

If $c=0$ (“test”), $\mathbf{V}$ either accepts or rejects the interaction but
outputs nothing. In particular, $\mathbf{V}$ checks that
$f_{\mathsf{pk}_{i}}(b_{i},x_{i})=y_{i}$. If any of the checks fail, reject.

If $c=1$ (“measure”), proceed as follows. Let $R\subseteq[N]$ be the set of
indices where $h_{i}=1$, corresponding to Hadamard basis measurements, and let
$S=[N]\setminus R$ be the set of indices corresponding to standard basis
measurements.

For each $i\in R$, $\mathbf{V}$ computes the two inverses $(0,x_{i,0})$ and
$(1,x_{i,1})$ of $y_{i}$ (which are guaranteed to exist since
$f_{\mathsf{pk},i}\in\mathsf{Cf}$) using $\mathsf{sk}_{i}$. $\mathbf{V}$ sets
$u_{i}:=d\cdot(1,x_{i,0}\oplus x_{i,1})$ as the $i^{th}$ measurement outcome.
For every $i\in S$, $\mathbf{V}$ ignores $d_{i}$, and sets $v_{i}$ to be the
first bit of $f_{\mathsf{pk}_{i}}^{-1}(y_{i})$, computed using the trapdoor
$\mathsf{sk}_{i}$ (this is well-defined since
$f_{\mathsf{pk},i}\in\mathsf{Inj}$). Finally $\mathbf{V}$ outputs the $N$-bit
string $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

Mahadev [Mah18] proves that if a malicious prover $\mathbf{P}^{*}$ passes the
test round with probability $1$, then there exists an $N$-qubit quantum state
$\bm{\rho}^{*}$ — _independent_ of the verifier’s measurement basis $h$ — such
that the result of measuring $\bm{\rho}^{*}$ according to $h$ is
computationally indistinguishable from the verifier’s $N$-bit output
distribution in the measurement round.888This can be extended to provers that
pass the test round with probability $1-\varepsilon$ by the gentle measurement
lemma. In particular, an efficient distinguisher can only distinguish the
verifier’s output distribution from the result of measuring some
$\bm{\rho}^{*}$ with advantage $\mathsf{poly}(\varepsilon)$. While her
definition requires that such a $\bm{\rho}^{*}$ _exists_ , Vidick and Zhang
[VZ21] showed that Mahadev’s proof steps implicitly define an extractor that
efficiently produces $\bm{\rho}^{*}$ using black-box access to
$\mathbf{P}^{*}$.

###  2.2 Defining a (Succinct) Measurement Protocol

Our first (straightforward but helpful) step is to give an explicit definition
of a _commit-and-measure protocol_ that abstracts the completeness and
soundness properties of Mahadev’s measurement protocol as established in
[Mah18, VZ21]. Roughly speaking, a commit-and-measure protocol is sound if,
for any malicious prover $\mathbf{P}^{*}$ that passes the test round with
probability $1$ and any basis choice $h$, there exists an efficient extractor
that (without knowledge of $h$) interacts with prover and outputs an extracted
state $\bm{\tau}$ such that the following are indistinguishable:

  * •

the distribution of verifier outputs obtained in the measurement round from
interacting with $\mathbf{P}^{*}$ using basis choice $h$, and

  * •

the distribution of measurement outcomes obtained from measuring $\bm{\tau}$
according to $h$.

This abstraction will be particularly helpful for reasoning about our eventual
_succinct_ measurement protocols, which will necessitate modifying Mahadev’s
original protocol.

##### Can a Measurement Protocol be Succinct?

Given the definition of a measurement protocol, an immediate concern arises
with respect to obtaining succinct arguments: the verifier’s _input_ to the
measurement protocol – the basis vector $h$ – is inherently non-succinct.
Since the number of qubits $N$ grows with the runtime of the BQP computation
when used to obtain quantum verification [FHM18], this poses an immediate
problem.

Our solution to this problem is to only consider basis vectors $h$ that are
_succinct_ ; our formalization is that $h$ must be the truth table of an
efficiently computable function $f:[\log N]\rightarrow\\{0,1\\}$. For any such
$h$, we can represent the verifier’s input as a circuit $C$ that computes $h$,
removing the above obstacle.

However, in order for there to be any hope of this idea working, it must be
the case that measurement protocols for bases with succinct representations
are still useful for constructing delegation for BQP. Fortunately, it has been
shown [ACGH20] that classically verifiable (non-succinct) arguments for BQP
can be constructed by invoking Mahadev’s measurement protocol (and, by
inspection of the proof, any measurement protocol satisfying our definition)
on a _uniformly random basis string_ $h\leftarrow\\{0,1\\}^{N}$. Then, by
computational indistinguishability, it is also possible to use a
_pseudorandom_ string $h$ that has a succinct representation, i.e.,
$h=(\mathsf{PRF}_{s}(1),\ldots,\mathsf{PRF}_{s}(N))$ for some (post-quantum)
pseudorandom function $\mathsf{PRF}$.

Thus, we focus for the moment on constructing a succinct measurement protocol
for $h$ with succinct representation, and return to the full delegation
problem later.

###  2.3 Constructing a Verifier-Succinct Measurement Protocol

Inspecting the description of the [Mah18] protocol, there are three distinct
reasons that the protocol is not succinct:

  1. 1.

The verifier’s first message, which consists of $N$ TCF public keys, is non-
succinct.

  2. 2.

The prover’s two messages, consisting of the commitments $y_{i}$ and openings
$z_{i}$ respectively, are non-succinct.

  3. 3.

The verifier’s decision predicate, as it is a function of these commitments
and openings, requires $\mathsf{poly}(N)$ time to evaluate.

The latter two issues turn out to be not too difficult to resolve (although
there is an important subtlety that we discuss later); for now, we focus on
resolving (1), which is our main technical contribution. Concretely, we want
to construct a measurement protocol for succinct bases $h$ where the
verifier’s first message is succinct.

##### Idea: Compress the Verifier’s message with iO.

Given the problem formulation, a natural idea presents itself: instead of
having $V$ send over $N$ i.i.d. public keys $\mathsf{pk}_{i}$, perhaps $V$ can
send a succinct program $\mathsf{PK}$ that contains the description of $N$
public keys $\mathsf{pk}_{i}$ that are in some sense “pseudoindependent!”
Using the machinery of obfuscation and the “punctured programs” technique
[SW14], it is straightforward to write down a candidate program for this task:
simply obfuscate the following code.

Input: index $i\leq N$
---
Hardwired Values: Puncturable PRF seed $s$. Circuit $C$.
• Compute $\mathsf{mode}=C(i)$ and $r=\mathsf{PRF}_{s}(i)$. • Compute
$(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Gen}(1^{\lambda},\mathsf{mode};r)$.
• Output $\mathsf{pk}_{i}$.

Here, $C$ is an efficient circuit with truth table $h$, and
$\mathsf{Gen}(1^{\lambda},\mathsf{mode})$ indicates sampling either from
$\mathsf{Inj}$ or $\mathsf{Cf}$ depending on whether $h_{i}=C(i)=0$ or
$h_{i}=C(i)=1$.

Letting $\mathsf{PK}$ denote an obfuscation of the above program, $V$ could
send $\mathsf{PK}$ to $P$ and allow the prover to compute each
$\mathsf{pk}_{i}=\mathsf{PK}(i)$ on its own, and the protocol could
essentially proceed as before, except that the verifier will have to expand
its PRF seed $s$ into $(\mathsf{sk}_{1},\ldots,\mathsf{sk}_{N})$ in order to
compute its final output.

##### Problem: Proving Soundness.

While it is not hard to describe this plausible modification to the [Mah18]
protocol that compresses the verifier’s message, it is very unclear how to
argue that the modified protocol is sound. The obfuscation literature has no
shortage of proof techniques developed over the last 10 years, but since we
have made a “non-black-box” modification of the [Mah18] protocol, a deep
understanding of the [Mah18] proof of soundness is required in order to
understand to what extent these techniques are compatible with the application
at hand.

We believe it _should_ be possible to incorporate punctured programming
techniques into Mahadev’s proof of soundness in [Mah18] and conclude the
desired soundness property of the new protocol. However, doing so would result
in an extremely complex proof that would require the reader to verify the
entirety of the [Mah18] (already very complicated) original security proof
with our modifications in mind.

###  2.4 Proof of Soundness

Given the complicated nature of the [Mah18] proof of soundness, we instead
give a _simpler_ and _more modular_ proof of soundness for the [Mah18]
measurement protocol. Moreover, we give this proof for a generic variant of
the [Mah18] protocol where the prover is given an arbitrary representation
$\mathsf{PK}$ of $N$ TCF public keys and show that precisely two properties of
this representation $\mathsf{PK}$ are required in order for the proof to go
through:

  * •

An appropriate generalization of the “dual-mode” property of individual TCFs
must hold for $\mathsf{PK}$: for any two circuits $C_{1},C_{2}$, it should be
that $\mathsf{PK}_{1}$ generated from basis $C_{1}$ is computationally
indistinguishable from $\mathsf{PK}_{2}$ generated from basis $C_{2}$. In
fact, a stronger variant of this indistinguishability must hold: it should be
the case that $\mathsf{PK}_{1}\approx_{c}\mathsf{PK}_{2}$ even if the
distinguisher is given all secret keys $\mathsf{sk}_{j}$ such that
$C_{1}(j)=C_{2}(j)$.

  * •

For every $i$, the adaptive hardcore bit property of $f_{\mathsf{pk}_{i}}$
should hold _even given_ $\mathsf{sk}_{j}$ for all $j\neq i$.

Since these two properties are (essentially) all that is required for our
proof to go through, in order to obtain a verifier-succinct protocol, it
suffices to show that the obfuscated program $\mathsf{PK}$ above satisfies
these two properties, which follows from standard techniques.

Thus, we proceed by describing our new soundness proof for the [Mah18]
measurement protocol, which transparently generalizes to the verifier-succinct
setting.

##### The “Operational Qubits” Approach.

Let $P^{*}$ denote a prover that passes the test round (i.e., makes the
verifier accept on the $0$ challenge) with probability $1$. Our goal is to
show that the prover in some sense “has an $N$-qubit state” such that
measuring this state in the $h$-bases produces the same (or an
indistinguishable) distribution as the verifier’s protocol output, which we
will denote $D_{P^{*},\mathrm{Out}}$. This $N$-qubit state should be
efficiently computable from the prover’s internal state $\ket{\psi}$;
specifically, we use $\ket{\psi}$ to denote the prover’s state after its first
message $y$ has been sent.

In order to show this, taking inspiration from [Vid20],999[Vid20] gives a
soundness proof for a variant of the [Mah18] protocol, but in a qualitatively
weaker setting. [Vid20] only proves indistinguishability of $N$-qubit
measurements that are either _all_ in the standard basis or _all_ in the
Hadamard basis, and only proves indistinguishability with respect to _linear_
tests of the distribution (that is, [Vid20] proves small-bias rather than full
indistinguishability). Both of these relaxations are unacceptable in our
setting, and achieving the latter specifically requires a different proof
strategy. we will proceed in two steps:

  1. 1.

Identify $N$ “operational qubits” within $\ket{\psi}$. That is, we will
identify a set of $2N$ observables
$Z_{1},\ldots,Z_{N},X_{1},\ldots,\allowbreak X_{N}$ (analogous to the “Pauli
observables”
$\sigma_{z,1},\ldots,\sigma_{z,N},\sigma_{x,1},\ldots\sigma_{x,N}$) such that
measuring $\ket{\psi}$ with these observables gives the outcome distribution
$D_{P^{*},\mathrm{Out}}$.

Provided that these $2N$ observables roughly “behave like” Pauli observables
with respect to $\ket{\psi}$ (e.g. satisfy the X/Z uncertainty principle), one
could then hope to:

  2. 2.

Extract a related state $\ket{\psi^{\prime}}$ such that measuring
$\ket{\psi^{\prime}}$ in the _actual_ standard/Hadamard bases matches the
“pseudo-Pauli” $\\{Z_{j}\\}$, $\\{X_{i}\\}$, measurements of $\ket{\psi}$ (and
therefore $D_{P^{*},\mathrm{Out}}$).

##### Relating the Verifier’s Output to Measuring $\ket{\psi}$.

Our current goal is to achieve Step (1) above. Let $\ket{\psi}$ denote
$P^{*}$’s post-commitment state and let $U$ denote the unitary such that
$P^{*}$’s opening is a measurement of $U\ket{\psi}$ in the Hadamard basis.

Now, let us consider the verifier’s output distribution. The $i$th bit of the
verifier’s output when $h_{i}=1$ is defined to be $d\cdot(x_{0,i}\oplus
x_{1,i})$ (where $d$ is the opening sent by the prover) of $U\ket{\psi}$ in
the Hadamard basis. For each such $i$, we can define an observable $X_{i}$
characterizing this measurement, that _roughly_ takes the form

$X_{i}\approx
U^{\dagger}(H_{\mathcal{Z}_{i}}\otimes\mathsf{Id})\left(\sum_{d}(-1)^{d\cdot(1,x_{0,i}\oplus
x_{1,i})}\outerproduct{d}{d}_{\mathcal{Z}_{i}}\otimes\mathsf{Id}_{\mathcal{I},\\{\mathcal{Z}_{j}\\}_{j\neq
i}}\right)(H_{\mathcal{Z}_{i}}\otimes\mathsf{Id})U.$

Here we have slightly simplified the expression for $X_{i}$ for the sake of
presentation; the correct definition of $X_{i}$ (see Section 6.2) must account
for the case where $d$ is rejected by the verifier. To reiterate, the
observable $X_{i}$ is a syntactic interpretation of the verifier’s output
$m_{i}$ as a function of $\ket{\psi}$.

On the other hand, when $h_{i}=0$, the verifier’s output $m_{i}$ is not _a
priori_ a measurement of $\ket{\psi}$; indeed, the verifier ignores the
prover’s second message and just inverts $y_{i}$. However, under the
assumption that the prover $P^{*}$ passes the test round with probability
$1-\mathsf{negl}(\lambda)$, making use of the fact that $f_{\mathsf{pk}_{i}}$
is injective, this $y_{i}$-inverse must be equal to what the prover _would_
have sent in the test round. This defines another observable on $\ket{\psi}$
that we call $Z_{i}$:

$Z_{i}=\sum_{b,x}(-1)^{b}\outerproduct{b,x}{b,x}_{\mathcal{Z}_{i}}\otimes\mathsf{Id}_{\mathcal{I},\\{\mathcal{Z}_{j}\\}_{j\neq
i}}.$

Finally, note that the operator $Z_{i}$ syntactically makes sense even when
$h_{i}=1$. However, $X_{i}$ cannot even be _defined_ when
$f_{\mathsf{pk}_{i}}$ is injective, corresponding to $h_{i}=0$, since $X_{i}$
explicitly requires _two_ inverses of $y_{i}$. Therefore, from now on, we
sample all $(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Cf}$ (forcing
all TCFs to be 2-to-1).

This brings us to the punchline of this step: by invoking a computational
assumption (the indistinguishability of $\mathsf{Cf}$ and $\mathsf{Inj}$), we
can define observables $(X_{i},Z_{i})$ for all $i\in[N]$ such that for _every_
$i$ and _every_ basis choice $h$, the distribution resulting from measuring
$\ket{\psi}$ with $X_{i}$ (resp. $Z_{i}$) matches the $i$th bit of the
verifier’s output distribution.

With a little more work, one can actually show that the verifier’s _entire_
output distribution in the $h$-basis is computationally indistinguishable from
the following distribution
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$:

  * •

Sample keys $(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Cf}$. Run
$P^{*}$ to obtain $y,\ket{\psi}$.

  * •

For each $i$ such that $h_{i}=0$, measure the first bit of the prover’s $i$th
response register in the standard basis to obtain (and output) a bit $b_{i}$.

  * •

Measure $U\ket{\psi}$ in the Hadamard basis, obtaining strings
$(d_{1},\ldots,d_{N})$.

  * •

For each $i$ such that $h_{i}=1$, compute (and output)
$d_{i}\cdot(1,x_{0,i}\oplus x_{1,i})$.

##### Aside: Why are these $Z_{j}$ and $X_{i}$ helpful?

As alluded to earlier, this approach is inspired by _operational_ definitions
of “having an $N$-qubit state,” which consists of a state $\ket{\psi}$ and
$2N$ “pseudo-Pauli” observables $Z_{1},\ldots,Z_{N},X_{1},\ldots X_{N}$ that
behave “like Pauli observables” on $\ket{\psi}$. For example, it is possible
to prove that many of the “Pauli group relations” hold _approximately_ on
these $X_{i},Z_{j}$ with respect to $\ket{\psi}$, meaning that (for example)

$\bra{\psi}Z_{i}X_{i}Z_{i}+X_{i}\ket{\psi}=\mathsf{negl}(\lambda)$

and

$\bra{\psi}Z_{j}X_{i}Z_{j}-X_{i}\ket{\psi}=\mathsf{negl}(\lambda)$

for $i\neq j$. In fact, these relations turn out to _encode_ the two basic
properties of the TCF $f_{\mathsf{pk}_{i}}$: the adaptive hardcore bit
property (encoded in the first relation) and that $f_{\mathsf{pk}_{i}}$ is
indistinguishable from injective101010Technically, the property encoded is the
_collapsing_ of $f_{\mathsf{pk}_{i}}$, which is implied by (but not equivalent
to) being indistinguishable from injective. (encoded in the second relation)!
We will not directly prove the relations here, but they are implicit in our
full security proof and are the motivation for this proof strategy.

##### The Extracted State.

Given these protocol observables $Z_{1},\ldots,Z_{N},X_{1},\ldots,X_{N}$, it
remains to implement Step (2) of our overall proof strategy: extracting a
state $\ket{\psi^{\prime}}$ whose standard/Hadamard measurement outcomes match
$D_{P^{*},\mathrm{Out}}$. At a high level, this is achieved by “teleporting”
the state $\ket{\psi}$ onto a fresh $N$-qubit register in a way that
_transforms_ the “pseudo-Paulis" $\\{X_{i}\\},\\{Z_{j}\\}$ into _real_ Pauli
observables $\\{\sigma_{x,i}\\},\\{\sigma_{z,j}\\}$.

Fix a choice of $\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}$. For
ease of notation, write
$\mathcal{H}=\mathcal{Z}\otimes\mathcal{I}\otimes\mathcal{U}$ so that
$\ket{\psi}\in\mathcal{H}$. We would like an efficient extraction procedure
that takes as input $\ket{\psi}\in\mathcal{H}$ and generates an $N$-qubit
state $\bm{\tau}$ such that, roughly speaking, measuring $\ket{\psi}$ with
$X/Z$ and measuring $\bm{\tau}$ with $\sigma_{X}/\sigma_{Z}$ produce
indistinguishable outcomes.

##### Intuition for the Extractor.

Before we describe our extractor, we first provide some underlying intuition.
For an arbitrary $N$-qubit Hilbert space, let $\sigma_{x,i}$/$\sigma_{z,i}$
denote the Pauli $\sigma_{x}$/$\sigma_{z}$ observable acting on the $i$th
qubit. For each $r,s\in\\{0,1\\}^{N}$, define the $N$-qubit Pauli “parity”
observables

$\sigma_{x}(r)\coloneqq\prod_{i:r_{i}=1}\sigma_{x,i}\;,\;\sigma_{z}(s)\coloneqq\prod_{i:r_{i}=1}\sigma_{z,i}.$

Suppose for a moment that $\ket{\psi}\in\mathcal{H}$ is _already_ an $N$-qubit
state (i.e., $\mathcal{H}$ is an $N$-qubit Hilbert space) and moreover, that
each $X_{i}$/$Z_{i}$ observable is simply the corresponding Pauli observable
$\sigma_{x,i}$/$\sigma_{z,i}$. While these assumptions technically trivialize
the task (the state already has the form we want from the extracted state), it
will be instructive to write down an extractor that “teleports” this state
into another $N$-qubit external register.

We can do this by initializing two $N$-qubit registers
$\mathcal{A}_{1}\otimes\mathcal{A}_{2}$ to $\ket{\phi^{+}}^{\otimes N}$ where
$\ket{\phi^{+}}$ is the EPR state $(\ket{00}+\ket{11})/\sqrt{2}$ (the $i$th
EPR pair lives on the $i$th qubit of $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$).
Now consider the following steps, which are inspired by the ($N$-qubit)
quantum teleportation protocol

  1. 1.

Initialize a $2N$-qubit ancilla $\mathcal{W}$ to $\ket{0^{2N}}$, and apply
$H^{\otimes 2N}$ to obtain the uniform superposition.

  2. 2.

Apply a “controlled-Pauli” unitary, which does the following for all
$r,s\in\\{0,1\\}^{N}$ and all
$\ket{\phi}\in\mathcal{H}\otimes\mathcal{A}_{1}$:

$\ket{r,s}_{\mathcal{W}}\ket{\phi}_{\mathcal{H},\mathcal{A}_{1}}\rightarrow\ket{r,s}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)_{\mathcal{H}}\otimes\sigma_{x}(r)\sigma_{z}(s)_{\mathcal{A}_{1}})\ket{\phi}_{\mathcal{H},\mathcal{A}_{1}}$

  3. 3.

Apply the unitary that XORs onto $\mathcal{W}$ the outcome of performing $N$
Bell-basis measurements111111The Bell basis consists of the $4$ states
$(\sigma_{x}^{a}\sigma_{z}^{b}\otimes\mathsf{Id})\ket{\phi^{+}}$ for
$a,b\in\\{0,1\\}$ on $2$ qubits. on $\mathcal{A}_{1}\otimes\mathcal{A}_{2}$
onto $\mathcal{W}$, i.e., for all $u,v,r,s\in\\{0,1\\}^{N}$:

$\ket{u,v}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})_{\mathcal{A}_{1},\mathcal{A}_{2}}\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}}\rightarrow\ket{u\oplus r,v\oplus
s}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})_{\mathcal{A}_{1},\mathcal{A}_{2}}\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}}.$

Finally, discard $\mathcal{W}$.

One can show that the resulting state is

$\frac{1}{2^{N}}\sum_{r,s\in\\{0,1\\}^{N}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})\ket{\psi}_{\mathcal{H}}\ket{\phi^{+}}_{\mathcal{A}_{1},\mathcal{A}_{2}}=\ket{\phi^{+}}_{\mathcal{H},\mathcal{A}_{1}}\ket{\psi}_{\mathcal{A}_{2}},$
(1)

where $\ket{\psi}$ is now “teleported” into the $\mathcal{A}_{2}$ register.

##### The Full Extractor.

To generalize this idea to the setting where $\ket{\psi}\in\mathcal{H}$ is an
arbitrary quantum state and $\\{X_{i},Z_{i}\\}_{i}$ are an arbitrary
collection of $2N$ observables, _we simply replace each $\sigma_{x}(r)$ and
$\sigma_{z}(s)$ acting on $\mathcal{H}$ above with the corresponding parity
observables $X(r)$, $Z(s)$_, defined analogously (for $r,s\in\\{0,1\\}^{N}$ as

$Z(s)=\prod_{i=1}^{N}Z_{i}^{s_{i}}\hskip 7.22743pt\mbox{and}\hskip
7.22743ptX(r)=\prod_{i=1}^{N}X_{i}^{r_{i}}.$

The rough intuition is that as long as the $\\{X_{i}\\}$ and $\\{Z_{i}\\}$
observables “behave like” Pauli observables with respect to $\ket{\psi}$, the
resulting procedure will “teleport” $\ket{\psi}$ into the $N$-qubit register
$\mathcal{A}_{2}$.

##### Relating Extracted State Measurements to Verifier Outputs.

With the extracted state defined to be the state on $\mathcal{A}_{2}$ after
performing the “generalized teleportation” described above, it remains to
prove that the distribution $D_{P^{*},\mathrm{Ext}}$ resulting from measuring
the extracted state on $\mathcal{A}_{2}$ in the $h$-bases is indistinguishable
from $D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$.

One can show (by a calculation) that $D_{P^{*},\mathrm{Ext}}$ is the following
distribution (differences from
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ in red)

  1. 1.

Sample keys $(\mathsf{pk}_{i},\mathsf{sk}_{i})\leftarrow\mathsf{Cf}$. Run
$P^{*}$ to obtain $y,\ket{\psi}$.

  2. 2.

For each $i$ such that $h_{i}=0$, measure the first bit of the prover’s $i$th
response register in the standard basis to obtain (and output) a bit $b_{i}$.

  3. 3.

For each $i$ such that $h_{i}=1$, flip a random bit $w_{i}$ and apply the
unitary $Z_{i}^{w_{i}}$.

  4. 4.

Measure $U\ket{\psi}$ in the Hadamard basis, obtaining strings
$(d_{1},\ldots,d_{N})$.

  5. 5.

For each $i$ such that $h_{i}=1$, compute (and output)
$d_{i}\cdot(1,x_{0,i}\oplus
x_{1,i})\;{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\oplus\;w_{i}}$.

We prove indistinguishability between the $N$-bit distributions
$D_{P^{*},\mathrm{Ext}}$ and
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ by considering $N$
hybrid distributions, where the difference between Hybrid $j-1$ and Hybrid $j$
is:

  * •

an additional application of the unitary $Z_{j}$ in Item 3, and

  * •

an additional XOR of $e_{j}$ (the $j$th standard basis vector) in Item 5.

To conclude the soundness proof, we show that Hybrid $j-1$ and Hybrid $j$ in
the following three steps.

  * •

First, we prove that the marginal distributions of Hybrid $(j-1)$ and Hybrid
$j$ on $N\setminus\\{j\\}$ are indistinguishable due to the collapsing
property of $f_{\mathsf{pk}_{j}}$. Intuitively this holds because the marginal
distributions on $N\setminus\\{j\\}$ only differ by the application of
$Z_{j}$, which is undetectable by collapsing.

  * •

By invoking an elementary lemma about $N$-bit indistinguishability, the task
reduces to proving a $1$-bit indistinguishability of the $j$th bit of Hybrid
$(j-1)$ and Hybrid $j$, conditioned on an efficiently computable property of
the marginal distributions on $N\setminus\\{j\\}$.

  * •

Finally, we show that the indistinguishability of the $j$th bit holds due to
the adaptive hardcore bit property of $f_{\mathsf{pk}_{j}}$. At a very high
level, the above $j$th bit property involves a measurement of $X_{j}$, and the
two hybrids differ in whether a random $Z_{j}^{b}$ is applied before $X_{j}$
is measured; in words, this exactly captures the adaptive hardcore bit
security game.

We refer the reader to Section 6.4 for a full proof of indistinguishability.

###  2.5 From a Verifier-Succinct Measurement Protocol to Succinct Arguments
for BQP

Using Sections 2.3 and 2.4, we have constructed a _verifier-succinct_
measurement protocol, for succinctly represented basis strings, with a single
bit verifier challenge. What remains is to convert this into a (fully)
succinct argument system for BQP (or QMA). This is accomplished via the
following transformations:

  * •

Converting a measurement protocol into a quantum verification protocol. As
described earlier, this is achieved by combining the [FHM18] protocol for BQP
verification with a limited quantum verifier (as modified by [ACGH20]) with
our measurement protocol, using a PRF to generate a pseudorandom basis choice
instead of a uniformly random basis choice for the [FHM18, ACGH20] verifier.
This results in a verifier-succinct argument system for BQP/QMA with constant
soundness error.

  * •

Parallel repetition to reduce the soundness error. This follows from the
“computational orthogonal projectors” property of the 1-bit challenge protocol
and follows from [ACGH20] (we give a somewhat more abstract formulation of
their idea in Appendix A). This results in a verifier-succinct argument system
for BQP/QMA with negligible soundness error.

  * •

Converting a verifier-succinct argument system into a fully succinct argument
system. We elaborate on this last transformation below, as a few difficulties
come up in this step.

Assume that we are given a (for simplicity, 4-message) verifier-succinct
argument system for BQP/QMA. Let $m_{1},m_{2},m_{3},m_{4}$ denote the four
messages in such an argument system. In order to obtain a fully succinct
argument system, we must reduce (1) the prover communication complexity
$|m_{2}|+|m_{4}|$, and (2) the runtime of the verifier’s decision predicate.

The first idea that comes to mind is to ask the prover to send short (e.g.
Merkle tree) commitments $\sigma_{2}$ and $\sigma_{4}$ of $m_{2}$ and $m_{4}$,
respectively, instead of sending $m_{2}$ and $m_{4}$ directly. At the end of
the interaction, the prover and verifier could then engage in a succinct
interactive argument (of knowledge) for a (classical) NP statement that “the
verifier would have accepted the committed messages underlying $\sigma_{2}$
and $\sigma_{4}$”. One could potentially employ Kilian’s succinct interactive
argument of knowledge for NP which was recently shown to be post-quantum
secure under the post-quantum LWE assumption [CMSZ21].

There are a few issues with this naive idea. First of all, the verifier’s
decision predicate is _private_ (it depends on the secret key $\mathsf{SK}$ in
the measurement protocol and the PRF seed for its basis), so the NP statement
above is not well-formed. One reasonable solution to this issue is to simply
have the verifier send this secret information $\mathsf{st}$ after the
verifier-succinct protocol emulation has occurred and before the NP-succinct
argument has started. For certain applications (e.g. obtaining a non-
interactive protocol in the QROM) we would like to have a _public-coin_
protocol; this can be achieved by using fully homomorphic encryption to
encrypt this secret information in the _first_ round rather than sending it in
the clear in a later round. For this overview, we focus on the private-coin
variant of the protocol.

Now, we can indeed write down the appropriate NP relation121212Note that the
verifier also takes as input the QMA instance, but we suppress it here for
clarity.

$\displaystyle\mathcal{R}_{V}=$
$\displaystyle\\{((h,m_{1},\sigma_{2},m_{3},\sigma_{4},\mathsf{st}),(m_{2},m_{4})):\sigma_{2}=h(m_{2})\mbox{
and }$ $\displaystyle\sigma_{4}=h(m_{4})\mbox{ and
}V(\mathsf{st},m_{1},m_{2},c,m_{4})=\mathsf{accept}\\}$

and execute the aforementioned strategy. However, this construction turns out
not to work. Specifically, it does not seem possible to _convert_ a cheating
prover $P^{*}$ in the above fully succinct protocol into a cheating prover
$P^{**}$ for the verifier-succinct protocol; for example, $P^{**}$ needs to be
able to produce a message $m_{2}$ given only $m_{1}$ from the verifier;
meanwhile, the message $m_{1}$ can only be extracted from $P^{*}$ by
repeatedly rewinding $P^{*}$’s _last_ message algorithm, which requires the
verifier’s secret information $\mathsf{st}$ as input! This does not correspond
to a valid $P^{**}$, who does not have access to $\mathsf{st}$ when computing
$m_{2}$.

Our refined compiler is to execute several arguments of knowledge: one right
after the prover sends $\sigma_{2}$, proving knowledge of $m_{2}$; another one
right after she sends $\sigma_{4}$, proving knowledge of $m_{4}$ (both before
receiving the secret state $\mathsf{st}$ from the verifier); and a third one
for the relation $\mathcal{R}_{V}$ described above. The first two arguments of
knowledge are for the relation

$\mathcal{R}_{H}=\\{(h,\sigma),m):h(m)=\sigma\\}$

This allows for immediate extraction of $m_{2}$ and $m_{3}$ and appears to
clear the way for a reduction between the verifier-succinct and fully succinct
protocol soundness properties.

However, there is one remaining problem: the argument-of-knowledge property of
Kilian’s protocol proved by [CMSZ21] is _insufficiently composable_ to be used
in our compiler. They demonstrate an extractor for Kilian’s protocol that
takes any quantum cheating prover that convinces the verifier and extracts a
witness from them. However, their post-quantum extractor might significantly
disturb the prover’s state, meaning that once we extract $m_{2}$ above, we may
not be able to continue the prover execution in our reduction.

Fortunately, a recent work [LMS21] shows that a slight variant of Kilian’s
protocol is a succinct argument of knowledge for NP satisfying a composable
extraction property called “state-preservation.” This security property is
exactly what is required for our compiler to extract a valid cheating prover
strategy $P^{**}$ for the verifier-succinct argument given a cheating prover
$P^{*}$ for the compiled protocol. A full discussion of this is given in
Section 9.

This completes our construction of a succinct argument system for BQP (and
QMA). We discuss additional results (2-message protocols, zero knowledge,
batch arguments) in Section 10.

##  3 Preliminaries

###  3.1 Quantum Information

Let $\mathcal{H}$ be a finite-dimensional Hilbert space. A pure state is a
unit vector $\ket{\psi}\in\mathcal{H}$. Let $\mathrm{D}(\mathcal{H})$ denote
the set of all positive semidefinite operators on $\mathcal{H}$ with trace
$1$. A mixed state is an operator $\bm{\rho}\in\mathrm{D}(\mathcal{H})$, and
is often called a _density matrix_. We sometimes divide $\mathcal{H}$ into
named _registers_ written in uppercase calligraphic font, e.g.,
$\mathcal{H}=\mathcal{A}\otimes\mathcal{B}\otimes\mathcal{C}$.

For a density matrix $\bm{\rho}\in\mathrm{D}(\mathcal{H})$, where
$\mathcal{H}\simeq(\mathbb{C}^{2})^{\otimes\ell}$, we sometimes use the
shortcut $M(h,\bm{\rho})$ to denote the distribution resulting from measuring
each qubit of $\bm{\rho}$ (where the qubits are specified by the isomorphism
$\mathcal{H}\simeq(\mathbb{C}^{2})^{\otimes\ell}$) in the basis determined by
$h\in\\{0,1\\}^{\ell}$. By convention, $h_{i}=0$ corresponds to measuring the
$i$-th register in the standard basis $\\{\ket{0},\ket{1}\\}$ and $h_{i}=1$
corresponds to measuring the $i$-th register in the Hadamard basis
$\\{\ket{+},\ket{-}\\}$.

An _observable_ is represented by a Hermitian operator $O$ on $\mathcal{H}$.
In particular, any observable $O$ can be written in the form
$\sum_{i}\lambda_{i}\Pi_{i}$ where $\\{\lambda_{i}\\}$ are real numbers and
$\sum_{i}\Pi_{i}=\mathsf{Id}$. The measurement corresponding to an observable
$O$ is the projective measurement $\\{\Pi_{i}\\}$ with corresponding outcomes
$\\{\lambda_{i}\\}$. A _binary observable_ satisfies the additional
requirement that $O^{2}=\mathsf{Id}$. Notice that for any binary observable,
$O$ is a unitary matrix with eigenvalues in $\\{1,-1\\}$. In this case we
sometimes treat the outcomes as bits through the usual correspondence $1\to
0$, $-1\to 1$.

Given a binary observable $O$, we define its corresponding _projection
operators_ $O^{+}=\frac{1}{2}(\mathsf{Id}+O)$ and
$O^{-}=\frac{1}{2}(\mathsf{Id}-O)$. $O^{+}$ and $O^{-}$ correspond to
projecting onto the $+1$ and $-1$ eigenspaces of $O$, respectively, and thus
form a binary projective measurement.

##### The Class QMA.

A language ${\cal L}=({\cal L}_{\text{yes}},{\cal L}_{\text{no}})$ is in QMA
if and only if there is a uniformly generated family of polynomial-size
quantum circuits $\mathcal{V}=\\{V_{\lambda}\\}_{\lambda\in\mathbb{N}}$ such
that for every $\lambda$, $V_{\lambda}$ takes as input a string
$x\in\\{0,1\\}^{\lambda}$ and a quantum state $\ket{\phi}$ on $p(\lambda)$
qubits and returns a single bit and moreover the following conditions hold.

  * •

For all $x\in{\cal L}_{\text{yes}}$ of length $\lambda$, there exists a
quantum state $\ket{\psi}$ on at most $p(\lambda)$ qubits such that the
probability that $V_{\lambda}$ accepts $(x,\ket{\phi})$ is at least $2/3$. We
denote the (possibly infinite) set of quantum states (which we will also refer
to as quantum witnesses) that make $V_{\lambda}$ accept $x$ by ${\cal R}(x)$.

  * •

For all $x\in{\cal L}_{\text{no}}$ of length $\lambda$, and all quantum states
$\ket{\psi}$ on at most $p(\lambda)$ qubits, it holds that $V_{\lambda}$
accepts on input $(x,\ket{\psi})$ with probability at most $1/3$.

###  3.2 Black-Box Access to Quantum Algorithms

Let $A$ be a polynomial-time quantum algorithm with internal state
$\bm{\rho}\in\mathrm{D}(\mathcal{I})$ that takes a classical input $r$ and
produces a classical output $z$. Without loss of generality, the behavior of
$A$ can be described as follows:

  1. 1.

Apply an efficient _classical_ algorithm to $r$ to generate the description of
a unitary $U(r)$.

  2. 2.

Initialize registers $\mathcal{Z}\otimes\mathcal{I}$ to
$\outerproduct{0}{0}_{\mathcal{Z}}\otimes\bm{\rho}_{\mathcal{I}}$.

  3. 3.

Apply $U(r)$ to $\mathcal{Z}\otimes\mathcal{I}$, measure $\mathcal{Z}$ in the
computational basis, and return the outcome $z$.

A quantum oracle algorithm $S^{A}$ with _black-box access_ to $(A,\bm{\rho})$
does not have direct access to the adversary’s _internal registers_
$\mathcal{I}$, and can only operate on the state
$\bm{\rho}\in\mathrm{D}(\mathcal{I})$ by applying $U(r)$ or $U(r)^{\dagger}$
for any $r$. In more detail, black-box access to $(A,\bm{\rho})$ means the
following:

  * •

The registers $\mathcal{Z}\otimes\mathcal{I}$ are initialized to
$\outerproduct{0}{0}_{\mathcal{Z}}\otimes\bm{\rho}_{\mathcal{I}}$.

  * •

Once the $\mathcal{Z}\otimes\mathcal{I}$ registers are initialized, the
algorithm is permitted to perform arbitrary operations on the $\mathcal{Z}$
register, but can only act on the $\mathcal{I}$ registers by applying $U(r)$
or $U(r)^{\dagger}$ for any $r$. We explicitly permit the $U(r)$ and
$U(r)^{\dagger}$ gates to be controlled on any external registers (i.e., any
registers other than the registers $\mathcal{Z}\otimes\mathcal{I}$ to which
$U(r)$ is applied).

We note that this definition is consistent with the notions of interactive
quantum machines and oracle access to an interactive quantum machine used in
e.g. [Unr12] and other works on post-quantum zero-knowledge.

##### The Binary Input Case.

Following [Mah18], in the special case where $r\in\\{0,1\\}$, it will be
convenient to re-define the internal state to be $\bm{\rho}\coloneqq
U(0)(\outerproduct{0}{0}_{\mathcal{Z}}\otimes\bm{\rho}^{\prime}_{\mathcal{I}})U(0)^{\dagger}$
(where $\bm{\rho}^{\prime}_{\mathcal{I}}\in\mathrm{D}(\mathcal{I})$ denotes
the “original” internal state), so that the behavior of $A$ on $r=0$ is to
simply measure $\mathcal{Z}$ in the computational basis, and on $r=1$ it
applies the unitary $U\coloneqq U(1)U(0)^{\dagger}$ to its state and then
measures the $\mathcal{Z}$ register. Notice that in this case, the internal
state is technically on $\mathcal{Z}\otimes\mathcal{I}$ instead of just
$\mathcal{I}$. Thus, black-box access to a quantum algorithm with binary input
is formalized as follows:

  * •

The registers $\mathcal{Z}\otimes\mathcal{I}$ are initialized to
$\bm{\rho}\coloneqq
U(0)(\outerproduct{0}{0}_{\mathcal{Z}}\otimes\bm{\rho}^{\prime}_{\mathcal{I}})U(0)^{\dagger}$.

  * •

Once the $\mathcal{Z}\otimes\mathcal{I}$ registers are initialized, the
algorithm is permitted to perform arbitrary operations on the $\mathcal{Z}$
register, but can only act on the $\mathcal{I}$ registers by applying
(possibly controlled) $U$ or $U^{\dagger}$ gates.

In this special case, an algorithm with black-box access to $A$ is denoted
$S^{U,\bm{\rho}}$.

We remark that these definitions are tailored to the two-message challenge-
response setting, whereas the protocols we consider in this paper have more
rounds of interaction. However, our analysis will typically focus on a single
back-and-forth round of interaction (e.g., the last two messages of the
[Mah18] protocol), so $\bm{\rho}$ will be the intermediate state of the
interactive algorithm right before the next challenge is sent.131313In the
multi-round setting, “re-defining” the intermediate state to be
$\bm{\rho}=U(0)(\outerproduct{0}{0}_{\mathcal{Z}}\otimes\bm{\rho}^{\prime}_{\mathcal{I}})U(0)^{\dagger}$
can be implemented by replacing any unitary $W$ applied in the previous round
with $U(0)W$; this follows the conventions used in [Mah18]. Moreover, the
unitaries $\\{U(r)\\}_{r}$ can be treated as independent of the (classical)
protocol transcript before challenge $r$ is sent, since we can assume this
transcript is saved in $\bm{\rho}$.

###  3.3 Interactive Arguments

In what follows we define the notion of an interactive argument for QMA
languages. We denote such arguments by $(P,V)$, and denote the output bit of
the verifier by $\mathsf{Out}(P,V)$.

######  Definition 3.1.

An interactive argument $(P,V)$ for a language ${\cal L}=({\cal
L}_{\mathsf{yes}},{\cal L}_{\mathsf{no}})\in\textbf{QMA}$ with relation ${\cal
R}(x)$ is a (classical) 2-party interactive protocol between a QPT prover $P$
and a p.p.t. verifier $V$, with the following completeness and soundness
guarantees:

##### Completeness.

For all $\lambda\in\mathbb{N}$, there exists a polynomial $k=k(\lambda)$ such
that for all $x\in{\cal L}_{\text{yes}}$, and all $\ket{\phi}\in{\cal R}(x)$,
it holds that

$\Pr\left[\mathsf{Out}\left(P(\ket{\phi}^{\otimes
k(\lambda)},x),V(x)\right)=1\right]\geq 1-\mathsf{negl}(\lambda).$

##### Computational Soundness.

For all $\lambda\in\mathbb{N}$, all $x\in{\cal L}_{\mathsf{no}}$, and all non-
uniform QPT provers $P^{*}$, it holds that

$\Pr\left[\mathsf{Out}(P^{*}(x),V(x))=1\right]\leq\mathsf{negl}(\lambda).$

##### Batch Arguments.

We also consider a sub-class of interactive arguments where the prover
simultaneously engages the verifier on $n$ sub-instances
$(x_{1},\dots,x_{n})$, where each $x_{i}$ is supposed to be a Yes-instance of
a fixed language $\mathcal{L}_{i}$. We require the following notion of
(computational) soundness.

######  Definition 3.2 (Soundness).

An interactive argument $(P,V)$ for a batch language ${\cal L}={\cal
L}_{1}\times\ldots\times{\cal L}_{n}\in\textbf{QMA}$ with relation ${\cal
R}(x)$ is sound if for all $\lambda\in\mathbb{N}$, all polynomials
$n=n(\lambda)$, all indices $i\in[n]$, all statements $(x_{1},\dots,x_{n})$,
where $x_{i}\in{\cal L}_{\mathsf{no}}$, and all non-uniform QPT provers
$P^{*}$, it holds that

$\Pr\left[\mathsf{Out}(P^{*}(x_{1},\dots,x_{n}),V((x_{1},\dots,x_{n})))=1\right]\leq\mathsf{negl}(\lambda).$

###  3.4 Computational Indistinguishability

Two classical distribution ensembles
$\\{(X^{(\lambda)},Y^{(\lambda)})\\}_{\lambda}$ are said to be post-quantum
computationally indistinguishable if for every non-uniform QPT algorithm
$A=\\{(A^{(\lambda)},\bm{\rho}^{(\lambda)})\\}_{\lambda}$ (that outputs a bit
$b$), we have that

$\left|\mathbf{\operatorname*{\mathbb{E}}}\left[A^{(\lambda)}(X^{(\lambda)},\bm{\rho}^{(\lambda)})\right]-\mathbf{\operatorname*{\mathbb{E}}}\left[A^{(\lambda)}(Y^{(\lambda)},\bm{\rho}^{(\lambda)})\right]\right|=\mathsf{negl}(\lambda).$

Two quantum state ensembles
$\\{\bm{\rho}_{0}^{(\lambda)},\bm{\rho}_{1}^{(\lambda)}\\}_{\lambda}$ are said
to be _computationally indistinguishable_ if for every non-uniform QPT
algorithm $A=\\{A^{(\lambda)},\bm{\rho}^{(\lambda)}\\}$ (that outputs a bit
$b$), we have that

$\Big{|}\mathbf{\operatorname*{\mathbb{E}}}\left[A^{(\lambda)}(\bm{\rho}^{(\lambda)},\bm{\rho}^{(\lambda)}_{0})\right]-\mathbf{\operatorname*{\mathbb{E}}}\left[A^{(\lambda)}(\bm{\rho}^{(\lambda)},\bm{\rho}^{(\lambda)}_{1})\right]\Big{|}=\mathsf{negl}(\lambda).$

Equivalently,
$\\{\bm{\rho}_{0}^{(\lambda)},\bm{\rho}_{1}^{(\lambda)}\\}_{\lambda}$ are
computationally indistinguishable if for every efficiently computable non-
uniform binary observable ($R,\bm{\sigma})$, we have that

$\Big{|}\Tr(R(\bm{\rho}_{0}\otimes\bm{\sigma}))-\Tr(R(\bm{\rho}_{1}\otimes\bm{\sigma}))\Big{|}=\mathsf{negl}(\lambda).$

We will occasionally use the notation $\bm{\rho}_{0}\approx_{c}\bm{\rho}_{1}$
to denote computational indistinguishability of
$\\{\bm{\rho}_{0}^{(\lambda)},\bm{\rho}_{1}^{(\lambda)}\\}_{\lambda}$.

More generally, we use
$(T(\lambda),\varepsilon(\lambda))$-indistinguishability to denote
computational indistiguishability as above where the distinguisher is allowed
to run in time $T$ and the advantage is required to be at most $\varepsilon$.

###  3.5 Mahadev Randomized TCFs

In this section, we define the cryptographic primitive used by Mahadev [Mah18]
to obtain a (non-succinct) delegation scheme for QMA with classical
verification. The primitive is closely related to Regev encryption [Reg05] and
LWE-based “lossy” trapdoor functions [PW08, PVW08, GVW15], but makes use of
special-purpose structure relevant for quantum functionality. Most of this
special-purpose structure, in particular, the “adaptive hardcore bit”, was
introduced in the work of Brakerski, Christiano, Mahadev, Vazirani and Vidick
[BCM+18], but [Mah18] further requires “dual-mode key generation” in addition
to the [BCM+18] properties. Given the numerous special-purpose requirements,
we refer to the primitive as “Mahadev randomized trapdoor claw-free functions
(rTCFs).”141414Actually, [Mah18] requires an extra (second) hardcore bit
property (Property 2 of Definition 4.4 in [Mah18]) that we drop from our
definition, as our proof does not require it.

######  Definition 3.3.

A Mahadev randomized trapdoor claw-free function family (Mahadev rTCF)
$\mathsf{ClawFree}$ is described by a tuple of efficient classical algorithms
$(\mathsf{Gen},\mathsf{Eval},\mathsf{Invert},\mathsf{Check},\mathsf{Good})$
with the following syntax:

  * •

$\mathsf{Gen}(1^{\lambda},\mathsf{mode})$ is a dual-mode PPT key generation
algorithm that takes as input a security parameter $\lambda$ in unary, and a
bit $\mathsf{mode}\in\\{0,1\\}$, and it outputs a public key $\mathsf{pk}$ and
a private key $\mathsf{sk}$. The description of the public key implicitly
defines a domain of the form $\\{0,1\\}\times\mathcal{D}_{\mathsf{pk}}$ for
the randomized function $f_{\mathsf{pk}}$. We view $\mathcal{D}_{\mathsf{pk}}$
as an explicit (efficiently verifiable and samplable) subset of
$\\{0,1\\}^{\ell(\lambda)}$, so that applying bit operations to elements of
$\mathcal{D}_{\mathsf{pk}}$ is well-defined.

In our context, $\mathsf{mode}=0$ samples keys for an injective function and
$\mathsf{mode}=1$ samples keys for a two-to-one function. For the sake of
readability, we use a descriptive notation by which
$\mathsf{mode}\in\\{\mathsf{injective},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}\\}$,
where $\mathsf{mode}=\mathsf{injective}$ corresponds to $\mathsf{mode}=0$ and
$\mathsf{mode}=\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}$ corresponds to
$\mathsf{mode}=1$.

  * •

$\mathsf{Eval}(\mathsf{pk},b,\mathbf{x})$ is a (possibly probabilistic)
algorithm that takes as input a public key $\mathsf{pk}$, a bit
$b\in\\{0,1\\}$ and an element $\mathbf{x}\in\mathcal{D}_{\mathsf{pk}}$, and
outputs a string $\mathbf{y}$ with distribution $\chi$.

  * •

$\mathsf{Invert}(\mathsf{mode},\mathsf{sk},\mathbf{y})$ is a deterministic
algorithm that takes as input
$\mathsf{mode}\in\\{\mathsf{injective},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}\\}$,
a secret key $\mathsf{sk}$, and an element $\mathbf{y}$ in the range. If
$\mathsf{mode}=\mathsf{injective}$ then it outputs a pair
$(b,\mathbf{x})\in\\{0,1\\}\times\mathcal{D}_{\mathsf{pk}}$ or $\bot$. If
$\mathsf{mode}=\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}$ then it
outputs two pairs $(0,\mathbf{x}_{0})$ and $(1,\mathbf{x}_{1})$ with
$\mathbf{x}_{0},\mathbf{x}_{1}\in\mathcal{D}_{\mathsf{pk}}$, or $\bot$.

  * •

$\mathsf{Check}(\mathsf{pk},b,\mathbf{x},\mathbf{y})$ is a deterministic
algorithm takes as input a public key $\mathsf{pk}$, a bit $b\in\\{0,1\\}$, an
element $\mathbf{x}\in\mathcal{D}_{\mathsf{pk}}$, and an element $\mathbf{y}$
in the range, and it outputs a bit.

  * •

$\mathsf{Good}(\mathbf{x}_{0},\mathbf{x}_{1},\mathbf{d})$ is a deterministic
poly-time algorithm that takes as input two domain elements
$\mathbf{x}_{0},\mathbf{x}_{1}\in\mathcal{D}_{\mathsf{pk}}$ and a string
$\mathbf{d}\in\\{0,1\\}^{\ell+1}$. It outputs a bit that characterizes
membership in a set that we call

$\mathsf{Good}_{\mathbf{x}_{0},\mathbf{x}_{1}}\coloneqq\\{\mathbf{d}:\mathsf{Good}(\mathbf{x}_{0},\mathbf{x}_{1},\mathbf{d})=1\\}.$

Moreover, we stipulate that
$\mathsf{Good}(\mathbf{x}_{0},\mathbf{x}_{1},\mathbf{d})$ ignores the first
bit of $\mathbf{d}$.151515We depart slightly from notation in prior work,
which defines $\mathbf{d}$ to be an element of $\\{0,1\\}^{\ell}$
(corresponding to the last $\ell$ bits of our $\mathbf{d}$).

We require that the following properties are satisfied.

  1. 1.

Correctness:

    1. (a)

For _all_ $(\mathsf{pk},\mathsf{sk})$ in the support of
$\mathsf{Gen}(\mathsf{injective},1^{\lambda})$: For every $b\in\\{0,1\\}$,
every $\mathbf{x}\in\mathcal{D}_{\mathsf{pk}}$, and every $\mathbf{y}\in{\sf
Supp}(\mathsf{Eval}(\mathsf{pk},(b,\mathbf{x})))$,

$\mathsf{Invert}(\mathsf{injective},\mathsf{sk},\mathbf{y})=(b,\mathbf{x}).$

    2. (b)

For _all_ $(\mathsf{pk},\mathsf{sk})$ in the support of
$\mathsf{Gen}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},1^{\lambda})$:
For every $b\in\\{0,1\\}$, every $\mathbf{x}\in\mathcal{D}_{\mathsf{pk}}$, and
every $\mathbf{y}\in{\sf Supp}(\mathsf{Eval}(\mathsf{pk},(b,\mathbf{x})))$,

$\mathsf{Invert}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},\mathsf{sk},\mathbf{y})=((0,\mathbf{x}_{0}),(1,\mathbf{x}_{1}))$

such that $\mathbf{x}_{b}=\mathbf{x}$ and $\mathbf{y}\in{\sf
Supp}(\mathsf{Eval}(\mathsf{pk},(\beta,\mathbf{x}_{\beta})))$ for every
$\beta\in\\{0,1\\}$.

    3. (c)

For every $(\mathsf{pk},\mathsf{sk})\in{\sf
Supp}(\mathsf{Gen}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},1^{\lambda}))\cup{\sf
Supp}(\mathsf{Gen}(\mathsf{injective},1^{\lambda}))$, every $b\in\\{0,1\\}$
and every $\mathbf{x}\in\mathcal{D}$,

$\Pr[\mathsf{Check}(\mathsf{pk},(b,\mathbf{x}),\mathbf{y})=1]=1$

if and only if $\mathbf{y}\in{\sf
Supp}(\mathsf{Eval}(\mathsf{pk},(b,\mathbf{x})))$.

    4. (d)

For every $(\mathsf{pk},\mathsf{sk})$ in the support of
$\mathsf{Gen}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},1^{\lambda})$
and every pair of domain elements $\mathbf{x}_{0},\mathbf{x}_{1}$, the density
of $\mathsf{Good}_{\mathbf{x}_{0},\mathbf{x}_{1}}$ is
$1-\mathsf{negl}(\lambda)$.

  2. 2.

Key Indistinguishability:

$\\{\mathsf{pk}:(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},1^{\lambda})\\}\approx_{c}\\{\mathsf{pk}:(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(\mathsf{injective},1^{\lambda})\\}$

  3. 3.

Adaptive Hardcore Bit: For every ${\sf BQP}$ adversary ${\cal
A}=(\cal{A}_{0},\cal{A}_{1})$ there exists a negligible function $\mu$ such
that for every $\lambda\in\mathbb{N}$, the following difference of
probabilities is equal to $\mu(\lambda)$:

$\displaystyle\Big{|}\Pr[{\cal
A}_{1}(\mathsf{pk},\mathbf{y})=(\mathbf{d},(b,\mathbf{x})):\mathsf{Check}(\mathsf{pk},b,\mathbf{x},\mathbf{y})=1~{}~{}\wedge~{}~{}\mathbf{d}\cdot(1,\mathbf{x}_{0}\oplus\mathbf{x}_{1})=0~{}~{}\wedge~{}~{}\mathbf{d}\in\mathsf{Good}_{\mathbf{x}_{0},\mathbf{x}_{1}}]$
$\displaystyle-\Pr[{\cal
A}_{1}(\mathsf{pk},\mathbf{y})=(\mathbf{d},(b,\mathbf{x})):\mathsf{Check}(\mathsf{pk},b,\mathbf{x},\mathbf{y})=1~{}~{}\wedge~{}~{}\mathbf{d}\cdot(1,\mathbf{x}_{0}\oplus\mathbf{x}_{1})=1~{}~{}\wedge~{}~{}\mathbf{d}\in\mathsf{Good}_{\mathbf{x}_{0},\mathbf{x}_{1}}]\Big{|}$

where the probabilities are over the experiment that generates
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},1^{\lambda})$,
$\mathbf{y}\leftarrow\mathcal{A}_{0}(\mathsf{pk})$, and where
$((0,\mathbf{x}_{0}),(1,\mathbf{x}_{1}))=\mathsf{Invert}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},\mathsf{sk},\mathbf{y})$.

######  Lemma 3.4 ([BCM+18, Mah18]).

Assuming LWE, there is a collection of Mahadev randomized TCFs.

######  Remark 3.5.

For some of our applications (and for simplicity of proofs), we will actually
require an rTCF that is _perfectly correct_ , which means that the correctness
properties (a) and (b) hold with probability 1. That is, they hold for all
$(\mathsf{pk},\mathsf{sk})\in\mathsf{Gen}(\mathsf{injective},1^{\lambda})$ and
$(\mathsf{pk},\mathsf{sk})\in\mathsf{Gen}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},1^{\lambda})$
respectively. We briefly argue that this is possible. In the injective mode
case, this is possible because the sampling procedure for injective keys given
in [Mah18, Section 9.2] can determine whether the key it sampled is indeed
injective and if not, output a fixed hard-coded injective key. In the 2-to-1
mode case, the sampling procedure given in [BCM+18, Section 4.1] is perfect
except for when $s=0^{n}$. Thus, we can again hard-code a fixed 2-to-1 key to
output instead whenever $s=0^{n}$.

###  3.6 Collapsing Hash Functions

##### Collapsing Hash Functions.

Let $H=\\{H_{\lambda}\\}_{\lambda\in\mathbb{N}}$ be a hash function family
where each $H_{\lambda}$ is a distribution over functions
$h:\\{0,1\\}^{n(\lambda)}\rightarrow\\{0,1\\}^{\ell(\lambda)}$.

Define the collapsing experiment $\texttt{CollapseExpt}_{H,\lambda,b}(D)$ on
quantum distinguisher $D$ as follows.
$\texttt{CollapseExpt}_{H,\lambda,b}(D)$:

  1. 1.

The challenger samples $h\leftarrow H_{\lambda}$ and sends $h$ to the
distinguisher $D$.

  2. 2.

The distinguisher replies with a classical binary string
$y\in\\{0,1\\}^{\ell(\lambda)}$ and an $n(\lambda)$-qubit quantum state on the
register $\mathcal{X}$. Note that the requirement that $y$ be classical can be
enforced by having the challenger immediately measure these registers upon
receiving them.

  3. 3.

The challenger computes $h$ in superposition on the $n(\lambda)$-qubit quantum
state, and measures the bit indicating whether the output of $h$ equals $y$.
If the output does not equal $y$, the challenger aborts and outputs $\bot$.

  4. 4.

If $b=0$, the challenger does nothing. If $b=1$, the challenger measures the
$n(\lambda)$-qubit state in the standard basis.

  5. 5.

The challenger returns the contents of the $\mathcal{X}$ register to the
distinguisher.

  6. 6.

The distinguisher outputs a bit $b^{\prime}$.

######  Definition 3.6 ([Unr16b]).

$H=\\{H_{\lambda}\\}_{\lambda}$ is _collapsing_ if for every security
parameter $\lambda\in\mathbb{N}$ and any polynomial-size quantum distinguisher
$\mathcal{D}=\\{D_{\lambda}\\}_{\lambda}$, there exists a negligible function
$\mu$ such that

$\left|\Pr[\texttt{\emph{CollapseExpt}}_{H,\lambda,0}(D_{\lambda})=1]-\Pr[\texttt{\emph{CollapseExpt}}_{H,\lambda,1}(D_{\lambda})=1]\right|\leq\mu(\lambda).$

Unruh [Unr16a] constructs collapsing hash functions from lossy functions,
which can be based on LWE [PW08].

######  Lemma 3.7 ([PW08, Unr16a]).

Assuming LWE, a family of collapsing hash functions
$\\{H_{\lambda}:\,\\{0,1\\}^{*}\to\\{0,1\\}^{\lambda}\\}_{\lambda}$ exists.

###  3.7 Fully Homomorphic Encryption

We define fully homomorphic encryption (FHE), which is used in Section 9. A
fully homomorphic encryption scheme
$\mathsf{FHE}=(\mathsf{FHE}.\mathsf{Gen},\mathsf{FHE}.\mathsf{Enc},\allowbreak\mathsf{FHE}.\mathsf{Dec},\mathsf{FHE}.\mathsf{Eval})$
for (classical) polynomial-time computation is a tuple of four PPT algorithms.

  * •

$\mathsf{Gen}(1^{\lambda})$ takes as input the security parameter and outputs
a key pair $(\mathsf{pk},\mathsf{sk})$.

  * •

$\mathsf{Enc}(\mathsf{pk},m)$ takes as input a message $m$ and outputs a
ciphertext $\mathsf{ct}$.

  * •

$\mathsf{Eval}(f,\mathsf{ct})$ takes as input a ciphertext $\mathsf{ct}$
corresponding to an $n$-bit plaintext as well as a function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. It outputs a ciphertext
$\mathsf{ct}_{f}$.

  * •

$\mathsf{Dec}(\mathsf{sk},\mathsf{ct})$ takes as input the secret key and a
ciphertext. It outputs a message.

We require the following properties.

  * •

Evaluation/Decryption Correctness: for any (polynomial-size circuit) function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and any message $m\in\\{0,1\\}^{n}$, we
have that

$\mathsf{Dec}(\mathsf{sk},\mathsf{Eval}(f,\mathsf{Enc}(\mathsf{pk},m)))=f(m)$

with probability $1-\mathsf{negl}(\lambda)$ over the parameter sampling.

  * •

Compactness: we require that
$\mathsf{FHE}.\mathsf{Eval}(f,\mathsf{Enc}(\mathsf{pk},m))$ has a fixed size
$\mathsf{poly}(\lambda)$ independent of $|f|,|m|$.

  * •

Semantic Security: For any pair of messages $(m_{0},m_{1})$, we have that
$(\mathsf{pk},\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},m_{0}))\approx_{c}(\mathsf{pk},\mathsf{FHE}.\mathsf{Enc}(\mathsf{pk},m_{1}))$.

######  Theorem 3.8 ([Gen09, BV11, BGV12, BV14]).

Under circular-secure variants of the Learning with Errors assumption, there
exists a fully homomorphic encryption scheme for all polynomial-time
computable functions. If the circular LWE variant is post-quantum, then so is
the FHE scheme.

Under the standard LWE assumption, there exists a FHE scheme for all
polynomial-size circuits of depth $d(\lambda)$, where the scheme has
compactness $\mathsf{poly}(\lambda,d)$.

###  3.8 Indistinguishability Obfuscation

An indistinguishability obfuscator (iO) is an algorithm
$\mathsf{i}\mathcal{O}$ that takes as input a circuit $C$ and satisfies the
following properties.

  * •

Functional Equivalence: for any (polynomial-size) circuit circuit
$C:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}$ and any input $x\in\\{0,1\\}^{n}$,
we have that

$\mathsf{i}\mathcal{O}(C)(x)=C(x).$

  * •

Security: For any pair of functionally equivalent circuits $(C_{0},C_{1})$, we
have that

$\mathsf{i}\mathcal{O}(C_{0})\approx_{c}\mathsf{i}\mathcal{O}(C_{1}).$

We mention that, while some recent candidates for iO (such as [JLS21]) can be
broken using quantum algorithms, others, such as [BGMZ18, CVW18, BDGM20, WW21,
GP21, DQV+21], are plausibly post-quantum secure. Furthermore, it will be
convenient for us to assume iO with perfect correctness to simplify our
analysis (in particular the argument in Section 10.3). We point out that this
property is already satisfied by most candidates and can also be attained via
generic transformations [BV17].

###  3.9 Puncturable PRFs

######  Definition 3.9 (Puncturable PRF [BW13, BGI14, KPTZ13, SW14]).

A puncturable PRF family is a family of functions

${\cal
F}=\left\\{F_{\lambda,s}:\\{0,1\\}^{\nu(\lambda)}\to\\{0,1\\}^{\mu(\lambda)}\right\\}_{\lambda\in\mathbb{N},s\in\\{0,1\\}^{\ell(\lambda)}}$

with associated (deterministic) polynomial-time algorithms $({\cal
F}.\mathsf{Eval},{\cal F}.\mathsf{Puncture},\allowbreak{\cal
F}.\mathsf{PuncEval})$ satisfying

  * •

For all $x\in\\{0,1\\}^{\nu(\lambda)}$ and all
$s\in\\{0,1\\}^{\ell(\lambda)}$, ${\cal
F}.\mathsf{Eval}(s,x)=F_{\lambda,s}(x)$.

  * •

For all distinct $x,x^{\prime}\in\\{0,1\\}^{\nu(\lambda)}$ and all
$s\in\\{0,1\\}^{\ell(\lambda)}$,

${\cal F}.\mathsf{PuncEval}({\cal F}.\mathsf{Puncture}(s,x),x^{\prime})={\cal
F}.\mathsf{Eval}(s,x^{\prime})$

For ease of notation, we write $F_{s}(x)$ and ${\cal F}.\mathsf{Eval}(s,x)$
interchangeably, and we write $s\\{x\\}$ to denote ${\cal
F}.\mathsf{Puncture}(s,x)$.

${\cal F}$ is said to be $(s,\delta)$-secure if for every
$\\{x^{(\lambda)}\in\\{0,1\\}^{\nu(\lambda)}\\}_{\lambda\in\mathbb{N}}$, the
following two distribution ensembles (indexed by $\lambda$) are
$\delta(\lambda)$-indistinguishable to circuits of size $s(\lambda)$:

$(S\\{x^{(\lambda)}\\},F_{S}(x^{(\lambda)}))\text{ where
$S\leftarrow\\{0,1\\}^{\ell(\lambda)}$}$

and

$(S\\{x^{(\lambda)}\\},U)\text{ where $S\leftarrow\\{0,1\\}^{\ell(\lambda)}$,
$U\leftarrow\\{0,1\\}^{\mu(\lambda)}$}.$

######  Theorem 3.10 ([GGM84, KPTZ13, BW13, BGI14, SW14]).

If {polynomially secure, subexponentially secure} one-way functions exist,
then for all functions $\mu:\mathbb{N}\to\mathbb{N}$ (with $1^{\mu(\nu)}$
polynomial-time computable from $1^{\nu}$), and all
$\delta:\mathbb{N}\rightarrow[0,1]$ with $\delta(\nu)\geq
2^{-\mathsf{poly}(\nu)}$, there are polynomials $\ell(\lambda),\nu(\lambda)$
and a {polynomially secure,
$(\frac{1}{\delta(\nu(\lambda))},\delta(\nu(\lambda)))$-secure} puncturable
PRF family

${\cal
F}_{\mu}=\left\\{F_{\lambda,s}:\\{0,1\\}^{\nu(\lambda)}\rightarrow\\{0,1\\}^{\mu(\nu(\lambda))}\\}_{\lambda\in\mathbb{N},s\in\\{0,1\\}^{\ell(\lambda)}}\right\\}.$

##  4 Commit-and-Measure Protocols

###  4.1 Defining Commit-and-Measure Protocols

In this section, we formalize the notion of a _commit-and-measure protocol_ ,
which was informally described in [Mah18]. A commit-and-measure protocol
enables a classical verifier to obtain the results of measuring, in the
standard or Hadamard basis, each qubit of an $N$-qubit quantum state
$\bm{\sigma}$ held by the prover. More precisely, the verifier encodes its
choice of basis with a classical circuit $C:[N]=\\{0,1\\}^{\log
N}\rightarrow\\{0,1\\}$, where $C(i)=b$ specifies the basis for the
measurement of the $i$th qubit. We adopt the convention that $b=0$ corresponds
to the standard basis and $b=1$ corresponds to the Hadamard basis. Note that
in Mahadev’s original protocol, $C$ is given as an explicit string
$(C(0),C(1),\dots,C(N-1))$, but our eventual _succinct_ protocols will require
circuits $C$ with size much smaller than $N$.

######  Definition 4.1 (Commit-and-Measure Protocol Syntax).

An $N$-qubit commit-and-measure protocol between a quantum polynomial-time
prover $P=(\mathsf{Commit},\mathsf{Open})$ and a classical probabilistic
polynomial-time verifier $V=(\mathsf{Gen},\mathsf{Test},\mathsf{Out})$ has the
following syntax.

  1. 1.

The verifier samples
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},C)$, where
$C:[N]=\\{0,1\\}^{\log N}\to\\{0,1\\}$ represents a _basis vector_
$h\in\\{0,1\\}^{N}$, obtaining public parameters $\mathsf{pk}$ and secret
parameters $\mathsf{sk}$. It sends the public parameters $\mathsf{pk}$ to the
prover.

  2. 2.

The prover computes
$(y,\bm{\rho})\leftarrow\mathsf{Commit}(\mathsf{pk},\bm{\sigma})$, obtaining a
classical “commitment” string $y$ and a private quantum state $\bm{\rho}$. It
sends $y$ to the verifier.

  3. 3.

The verifier samples a random challenge bit $c\leftarrow\\{0,1\\}$ and sends
$c$ to the prover; $c=0$ corresponds to a “test round” and $c=1$ corresponds
to a “measurement round”.

  4. 4.

The prover computes $z\leftarrow\mathsf{Open}(\bm{\rho},c)$, obtaining a
classical string $z$ that it sends to the verifier.

  5. 5.

If $c=0$, the verifier computes
$\\{\mathsf{acc},\mathsf{rej}\\}\leftarrow\mathsf{Test}(\mathsf{pk},(y,z))$.

If $c=1$, the verifier computes $m\leftarrow\mathsf{Out}(\mathsf{sk},(y,z))$
to obtain a classical string $m\in\\{0,1\\}^{N}$ of measurement outcomes.

The protocol is required to satisfy the following completeness (Definition
4.2) and soundness (Definition 4.5) properties. For the definitions below, we
write $M(h,\bm{\sigma})$ to denote the distribution of outcomes from measuring
$\bm{\sigma}$ in the basis $h$.

######  Definition 4.2 (Completeness).

A commit-and-measure protocol is required to satisfy two completeness
properties.

  1. 1.

(Test Round Completeness) For all $C:[N]\to\\{0,1\\}$ and $N$-qubit states
$\bm{\sigma}$:

$\Pr\left[\mathsf{acc}\leftarrow\mathsf{Test}(\mathsf{pk},(y,z)):\begin{array}[]{r}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},C)\\\
(y,\bm{\rho})\leftarrow\mathsf{Commit}(\mathsf{pk},\bm{\sigma})\\\
z\leftarrow\mathsf{Open}(\bm{\rho},0)\\\
\end{array}\right]=1-\mathsf{negl}(\lambda).$

  2. 2.

(Measurement Round Completeness) For all $C:[N]\to\\{0,1\\}$ and $N$-qubit
states $\bm{\sigma}$:

$\left\\{m\leftarrow\mathsf{Out}(\mathsf{sk},(y,z)):\begin{array}[]{r}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda},C)\\\
(y,\bm{\rho})\leftarrow\mathsf{Commit}(\mathsf{pk},\bm{\sigma})\\\
z\leftarrow\mathsf{Open}(\bm{\rho},1)\\\
\end{array}\right\\}\approx_{c}M(h,\bm{\sigma}),$

where $h\in\\{0,1\\}^{N}$ is such that $h_{i}=C(i)$ for all
$i\in[N]=\\{0,1\\}^{\log N}$.

######  Remark 4.3.

The [Mah18] protocol satisfies _statistical_ measurement round completeness,
but our verifier-succinct commit-and-measure protocol will not.

######  Remark 4.4.

One of our applications will require a measurement protocol with _perfect_
completeness, which stipulates that the above completeness guarantees hold
over _all_ $(\mathsf{pk},\mathsf{sk})\in\mathsf{Gen}(1^{\lambda},C)$ (and
where the measurement round completeness is statistical rather than
computational). This can be achieved by using an rTCF with perfect
correctness, which we discuss in Section 3.5, and, in the succinct case, an
indistinguishability obfuscation scheme with perfect correctness (Section
3.8).

To state our soundness definition (Definition 4.5), we first specify the
registers that any non-uniform cheating prover acts on:

  * •

$\mathcal{P}$ contains the public parameters $\mathsf{pk}$,

  * •

$\mathcal{Y}$ contains the classical commitment string $y$,

  * •

$\mathcal{Z}$ contains the classical opening string $z$,

  * •

$\mathcal{I}$ contains the prover’s initial state and its internal work
registers.

In a protocol execution, $\mathcal{P}$ is initialized with
$\outerproduct{\mathsf{pk}}{\mathsf{pk}}$. A non-uniform cheating prover

$P^{*}=(\bm{\rho}_{0},U_{\mathsf{Commit}^{*}},U_{\mathsf{Open}^{*},0},U_{\mathsf{Open}^{*},1})$

is parameterized by:

  * •

An arbitrary quantum state
$\bm{\rho}_{0}\in\mathrm{D}(\mathcal{Y}\otimes\mathcal{Z}\otimes\mathcal{I})$.
In a protocol execution with $\widetilde{P}$,
$\mathcal{Y}\otimes\mathcal{Z}\otimes\mathcal{I}$ is initialized with
$\bm{\rho}_{0}$.

  * •

An adversarial commitment unitary $U_{\mathsf{Commit}^{*}}$ on
$\mathcal{P}\otimes\mathcal{Y}\otimes\mathcal{Z}\otimes\mathcal{I}$ of the
form

$\sum_{\mathsf{pk}}\outerproduct{\mathsf{pk}}{\mathsf{pk}}_{\mathcal{P}}\otimes(U_{\mathsf{Commit}^{*},\mathsf{pk}})_{\mathcal{Y},\mathcal{Z},\mathcal{I}}.$

That is, $U_{\mathsf{Commit}^{*}}$ is classically controlled on $\mathcal{P}$.
In particular, the adversarial prover’s commitment on verifier message
$\mathsf{pk}$ is obtained by measuring register $\mathcal{Y}$ of

$U_{\mathsf{Commit}^{*}}(\outerproduct{\mathsf{pk}}{\mathsf{pk}}_{\mathcal{P}}\otimes(\bm{\rho}_{0})_{\mathcal{Y},\mathcal{Z},\mathcal{I}})$

in the computational basis to obtain $y$.

  * •

An adversarial opening unitary $U_{\mathsf{Open}^{*},0}$ on
$\mathcal{P}\otimes\mathcal{Y}\otimes\mathcal{Z}\otimes\mathcal{I}$
corresponding to the prover’s behavior in the test round $(b=0)$ of the form:

$\sum_{\mathsf{pk},y}\outerproduct{\mathsf{pk},y}{\mathsf{pk},y}_{\mathcal{P},\mathcal{Y}}\otimes(U_{\mathsf{Open}^{*},0,\mathsf{pk},y})_{\mathcal{Z},\mathcal{I}}.$

That is, $U_{\mathsf{Open}^{*},0}$ is classically controlled on $\mathcal{P}$
and $\mathcal{Y}$. In particular, given a commitment string $y$ and residual
prover state $\bm{\rho}\in\mathrm{D}(\mathcal{Z}\otimes\mathcal{I})$, the
prover’s response on challenge $c=0$ is obtained by measuring register
$\mathcal{Z}$ of

$U_{\mathsf{Open}^{*},0}(\outerproduct{\mathsf{pk},y}{\mathsf{pk},y}_{\mathcal{P},\mathcal{Y}}\otimes\bm{\rho}_{\mathcal{Z},\mathcal{I}})$

in the computational basis to obtain $z$.

  * •

An adversarial opening unitary $U_{\mathsf{Open}^{*},1}$ on
$\mathcal{P}\otimes\mathcal{Y}\otimes\mathcal{Z}\otimes\mathcal{I}$
corresponding to the prover’s behavior in the measurement round $(b=1)$ of the
form:

$\sum_{\mathsf{pk},y}\outerproduct{\mathsf{pk},y}{\mathsf{pk},y}_{\mathcal{P},\mathcal{Y}}\otimes(U_{\mathsf{Open}^{*},1,\mathsf{pk},y})_{\mathcal{Z},\mathcal{I}}.$

In particular, given a commitment string $y$ and residual prover state
$\bm{\rho}\in\mathrm{D}(\mathcal{Z}\otimes\mathcal{I})$, the prover’s response
on challenge $c=1$ is obtained by measuring register $\mathcal{Z}$ of

$U_{\mathsf{Open}^{*},1}(\outerproduct{\mathsf{pk},y}{\mathsf{pk},y}_{\mathcal{P},\mathcal{Y}}\otimes\bm{\rho}_{\mathcal{Z},\mathcal{I}})$

in the Hadamard basis to obtain $z$.

Following [Mah18], we can assume without loss of generality that
$U_{\mathsf{Open}^{*},0}$ is the identity (refer to Section 3.2 for additional
details). We will therefore write $U$ to describe the prover’s “attack
unitary” for the measurement round $(c=1)$.

For defining soundness, we informally require that a prover $P^{*}$ that
passes the test round with probability $1-\mathsf{negl}(\lambda)$ (this could
alternatively be enforced by applying a measurement in the security game)
implicitly defines171717In fact, we require that $\bm{\tau}$ can be extracted
efficiently from $P^{*}$. an $N$-qubit state $\bm{\tau}$ whose measurement
outcome distribution matches the output distribution of $\mathsf{Out}(\cdot)$
(up to computational indistinguishability).

######  Definition 4.5 (Soundness).

There exists an efficient classical algorithm $\mathsf{SimGen}(1^{\lambda})$
and an efficient quantum algorithm
$\mathsf{Ext}^{U,\bm{\rho}}(\mathsf{pk},\mathsf{sk},y)$ with black-box access
to an attacker parameterized by a state $\bm{\rho}$ and a unitary $U$ (see
Section 3.2 for more details on how we formalize quantum black-box access),
that takes as input classical strings $(\mathsf{pk},\mathsf{sk},y)$, and
satisfies the following properties:

  * •

Consider any non-uniform QPT cheating prover
$P^{*}=(\bm{\rho}_{0},U_{\mathsf{Commit}^{*}},U)$ that passes the test round
with probability $1-\mathsf{negl}(\lambda)$ for all $h\in\\{0,1\\}^{N}$.

Then, for all $h\in\\{0,1\\}^{N}$ with circuit representation $C$, the
following two distributions are computationally indistinguishable:

Real:

    1. 1.

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

    2. 2.

Run the attacker $P^{*}$ on $\mathsf{pk}$ to obtain a classical commitment
string $y$ (i.e., apply $U_{\mathsf{Commit}^{*}}$ and then measure the
register containing $y$). Denote the post-measurement state as
$\bm{\rho}\in\mathrm{D}(\mathcal{Z}\otimes\mathcal{I})$, where $\mathcal{Z}$
corresponds to the registers that will eventually be measured to obtain the
prover’s final message, and $\mathcal{I}$ contains all of the other internal
registers of the prover.181818We will also assume, without loss of generality,
that the prover always copies $\mathsf{pk}$ and $y$ into its internal state
registers $\mathcal{I}$.

    3. 3.

Apply the prover’s attack unitary $U$. This yields the state
$\bm{\rho}^{\prime}\coloneqq U\bm{\rho}_{\mathcal{Z},\mathcal{I}}U^{\dagger}$.
Measure the $\mathcal{Z}$ register of $\bm{\rho}^{\prime}$ in the Hadamard
basis to obtain the prover’s opening string $z$.

    4. 4.

Compute $m\leftarrow\mathsf{Out}(\mathsf{sk},(y,z))$ and output $m$.

Sim:

    1. 1.

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

    2. 2.

Run the attacker $P^{*}$ on $\mathsf{pk}$ to obtain a classical commitment
string $y$ (i.e., apply $U_{\mathsf{Commit}^{*}}$ and then measure the
register containing $y$). Denote the post-measurement state as
$\bm{\rho}\in\mathrm{D}(\mathcal{Z}\otimes\mathcal{I})$.

    3. 3.

Run
$\mathsf{Ext}^{U,\bm{\rho}}(\mathsf{pk},\mathsf{sk},y)\rightarrow\bm{\tau}$ to
obtain an $N$-qubit state $\bm{\tau}$.

    4. 4.

Measure each qubit of $\bm{\tau}$ according to the bases specified by
$h\in\\{0,1\\}^{N}$ (i.e., qubit $i$ is measured in the Hadamard basis if
$h_{i}=1$ and the standard basis if $h_{i}=0$) and output the result.

##  5 A Measurement Protocol Template

In this section, we describe a generic construction of a $N$-qubit commit-and-
measure protocol (Section 4) using two building blocks: (1) a family of
Mahadev rTCFs (Definition 3.3), and (2) a “batch key generation” scheme (fully
defined in Section 7) whose syntax we describe below. We consider two
different instantiations of this template:

  * •

Using a “trivial” batch key generation scheme in which the $N$ rTCF keys are
sampled i.i.d., we recover Mahadev’s original protocol [Mah18].

  * •

Using a succinct key generation scheme (constructed in Sections 7 and 7.2, we
obtain a measurement protocol in which the verifier’s messages are succinct.
We refer to this as a verifier-succinct measurement protocol.

##### Batch Key Generation.

For our construction, we make use of what we call a “batch key generation
scheme” for the Mahadev rTCF. Let
$\mathsf{TCF}.\mathsf{Gen}(1^{\lambda},\mathsf{mode})$ denote the “standard”
key generation algorithm for a Mahadev rTCF. Informally, a batch key
generation scheme for $\mathsf{TCF}.\mathsf{Gen}(1^{\lambda},\mathsf{mode})$
is a mechanism that produces a joint representation of $N$ TCF pairs
$(\mathsf{pk}_{i},\mathsf{sk}_{i})$, from which any individual
$\mathsf{pk}_{i},\mathsf{sk}_{i}$ can be computed, such that the pairs
$(\mathsf{pk}_{i},\mathsf{sk}_{i})$ are sufficiently “independent” of each
other.

A full definition of a batch key generation scheme is given in Definition 7.2,
but we formally state here the relevant syntax and security properties.
Syntactically, a batch key generation scheme includes three algorithms
$(\mathsf{Gen},\mathsf{ExtPk},\mathsf{ExtSk})$, where:

  * •

$\mathsf{Gen}(1^{\lambda},C)$ takes as input a security parameter $\lambda$
and a circuit $C:[N]\rightarrow\\{0,1\\}$ representing (through its truth
table) an $N$-bit string. It outputs a master public key $\mathsf{PK}$ and
master secret key $\mathsf{SK}$.

  * •

$\mathsf{ExtPk}(\mathsf{PK},i)$ is a deterministic algorithm that takes as
input $\mathsf{PK}$ and an index $i\in N$, and outputs a public key
$\mathsf{pk}_{i}$.

  * •

$\mathsf{ExtSk}(\mathsf{SK},i)$ is a deterministic algorithm that takes as
input $\mathsf{SK}$ and an index $i\in N$, and outputs a secret key
$\mathsf{sk}_{i}$.

When instantiated for a Mahadev rTCF family, we require the following
properties to hold for such a procedure:

  * •

Correctness: for
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{Gen}(1^{\lambda},N,C)$ and
$(\mathsf{pk}_{i},\mathsf{sk}_{i})=(\mathsf{ExtPk}(\mathsf{PK},i),\mathsf{ExtSk}(\mathsf{SK},i))$,
we have that $(\mathsf{pk}_{i},\mathsf{sk}_{i})$ is in the range of
$\mathsf{TCF}.\mathsf{Gen}(1^{\lambda},C(i))$ (i.e. they are a valid key pair
in mode $C(i)$).

  * •

Key Indistinguishability: if $C_{1}$ and $C_{2}$ represent functions that
agree on a set $T$ of inputs, then $\mathsf{PK}$ output by
$\mathsf{Gen}(1^{\lambda},C_{1})$ is computationally indistinguishable from
$\mathsf{PK}$ output by $\mathsf{Gen}(1^{\lambda},C_{2})$, _even_ in the
presence of all $\\{\mathsf{sk}_{i},i\in T\\}$.

  * •

Collapsing at a single index: For any index $j$, the function
$f_{\mathsf{pk}_{j}}$ is collapsing even given all secret keys
$\mathsf{sk}_{i}$ for $i\neq j$.

  * •

Adaptive hardcore bit at a single index: For any index $j$, the function
$f_{\mathsf{pk}_{j}}$ satisfies the rTCF adaptive hardcore bit property even
given all secret keys $\mathsf{sk}_{i}$ for $i\neq j$.

Our protocol is a variant of the Mahadev protocol [Mah18] in which the
verifier’s first message $(\mathsf{pk}_{1},\ldots,\mathsf{pk}_{N})$ is
replaced by the output $\mathsf{PK}$ of a batch key generation procedure.

###  5.1 Measurement Protocol Description

Let
$\mathsf{ClawFree}=(\mathsf{TCF.}\mathsf{Gen},\mathsf{Eval},\mathsf{Invert},\mathsf{Check},\mathsf{Good})$
denote a family of [Mah18] randomized TCFs (Definition 3.3). For simplicity of
the analysis, we assume that on a fixed security parameter $1^{\lambda}$,
$\mathsf{Gen}$ outputs keys defining functions from $\\{0,1\\}\times D$ to
$R$, where $D$ is a fixed-size subset of $\\{0,1\\}^{\ell(\lambda)}$
independent of $\mathsf{pk}$.191919The LWE-based instantiation from [BCM+18]
satisfies this property. However, with more complicated expressions, our proof
should go through without this simplifying assumption. We denote the size of
$D$ by $L(\lambda)$. Let $(\mathsf{Gen},\mathsf{ExtPk},\mathsf{ExtSk})$ denote
a batch key generation algorithm for $\mathsf{TCF}.\mathsf{Gen}$ satisfying
the requirements described above.

For simplicity, we assume the honest prover $P$ has an $N$-qubit pure state of
the form

$\ket{\psi}_{\mathcal{W}}=\sum_{w_{1},\ldots,w_{N}}\alpha_{w_{1},\ldots,w_{N}}\ket{w_{1}\ldots
w_{N}}$

on its internal $N$-qubit register $\mathcal{W}$; the protocol completeness
immediately extends to mixed states by linearity. The verifier has a basis
string $h\in\\{0,1\\}^{N}$, represented by a circuit
$C:[N]\rightarrow\\{0,1\\}$, and wants to obtain a measurement of $\ket{\psi}$
in this basis (where $h_{i}=0$ denotes a standard basis measurement and
$h_{i}=1$ denotes a Hadamard basis measurement). The protocol $\mathsf{MP}$
(for measurement protocol), with prover algorithm
$P=(\mathsf{MP}.\mathsf{Commit},\mathsf{MP}.\mathsf{Open})$ and verifier
algorithm
$V=(\mathsf{MP}.\mathsf{Gen},\mathsf{MP}.\mathsf{Test},\mathsf{MP}.\mathsf{Out})$,
is executed as follows.

  * •

$\mathsf{MP}.\mathsf{Gen}$: On input $1^{\lambda}$, $N$ and $C$, the verifier
samples a representation of $N$ TCF key pairs by computing
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{Gen}(1^{\lambda},N,C)$, where $C$
is circuit computing $C(i)=h_{i}$. The verifier sends $\mathsf{PK}$ to the
prover.

  * •

$\mathsf{MP}.\mathsf{Commit}$: Given $\mathsf{PK}$ and its input state
$\ket{\psi}_{\mathcal{W}}$, the prover computes public keys
$\mathsf{pk}_{i}\leftarrow\mathsf{ExtPk}(\mathsf{PK},i)$ for $1\leq i\leq N$.
From now on, $P$ operates directly on $(\mathsf{pk}_{i})$ and ignores
$\mathsf{PK}$.

The prover coherently (with respect to $\ket{\psi}$) computes a “range
superposition”

$\frac{1}{\sqrt{L^{N}}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{N}\in D\\\
y_{1},\ldots,y_{N}\in R\\\
w\in\\{0,1\\}^{N}\end{subarray}}\left(\alpha_{w}\prod_{i}\sqrt{p_{\mathsf{pk}_{i}}(w_{i},x_{i},y_{i})}\ket{w}_{\mathcal{W}}\ket{x_{1}}_{\mathcal{X}_{1}}\ldots\ket{x_{N}}_{\mathcal{X}_{N}}\ket{y_{1}}_{\mathcal{Y}_{1}}\ldots\ket{y_{N}}_{\mathcal{Y}_{N}}\right)$

where each $\mathcal{X}_{i}$ is an $\ell(\lambda)$-qubit register (where
$D\subset\\{0,1\\}^{\ell})$, and each $\mathcal{Y}_{i}$

has basis $\\{\ket{y}\\}_{y\in R}$. Here, $p_{\mathsf{pk}}(b,x,y)$ denotes the
probability density of $y$ in the distribution $f_{\mathsf{pk}}(b,x)$, where
$p_{\mathsf{pk}}(b,x,y)\coloneqq 0$ for $x\in\\{0,1\\}^{\ell}\setminus D$.
Following [BCM+18, Section 4.3] the honest prover algorithm can efficiently
prepare this state up to exponentially small trace distance.

After preparing this state, the prover measures
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{N}$ in the standard ($R$-)basis and sends
the outcome $(y_{1},\dots,y_{N})$ to the verifier.

  * •

The verifier sends a uniformly random challenge bit $c$. After receiving the
prover response, the verifier computes each public key
$\mathsf{pk}_{i}\leftarrow\mathsf{ExtPk}(\mathsf{PK},i)$ and secret key
$\mathsf{sk}_{i}\leftarrow\mathsf{ExtSk}(\mathsf{SK},i)$ in order to evaluate
either $\mathsf{MP}.\mathsf{Test}$ or $\mathsf{MP}.\mathsf{Out}$.

  * •

$\mathsf{MP}.\mathsf{Open}$: On challenge bit $c$, the prover operates as
follows.

    * –

If $c=0$, the prover measures
$\mathcal{W}\otimes\mathcal{X}_{1}\otimes\ldots\otimes\mathcal{X}_{N}$ in the
standard basis and sends the outcome $(b_{1},\ldots,b_{N},x_{1},\ldots,x_{N})$
to the verifier.

    * –

If $c=1$, the prover instead measures
$\mathcal{W}\otimes\mathcal{X}_{1}\otimes\ldots\otimes\mathcal{X}_{N}$ in the
Hadamard basis, returning strings $d_{1},\ldots d_{N}$.

  * •

$\mathsf{MP}.\mathsf{Test}$: Given $(b_{1},\ldots,b_{N},x_{1},\ldots,x_{N})$,
the verifier computes (for every $i$)
$\mathsf{Check}(\mathsf{pk}_{i},b_{i},x_{i},y_{i})$ and rejects if any of
these checks do not pass.

  * •

$\mathsf{MP}.\mathsf{Out}$: Given $d_{1},\ldots d_{N}$, the verifier outputs
$N$ bits as follows. For each $i\in[N]$:

    * –

If $h_{i}=0$, the verifier ignores $d_{i}$, computes
$(b_{i},x_{i})=\mathsf{Invert}(\mathsf{injective},\mathsf{sk}_{i},y_{i})$, and
outputs $b_{i}$.

    * –

If $h_{i}=1$, the verifier computes the two inverses
$\\{(0,x_{0,i}),(1,x_{1,i})\\}\leftarrow\mathsf{Invert}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},\mathsf{sk}_{i},y_{i})$.
For each $i$, the verifier checks whether
$d_{i}\in\mathsf{Good}_{x_{0,i},x_{1,i}}$ (corresponding to a valid equation
in the $i$th slot), and if so, the verifier outputs
$d_{i}\cdot(1,x_{0,i}\oplus x_{1,i})$. If
$d_{i}\not\in\mathsf{Good}_{x_{0,i},x_{1,i}}$, the verifier samples a
uniformly random bit and outputs it.

Completeness of this protocol follows immediately from [Mah18] and the
correctness property of $\mathsf{Gen}$. Specifically, the correctness property
of $\mathsf{Gen}$ implies that each $(\mathsf{pk}_{i},\mathsf{sk}_{i})$ in our
protocol is in the range of $\mathsf{TCF}.\mathsf{Gen}(1^{\lambda},C(i))$, in
which case (as shown in [Mah18]) the verifier’s output distribution is
statistically close to $h=(C(0),\ldots,C(N))$-measurement outcome on
$\ket{\psi}$.

##  6 Soundness of Mahadev’s Protocol

In this section, we prove that the measurement protocol from Section 5 a
computationally sound (Definition 4.5) commit-and-measure protocol. As a
consequence, we obtain a new, self-contained proof of soundness of the [Mah18]
protocol. Later (Section 7.1), we will instead instantiate our protocol with a
_succinct_ key generation algorithm to obtain a verifier-succinct measurement
protocol.

Our soundness proof is based in part on both [Mah18] itself as well as a proof
strategy suggested in [Vid20].

##### Notation.

Throughout this section, we will fix the verifier’s choice of basis
$h\in\\{0,1\\}^{N}$. We write $R\coloneqq\\{i\in[N]:h_{i}=1\\}$ and
$S\coloneqq\\{i\in[N]:h_{i}=0\\}$, where $R\subset[N]$ denotes the set of
indices that the verifier wants to measure in the Hadamard basis, and
$S\subset[N]$ denotes the set of indices the verifier wants to measure in the
standard basis.

Finally, we will decompose the state space of the prover as
$\mathcal{Z}\otimes\mathcal{I}$, where:

  * •

$\mathcal{Z}=\mathcal{Z}_{1}\otimes\cdots\otimes\mathcal{Z}_{N}$. $1\leq i\leq
N$, $\mathcal{Z}_{i}$ is an $(\ell(\lambda)+1)$-qubit register that contains
the classical opening string $z_{i}$. We will sometimes write $\mathcal{Z}$ as
shorthand for $\mathcal{Z}_{1}\otimes\ldots\otimes\mathcal{Z}_{N}$.

  * •

Each $\mathcal{Z}_{i}$ can be written as
$\mathcal{Z}_{i}=\mathcal{B}_{i}\otimes\mathcal{X}_{i}$, where
$\mathcal{B}_{i}$ is a one-bit register and $\mathcal{X}_{i}$ is an
$\ell(\lambda)$-bit register.

  * •

$\mathcal{I}$ denotes any additional registers the prover uses.

###  6.1 The Verifier’s Output Distribution

Our goal is to characterize the $N$-bit distribution $D_{P^{*},\mathrm{Out}}$
corresponding to the verifier’s output in the measurement protocol when
interacting with a malicious prover $P^{*}$ using $h\in\\{0,1\\}^{N}$ as its
choice of bases. In particular, we want to prove that if $P^{*}$ succeeds in
passing the test round with probability $1-\mathsf{negl}(\lambda)$, then
$D_{P^{*},\mathrm{Out}}$ is computationally indistinguishable from
$D_{P^{*},\mathrm{Ext}}$, a distribution obtained from (1) running an
efficient extractor $\mathsf{Ext}^{P^{*}}$ to obtain an $N$-qubit quantum
state $\bm{\tau}$, and (2) measuring $\bm{\tau}$ in the verifier’s specified
bases.

The distribution $D_{P^{*},\mathrm{Out}}$ produces a sample according to the
following steps:

  1. 1.

Sample keys
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{MP}.\mathsf{Gen}(1^{\lambda},N,C)$
(where $C$ specifies the choice of bases $R,S$).

  2. 2.

Run the malicious prover on $\mathsf{PK}$ to obtain a classical commitment
string $y$. Let $\ket{\psi}\in\mathcal{Z}\otimes\mathcal{I}$ denote the
prover’s residual state.

  3. 3.

For each $i\in S$, compute
$(b_{i},x_{i})\leftarrow\mathsf{Invert}(\mathsf{injective},\mathsf{sk}_{i},y_{i})$.
Let $v\in\\{0,1\\}^{S}$ be the vector whose $i$th entry is $b_{i}$.

  4. 4.

Next, apply the prover’s attack unitary $U$ on
$\mathcal{Z}\otimes\mathcal{I}$, and then measure $\mathcal{Z}$ in the
Hadamard basis to obtain a response $z=(d_{1},\dots,d_{N})$.

  5. 5.

For each $i\in R$, compute
$(0,x_{0,i}),(1,x_{1,i})\leftarrow\mathsf{Invert}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},\mathsf{sk}_{i},y_{i})$.
If $d_{i}\in\mathsf{Good}_{x_{0,i},x_{1,i}}$, set
$u_{i}=d_{i}\cdot(1,x_{0,i}\oplus x_{1,i})$. Otherwise, set $u_{i}$ to be a
uniformly random bit. This results in a string $u\in\\{0,1\\}^{R}$

  6. 6.

Output $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

Our first step is to show that $D_{P^{*},\mathsf{Out}}$ is computationally
indistinguishable from a distribution
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ that does _not_
require running the $\mathsf{Invert}$ algorithm for any key pair
$(\mathsf{pk}_{i},\mathsf{sk}_{i})$ in injective mode. Instead, this second
distribution can be produced by directly measuring the register
$\mathcal{B}_{i}$ (i.e., the first bit of $\mathcal{Z}_{i}$) of the prover’s
state $\ket{\psi}$). Since $\\{\mathsf{sk}_{i}\\}_{i\in S}$ will no longer be
required at this point, we are also able to switch all key pairs
$(\mathsf{pk}_{i},\mathsf{sk}_{i})$ to be in two-to-one mode by invoking key
indistinguishability.

Formally, $D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ produces
outcomes as follows (differences from $D_{P^{*},\mathrm{Out}}$ highlighted in
red):

  1. 1.

Sample keys
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{MP}.\mathsf{Gen}(1^{\lambda},N,\mathbf{1})$
(where $\mathbf{1}$ denotes the constant $1$ function, corresponding to two-
to-one mode)

  2. 2.

Run the malicious prover on $\mathsf{PK}$ to obtain a classical commitment
string $y$. Let $\ket{\psi}\in\mathcal{Z}\otimes\mathcal{I}$ denote the
prover’s residual state.

  3. 3.

For each $i\in S$, measure $\mathcal{B}_{i}$ to obtain a bit $v_{i}$; the
result of this step is a string $v\in\\{0,1\\}^{S}$.

  4. 4.

Next, apply the prover’s attack unitary $U$ on
$\mathcal{Z}\otimes\mathcal{I}$, and then measure $\mathcal{Z}$ in the
Hadamard basis to obtain a response $z=(d_{1},\dots,d_{N})$.

  5. 5.

For each $i\in R$, compute
$(0,x_{0,i}),(1,x_{1,i})\leftarrow\mathsf{Invert}(\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1},\mathsf{sk}_{i},y_{i})$.
If $d_{i}\in\mathsf{Good}_{x_{0,i},x_{1,i}}$, set
$u_{i}=d_{i}\cdot(1,x_{0,i}\oplus x_{1,i})$. Otherwise, set $u_{i}$ to be a
uniformly random bit. This results in a string $u\in\\{0,1\\}^{R}$

  6. 6.

Output $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

######  Lemma 6.1.

$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ is computationally
indistinguishable from $D_{P^{*},\mathrm{Out}}$.

We prove Lemma 6.1 by first switching the keys sampled in
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ to match the
verifier’s basis choice $h$. That is, we define the distribution $D_{P^{*},h}$
to be the same distribution as
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$, except that the
keys $(\mathsf{pk}_{i},\mathsf{sk}_{i})$ are sampled in mode $h_{i}$, i.e.,
Step 1 is replaced with:

  1. 1.

Sample keys
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{MP}.\mathsf{Gen}(1^{\lambda},N,C)$
(where $C(i)=h_{i}$ for all $i$).

This is well-defined because the $i$th bit of the output is still obtained by
measuring $\mathcal{B}_{i}$, which can be done regardless of how
$(\mathsf{pk}_{i},\mathsf{sk}_{i})$ is sampled.

######  Claim 6.2.

For every basis choice $h$, $D_{P^{*},h}$ is computationally indistinguishable
from $D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$.

###### Proof.

This follows by invoking the following key indistinguishability property of
$\mathsf{Gen}$:

$\left\\{(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{Gen}(1^{\lambda},1):(\mathsf{PK},\\{\mathsf{sk}_{i}\\}_{i\not\in
S})\right\\}\approx_{c}\left\\{(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{Gen}(1^{\lambda},C):(\mathsf{PK},\\{\mathsf{sk}_{i}\\}_{i\not\in
S})\right\\}.$

Since the distributions are sampled without use of $\mathsf{sk}_{i}$ for all
$i\in S$, 6.2 follows from this indistinguishability. ∎

To conclude that
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}\approx_{c}D_{P^{*},\mathrm{Out}}$,
we note:

######  Claim 6.3.

If $D_{P^{*},\mathsf{Out}}$ is instantiated with basis choice $h$, then
$D_{P^{*},\mathsf{Out}}$ is statistically indistinguishable from
$D_{P^{*},h}$.

###### Proof.

6.3 follows from the injectivity of $f_{\mathsf{pk}_{i}}$ for each $i\in S$;
by the correctness of $\mathsf{Gen}$, we have that each $\mathsf{pk}_{i}$ (for
$i\in S$) is in the support of
$\mathsf{TCF}.\mathsf{Gen}(1^{\lambda},\mathsf{injective})$. Therefore, since
$\ket{\psi}$ is guaranteed to pass the test round with probability
$1-\mathsf{negl}(\lambda)$, we have that with probability
$1-\mathsf{negl}(\lambda)$, measuring $\mathcal{B}_{i}$ gives the same result
as computing the first bit of $\mathsf{Invert}(\mathsf{sk}_{j},y_{j})$ (which
is the verifier’s output). ∎

###  6.2 The Protocol Observables

##### Defining the Protocol Observables.

In $D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$, the entire
$N$-bit output $(u,v)$ is the result of performing measurements on
$\ket{\psi}$, the prover’s residual state after it sends its commitment $y$.

We now define a collection of binary observables
$\\{X_{i},Z_{i}\\}_{i\in[N]}$, parameterized by $(\mathsf{PK},\mathsf{SK},y)$
and the malicious prover’s attack unitary $U$, such that the following process
is equivalent to sampling from
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$:

  1. 1.

Sample keys
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{MP}.\mathsf{Gen}(1^{\lambda},N,\mathbf{1})$.

  2. 2.

Run the malicious prover on $\mathsf{PK}$ to obtain a classical commitment
string $y$. Let $\ket{\psi}$ denote the prover’s residual state.

  3. 3.

For each $i\in S$, measure $\ket{\psi}$ with the observable $Z_{i}$ to obtain
a bit $v_{i}$.

  4. 4.

Next, for each $i\in R$, measure the observable $X_{i}$ to obtain a bit
$u_{i}$.

  5. 5.

Output $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

The definition of the $Z_{i}$ observable is straightforward: since each
$v_{i}$ is obtained by measuring $\mathcal{B}_{i}$ in the standard basis,
$Z_{i}$ is simply the Pauli-$Z$ observable
$Z_{i}\coloneqq(\sigma_{Z})_{\mathcal{B}_{i}}$.

Defining the $X_{i}$ observable requires more care. In
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$, the string
$u\in\\{0,1\\}^{R}$ is obtained by applying the following steps (after
$v\in\\{0,1\\}^{S}$ is measured)

  1. 1.

Apply the prover’s attack unitary $U$ on $\mathcal{Z}\otimes\mathcal{I}$.

  2. 2.

For each $i\in R$:

    1. (a)

Apply $H^{\otimes\ell+1}$ to the register $\mathcal{Z}_{i}$ containing the
prover’s response in the $i$th slot.

    2. (b)

Measure $\mathcal{Z}_{i}$ to obtain $d_{i}$. If
$d_{i}\in\mathsf{Good}(x_{0,i},x_{1,i})$, set
$u_{i}=d_{i}\cdot(1,x_{0,i}\oplus x_{1,i})$. If
$d_{i}\not\in\mathsf{Good}(x_{0,i},x_{1,i})$, set $u_{i}$ to be a uniformly
random bit.

In order to output a uniformly random bit, we will prepare fresh one-qubit
ancilla registers $\mathcal{U}_{1},\dots,\mathcal{U}_{N}$, so that in the
event that the prover returns an invalid $d_{i}$ in slot $i$, the verifier can
generate a random bit by measuring $\mathcal{U}_{i}$ (initialized to
$\ket{0}$) in the Hadamard basis. Note that the
$\mathcal{U}=\mathcal{U}_{1},\dots,\mathcal{U}_{N}$ register is not part of
the malicious prover’s state.

We therefore redefine
$\ket{\psi}\coloneqq\ket{\psi}_{\mathcal{Z},\mathcal{I}}\ket{0}_{\mathcal{U}}$
to denote the global state on
$\mathcal{Z}\otimes\mathcal{I}\otimes\mathcal{U}$ including the ancilla
$\mathcal{U}$ registers initialized to $\ket{0}_{\mathcal{U}}$.

Finally, the $X_{i}$ observable is defined as

$X_{i}=(U\otimes\mathsf{Id}_{\mathcal{U}})^{\dagger}(H^{\otimes\ell+1}_{\mathcal{Z}_{i}}\otimes\mathsf{Id}\otimes
H_{\mathcal{U}_{i}})X^{\prime}_{i}(H^{\otimes\ell+1}_{\mathcal{Z}_{i}}\otimes\mathsf{Id}\otimes
H_{\mathcal{U}_{i}})(U\otimes\mathsf{Id}_{\mathcal{U}}).$

where

$\displaystyle X^{\prime}_{i}=$
$\displaystyle\sum_{d\in\mathsf{Good}(x_{0,i},x_{1,i})}(-1)^{d\cdot(1,x_{0,i}\oplus
x_{1,i})}\outerproduct{d}{d}_{\mathcal{Z}_{i}}\otimes\mathsf{Id}_{\mathcal{I},\\{\mathcal{Z}_{j}\\}_{j\neq
i},\mathcal{U}}$
$\displaystyle+\sum_{d\not\in\mathsf{Good}(x_{0,i},x_{1,i}),u\in\\{0,1\\}}(-1)^{u}\outerproduct{d,u}{d,u}_{\mathcal{Z}_{i},\mathcal{U}_{i}}\otimes\mathsf{Id}_{\mathcal{I},\\{\mathcal{Z}_{j}\\}_{j\neq
i},\\{\mathcal{U}_{j}\\}_{j\neq i}}.$

Note that the $X_{i}$ observables are defined so that each pair of
$X_{i},X_{j}$ commute. Moreover, one can verify that measuring $X_{i}$ for
each $i\in R$ exactly corresponds to measuring $u\in\\{0,1\\}^{R}$ as
described above.

The description of $X_{i}$ depends on $(y_{i},\mathsf{sk}_{i})$ because of the
appearance of $x_{i,0},x_{i,1}$ in $X_{i}^{\prime}$. Moreover, note that each
$X_{i}$ is efficiently computable given $\mathsf{sk}_{i}$.

For convenience, we define a procedure
$\\{X_{i},Z_{i}\\}_{i},\ket{\psi}_{\mathcal{Z},\mathcal{I},\mathcal{U}}\leftarrow\mathsf{Samp}$
that works as follows:

  * •

Sample keys
$(\mathsf{PK},\mathsf{SK})\leftarrow\mathsf{MP}.\mathsf{Gen}(1^{\lambda},N,\mathbf{1})$.

  * •

Run the malicious prover on $\mathsf{PK}$ to obtain a classical commitment
string $y$. Let $\ket{\psi^{\prime}}$ denote the prover’s residual state on
$\mathcal{Z}\otimes\mathcal{I}$.

  * •

Output the observables $\\{X_{i},Z_{i}\\}$ parameterized by
$(\mathsf{PK},\mathsf{SK},y)$ and malicious prover’s unitary $U$, along with
the state
$\ket{\psi}\coloneqq\ket{\psi^{\prime}}\otimes\ket{0}_{\mathcal{U}}$.

For the remainder of this section, we will write
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ as a two-step
sampling process:

  1. 1.

Run
$\\{X_{i},Z_{i}\\}_{i},\ket{\psi}_{\mathcal{Z},\mathcal{I},\mathcal{U}}\leftarrow\mathsf{Samp}$.

  2. 2.

Starting with $\ket{\psi}$, measure each $Z_{i}$ for $i\in S$ to obtain
$v\in\\{0,1\\}^{S}$. Then measure each $X_{i}$ for $i\in R$ to obtain
$u\in\\{0,1\\}^{R}$. Output $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

###  6.3 The Extracted State

Recall that our definition of measurement protocol soundness (Definition 4.5)
requires us to give an extractor that:

  1. 1.

Generates keys $(\mathsf{PK},\mathsf{SK})$ according to an algorithm
$\mathsf{SimGen}(1^{\lambda})$ (independently of the verifier’s basis choice
$h$).

  2. 2.

Runs the malicious prover $P^{*}$ on $\mathsf{PK}$ to obtain $y$; as usual,
$\ket{\psi}\in\mathcal{Z}\otimes\mathcal{I}\otimes\mathcal{U}$ denotes the
residual prover state with $\mathcal{U}$ initialized to
$\ket{0}_{\mathcal{U}}$.202020To match the syntax of our definition in
Definition 4.5, the register $\mathcal{U}$ should be viewed as an internal
register initialized by the extractor.

  3. 3.

Generates an extracted state
$\bm{\tau}\leftarrow\mathsf{Ext}^{U,\ket{\psi}}(\mathsf{PK},\mathsf{SK},y)$
(the superscript denotes black-box access to a unitary $U$ and state
$\ket{\psi}$, see Section 3.2).

We define $\mathsf{SimGen}(1^{\lambda})$ to be
$\mathsf{MP}.\mathsf{Gen}(1^{\lambda},N,\mathbf{1})$, which exactly
corresponds to how keys are sampled in
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$.

To establish soundness, it remains to (1) describe how to generate the
extracted state $\bm{\tau}$ given $(\mathsf{PK},\mathsf{SK},y),U$, and (2)
prove that the distribution that arises from measuring $\bm{\tau}$ with the
Pauli-$X$ and Pauli-$Z$ observables in the verifier’s chosen bases $h$ is
computationally indistinguishable from
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$.

We handle (1) in Section 6.3.1. We then describe the distribution
$D_{P^{*},\mathrm{Ext}}$ that arises from measuring our extracted state in
Section 6.3.2 and prove that indistinguishability from
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ in Section 6.4.

####  6.3.1 A Teleportation-Inspired Extraction Procedure

Fix a choice of $\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}$. For
ease of notation, write
$\mathcal{H}=\mathcal{Z}\otimes\mathcal{I}\otimes\mathcal{U}$ so that
$\ket{\psi}\in\mathcal{H}$. We would like an efficient extraction procedure
that takes as input $\ket{\psi}\in\mathcal{H}$ and generates an $N$-qubit
state $\bm{\tau}$ such that, roughly speaking, measuring $\ket{\psi}$ with
$X/Z$ and measuring $\bm{\tau}$ with $\sigma_{X}/\sigma_{Z}$ produce
indistinguishable outcomes.

##### Intuition for the Extractor.

Before we describe our extractor, we first provide some underlying intuition.
For an arbitrary $N$-qubit Hilbert space, let $\sigma_{x,i}$/$\sigma_{z,i}$
denote the Pauli $\sigma_{x}$/$\sigma_{z}$ observable acting on the $i$th
qubit. For each $r,s\in\\{0,1\\}^{N}$, define the $N$-qubit Pauli “parity”
observables

$\sigma_{x}(r)\coloneqq\prod_{i:r_{i}=1}\sigma_{x,i}\;,\;\sigma_{z}(s)\coloneqq\prod_{i:s_{i}=1}\sigma_{z,i}.$

Suppose for a moment that $\ket{\psi}\in\mathcal{H}$ is _already_ an $N$-qubit
state (i.e., $\mathcal{H}$ is an $N$-qubit Hilbert space) and moreover, that
each $X_{i}$/$Z_{i}$ observable is simply the corresponding Pauli observable
$\sigma_{x,i}$/$\sigma_{z,i}$. While these assumptions technically trivialize
the task (the state already has the form we want from the extracted state), it
will be instructive to write down an extractor that “teleports” this state
into another $N$-qubit external register.

We can do this by initializing two $N$-qubit registers
$\mathcal{A}_{1}\otimes\mathcal{A}_{2}$ to $\ket{\phi^{+}}^{\otimes N}$ where
$\ket{\phi^{+}}$ is the EPR state $(\ket{00}+\ket{11})/\sqrt{2}$ (the $i$th
EPR pair lives on the $i$th qubit of $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$).
Now consider the following steps, which are inspired by the ($N$-qubit)
quantum teleportation protocol

  1. 1.

Initialize a $2N$-qubit ancilla $\mathcal{W}$ to $\ket{0^{2N}}$, and apply
$H^{\otimes 2N}$ to obtain the uniform superposition.

  2. 2.

Apply a “controlled-Pauli” unitary, which does the following for all
$r,s\in\\{0,1\\}^{N}$ and all
$\ket{\phi}\in\mathcal{H}\otimes\mathcal{A}_{1}$:

$\ket{r,s}_{\mathcal{W}}\ket{\phi}_{\mathcal{H},\mathcal{A}_{1}}\rightarrow\ket{r,s}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)_{\mathcal{H}}\otimes\sigma_{x}(r)\sigma_{z}(s)_{\mathcal{A}_{1}})\ket{\phi}_{\mathcal{H},\mathcal{A}_{1}}$

  3. 3.

Apply the unitary that XORs onto $\mathcal{W}$ the outcome of performing $N$
Bell-basis measurements212121The Bell basis consists of the $4$ states
$(\sigma_{x}^{a}\sigma_{z}^{b}\otimes\mathsf{Id})\ket{\phi^{+}}$ for
$a,b\in\\{0,1\\}$ on $2$ qubits. on $\mathcal{A}_{1}\otimes\mathcal{A}_{2}$
onto $\mathcal{W}$, i.e., for all $u,v,r,s\in\\{0,1\\}^{N}$:

$\ket{u,v}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})_{\mathcal{A}_{1},\mathcal{A}_{2}}\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}}\rightarrow\ket{u\oplus r,v\oplus
s}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})_{\mathcal{A}_{1},\mathcal{A}_{2}}\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}}.$

Finally, discard $\mathcal{W}$.

One can show that the resulting state is

$\frac{1}{2^{N}}\sum_{r,s\in\\{0,1\\}^{N}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})\ket{\psi}_{\mathcal{H}}\ket{\phi^{+}}_{\mathcal{A}_{1},\mathcal{A}_{2}}=\ket{\phi^{+}}_{\mathcal{H},\mathcal{A}_{1}}\ket{\psi}_{\mathcal{A}_{2}},$
(2)

where $\ket{\psi}$ is now “teleported” into the $\mathcal{A}_{2}$ register.

To generalize this idea to the setting where $\ket{\psi}\in\mathcal{H}$ is an
arbitrary quantum state and $\\{X_{i},Z_{i}\\}_{i}$ are an arbitrary
collection of $2N$ observables, _we simply replace each $\sigma_{x}(r)$ and
$\sigma_{z}(s)$ acting on $\mathcal{H}$ above with the corresponding parity
observables for $\\{X_{i},Z_{i}\\}$_. That is for each $r,s\in\\{0,1\\}^{N}$,
define

$Z(s)=\prod_{i=1}^{N}Z_{i}^{s_{i}}\hskip 7.22743pt\mbox{and}\hskip
7.22743ptX(r)=\prod_{i=1}^{N}X_{i}^{r_{i}}.$

The rough intuition is that as long as the $\\{X_{i}\\}$ and $\\{Z_{i}\\}$
observables “behave like” Pauli observables with respect to $\ket{\psi}$, the
resulting procedure will “teleport” $\ket{\psi}$ into the $N$-qubit register
$\mathcal{A}_{2}$.

##### The Full Extractor.

In more detail, we have the state
$\ket{\psi}_{\mathcal{H}}=\ket{\psi}_{\mathcal{Z},\mathcal{I},\mathcal{U}}$,
and we initialize two $N$-qubit registers
$\mathcal{A}_{1}\otimes\mathcal{A}_{2}$ to $\ket{\phi}^{\otimes N}$. We run
the following steps (the changes from the above procedure are highlighted in
red):

  1. 1.

Initialize a $2N$-qubit ancilla $\mathcal{W}$ to $\ket{0^{2N}}$, and apply
$H^{\otimes{2N}}$.

  2. 2.

Apply a unitary that does the following for all $r,s\in\\{0,1\\}^{N}$:

$\ket{r,s}_{\mathcal{W}}\ket{\phi}_{\mathcal{H},\mathcal{A}_{1}}\rightarrow\ket{r,s}_{\mathcal{W}}({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}X(r)Z(s)_{\mathcal{H}}}\otimes\sigma_{x}(r)\sigma_{z}(s)_{\mathcal{A}_{1}})\ket{\phi}_{\mathcal{H},\mathcal{A}_{1}}$

  3. 3.

Apply the unitary that XORs onto $\mathcal{W}$ the outcome of performing $N$
Bell-basis measurements on $\mathcal{A}_{1}\otimes\mathcal{A}_{2}$ onto
$\mathcal{W}$, i.e., for all $u,v,r,s\in\\{0,1\\}^{N}$:

$\ket{u,v}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}}\rightarrow\ket{u\oplus r,v\oplus
s}_{\mathcal{W}}(\sigma_{x}(r)\sigma_{z}(s)\otimes\mathsf{Id})\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}}.$

Finally, discard $\mathcal{W}$.

All of these steps can be efficiently implemented given black-box access to
$\\{X_{i},Z_{i}\\}_{i}$. The resulting state is

$\displaystyle\frac{1}{2^{N}}\sum_{r,s\in\\{0,1\\}^{N}}X(r)Z(s)\ket{\psi}_{\mathcal{H}}\otimes\sigma_{x}(r)\sigma_{z}(s)\ket{\phi^{+}}^{\otimes
N}_{\mathcal{A}_{1},\mathcal{A}_{2}},$

and we define the extracted state
$\bm{\tau}\coloneqq\mathsf{Ext}_{\\{X_{i}\\},\\{Z_{i}\\}}(\ket{\psi})$ to be
the residual state on $\mathcal{A}_{2}$ after tracing out $\mathcal{H}$ and
$\mathcal{A}_{1}$.222222The same extracted state is defined in Vidick’s
lecture notes [Vid20], although the notes do not give an explicit procedure
for generating it.

####  6.3.2 Measuring the Extracted State

We now consider the $N$-bit distribution of measurement outcomes that arise
from measuring the extracted state $\bm{\tau}$ using the Pauli observables
$\sigma_{x},\sigma_{z}$. In particular, we consider performing the
measurements according to the verifier’s basis choice, so that we measure
$\sigma_{z,i}$ for each $i\in S$ and $\sigma_{x,i}$ for each $i\in R$.

Formally, we define the distribution $D_{P^{*},\mathrm{Ext}}$ on
$\\{0,1\\}^{N}$ obtained by the following process:

  * •

Run $\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}$.

  * •

Let $\bm{\tau}=\mathsf{Ext}_{\\{X_{i}\\},\\{Z_{i}\\}}(\ket{\psi})$ be the
$N$-qubit extracted state.

  * •

Measure the Pauli-$Z$ observable $\sigma_{z,i}$ for all $i\in S$, obtaining
$v\in\\{0,1\\}^{S}$.

  * •

Measure the Pauli-$X$ observable $\sigma_{x,i}$ for all $i\in R$, obtaining
$u\in\\{0,1\\}^{R}$.

  * •

Output $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

It will be convenient to define the following projection operators. For each
$u\in\\{0,1\\}^{R}$ and $v\in\\{0,1\\}^{S}$ let

$\Pi^{\sigma_{x}}_{u}=\operatorname*{\mathbb{E}}_{u^{\prime}\in\\{0,1\\}^{R}}(-1)^{u\cdot
u^{\prime}}\sigma_{x}(u^{\prime})\qquad\text{and}\qquad\Pi^{\sigma_{z}}_{v}=\operatorname*{\mathbb{E}}_{v^{\prime}\in\\{0,1\\}^{S}}(-1)^{v\cdot
v^{\prime}}\sigma_{z}(v^{\prime})$ (3)

In words, $\Pi^{\sigma_{x}}_{u}$ is the projection that corresponds to
measuring $\sigma_{x,i}$ for each $i\in R$ and obtaining the string of
outcomes $u\in\\{0,1\\}^{R}$, and $\Pi^{\sigma_{z}}_{v}$ is the projection
that corresponds to measuring $\sigma_{z,i}$ for each $i\in S$ and obtaining
the string of outcomes $v\in\\{0,1\\}^{S}$.

Then the probability $D_{P^{*},\mathrm{Ext}}$ outputs any
$(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$ can be written as

$D_{P^{*},\mathrm{Ext}}(u,v)=\operatorname*{\mathbb{E}}_{\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}}[\Tr\big(\Pi^{\sigma_{x}}_{u}\Pi^{\sigma_{z}}_{v}\bm{\tau}\big{missing}):\bm{\tau}=\mathsf{Ext}_{\\{X_{i}\\},\\{Z_{i}\\}}(\ket{\psi})].$

We define a set of analogous projection operators for the $\\{X_{i}\\}$ and
$\\{Z_{i}\\}$ observables. For each $u\in\\{0,1\\}^{R}$ and
$v\in\\{0,1\\}^{S}$, let

$\Pi^{X}_{u}=\operatorname*{\mathbb{E}}_{u^{\prime}\in\\{0,1\\}^{R}}(-1)^{u\cdot
u^{\prime}}X(u^{\prime})\qquad\text{and}\qquad\Pi^{Z}_{v}=\operatorname*{\mathbb{E}}_{v^{\prime}\in\\{0,1\\}^{S}}(-1)^{v\cdot
v^{\prime}}Z(v^{\prime})$ (4)

In words, $\Pi^{X}_{u}$ is the projection that corresponds to measuring
$X_{i}$ for each $i\in R$ and obtaining the string of outcomes
$u\in\\{0,1\\}^{R}$, and $\Pi^{Z}_{v}$ is the projection that corresponds to
measuring $Z_{i}$ for each $i\in S$ and obtaining the string of outcomes
$v\in\\{0,1\\}^{S}$.

With these definitions in mind, we state a claim that allows us to
characterize the result of measuring the extracted state $\bm{\tau}$ with the
Pauli observables.

######  Claim 6.4.

Fix any choice of $\\{X_{i},Z_{i}\\}_{i\in[N]}$ and state $\ket{\psi}$, and
let $\bm{\tau}=\mathsf{Ext}_{\\{X_{i}\\},\\{Z_{i}\\}}(\ket{\psi})$. For all
$(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$ it holds that

$\Tr\big(\Pi^{\sigma_{x}}_{u}\Pi^{\sigma_{z}}_{v}\bm{\tau}\big{missing})=\operatorname*{\mathbb{E}}_{u^{\prime}\in\\{0,1\\}^{R}}\bra{\psi}\Pi^{Z}_{v}Z(u^{\prime})\Pi^{X}_{u^{\prime}\oplus
u}Z(u^{\prime})\Pi^{Z}_{v}\ket{\psi}.$ (5)

The proof of 6.4 is a straightforward (but slightly tedious) computation and
is deferred to Appendix B.

Importantly, 6.4 gives a clear understanding of how
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ and
$D_{P^{*},\mathrm{Ext}}$ relate to each other, since it allows us to view the
distribution $D_{P^{*},\mathrm{Ext}}$ (which arises from Pauli measurements on
the extracted state $\bm{\tau}$) as the result of performing certain protocol
observable measurements $\\{X_{i},Z_{i}\\}$ on $\ket{\psi}$.

Recall that the distribution
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ is the following
distribution:

  1. 1.

Run
$\\{X_{i},Z_{i}\\}_{i},\ket{\psi}_{\mathcal{Z},\mathcal{I},\mathcal{U}}\leftarrow\mathsf{Samp}$.

  2. 2.

Starting with $\ket{\psi}$, measure each $Z_{i}$ for $i\in S$ to obtain
$v\in\\{0,1\\}^{S}$. Then measure each $X_{i}$ for $i\in R$ to obtain
$u\in\\{0,1\\}^{R}$. Output $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

By 6.4, we can write $D_{P^{*},\mathrm{Ext}}$ as follows (differences from
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ are in red):

  1. 1.

Run $\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}$.

  2. 2.

Starting with $\ket{\psi}$ measure each $Z_{i}$ for $i\in S$ to obtain
$v\in\\{0,1\\}^{S}$. Then sample a uniformly random string
$u^{\prime}\leftarrow\\{0,1\\}^{R}$ and apply the unitary $Z(u^{\prime})$.
Finally, measure each $X_{i}$ for $i\in R$ and XOR the output with
$u^{\prime}$ to obtain $u\in\\{0,1\\}^{R}$. Output
$(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$.

With this key difference in mind, it remains to prove indistinguishability of
these two distributions.

###  6.4 Indistinguishability of Measurement Outcomes

In this subsection, we complete the proof that
$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ and
$D_{P^{*},\mathrm{Ext}}$ are computationally indistinguishable. We first write
out their probability mass functions:

  * •

$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}$ outputs
$(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$ with probability

$D_{P^{*},\mathsf{2}\text{-}\mathsf{to}\text{-}\mathsf{1}}(u,v)=\underset{\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}}{\mathbb{E}}\left[\bra{\psi}\Pi^{Z}_{v}\Pi^{X}_{u}\Pi^{Z}_{v}\ket{\psi}\right].$

  * •

$D_{P^{*},\mathrm{Ext}}$ outputs $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$
with probability

$D_{P^{*},\mathrm{Ext}}(u,v)=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}\\\
u^{\prime}\in\\{0,1\\}^{R}\end{subarray}}\left[\bra{\psi}\Pi^{Z}_{v}Z(u^{\prime})\Pi^{X}_{u^{\prime}\oplus
u}Z(u^{\prime})\Pi^{Z}_{v}\ket{\psi}\right].$

At this point, the reader may find it helpful to convince themselves that
probability mass functions above exactly correspond to the descriptions of
these distributions given at the end of Section 6.3. The equivalence between
these two representations will be a key component of the upcoming proofs.

For convenience, we will reorder the indices so that the indices in $R$ are
labeled $1,2,\dots,|R|$. Let $u_{\leq j}\in\\{0,1\\}^{R}$ be the vector equal
to $u$ on the first $j$ indices, and is $0$ on the remaining indices. For each
$j\in\\{0,1,\dots,|R|\\}$, define hybrid $\mathsf{Hyb}_{j}$ to be the
distribution that outputs $(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$ with
probability

$\mathsf{Hyb}_{j}(u,v)=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}\\\
u^{\prime}\in\\{0,1\\}^{R}\end{subarray}}\left[\bra{\psi}\Pi^{Z}_{v}Z(u^{\prime}_{\leq
j})\Pi^{X}_{u\oplus u^{\prime}_{\leq j}}Z(u^{\prime}_{\leq
j})\Pi^{Z}_{v}\ket{\psi}\right].$

Additionally, for each $j\in\\{1,\dots,|R|\\}$, and $b\in\\{0,1\\}$ define
hybrid $\mathsf{Hyb}_{j,b}$ to be the distribution that outputs
$(u,v)\in\\{0,1\\}^{R}\times\\{0,1\\}^{S}$ with probability

$\mathsf{Hyb}_{j,b}(u,v)=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\\{X_{i},Z_{i}\\},\ket{\psi}\leftarrow\mathsf{Samp}\\\
u^{\prime}\in\\{0,1\\}^{R}\end{subarray}}\left[\bra{\psi}\Pi^{Z}_{v}Z(u^{\prime}_{\leq
j-1})Z_{j}^{b}\Pi^{X}_{u\oplus u^{\prime}_{\leq j-1}\oplus b\cdot
e_{j}}Z_{j}^{b}Z(u^{\prime}_{\leq j-1})\Pi^{Z}_{v}\ket{\psi}\right],$

where $e_{j}\in\\{0,1\\}^{R}$ denotes the $j$th standard basis vector.

######  Claim 6.5.

For all $j\in\\{1,\dots,|R|\\}$, the distributions $\mathsf{Hyb}_{j,0}$ and
$\mathsf{Hyb}_{j,1}$ are computationally indistinguishable.

Observe that for $j\in\\{1,2,\dots,|R|\\}$,
$\mathsf{Hyb}_{j,0}=\mathsf{Hyb}_{j-1}$, and that $\mathsf{Hyb}_{j,0}$ is the