Essentially the same argument as in 20 yields the result. ∎

######  Claim 25.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,6)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta+1,0)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Essentially the same argument as in 19 yields the result. ∎

######  Claim 26.

For all $\ell\in[k+1]$, we have

  * •

${\mathsf{Exp}}_{{\mathcal{D}_{0}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{\mathcal{D}_{1}},{\ell}}$

  * •

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(0,4)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{\mathcal{D}_{j+1}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$

  * •

${\mathsf{Exp}}_{{\mathcal{D}_{j}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(0,3)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$

where $\nu(\lambda)=2^{-5\lambda}\cdot
2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

###### Proof.

It is easy to see that
$\mathcal{D}_{0}\approx^{c}_{\nu(\lambda)}\mathcal{D}_{0}^{(0,0)}$ and
$\mathcal{D}_{k+1}\approx^{c}_{\nu(\lambda)}\mathcal{D}_{k+1}^{(0,0)}$ by the
security of $i\mathcal{O}$. For the former, in particular, observe that the
obfuscated punctured master secret key programs have the same functionality
since while $K_{1}$ in $\mathcal{D}_{0}$ is punctured at
$id_{j^{*}}||f_{j^{*}}$, we have that $f_{j^{*}}(m_{0})\neq f_{j^{*}}(m_{1})$.

Rest follows by a simple calculation using the above results. ∎

######  Notation.

We will write $\mathcal{D}^{\prime}$ to denote $\mathcal{D}_{j^{*}}^{(0,3)}$
and $\mathcal{D}^{\prime\prime}$ to denote $\mathcal{D}_{j^{*}}^{(0,4)}$ where
$j^{*}$ is as output by $\mathcal{A}_{0}^{\prime}$.

######  Claim 27.

Let $\tau$ be the bipartite state output by $\mathcal{A}^{\prime}_{0}$ in
$\mathcal{G}$. Let $p^{\prime}_{x},p^{\prime}_{y}$ be the outcome of applying
$\mathsf{PI}_{x,\mathcal{D}^{\prime}}\otimes\mathsf{PI}_{y,\mathcal{D}^{\prime}}$
to $\tau$. Similarly, let $p^{\prime\prime}_{x},p^{\prime\prime}_{y}$ be the
outcome of applying
$\mathsf{PI}_{x,\mathcal{D}^{\prime\prime}}\otimes\mathsf{PI}_{y,\mathcal{D}^{\prime\prime}}$
to $\tau$. Then,

  * •

$\Pr[p^{\prime}_{x}>b_{x,j^{*}}-\frac{3\gamma}{32k}\wedge
p^{\prime}_{y}>b_{y,j^{*}}-\frac{3\gamma}{32k}]\geq 1-2^{-2\lambda}\cdot
2^{-4\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

  * •

$\Pr[b_{x,j^{*}}-p^{\prime\prime}_{x}>\frac{28\gamma}{32k}\wedge
b_{y,j^{*}}-p^{\prime\prime}_{y}>\frac{28\gamma}{32k}]>\frac{1}{q(\lambda)}$
for some polynomial $q(\cdot)$.

###### Proof.

Follows from the same argument as in 14. ∎

######  Claim 28.

There exist efficient $\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime}$ such
that
$(\mathcal{A}^{\prime}_{0},\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime})$
wins $\mathcal{G}$ with probability
$\frac{1}{2^{0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$

###### Proof.

Follows from the same argument as in 15. ∎

######  Claim 29.

There exists efficient
$\mathcal{A}^{\prime\prime}=(\mathcal{A}_{0}^{\prime\prime},\mathcal{A}_{1}^{\prime\prime},\mathcal{A}_{2}^{\prime\prime})$
such that

$\Pr[\mathsf{MoE-
Coll}(\lambda,L(\lambda),\mathcal{A}^{\prime\prime})=1]\geq{2^{-0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$

###### Proof.

It is straightforward to reduce $\mathcal{G}$ to the stronger version of
$\mathsf{MoE-Coll}$ shown secure in the proof of Theorem 19. See also 16. ∎

The above constitutes a contradiction by Theorem 19, therefore this completes
the security proof.

##  8 Acknowledgements

We thank Jiahui Liu for helpful discussions.

## References

  * [Aar09] Scott Aaronson.  Quantum copy-protection and quantum money.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 229–242, 2009.
  * [Aar16] Scott Aaronson.  The complexity of quantum states and transformations: From quantum money to black holes, 2016.
  * [AC12] Scott Aaronson and Paul Christiano.  Quantum money from hidden subspaces.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 41–60, New York, NY, USA, 2012. Association for Computing Machinery.
  * [AKL+22] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry.  On the feasibility of unclonable encryption, and more.  Cryptology ePrint Archive, Paper 2022/884, 2022.  https://eprint.iacr.org/2022/884.
  * [ALL+20] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang.  New approaches for quantum copy-protection, 2020.
  * [ALL+21] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang.  New approaches for quantum copy-protection.  In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 526–555, Cham, 2021. Springer International Publishing.
  * [ALP21] Prabhanjan Ananth and Rolando L. La Placa.  Secure software leasing.  In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, pages 501–530, Cham, 2021. Springer International Publishing.
  * [BGG+23] James Bartusek, Sanjam Garg, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts.  Obfuscation and outsourced computation with certified deletion.  Cryptology ePrint Archive, Paper 2023/265, 2023.  https://eprint.iacr.org/2023/265.
  * [BV18] Nir Bitansky and Vinod Vaikuntanathan.  Indistinguishability obfuscation from functional encryption.  J. ACM, 65(6), nov 2018.
  * [CGJS15] Nishanth Chandran, Vipul Goyal, Aayush Jain, and Amit Sahai.  Functional encryption: Decentralised and delegatable.  Cryptology ePrint Archive, Paper 2015/1017, 2015.  https://eprint.iacr.org/2015/1017.
  * [ÇGLZR23] Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro.  Unbounded leakage-resilience and leakage-detection in a quantum world.  Cryptology ePrint Archive, Paper 2023/410, 2023.  https://eprint.iacr.org/2023/410.
  * [CHSH69] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt.  Proposed experiment to test local hidden-variable theories.  Physical review letters, 23(15):880, 1969.
  * [CLLZ21] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry.  Hidden cosets and applications to unclonable cryptography.  In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 556–584, Cham, 2021. Springer International Publishing.
  * [CMP20] Andrea Coladangelo, Christian Majenz, and Alexander Poremba.  Quantum copy-protection of compute-and-compare programs in the quantum random oracle model.  Cryptology ePrint Archive, Paper 2020/1194, 2020.  https://eprint.iacr.org/2020/1194.
  * [CV22] Eric Culf and Thomas Vidick.  A monogamy-of-entanglement game for subspace coset states.  Quantum, 6:791, 2022.
  * [CZDC19] Yu Chen, Jiang Zhang, Yi Deng, and Jinyong Chang.  Kdm security for identity-based encryption: Constructions and separations.  Information Sciences, 486:450–473, 2019.
  * [FGH+12] Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor.  Quantum money from knots.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 276–289, New York, NY, USA, 2012. Association for Computing Machinery.
  * [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to construct random functions.  J. ACM, 33(4):792–807, aug 1986.
  * [GPSW06] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters.  Attribute-based encryption for fine-grained access control of encrypted data.  In Proceedings of the 13th ACM conference on Computer and communications security, pages 89–98, 2006.
  * [GZ20] Marios Georgiou and Mark Zhandry.  Unclonable decryption keys.  Cryptology ePrint Archive, Paper 2020/877, 2020.  https://eprint.iacr.org/2020/877.
  * [KN22] Fuyuki Kitagawa and Ryo Nishimaki.  Functional encryption with secure key leasing.  In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, pages 569–598, Cham, 2022. Springer Nature Switzerland.
  * [KNT22] Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka.  Obfustopia built on secret-key functional encryption.  volume 35, page 19, Jun 2022.
  * [KNY21] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Secure software leasing from standard assumptions.  In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography, pages 31–61, Cham, 2021. Springer International Publishing.
  * [Kre21] William Kretschmer.  Quantum pseudorandomness and classical complexity.  In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [LAF+09] Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, and Peter Shor.  Breaking and making quantum money: toward a new quantum cryptographic protocol, 2009.
  * [LLQZ22] Jiahui Liu, Qipeng Liu, Luowen Qian, and Mark Zhandry.  Collusion resistant copy-protection for watermarkable functionalities.  Cryptology ePrint Archive, Paper 2022/1429, 2022.  https://eprint.iacr.org/2022/1429.
  * [MW04] C. Marriott and J. Watrous.  Quantum arthur-merlin games.  In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 275–285, 2004.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * [Sha85] Adi Shamir.  Identity-based cryptosystems and signature schemes.  In George Robert Blakley and David Chaum, editors, Advances in Cryptology, pages 47–53, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg.
  * [SW05] Amit Sahai and Brent Waters.  Fuzzy identity-based encryption.  In Ronald Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, pages 457–473, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [SW14] Amit Sahai and Brent Waters.  How to use indistinguishability obfuscation: Deniable encryption, and more.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 475–484, New York, NY, USA, 2014. Association for Computing Machinery.
  * [Wat18] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  SIGACT News, 15(1):78–88, jan 1983.
  * [Wil15] Mark Wilde.  Quantum information theory lecture notes, lecture 16, 2015.
  * [WZ17] Daniel Wichs and Giorgos Zirdelis.  Obfuscating compute-and-compare programs under lwe.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 600–611, 2017.
  * [YAL+19] Rupeng Yang, Man Ho Au, Junzuo Lai, Qiuliang Xu, and Zuoxia Yu.  Collusion resistant watermarking schemes for cryptographic functionalities.  In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, pages 371–398, Cham, 2019. Springer International Publishing.
  * [Zha12a] Mark Zhandry.  How to construct quantum random functions.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 679–687, 2012.
  * [Zha12b] Mark Zhandry.  Secure identity-based encryption in the quantum random oracle model.  In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012, pages 758–775, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [Zha19] Mark Zhandry.  Quantum lightning never strikes the same state twice.  In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 408–438, Cham, 2019. Springer International Publishing.
  * [Zha20] Mark Zhandry.  Schrödinger’s pirate: How to trace a quantum decoder.  In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography, pages 61–91, Cham, 2020. Springer International Publishing.

##  Appendix A Proofs from Section 3

###  A.1 Proof of Theorem 5

We can write $\rho$ as
$\rho=\sum_{j,k}\alpha_{j,k}\outerproduct{j}{j}\otimes\outerproduct{k}{k}$.
Then, $(M_{i}\otimes I)\rho(M_{i}^{\dagger}\otimes
I)=\sum_{j,k}\alpha_{j,k}(M_{i}\outerproduct{j}{j}M_{i}^{\dagger})\otimes\outerproduct{k}{k}$
and therefore $(\Tr\otimes I)(M_{i}\otimes I)\rho(M_{i}^{\dagger}\otimes
I)=\sum_{j,k}\alpha_{j,k}\bra{j}M_{i}^{\dagger}M_{i}\ket{j}\otimes\outerproduct{k}{k}$.
Note that this summation only depends on the POVM element
$M_{i}^{\dagger}M_{i}$. The same argument applies to $\Lambda^{\prime}$.
Hence, the result follows by POVM equivalence of $\Lambda,\Lambda^{\prime}$.

###  A.2 Proof of Theorem 6

First, we will prove the case where $\varepsilon=0$. We will prove it only for
pure states, but the general case follows from purification. Let $\ket{\psi}$
be any state of appropriate dimension. We can write
$\ket{\psi}=\sum_{j\in\mathcal{J},k\in\mathcal{K}}\alpha_{j,k}\ket{{v_{j}}}\otimes\ket{w_{k}}$
where
$\\{\ket{v_{j}}\\}_{j\in\mathcal{J}},\\{\ket{w_{k}}\\}_{k\in\mathcal{K}}$ are
orthonormal eigenbases of $\Pi_{1}$ and $\Pi^{\prime}_{1}$ respectively. We
have $\Pi_{1}=\sum_{j\in\mathcal{J}^{\prime}}\ket{{v_{j}}}$ and
$\Pi^{\prime}_{1}=\sum_{k\in\mathcal{K}^{\prime}}\ket{{w_{k}}}$ for some
subsets
$\mathcal{J}^{\prime}\subseteq\mathcal{J},\mathcal{K}^{\prime}\subseteq\mathcal{K}$.
Since $\Tr{\Pi_{1}\otimes\Pi^{\prime}_{1}\rho}$, we get $\alpha_{j,k}=0$ if
$(j,k)\not\in\mathcal{J}^{\prime}\times\mathcal{K}^{\prime}$.

We can write the post-measurement state conditioned on outcome $i$ as
$\ket{\phi}/\norm{\ket{\phi}}$ where
$\ket{\phi}=\sum_{j\in\mathcal{J}^{\prime},k\in\mathcal{K}^{\prime}}\alpha_{j,k}(M_{i}\ket{{v_{j}}})\otimes\ket{w_{k}}$.
When we apply $I\otimes\Pi^{\prime}_{1}$ to $\ket{\phi}$, we get $\ket{\phi}$
again. Hence,
$\Tr{\Pi^{\prime}_{1}\frac{\outerproduct{\phi}{\phi}}{\norm{\ket{\phi}}^{2}}}=1$,
completing the first part of the proof.

Now, we move onto any $\varepsilon\in(0,1]$. Let $\rho^{\prime}$ denote the
post-measurement state obtained after applying
$\Lambda\otimes\Lambda^{\prime}$ to $\rho$ obtaining the outcome $(1,1)$. Note
that $\rho^{\prime}$ satisfies the claim with $\varepsilon=0$. Then, by Lemma
2, $\norm{\rho-\rho^{\prime}}_{Tr}\leq\sqrt{\varepsilon}$. Hence, applying the
measurement $M$ on the first register and conditioning the outcome $i$, the
post-measurement states of the second registers will have trace distance at
most $\sqrt{\varepsilon}/p_{i}$. Hence, invoking the sub-claim for
$\rho^{\prime}$ with $\varepsilon=0$ and using the trace distance bound, we
get the result.

###  A.3 Proof of Theorem 7

We will prove the result only for pure states $\rho=\outerproduct{\phi}{\phi}$
and the general case follows from convexity.

We will first prove the case $n=2$. Since $\Pi_{1},\Pi_{2}$ are commuting
projectors, there exists an orthonormal basis
$\\{\ket{v_{i}}\\}_{i\in\mathcal{I}}$ and
$\mathcal{I}_{1},\mathcal{I}_{2}\subseteq\mathcal{I}$ such that
$\Pi_{1}=\sum_{i\in\mathcal{I}_{1}}\outerproduct{v_{i}}{v_{i}}$ and
$\Pi_{2}=\sum_{i\in\mathcal{I}_{2}}\outerproduct{v_{i}}{v_{i}}$. We also have
$\ket{\phi}=\sum_{i\in\mathcal{I}}c_{i}\ket{v_{i}}$ for some
$\\{c_{i}\\}_{i\in\mathcal{I}}$ with $\sum_{i\in\mathcal{I}}|c_{i}|^{2}=1$.
Then,

$\displaystyle\Tr[\Pi_{1}\rho]+\Tr[\Pi_{2}\rho]-\Tr[(I-\Pi_{1}\Pi_{2})\rho]$
$\displaystyle=\sum_{i\in\mathcal{I}_{1}}|c_{i}|^{2}+\sum_{i\in\mathcal{I}_{2}}|c_{i}|^{2}-\sum_{i\in\mathcal{I}_{1}\cap\mathcal{I}_{2}}|c_{i}|^{2}$
$\displaystyle=\sum_{i\in\mathcal{I}_{1}\cup\mathcal{I}_{2}}|c_{i}|^{2}$
$\displaystyle\leq\sum_{i\in\mathcal{I}}|c_{i}|^{2}=1.$

Hence,
$\Tr[(I-\Pi_{1}\Pi_{2})\rho]\leq\Tr[(I-\Pi_{1})\rho]+\Tr[(I-\Pi_{2})\rho]$.
The general case follows by repeatedly applying this case and observing that
$\Pi_{i}$ commutes with $\Pi_{i+1}\cdots\Pi_{n}$.

###  A.4 Proof of Theorem 12

First, we note that the result does not directly follow from the efficiency of
$\mathsf{API}^{\varepsilon,\delta}$. The reason is that while it is indeed
efficient, it obtains superpositions of (exponentially many) outputs from the
underlying distributions.

The proof will closely follow the proof of [Zha20, Theorem 6.5]. We first
state some of technical results that will be needed in the proof.

####  A.4.1 Technical Lemmata

######  Lemma 12.

Let $\mathcal{D}_{0},\mathcal{D}_{1}$ be two efficient distributions with the
same support and $\mathcal{P}$ be a collection of projective measurements
indexed by this support. Suppose $\mathcal{D}_{0}\equiv\mathcal{D}_{1}$. Then,
$\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P},\mathcal{D}_{0}}\rho\equiv\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P},\mathcal{D}_{1}}\rho$
for any state $\rho$ of appropriate dimension.

While the claim might seem obvious, it needs to be proven formally since
$\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P},\mathcal{D}}$ does not work by
obtaining random samples from $\mathcal{D}$ but instead runs the algorithm
$\mathcal{D}$ on various choices on random coins.

###### Proof.

When we inspect the actual implementation of
$\mathsf{API}^{\varepsilon,\delta}$ and proof of [Zha20, Theorem 6.2], we see
that the output distribution of
$\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P},\mathcal{D}}\rho$ is
equivalent to the following:

  1. 1.

Sample $p\leftarrow\mathsf{PI}_{\mathcal{P}_{\mathcal{D}}}\rho$.

  2. 2.

Flip $2T$ independent biased coins, where each coin has expected value $p$.

  3. 3.

Output some deterministic function of all coin flips.

Since $\mathcal{D}_{0}\equiv\mathcal{D}_{1}$ implies
$\mathsf{PI}({\mathcal{P}}_{\mathcal{D}_{0}})=\mathsf{PI}({\mathcal{P}}_{\mathcal{D}_{1}})$,
the result follows. ∎

######  Lemma 13.

Let $\mathcal{D}_{0},\mathcal{D}_{1}$ be two distributions with sampling time
$p(\lambda)$ such that
$\mathcal{D}_{0}\approx^{c}_{\nu(\lambda)}\mathcal{D}_{1}$ for all adversaries
that run in time $t(\lambda)$. Define $\mathcal{D}^{s(\lambda)}_{b}$ to be the
distribution where we sample $s$ independent samples from $\mathcal{D}_{b}$.
Then,
$\mathcal{D}^{s}_{0}\approx^{c}_{s(\lambda)\cdot\nu(\lambda)}\mathcal{D}^{s}_{1}$
for all adversaries that run in time $t(\lambda)/(p(\lambda)\cdot
s(\lambda))$.

###### Proof.

The result follows from a standard hybrid argument. We give in full detail for
completeness.

For all $i\in\\{0,1,\dots,s(\lambda)\\}$, we define the hybrid distribution
$\mathsf{Hyb}_{i}$ as the distribution where the first $i$ components are
sampled from $\mathcal{D}_{1}$ and the rest are sampled from
$\mathcal{D}_{0}$. Observe that $\mathsf{Hyb}_{0}$ is $\mathcal{D}^{s}_{0}$
and $\mathsf{Hyb}_{s}$ is $\mathcal{D}^{s}_{1}$.

Now, we claim $\mathsf{Hyb}_{i-1}\approx^{c}_{\nu(\lambda)}\mathsf{Hyb}_{i}$
for adversaries that run in $t(\lambda)/s(\lambda)$, for all $i\in[s]$.
Suppose otherwise, for a contradiction. Let $\mathcal{A}$ be the that
distinguishes them. Then, we can create an adversary $\mathcal{A}^{\prime}$
for distinguishing $\mathcal{D}_{0}$ versus $\mathcal{D}_{1}$ as follows.

##### $\underline{\mathcal{A}^{\prime}(a)}$

  1. 1.

For $j\in[s]$, sample $a_{j}\leftarrow\mathcal{D}_{1}$ if $j\leq i-1$ and
$a_{j}\leftarrow\mathcal{D}_{0}$ if $j>i$.

  2. 2.

Set $a_{i}=a$.

  3. 3.

Output $\mathcal{A}((a_{j})_{j\in[s]})$.

It is easy to see that $\mathcal{A}^{\prime}$ runs in time
$O(t(\lambda)/(p(\lambda)\cdot s(\lambda))\cdot p(\lambda)\cdot s(\lambda))$
and has advantage $\geq\nu(\lambda)$, which is a contradiction.

Finally, triangle inequality yields the claim. ∎

######  Lemma 14 ([Zha20]).

Let $A$ be a set. Sample $\Pi$ to be a random permutation on $A$. Sample
random functions $G:[s]\to A$ and $F:A\to[s]$. Then, for any quantum algorithm
$B$ making $Q$ quantum queries to its oracle, we have

$\mathopen{}\mathclose{{}\left|\Pr[B^{\Pi}()=1]-\Pr[B^{G\circ
F}()=1]}\right|\leq O(Q^{3}/s+Q^{3}/|A|).$

######  Lemma 15 ([Zha12b]).

Sample a random function $F:\mathcal{A}\to\mathcal{B}$ and a $2Q$-wise
independent function $E:\mathcal{A}\to\mathcal{B}$. Then, for any quantum
algorithm $B$ making $Q$ quantum queries to its oracle, we have

$\Pr[B^{F}()=1]=\Pr[B^{E}()=1].$

####  A.4.2 Proof of the Theorem

Now we move onto the proof of the theorem. We will construct a sequence of
hybrid distributions, starting with $\vec{p_{0}}$ and ending with
$\vec{p_{1}}$, that are obtained by modifying the previous one. Without loss
of generality, assume that all $\mathcal{B}_{\ell}^{b}$ have the same random
coin set $\mathcal{R}$. Let $s$ be a parameter that we will set later. We
assume that $|\mathcal{R}|$ is at least $s$, which is without loss of
generality since we can pad the random coins (and later ignore the padding
when using the coins).

#####  $\mathsf{Hyb}_{0}$:

Same as $\vec{p_{0}}$.

#####  $\mathsf{Hyb}_{1}$:

We now sample $\rho,pp$ as $\mathcal{S}^{1}(1^{\lambda})$.

#####  $\mathsf{Hyb}_{2}$:

For all $\ell\in[k]$, sample a random permutation
$\Pi_{\ell}:\mathcal{R}\to\mathcal{R}$. Then, instead of applying
$\bigotimes_{\ell\in[k]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{0}_{\ell}(pp)}$
to $\rho$, now apply
$\bigotimes_{\ell\in[k]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime}0}_{\ell}(pp))}$
where we define
$\mathcal{B}^{{}^{\prime}0}_{\ell}(pp;r)=\mathcal{B}^{0}_{\ell}(pp;\Pi_{\ell}(r))$.

#####  $\mathsf{Hyb}_{3,i}$ for $i\in[k]$:

Sample random functions $G_{\ell}:[s]\to\mathcal{R}$ and
$F_{\ell}:\mathcal{R}\to[s]$ for all $\ell\in[i]$. We now apply
$\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[i]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime}0}_{\ell}(pp))}}\right)\otimes\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in\\{i+1,\dots,k\\}}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime}0}_{\ell}(pp))}}\right)$
where we define
$\mathcal{B}^{{}^{\prime\prime}0}_{\ell}(pp;r)=\mathcal{B}^{0}_{\ell}(pp;G(F(r)))$.

#####  $\mathsf{Hyb}_{4,i}$ for $i\in[k]$:

Sample $2Q$-wise independent function $E_{\ell}:\mathcal{R}\to[s]$ for all
$\ell\in[i]$. We now apply
$\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[i]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime\prime}0}_{\ell}(pp))}}\right)\otimes\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in\\{i+1,\dots,k\\}}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime}0}_{\ell}(pp))}}\right)$
where we define
$\mathcal{B}^{{}^{\prime\prime\prime}0}_{\ell}(pp;r)=\mathcal{B}^{0}_{\ell}(pp;G(E(r)))$.

#####  $\mathsf{Hyb}_{5,i}$ for $i\in\\{0,1,\dots,k-1\\}$:

We now apply
$\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[i]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime\prime}1}_{\ell}(pp))}}\right)\otimes\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in\\{i+1,\dots,k\\}}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime\prime}0}_{\ell}(pp))}}\right)$.

#####  $\mathsf{Hyb}_{6,k-i+1}$ for $i\in[k]$:

We now apply
$\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[i]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime\prime}1}_{\ell}(pp))}}\right)\otimes\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in\\{i+1,\dots,k\\}}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime}1}_{\ell}(pp))}}\right)$
where we define
$\mathcal{B}^{{}^{\prime\prime\prime}1}_{\ell}(pp;r)=\mathcal{B}^{1}_{\ell}(pp;G(E(r)))$
and
$\mathcal{B}^{{}^{\prime\prime}1}_{\ell}(pp;r)=\mathcal{B}^{1}_{\ell}(pp;G(F(r)))$.

#####  $\mathsf{Hyb}_{7,k-i+1}$ for $i\in[k]$:

We now apply
$\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[i]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime\prime}1}_{\ell}(pp))}}\right)\otimes\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in\\{i+1,\dots,k\\}}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime}1}_{\ell}(pp))}}\right)$
where we define
$\mathcal{B}^{{}^{\prime}1}_{\ell}(pp;r)=\mathcal{B}^{1}_{\ell}(pp;\Pi_{\ell}(r))$.

#####  $\mathsf{Hyb}_{8}$:

We now apply
$\bigotimes_{\ell\in[k]}\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{B}^{{}^{\prime}1}_{\ell}(pp))}$
to $\rho$.

#####  $\mathsf{Hyb}_{9}$:

Same as $\vec{p_{1}}$.

######  Lemma 16.

$|\mathsf{Hyb}_{0}-\mathsf{Hyb}_{1}|\leq\nu(\lambda)$

######  Lemma 17.

$\mathsf{Hyb}_{1}\equiv\mathsf{Hyb}_{2}$ and
$\mathsf{Hyb}_{8}\equiv\mathsf{Hyb}_{9}$.

###### Proof.

Observe that $\mathcal{B}^{{}^{\prime}b}_{\ell}(pp)$ and
$\mathcal{B}^{b}_{\ell}(pp)$ are exactly the same distribution. The result
follows from Lemma 12. ∎

######  Lemma 18.

  * •

$|\mathsf{Hyb}_{2}-\mathsf{Hyb}_{3,1}|\leq O(Q^{3}/s).$

  * •

$|\mathsf{Hyb}_{3,i}-\mathsf{Hyb}_{3,i+1}|\leq O(Q^{3}/s)$ for all
$i\in[k-1]$.

  * •

$|\mathsf{Hyb}_{7,i}-\mathsf{Hyb}_{7,i+1}|\leq O(Q^{3}/s)$ for all
$i\in[k-1]$.

  * •

$|\mathsf{Hyb}_{7,k}-\mathsf{Hyb}_{8}|\leq O(Q^{3}/s).$

###### Proof.

Follows from Lemma 14. ∎

######  Lemma 19.

  * •

$\mathsf{Hyb}_{3,k}\equiv\mathsf{Hyb}_{4,1}$.

  * •

$\mathsf{Hyb}_{4,i}\equiv\mathsf{Hyb}_{4,i+1}$ for all $i\in[k-1]$.

  * •

$\mathsf{Hyb}_{6,k}\equiv\mathsf{Hyb}_{7,1}$.

  * •

$\mathsf{Hyb}_{6,i}\equiv\mathsf{Hyb}_{6,i+1}$ for all $i\in[k-1]$.

###### Proof.

Follows from Lemma 15. ∎

######  Lemma 20.

  * •

$|\mathsf{Hyb}_{5,k-1}-\mathsf{Hyb}_{6,0}|\leq\nu(\lambda)\cdot s(\lambda)$.

  * •

$|\mathsf{Hyb}_{5,i-1}-\mathsf{Hyb}_{5,i}|\leq\nu(\lambda)\cdot s(\lambda)$
for $i\in[k]$

###### Proof.

Observe that $\mathcal{B}^{b}_{\ell}(pp;G(E(\cdot)))$ can be interpreted as
$s$ samples from $\mathcal{B}^{b}$ with the input selecting which sample to
use. Also, both experiments can be computed in time
$\textnormal{poly}(\lambda)\cdot k\cdot s$. The result then follows from Lemma
13. ∎

Combining the above, we get
$|\vec{p_{0}}-\vec{p_{1}}|<O(k\cdot(Q^{3}/s+\nu(\lambda)\cdot s(\lambda)))$.
We set $s=1/\mu(\lambda)$, which yields the result since
$Q=\textnormal{poly}(\lambda)$.

###  A.5 Proof of Theorem 15

See [ALL+20, Corollary 3] for the proofs of the first two points. Note that
while they consider the same threshold value $\eta_{\ell}$ for all indices
$\ell$, an inspection of their proof easily shows that the results still hold
for any $\eta_{\ell}$.

Combining the first two bullet points yields the third bullet point in a
straightforward manner.

We now prove the fourth point. Let $p_{i}$ denote

$\Tr[\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[i]}\mathsf{TI}_{\eta_{\ell}-\varepsilon}({\mathcal{P}_{\ell}}_{\mathcal{D}_{\ell}})}\right)\otimes\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in\\{i+1,\dots,k\\}}\mathsf{ATI}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{D}_{\ell},\eta_{\ell}}}\right)\rho]$

Fourth point follows from a simple hybrid lemma.

###  A.6 Proof of Theorem 15

We will only prove the first claim, and the second prove follows by the same
argument.

Fix any $\ell\in[k]$. Consider the projective measurement $\mathcal{M}_{\ell}$
where we apply $\mathsf{PI}({\mathcal{P}_{\ell}}_{\mathcal{D}_{\ell}})$ to the
$\ell$-th register and apply $I$ to the other registers. Then, we have
$\Pr[(\mathcal{M}_{\ell}\rho)\leq(\vec{p})_{\ell}+2\varepsilon]\geq 1-2\delta$
since $\mathsf{API}^{\varepsilon,\delta}$ is $(\varepsilon,\delta)$-almost
projective and since it $\delta$-approximates $\mathsf{PI}$ in
$\varepsilon$-shift distance. Note while $\rho^{\prime}$ is obtained after a
measurement on all registers, we can assume that
$\mathsf{API}^{\varepsilon,\delta}_{\mathcal{P}_{\ell},\mathcal{D}_{\ell}}$
was applied last since measurements on disjoint registers commute.

Now, observe that
$\mathcal{M}_{1}\mathcal{M}_{2}\cdots\mathcal{M}_{k}=\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k]}\mathsf{PI}({\mathcal{P}_{\ell}}_{\mathcal{D}_{\ell}})}\right)$
and that $\mathcal{M}_{\ell}$ commute. We define $\mathcal{M}^{\prime}_{\ell}$
to be the binary projective measurement where we apply $\mathcal{M}_{\ell}$
and output $1$ if the outcome is $\leq\vec{p}_{\ell}+2\varepsilon$. Then, by
above we have $\Pr[\mathcal{M}^{\prime}_{\ell}\rho^{\prime}=1]\geq 1-2\delta$.
We get
$\Pr[\forall\ell\in[k]~{}~{}(\vec{p^{\prime}})_{\ell}\leq(\vec{p})_{\ell}+2\varepsilon]\geq
1-2\cdot k\cdot\delta$ by Theorem 7.

###  A.7 Proof of Theorem 16

Follows from a simpe hybrid lemma.