Quantum Measurement Adversary

Divesh Aggarwal ¹¹1Centre for Quantum Technologies and Department of Computer Science, National University of Singapore, [email protected] Naresh Goud Boddu ²²2NTT Research, Sunnyvale, USA, [email protected] Rahul Jain ³³3Centre for Quantum Technologies and Department of Computer Science, National University of Singapore and MajuLab, UMI 3654, Singapore, [email protected] Maciej Obremski ⁴⁴4Center for Quantum Technologies, National University of Singapore, [email protected]

Abstract

Multi-source extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. Quantum multi-source extractors were considered by Kasher and Kempe [KK10] (for the quantum independent adversary and the quantum bounded storage adversary), Chung, Li and Wu [CLW14] (for the general entangled adversary) and Arnon-Friedman, Portmann and Scholz [AFPS16] (for the quantum Markov adversary).

One of the main objectives of this work is to unify all the existing quantum multi-source adversary models. We propose two new models of adversaries: 1) the quantum measurement adversary ( $\mathsf{qma}$ ), which generates side information using entanglement and on post-measurement and 2) the quantum communication adversary ( $\mathsf{qca}$ ), which generates side information using entanglement and communication between multiple sources. We show that,

1.

$\mathsf{qma}$ is the strongest adversary among all the known adversaries, in the sense that the side information of all other adversaries can be generated by $\mathsf{qma}$ .
2.

The (generalized) inner-product function (in fact a general class of two-wise independent functions) continues to work as a good extractor with matching parameters as that of Chor and Goldreich [CG85] against classical adversaries.
3.

A non-malleable extractor proposed by Li [Li12] (against classical adversaries) continues to be secure against quantum side information. This result implies a non-malleable extractor result of Aggarwal, Chung, Lin and Vidick [ACLV19] with uniform seed. We strengthen their result via a completely different proof to make the non-malleable extractor of Li secure against quantum side information even when the seed is not uniform.
4.

A modification (working with weak local randomness instead of uniform local randomness) of the Dodis and Wichs [DW09] protocol for privacy-amplification is secure against active quantum adversaries (those who arbitrarily modify the messages exchanged in the protocol). This strengthens on a recent result due to Aggarwal, Chung, Lin and Vidick [ACLV19] which uses uniform local randomness.
5.

A tight efficiency lower bound for the (generalized) inner-product function (in fact a general class of two-wise independent functions).

1 Introduction

Randomized algorithms are designed under the assumption that randomness used within the algorithms is uniformly distributed. However, random sources in nature are often not necessarily uniform (aka weak). Thus, it is important to understand how to extract uniform randomness from weak-sources. Extractors are functions that transform weak-sources to uniform randomness. Extractors have numerous applications including privacy-amplification, pseudo-randomness, derandomization, expanders, combinatorics and cryptography. A general model of weak-sources is the so-called min-entropy source (please refer to Section 2 for definitions of information-theoretic quantities). Let $n,t,m$ be positive integers and $k,k_{1},k_{2},k_{1}^{\prime},k_{2}^{\prime},b_{1},b_{2},l$ be positive reals.

Definition 1 ([Zuc90]).

An $(n,k)$ -source denotes an $n$ -bit source $X\in\{0,1\}^{n}$ with the min-entropy bound $k$ , i.e. $\mathrm{H}_{\min}(X)\geq k$ .

It can be argued that no deterministic function can extract even one uniform bit given an (arbitrary) $(n,k)$ -source as long as $k\leq n-1$ [CG85]. This lead to designing extractors using an additional uniform source (aka seed) called seeded extractors [FS]. Another approach is to consider multiple independent weak-sources.

Definition 2 ([Zuc90, CLW14]).

An $(n,k_{1},k_{2},\ldots,k_{t})$ -source denotes $t$ independent $n$ -bit sources $X_{1},X_{2},\ldots,X_{t}$ with min-entropy bounds $\mathrm{H}_{\min}(X_{i})\geq k_{i}$ for every $i\in[t].$

Multi-source extractors are functions that transform multiple weak-sources to uniform randomness. Multi-source extractors have been studied extensively in the classical setting [Bou05, CG85, KLRZ08, Rao06, Raz05, KLR09]. With the advent of quantum computers, it is natural to investigate the security of extractors against a quantum adversary with quantum side information on weak-sources. As expected quantum side information presents many more challenges compared to classical side information. Gavinsky et al. [GKK⁺07] gave an example of a seeded extractor secure against a classical adversary but not secure against a quantum adversary (even with a very small side information). Several definitions of quantum multi-source adversaries have been proposed in the literature. Kasher and Kempe [KK10] introduced quantum bounded storage adversary ( $\mathsf{qbsa}$ ), where the adversary has bounded memory. They also introduced quantum independent adversary ( $\mathsf{qia}$ ) which obtains independent side information from various sources. Arnon-Friedman, Portmann and Scholz [AFPS16] introduced quantum Markov adversary ( $\mathsf{qMara}$ ), such that $X-E-Y$ forms a Markov-chain ( $\mathrm{I}\>\!\!\left(X\>\!:\>\!Y\>\!\middle|\>\!E\right)=0$ ) ⁵⁵5 $\mathrm{I}\>\!\!\left(A\>\!:\>\!B\>\!\middle|\>\!C\right)_{\rho}$ represents conditional mutual information between registers $A,B$ given register $C$ in state $\rho$ ., where $E$ is adversary’s side information. Chung, Li and Wu [CLW14] introduced general entangled adversary ( $\mathsf{gea}$ ). A natural question that arises is what is the relationship/hierarchy between these different adversary models. Previous works [CLW14, KK10, AFPS16] also ask if there is a model which is stronger than the existing models. To quote [KK10]

In light of this, it is not clear if and how entangled guessing entropy sources can be incorporated into the model, and hence we only consider bounded storage adversaries in the entangled case.

A difficulty that they point is that in the quantum setting (unlike the classical setting), measuring the adversary side information might break the independence of the sources [KK10]. Quantum entanglement between various parties, used to generate side information raises additional issues. Entanglement is of course known to yield several unexpected effects with no classical counterparts, e.g., non-local correlations [Bel64] and super-dense coding [BW92] etc.

A main objective of this work is to unify all the existing quantum multi-source adversary models. We propose two new models of adversaries: 1) the quantum measurement adversary ( $\mathsf{qma}$ , Definition 3), which generates side information using entanglement and conditioned on post-measurement outcomes and 2) the quantum communication adversary ( $\mathsf{qca}$ , Definition 4), which generates side information using entanglement and communication between multiple sources.

Definition 3 ( $l\mathchar 45\relax\mathsf{qma}$ , $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ ).

Let $\tau_{X\hat{X}}$ , $\tau_{Y\hat{Y}}$ be canonical purifications of uniform sources $X,Y$ respectively (registers $\hat{X}\hat{Y}$ with Reference).

1.

Alice and Bob hold $X,Y$ respectively. They also share an entangled state $\tau_{NM}$ (Alice holds $N$ , Bob holds $M$ ).

Alice applies an (safe) isometry $V_{A}:\mathcal{H}_{X}\otimes\mathcal{H}_{N}\rightarrow\mathcal{H}_{X}\otimes\mathcal{H}_{N^{\prime}}\otimes\mathcal{H}_{A}$ and Bob applies an (safe) isometry $V_{B}:\mathcal{H}_{Y}\otimes\mathcal{H}_{M}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{M^{\prime}}\otimes\mathcal{H}_{B}$ . Registers $A,B$ are single qubit registers. Let

\rho_{X\hat{X}AN^{\prime}M^{\prime}BY\hat{Y}}=(V_{A}\otimes V_{B})(\tau_{X\hat{X}}\otimes\tau_{NM}\otimes\tau_{Y\hat{Y}})(V^{\dagger}_{A}\otimes V^{\dagger}_{B}).

Alice and Bob perform a measurement in the computational basis on the registers $A$ and $B$ respectively. Let

l=\log\left(\frac{1}{\Pr(A=1,B=1)_{\rho}}\right)\quad;\quad\Phi_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}=\rho_{X\hat{X}AN^{\prime}M^{\prime}BY\hat{Y}}|(A=1,B=1).

4.

Adversary gets access to either $\Phi_{XN^{\prime}}$ or $\Phi_{M^{\prime}Y}.$ The pure state $\Phi$ is called an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ .

Motivation for the $l\mathchar 45\relax\mathsf{qma}$ model. A general model classically for two sources with side information is the Markov model of the form

\mathcal{C}=\{X-E-Y:\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)\geq k_{1}\ \textnormal{and}\ \mathrm{H}_{\min}\>\!\!\left(Y\middle|E\right)\geq k_{2}\}.

We can generate Markov-chain as above via the following procedure. Let Alice and Bob hold independent and uniform sources $X^{\prime}$ and $Y^{\prime}$ respectively. In addition, let Alice and Bob share independent randomness $E^{\prime}$ . Let Alice generate a local random variable $A\in\{0,1\}$ (using $X^{\prime}E^{\prime}$ ) and Bob generate a local random variable $B\in\{0,1\}$ (using $Y^{\prime}E^{\prime}$ ). It can be readily verified that $(X^{\prime}E^{\prime}Y^{\prime}~{}|~{}A=B=1)$ is a Markov-chain. It can also be checked that any Markov-chain $X-E-Y$ can be generated using this procedure.

The natural analogue of this procedure in the quantum setting is as described in Definition 3. A key difference with the classical setting is that, in the quantum setting, the resultant post-measurement state, does not form a Markov-chain and thus bringing the elusive nature of quantum side information. This brings us to consider sources ⁶⁶6Even though the state contain adversary side information, we call entire pure state as source for simplicity. of the form

\mathcal{Q}=\{\sigma_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}:\sigma_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}\ \textnormal{is an}\ l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}\}.

A question may be asked if one can provide both the registers $M^{\prime}$ and $N^{\prime}$ as side information to the adversary. However this may allow adversary to gain complete knowledge of $X,Y$ (since $N^{\prime}$ may contain a copy of $X$ and $M^{\prime}$ may contain a copy of $Y$ ) making the model trivial. Thus we settle on the model as in Definition 3.

We next define $2$ -source quantum communication adversary inspired from quantum communication protocols.

Definition 4 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca\mathchar 45\relax state}$ ).

Let $\tau_{X\hat{X}}$ , $\tau_{Y\hat{Y}}$ be the canonical purifications of the independent sources $X,Y$ respectively (registers $\hat{X}\hat{Y}$ with Reference).

1.

Alice and Bob hold $X,Y$ respectively. They also share an entangled pure state $\tau_{NM}$ (Alice holds $N$ , Bob holds $M$ ).
2.

Alice and Bob execute a quantum communication protocol, at the end of which the final state is $|\Phi\rangle_{XY\hat{X}\hat{Y}N^{\prime}M^{\prime}}$ (Alice holds $XN^{\prime}$ and Bob holds $YM^{\prime}$ ), with $\mathrm{H}_{\min}\>\!\!\left(X\middle|M^{\prime}Y\hat{Y}\right)_{\Phi}\geq k_{1}$ and $\mathrm{H}_{\min}\>\!\!\left(Y\middle|N^{\prime}X\hat{X}\right)_{\Phi}\geq k_{2}$ .
3.

Adversary gets access to either one of $\Phi_{XN^{\prime}}$ or $\Phi_{YM^{\prime}}$ of its choice. The state $\Phi$ is called a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca\mathchar 45\relax state}.$

Remark.

We note to the reader that indeed every $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca\mathchar 45\relax state}$ is a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ (where, $\mathsf{qpa\mathchar 45\relax state}$ stands for quantum purified adversary state) defined in Boddu, Jain and Kapshikar [BJK22] (see Definition 10). But, it is apriori not clear if every $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ can be generated via a communication protocol as in Definition 4.

Our results

We show that,

1.

$\mathsf{qma}$ is the strongest adversary among all the known adversaries (Theorem 1), in the sense that the side information of all other adversaries can be generated by $\mathsf{qma}$ .
2.

The (generalized) inner-product function (in fact a general class of two-wise independent functions) continues to work as a good extractor against $\mathsf{qma}$ (Theorem 2) with matching parameters as that of Chor and Goldreich [CG85] against classical adversaries.
3.

A non-malleable extractor proposed by Li [Li12] (against classical adversaries) continues to be secure against quantum side information (Theorem 3). A non-malleable extractor ( $\mathsf{nmExt}$ ) for sources ( $X,Y$ ) is an extractor such that $\mathsf{nmExt}(X,Y)$ is uniform and independent of $\mathsf{nmExt}(X,Y^{\prime})YY^{\prime}$ , where $Y^{\prime}\neq Y$ is generated by the adversary using $Y$ and the side information on $X$ .

This result implies a non-malleable extractor result of Aggarwal, Chung, Lin and Vidick
[ACLV19] with uniform $Y$ . We strengthen their result via a completely different proof to make the non-malleable extractor of Li ( $\mathsf{nmExt}(X,Y)=\langle X,Y||Y^{2}\rangle$ ) secure against quantum side information even when $Y$ is not uniform.
4.

A modification (working with weak local randomness instead of uniform local randomness) of the Dodis and Wichs [DW09] protocol for privacy-amplification (PA) is secure against active quantum adversaries (those who arbitrarily modify the messages exchanged in the protocol). This strengthens on a recent result due to [ACLV19] which uses uniform local randomness.
5.

We also show a tight efficiency lower bound (Corollary 1) for the (generalized) inner-product function (in fact a general class of two-wise independent functions).

$\mathsf{qma}$ can simulate other adversaries

We show that the side information of all the adversaries can be simulated (see Definition 22) in the model of $\mathsf{qma}$ .

Theorem 1.

Quantum side information of $(b_{1},b_{2})$ - $\mathsf{qbsa}$ (see Definition 23), $(k_{1},k_{2})$ - $\mathsf{qia}$ (see Definition 24), $(k_{1},k_{2})$ - $\mathsf{gea}$ (see Definition 25), acting on an $(n,k^{\prime}_{1},k^{\prime}_{2})$ -source can be simulated by an $l\mathchar 45\relax\mathsf{qma}$ for some $l\leq 2\min\{b_{1},b_{2}\}+2n-k^{\prime}_{1}-k^{\prime}_{2}$ , $l\leq 2n-k_{1}-k_{2}$ , $l\leq 2n-k_{1}-k_{2}$ respectively.

Quantum side information of $(k_{1},k_{2})$ - $\mathsf{qMara}$ (see Definition 26) and $(k_{1},k_{2})$ - $\mathsf{qca}$ (see Definition 4) can be simulated $\varepsilon$ -approximately by an $l\mathchar 45\relax\mathsf{qma}$ for some $l\leq 2n-k_{1}-k_{2}+25+6\log(1/\varepsilon)$ , $l\leq 2n-k_{1}-k_{2}+25+6\log(1/\varepsilon)$ respectively.

Inner-product is secure against $\mathsf{qma}$

A $2$ -source extractor secure against $l\mathchar 45\relax\mathsf{qma}$ is defined as follows:

Definition 5.

An $(n,n,m)$ - $2$ -source extractor $2\mathsf{Ext}:\{0,1\}^{n}\times\{0,1\}^{n}\to\{0,1\}^{m}$ is said to be $(l,\varepsilon)$ -quantum secure against $l\mathchar 45\relax\mathsf{qma}$ if for every $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ $\Phi$ (chosen by $l\mathchar 45\relax\mathsf{qma}$ ), we have

\|\Phi_{2\mathsf{Ext}(X,Y)N^{\prime}}-U_{m}\otimes\Phi_{N^{\prime}}\|_{1}\leq\varepsilon\hskip 20.00003pt\text{and}\hskip 20.00003pt\|\Phi_{2\mathsf{Ext}(X,Y)M^{\prime}}-U_{m}\otimes\Phi_{M^{\prime}}\|_{1}\leq\varepsilon.

The extractor is called $Y$ -strong if

\|\Phi_{2\mathsf{Ext}(X,Y)M^{\prime}Y}-U_{m}\otimes\Phi_{M^{\prime}Y}\|_{1}\leq\varepsilon,

and $X$ -strong if

\|\Phi_{2\mathsf{Ext}(X,Y)N^{\prime}X}-U_{m}\otimes\Phi_{N^{\prime}X}\|_{1}\leq\varepsilon.

We show that the inner-product extractor (in fact a general class of $\mathcal{X}$ -two-wise independent function (Definition 16 [4])) of Chor and Goldreich [CG85] continues to be secure against $l\mathchar 45\relax\mathsf{qma}$ .

Theorem 2.

Let $p=2^{m}$ and $n^{\prime}=n\log p$ . Let $\rho_{X\hat{X}NY\hat{Y}M}$ be an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ such that $|X|=|\hat{X}|=|Y|=|\hat{Y}|=n^{\prime}$ and $XY$ classical (with copies $\hat{X}\hat{Y}$ respectively). Let $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ be a $\mathcal{X}$ -two-wise independent function such that $\mathcal{X}=\mathcal{Y}=\mathbb{F}_{p}^{n}$ , $\mathcal{Z}=\mathbb{F}_{p}$ and $(X,Y)\in(\mathcal{X},\mathcal{Y})$ . Let $Z=f(X,Y)\in\mathcal{Z}$ . Then,

\|\rho_{ZYM}-U_{m}\otimes\rho_{YM}\|_{1}\leq\varepsilon,

for parameters $l\leq\left(n^{\prime}-m-40+8\log\left(\varepsilon\right)\right)/2.$

Symmetric results follow for a $\mathcal{Y}$ -two-wise independent function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ by exchanging $(N,X)\leftrightarrow(M,Y)$ above.

As a corollary of Theorem 2, we also get a tight efficiency (Definition 21) lower bound for a $\mathcal{X}$ -two-wise independent function.

Corollary 1 (Efficiency lower bound for a $\mathcal{X}$ -two-wise independent function).

Let function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ be a $\mathcal{X}$ -two-wise independent function such that $|\mathcal{X}|=|\mathcal{Y}|$ . Let $U$ be the uniform distribution on $\mathcal{X}\times\mathcal{Y}$ . For any $\gamma>0$ ,

\log\left(\tilde{\mathsf{eff}}_{\gamma}(f,U)\right)\geq\frac{1}{2}\left(\log|\mathcal{X}|-\log|\mathcal{Z}|-40+8\log\left(1-\gamma-\frac{1}{|\mathcal{Z}|}\right)\right).

Noting entanglement-assisted communication complexity of a function $f$ is lower bounded by efficiency of a function $f$ (Fact 29) and that the (generalized) inner-product function is a $\mathcal{X}$ -two-wise independent function (note $\mathcal{X}=\mathbb{F}^{n}_{p}$ ), we immediately get the following as a corollary.

Corollary 2.

Let $\mathsf{IP}^{n}_{p}:\mathbb{F}^{n}_{p}\times\mathbb{F}^{n}_{p}\to\mathbb{F}_{p}$ be defined as,

\mathsf{IP}_{p}^{n}(x,y)=\sum_{i=1}^{n}x_{i}y_{i}\mod p\enspace.

We have,

\mathcal{Q}_{\gamma}(\mathsf{IP}_{p}^{n})\geq\frac{(n-1)\log p}{4}+\log\left(1-\gamma-\frac{1}{p}\right)-20\enspace.

A quantum secure weak-seeded non-malleable extractor

Quantum secure non-malleable extractors [ACLV19] are studied when the seed is completely uniform. That is for a state $\sigma_{XMY}$ , we have $\sigma_{XMY}=\sigma_{XM}\otimes\sigma_{Y}$ , $\sigma_{Y}=U_{Y}$ and we have $\mathrm{H}_{\min}\>\!\!\left(X\middle|M\right)_{\sigma}\geq k.$ In this work, we extend the definition to study when the seed is not uniform.

Let $\sigma_{XMY}$ be such that $\sigma_{XMY}=\sigma_{XM}\otimes\sigma_{Y}$ , $\mathrm{H}_{\min}\>\!\!\left(X\middle|M\right)_{\sigma}\geq k_{1}$ and $\mathrm{H}_{\min}(Y)_{\sigma}\geq k_{2}$ . One may consider register $Y$ as weak-seed and register $M$ as adversary quantum side information on source $X$ . We consider the pure state extension of $\sigma_{XMY}$ denoted by $\sigma_{X\hat{X}NMY\hat{Y}}=\sigma_{X\hat{X}NM}\otimes\sigma_{Y\hat{Y}}$ and call it a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}$ .

Definition 6 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}$ ).

We call a pure state $\sigma_{X\hat{X}NMY\hat{Y}}$ , with $(XY)$ classical and $(\hat{X}\hat{Y})$ copy of $(XY)$ , a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}$ iff

\sigma_{X\hat{X}NMY\hat{Y}}=\sigma_{X\hat{X}NM}\otimes\sigma_{Y\hat{Y}}\quad;\quad\mathrm{H}_{\min}\>\!\!\left(X\middle|M\right)_{\sigma}\geq k_{1}\quad;\quad\mathrm{H}_{\min}(Y)_{\sigma}\geq k_{2}.

A non-malleable extractor ( $\mathsf{nmExt}$ ) is an extractor such that $\mathsf{nmExt}(X,Y)$ is uniform and independent of $\mathsf{nmExt}(X,Y^{\prime})YY^{\prime}M^{\prime}$ , where $Y^{\prime}\neq Y$ is generated by the adversary using $Y$ and the side information on $X$ , i.e. $M$ . Without any loss of generality, we consider the adversary operation to be isometry (since one can consider Stinespring extension of a CPTP map as an isometry (see Fact 18) if the adversary operation is a CPTP map). This leads us to consider $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ .

Definition 7 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ ).

Let $\sigma_{X\hat{X}NMY\hat{Y}}$ be a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}$ . Let $V:\mathcal{H}_{Y}\otimes\mathcal{H}_{M}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{Y^{\prime}}\otimes\mathcal{H}_{\hat{Y}^{\prime}}\otimes\mathcal{H}_{M^{\prime}}$ be an isometry such that for $\rho=V\sigma V^{\dagger},$ we have $Y^{\prime}$ classical (with copy $\hat{Y}^{\prime}$ ) and $\Pr(Y\neq Y^{\prime})_{\rho}=1.$ We call state $\rho$ a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ .

Since we require the non-malleable extractor to extract from every $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ , we phrase an adversary $\mathsf{qnma}$ (short for quantum non-malleable adversary) to choose the $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ .

Definition 8 (Quantum secure weak-seeded non-malleable extractor).

An $(n_{1},n_{2},m)$ -non-malleable extractor $\mathsf{nmExt}:\{0,1\}^{n_{1}}\times\{0,1\}^{n_{2}}\to\{0,1\}^{m}$ is $(k_{1},k_{2},\varepsilon)$ -secure against $\mathsf{qnma}$ if for every $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ $\rho$ (chosen by the adversary $\mathsf{qnma}$ ),

\|\rho_{\mathsf{nmExt}(X,Y)\mathsf{nmExt}(X,Y^{\prime})YY^{\prime}M^{\prime}}-U_{m}\otimes\rho_{\mathsf{nmExt}(X,Y^{\prime})YY^{\prime}M^{\prime}}\|_{1}\leq\varepsilon.

Following is an inner-product based non-malleable extractor proposed by Li [Li12].

Definition 9 ([Li12]).

Let $p\neq 2$ be a prime and $n$ be an integer. Define $\mathsf{nmExt}:\mathbb{F}^{n}_{p}\times\mathbb{F}^{n/2}_{p}\to\mathbb{F}_{p}$ given by $\mathsf{nmExt}(X,Y)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\langle X,Y||Y^{2}\rangle$ , where $||$ represents concatenation of strings and $Y^{2}$ is computed via multiplication in $\mathbb{F}_{p^{n/2}}$ .

We show that the inner-product based non-malleable extractor proposed by Li [Li12] continues to be secure against quantum side information.

Theorem 3.

Let $p\neq 2$ be a prime, $n$ be an even integer and $\varepsilon>0$ . The function $\mathsf{nmExt}(X,Y)$ is a $(k_{1},k_{2},\varepsilon)$ -quantum secure weak-seeded non-malleable extractor against $\mathsf{qnma}$ for the parameters $k_{1}+k_{2}\geq(n+17)\log p+33+16\log\left(\frac{1}{\varepsilon}\right)$ .

Privacy-amplification with weak-sources

We study the problem of privacy-amplification (PA) [BBR88, Mau92, BBCM95, MW97]. In this problem, two parties, Alice and Bob, share a weak secret $X$ (with $\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)\geq k$ , where $E$ is adversary Eve side information). Using $X$ and an insecure communication channel, Alice and Bob would like to securely agree on a secret key $R$ that is close to uniformly random to an active adversary Eve who may have full control over their communication channel. In all prior protocols including [ACLV19], we assume that Alice and Bob have local access to uniform sources of randomness. In practice, uniform sources are hard to come by, and it is more reasonable to assume that Alice and Bob have only weak-sources of randomness. For this we make use of breakthrough result by Dodis and Wichs [DW09], who were first to show the existence of a two-round PA protocol with optimal (up to constant factors) entropy loss, for any initial min-entropy. We modify the protocol of [DW09], to accommodate the non-uniform local randomness at Alice and Bob side. Based on our construction of a quantum secure weak-seeded non-malleable extractor (Theorem 3) we obtain a PA protocol working with weak local sources of randomness and is secure against active quantum adversaries as long as the initial secret $X$ has min-entropy rate of more than half.

Proof overview

For the proof of Theorem 1, we first prove Lemma 1. To prove Lemma 1, we first establish Claims 1 and 2 using the standard quantum information-theoretic techniques. Claim 1 corresponds to correlating independent and uniform $X$ with quantum side information while Claim 2 corresponds to correlating independent and uniform $Y$ with quantum side information conditioned on post-measurement by Alice. In particular, we used a quantum analogue of the rejection-sampling argument of [JRS09] to prove them. Next, using Lemma 1, we generate side information (of other adversary models) in the $l\mathchar 45\relax\mathsf{qma}$ model, since it suffices to showing appropriate conditional-min-entropy and modified-conditional-min-entropy bounds of various adversary models in the purification picture.

For the proof of Theorem 4, let initial state of $l\mathchar 45\relax\mathsf{qma}$ model be $\tau$ , state after the Alice measurement outcome $A=1$ be $\rho$ and state after the Bob measurement outcome $B=1$ conditioned on Alice post-measurement outcome $A=1$ be $\Phi$ . We first reduce the task of bounding $\|\Phi_{ZYM}-U_{Z}\otimes\Phi_{YM}\|_{1}$ to bounding the collision-probability $\Gamma(\rho_{ZYM}|\rho_{YM})$ at the expense of multiplicative factor given by $\frac{|\mathrm{supp}(Z)|}{\Pr(B=1)}$ using Cauchy Schwarz inequality as key ingredient. Notice, in state $\rho$ , we have $\rho_{YX\hat{X}N^{\prime}}=\rho_{Y}\otimes\rho_{X\hat{X}N^{\prime}}$ . Thus, this enables us to use the argument of Renner [Ren05] to further bound the collision-probability $\Gamma(\rho_{ZYM}|\rho_{YM})$ to be exponentially small in min-entropy $\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|YM\right)_{\rho}$ for pairwise-independent function $f$ such that $Z=f(X,Y)$ . Additionally when $\tau_{M}=\rho_{M}$ , the proof follows by noting the relation of $\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|YM\right)_{\rho}$ with probability of Alice’s measurement outcome $A=1$ ( $\Pr(A=1)$ ).

For the proof of Theorem 3, we first make use the result of [ACLV19] which reduces the task of showing non-malleable extractor security of Li’s extractor to showing hardness of inner-product in a guessing game. We note that it is equivalent to showing hardness of inner-product in a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ (see Definition 7). We next show that we can get the conditional-min-entropy bounds required to make use of Fact 30 to simulate $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ as $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ . Thus, hardness of inner-product in a guessing game further reduces to showing security of inner-product against $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ . Using Fact 30, the proof now follows.

Comparison with [ACLV19]

Both [ACLV19] and Theorem 3 have considered the inner-product based non-malleable extractor proposed by Li [Li12]. [ACLV19] extends the first step of classical proof, the reduction provided by the non-uniform XOR lemma, to the quantum case. This helps in reducing the task of showing non-malleable extractor property of inner-product to showing security of inner-product in a certain communication game. They then approach the problem of showing security of inner-product in a communication game by using the “reconstruction paradigm” of [DPVR12] to guess the entire input $X$ from the modified side information.

On the other hand, in Theorem 3, we reduce the security of inner-product in a communication game to the security of inner-product against the quantum measurement adversary. In the process, both [ACLV19] and Theorem 3 crucially use the combinatorial properties of inner-product. For example, in the proof of Theorem 3, we heavily uses the pairwise independence property of inner-product.

Other related works

Seeded extractors have been studied extensively in the classical setting [ILL89, FS]. König et al. [KT08] showed that any one-bit output extractor is also secure against quantum adversaries, with roughly the same parameters. Ta-Shma [TS09], De and Vidick [DV10], and later De et al. [DPVR12] gave seeded extractors with short seeds that are secure against quantum side information and can extract almost all of min-entropy and are based on Trevisan’s extractor [Tre01]. The extractor of Impagliazzo et al. [ILL89] was shown to be secure against quantum side information by [KMR05, Ren05, RK05].

In the multi-source setting, a probabilistic argument shows the existence of $2$ -source extractors for min-entropy $k=\log n+O(1)$ . Explicit constructions of multi-source extractors with access to more than $2$ -sources has been considered in the successful line of work [BIW06, Li12, Li11, Rao09, Li13] leading to a near optimal $3$ -source extractor that works for polylogarithmic min-entropy and has negligible error [Li15]. Explicit constructions of $2$ -source extractors has been first considered in [CG85] who showed that inner-product is a $2$ -source extractor for min-entropy $k\geq n/2$ . After nearly two decades, Bourgain [Bou05] broke the “half entropy barrier”, and constructed a $2$ -source extractor for min-entropy $(1/2-\delta)n$ , for some tiny constant $\delta>0.$ A long line of research starting with [CG85, Bou05, Raz05, CZ19, Li19] leading to a near optimal $2$ -source extractor that works for polylogarithmic min-entropy and has inverse polynomial error [CZ19, Li19].

Subsequent works

Inspired from our work, Boddu, Jain and Kapshikar [BJK22] have defined $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ as specified below.

Definition 10 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ ).

A pure state $\sigma_{X\hat{X}NMY\hat{Y}}$ , with $(XY)$ classical and $(\hat{X}\hat{Y})$ copy of $(XY)$ , a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ iff

\mathrm{H}_{\min}\>\!\!\left(X\middle|MY\hat{Y}\right)_{\sigma}\geq k_{1}\quad;\quad\mathrm{H}_{\min}\>\!\!\left(Y\middle|NX\hat{X}\right)_{\sigma}\geq k_{2}.

They showed that every $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ is also a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ as stated in the below fact.

Fact 1 ([BJK22]).

Let $\sigma_{X\hat{X}NMY\hat{Y}}$ be an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ such that $|X|=|\hat{X}|=|Y|=|\hat{Y}|=n$ . There exists $k_{1},k_{2}$ such that $\sigma$ is a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ , $k_{1}\geq n-l$ and $k_{2}\geq n-l$ .

They also showed that for every $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ there is a close-by $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ as stated in the below fact.

Fact 2 ([BJK22]).

Let $\rho_{X\hat{X}NY\hat{Y}M}$ be a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ such that $|X|=|\hat{X}|=|Y|=|\hat{Y}|=n$ . There exists an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ $\rho^{(1)}$ such that,

\Delta_{B}(\rho^{(1)};\rho)\leq 6\varepsilon\quad and\quad l\leq 2n-k_{1}-k_{2}+4+6\log\left(\frac{1}{\varepsilon}\right).

Furthermore,

\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|MY\hat{Y}\right)_{\rho^{(1)}}\geq k_{1}-2\log\left(\frac{1}{\varepsilon}\right)\quad;\quad\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|NX\hat{X}\right)_{\rho^{(1)}}\geq k_{2}-4-4\log\left(\frac{1}{\varepsilon}\right).

They used $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ framework to construct the first explicit quantum secure non-malleable extractor for (source) min-entropy $\geq\mathsf{polylog}\left(\frac{n}{\varepsilon}\right)$ and seed length of $\mathsf{polylog}\left(\frac{n}{\varepsilon}\right)$ ( $n$ is the length of the source and $\varepsilon$ is the error parameter) which lead to a $2$ -round privacy-amplification protocol that is secure against active quantum adversaries with communication $\mathsf{polylog}\left(\frac{n}{\varepsilon}\right)$ , exponentially improving upon the linear communication required by the protocol due to [ACLV19].

In addition, using our result, the security of inner-product against $l\mathchar 45\relax\mathsf{qma}$ as key ingredient, they constructed the first explicit quantum secure $2$ -source non-malleable extractor for min-entropy $k_{1},k_{2}\geq n-n^{\Omega(1)}$ , with an output of size $n/4$ and error $2^{-n^{\Omega(1)}}$ .

Also, recently Aggarwal, Boddu and Jain [ABJ22] have extended the connection of [CG14] between $2$ -source non-malleable extractors and non-malleable codes in the split-state model in classical setting to quantum setting. They further used quantum secure $2$ -source non-malleable extractor [BJK22] to construct the first explicit quantum secure non-malleable code in the split-state model for message length $m=n^{\Omega(1)}$ , error $\varepsilon=2^{-n^{\Omega(1)}}$ and codeword size $2n$ .

Additionally, Jain and Kundu [JK22] have used our efficiency lower bound result (Corollary 4) to obtain a direct-product result for two-wise independent functions including for the generalized inner-product function ( $\mathsf{IP}$ ).

Organization

In Section 2, we present our notations, definitions and other information-theoretic preliminaries. In Section 3, we present the proof of Theorem 4 and Fact 30. In Section 4, we present the proof of Theorem 1. In Section 5 we present the proof of Theorem 3.

2 Preliminaries

Quantum information theory

Let $\mathcal{X},\mathcal{Y},\mathcal{Z}$ be finite sets (we only consider finite sets in this paper). We use $x\leftarrow\mathcal{X}$ to denote $x$ drawn uniformly from $\mathcal{X}$ . All the logarithms are evaluated to the base $2$ . Consider a finite dimensional Hilbert space $\mathcal{H}$ endowed with an inner-product $\langle\cdot,\cdot\rangle$ (we only consider finite dimensional Hilbert-spaces). A quantum state (or a density matrix or a state) is a positive semi-definite matrix on $\mathcal{H}$ with trace equal to $1$ . It is called pure if and only if its rank is $1$ . Let $|\psi\rangle$ be a unit vector on $\mathcal{H}$ , that is $\langle\psi,\psi\rangle=1$ . With some abuse of notation, we use $\psi$ to represent the state and also the density matrix $|\psi\rangle\langle\psi|$ , associated with $|\psi\rangle$ . Given a quantum state $\rho$ on $\mathcal{H}$ , support of $\rho$ , called $\text{supp}(\rho)$ is the subspace of $\mathcal{H}$ spanned by all eigenvectors of $\rho$ with non-zero eigenvalues.

A quantum register $A$ is associated with some Hilbert space $\mathcal{H}_{A}$ . Define $|A|:=\log\dim(\mathcal{H}_{A})$ . Let $\mathcal{L}(\mathcal{H}_{A})$ represent the set of all linear operators on $\mathcal{H}_{A}$ . For operators $O,O^{\prime}\in\mathcal{L}(\mathcal{H}_{A})$ , the notation $O\leq O^{\prime}$ represents the Löwner order, that is, $O^{\prime}-O$ is a positive semi-definite matrix. We denote by $\mathcal{D}(\mathcal{H}_{A})$ , the set of quantum states on the Hilbert space $\mathcal{H}_{A}$ . State $\rho$ with subscript $A$ indicates $\rho_{A}\in\mathcal{D}(\mathcal{H}_{A})$ . If two registers $A,B$ are associated with the same Hilbert space, we shall represent the relation by $A\equiv B$ . For two states $\rho_{A},\sigma_{B}$ , we let $\rho_{A}\equiv\sigma_{B}$ represent that they are identical as states, just in different registers. Composition of two registers $A$ and $B$ , denoted $AB$ , is associated with the Hilbert space $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ . For two quantum states $\rho\in\mathcal{D}(\mathcal{H}_{A})$ and $\sigma\in\mathcal{D}(\mathcal{H}_{B})$ , $\rho\otimes\sigma\in\mathcal{D}(\mathcal{H}_{AB})$ represents the tensor product (Kronecker product) of $\rho$ and $\sigma$ . The identity operator on $\mathcal{H}_{A}$ is denoted $\mathrm{I}_{A}$ . Let $U_{A}$ denote maximally mixed state in $\mathcal{H}_{A}$ . We also use $U_{m}$ to denote uniform distribution supported on $m$ -bit strings. Let $\rho_{AB}\in\mathcal{D}(\mathcal{H}_{AB})$ . Define

\rho_{B}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{Tr}_{A}{\rho_{AB}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i}(\langle i|\otimes\mathrm{I}_{B})\rho_{AB}(|i\rangle\otimes\mathrm{I}_{B}),

where $\{|i\rangle\}_{i}$ is an orthonormal basis for the Hilbert space $\mathcal{H}_{A}$ . The state $\rho_{B}\in\mathcal{D}(\mathcal{H}_{B})$ is referred to as the marginal state of $\rho_{AB}$ . Unless otherwise stated, a missing register from subscript in a state will represent partial trace over that register. Given $\rho_{A}\in\mathcal{D}(\mathcal{H}_{A})$ , a purification of $\rho_{A}$ is a pure state $\rho_{AB}\in\mathcal{D}(\mathcal{H}_{AB})$ such that $\mathrm{Tr}_{B}{\rho_{AB}}=\rho_{A}$ . Purification of a quantum state is not unique. Suppose $A\equiv B$ . Given $\{|i\rangle_{A}\}$ and $\{|i\rangle_{B}\}$ as orthonormal bases over $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ respectively, the canonical purification of a quantum state $\rho_{A}$ is $|\rho_{A}\rangle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\rho_{A}^{\frac{1}{2}}\otimes\mathrm{I}_{B})\left(\sum_{i}|i\rangle_{A}|i\rangle_{B}\right)$ .

A quantum map $\mathcal{E}:\mathcal{L}(\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{B})$ is a completely positive and trace preserving (CPTP) linear map (mapping states in $\mathcal{D}(\mathcal{H}_{A})$ to states in $\mathcal{D}(\mathcal{H}_{B})$ ). A unitary operator $V_{A}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A}$ is such that $V_{A}^{\dagger}V_{A}=V_{A}V_{A}^{\dagger}=\mathrm{I}_{A}$ . The set of all unitary operators on $\mathcal{H}_{A}$ is denoted by $\mathcal{U}(\mathcal{H}_{A})$ . An isometry $V:\mathcal{H}_{A}\rightarrow\mathcal{H}_{B}$ is such that $V^{\dagger}V=\mathrm{I}_{A}$ and $VV^{\dagger}=\mathrm{I}_{B}$ . A POVM element is an operator $0\leq M\leq\mathrm{I}$ . We use shorthand $\bar{M}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{I}-M$ , where $\mathrm{I}$ is clear from the context. We use shorthand $M$ to represent $M\otimes\mathrm{I}$ , where $\mathrm{I}$ is clear from the context.

Definition 11 (Classical register in a pure state).

Let $\mathcal{X}$ be a set. A classical-quantum (c-q) state $\rho_{XE}$ is of the form

\rho_{XE}=\sum_{x\in\mathcal{X}}p(x)|x\rangle\langle x|\otimes\rho^{x}_{E},

where ${\rho^{x}_{E}}$ are states.

Let $\rho_{XEA}$ be a pure state. We call $X$ a classical register in $\rho_{XEA}$ , if $\rho_{XE}$ (or $\rho_{XA}$ ) is a c-q state. We identify random variable $X$ with the register $X$ , with $\Pr(X=x)=p(x)$ .

Definition 12 (Copy of a classical register).

Let $\rho_{X\hat{X}E}$ be a pure state with $X$ being a classical register in $\rho_{X\hat{X}E}$ (see Definition 11) taking values in $\mathcal{X}$ . Similarly, let $\hat{X}$ be a classical register in $\rho_{X\hat{X}E}$ taking values in $\mathcal{X}$ . Let $\Pi_{\mathsf{Eq}}=\sum_{x\in\mathcal{X}}|x\rangle\langle x|\otimes|x\rangle\langle x|$ be the equality projector acting on the registers $X\hat{X}$ . We call $X$ and $\hat{X}$ copies of each other (in the computational basis) if $\mathrm{Tr}\left(\Pi_{\mathsf{Eq}}\rho_{X\hat{X}}\right)=1$ .

Definition 13 (Conditioning).

Let

\rho_{XE}=\sum_{x\in\{0,1\}^{n}}p(x)|x\rangle\langle x|\otimes\rho^{x}_{E},

be a c-q state. For an event $\mathcal{S}\subseteq\{0,1\}^{n}$ , define

\Pr(\mathcal{S})_{\rho}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{x\in\mathcal{S}}p(x)\quad;\quad(\rho|X\in\mathcal{S})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{\Pr(\mathcal{S})_{\rho}}\sum_{x\in\mathcal{S}}p(x)|x\rangle\langle x|\otimes\rho^{x}_{E}.

We sometimes shorthand $(\rho|X\in\mathcal{S})$ as $(\rho|\mathcal{S})$ when the register $X$ is clear from the context.

Let $\rho_{AB}$ be a state with $|A|=n$ . We define $(\rho|A\in\mathcal{S})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\sigma|\mathcal{S})$ , where $\sigma_{AB}$ is the c-q state obtained by measuring the register $A$ in $\rho_{AB}$ in the computational basis. In case $\mathcal{S}=\{s\}$ is a singleton set, we shorthand $(\rho|A=s)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{Tr}_{A}(\rho|A=s)$ .

Definition 14 (Extension).

Let

\rho_{XE}=\sum\limits_{x\in\{0,1\}^{n}}p(x)|x\rangle\langle x|\otimes\rho^{x}_{E},

be a c-q state. For a function $Z:\mathcal{X}\rightarrow\mathcal{Z}$ , define the following extension of $\rho_{XE}$ ,

\rho_{ZXE}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{x\in\mathcal{X}}p(x)|Z(x)\rangle\langle Z(x)|\otimes|x\rangle\langle x|\otimes\rho^{x}_{E}.

Definition 15 (Safe maps).

We call an isometry $V:\mathcal{H}_{X}\otimes\mathcal{H}_{A}\rightarrow\mathcal{H}_{X}\otimes\mathcal{H}_{B}$ , safe on $X$ iff there is a collection of isometries $V_{x}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{B}$ such that the following holds. For all states $|\psi\rangle_{XA}=\sum_{x}\alpha_{x}|x\rangle_{X}|\psi^{x}\rangle_{A}$ ,

V|\psi\rangle_{XA}=\sum_{x}\alpha_{x}|x\rangle_{X}V_{x}|\psi^{x}\rangle_{A}.

We call a CPTP map $\Phi:\mathcal{L}(\mathcal{H}_{X}\otimes\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{X}\otimes\mathcal{H}_{B})$ , safe on classical register $X$ iff there is a collection of CPTP maps $\Phi_{x}:\mathcal{L}(\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{B})$ such that the following holds. For all c-q states $\rho_{XA}=\sum_{x}\Pr(X=x)_{\rho}|x\rangle\langle x|\otimes\rho^{x}_{A}$ ,

\Phi({\rho}_{XA})=\sum_{x}\Pr(X=x)_{\rho}|x\rangle\langle x|\otimes\Phi_{x}(\rho^{x}_{A}).

All isometries (or in general CPTP maps) considered in this paper are safe on classical registers that they act on. CPTP maps applied by adversaries can be assumed w.l.o.g as safe on classical registers, by the adversary first making a (safe) copy of classical registers and then proceeding as before. This does not reduce the power of the adversary.

Definition 16.

1.

For $p\geq 1$ and matrix $A$ , let $\|A\|_{p}$ denote the Schatten $p$ -norm.
2.

Let $\Delta(\rho;\sigma)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{2}\|\rho-\sigma\|_{1}$ . We write $\approx_{\varepsilon}$ to denote $\Delta(\rho;\sigma)\leq\varepsilon$ .
3.

Let $d(X)_{\rho}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Delta(\rho_{X};U_{X})$ and $d(X|Y)_{\rho}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Delta(\rho_{XY};U_{X}\otimes\rho_{Y})$ .
4.

$\mathcal{X}$ -two-wise independent function: We call a function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ , $\mathcal{X}$ -two-wise independent iff for any two distinct $x_{1},x_{2}\in\mathcal{X}$ ,

$\Pr_{y\leftarrow\mathcal{Y}}(f(x_{1},y)=f(x_{2},y))=\frac{1}{|\mathcal{Z}|}.$
5.

Fidelity: For states $\rho,\sigma:~{}\mathrm{F}(\rho;\sigma)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\|\sqrt{\rho}\sqrt{\sigma}\|_{1}.$
6.

Bures metric: For states $\rho,\sigma:\Delta_{B}(\rho;\sigma)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sqrt{1-\mathrm{F}(\rho;\sigma)}.$ Being a metric, it satisfies the triangle inequality.

Max-divergence [Dat09, JRS09]: For states $\rho,\sigma$ such that $\mathrm{supp}(\rho)\subset\mathrm{supp}(\sigma)$ ,

\mathrm{D}_{\max}\>\!\!\left(\rho\middle\|\sigma\right)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min\{\lambda\in\mathbb{R}:\rho\leq 2^{\lambda}\sigma\}.

Sandwitched-Rényi-divergence: Let $1\neq\alpha>0$ . For states $\rho,\sigma$ such that $\text{supp}(\rho)\subset\text{supp}(\sigma)$ ,

\mathrm{D}_{\alpha}\>\!\!\left(\rho\middle\|\sigma\right)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{\alpha-1}\log\mathrm{Tr}\left(\sigma^{\frac{1-\alpha}{2\alpha}}\rho\sigma^{\frac{1-\alpha}{2\alpha}}\right)^{\alpha}.

Collision-probability [Ren05]: For state $\rho_{AB}$ ,

\Gamma(\rho_{AB}|\rho_{B})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{Tr}\left(\rho_{AB}(\mathrm{I}_{A}\otimes\rho_{B}^{-1/2})\right)^{2}=2^{\mathrm{D}_{2}\>\!\!\left(\rho_{AB}\middle\|\mathrm{I}_{A}\otimes\rho_{B}\right)}=\|(\mathrm{I}_{A}\otimes\rho_{B}^{-1/4})\rho_{AB}(\mathrm{I}_{A}\otimes\rho_{B}^{-1/4})\|^{2}_{2}.

10.

Min-entropy: For a random variable $X$ ,

$\mathrm{H}_{\min}(X)=\min_{x\in\text{supp}(X)}\log\left(\frac{1}{P_{X}(x)}\right).$

11.

Conditional-min-entropy: For state $\rho_{XE}$ , min-entropy of $X$ conditioned on $E$ is defined as,

\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}=-\inf_{\sigma_{E}\in\mathcal{D}(\mathcal{H}_{E})}\mathrm{D}_{\max}\>\!\!\left(\rho_{XE}\middle\|\mathrm{I}_{X}\otimes\sigma_{E}\right).

12.

Max-information [Dat09]: For a state $\rho_{AB}$ ,

\mathrm{I}_{\max}(A:B)_{\rho}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\inf_{\sigma_{B}\in\mathcal{D}(\mathcal{H}_{B})}\mathrm{D}_{\max}\>\!\!\left(\rho_{AB}\middle\|\rho_{A}\otimes\sigma_{B}\right).

If $\rho$ is a classical state (diagonal in the computational basis) then the $\inf$ above is achieved by a classical state $\sigma_{B}$ .

13.

Modified-conditional-min-entropy: For state $\rho_{XE}$ , the modified-min-entropy of $X$ conditioned on $E$ is defined as,

$\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}=-\mathrm{D}_{\max}\>\!\!\left(\rho_{XE}\middle\|\mathrm{I}_{X}\otimes\rho_{E}\right).$
14.

Markov-chain: A state $\rho_{XEY}$ forms a Markov-chain (denoted $(X-E-Y)_{\rho}$ ) iff $\mathrm{I}\>\!\!\left(X\>\!:\>\!Y\>\!\middle|\>\!E\right)_{\rho}=0$ .

For the facts stated below without citation, we refer the reader to standard text books [NC00, Wat11, Wil12, Wat18].

Fact 3.

For even $p:~{}\|A\|^{p}_{p}=\mathrm{Tr}(A^{\dagger}A)^{p/2}.$

Fact 4 ([BJL23]).

For a c-q state $\rho_{XA}$ ( $X$ classical): $\rho_{XA}\leq\mathrm{I}_{X}\otimes\rho_{A}$ and $\rho_{XA}\leq\rho_{X}\otimes\mathrm{I}_{A}$ .

Fact 5 ([BJL23]).

Let $\rho_{XBD}$ be a c-q state ( $X$ classical) such that $\rho_{XB}=\rho_{X}\otimes\rho_{B}$ . Then,

\mathrm{I}_{\max}(X:BD)_{\rho}\leq 2|D|.

Fact 6.

For a quantum state $\rho_{XE}:~{}\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}\geq\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}.$

Fact 7 ([BJK22]).

Let $\rho\in\mathcal{D}(\mathcal{H}_{AB})$ . There exists $\rho^{\prime}\in\mathcal{D}(\mathcal{H}_{AB})$ such that

\Delta_{B}(\rho;\rho^{\prime})\leq\varepsilon\quad;\quad\mathrm{\tilde{H}}_{\min}\>\!\!\left(A\middle|B\right)_{\rho}\leq\mathrm{H}_{\min}\>\!\!\left(A\middle|B\right)_{\rho}\leq\mathrm{\tilde{H}}_{\min}\>\!\!\left(A\middle|B\right)_{\rho^{\prime}}+2\log\left(\frac{1}{\varepsilon}\right).

Fact 8 ([CLW14]).

Let $\Phi:\mathcal{L}(\mathcal{H}_{M})\rightarrow\mathcal{L}(\mathcal{H}_{M^{\prime}})$ be a CPTP map and let $\sigma_{XM^{\prime}}=(\mathrm{I}\otimes\Phi)(\rho_{XM})$ . Then

\mathrm{H}_{\min}\>\!\!\left(X\middle|M^{\prime}\right)_{\sigma}\geq\mathrm{H}_{\min}\>\!\!\left(X\middle|M\right)_{\rho}.

Fact 9.

Let $\rho,\sigma,\tau$ be quantum states. Then $\Delta(\rho;\sigma)\leq\Delta(\rho;\tau)+\Delta(\sigma;\tau).$

Fact 10 ([FvdG06]).

Let $\rho,\sigma$ be two states. Then,

1-\mathrm{F}(\rho;\sigma)\leq\Delta(\rho;\sigma)\leq\sqrt{1-\mathrm{F}^{2}(\rho;\sigma)}\quad;\quad\Delta_{B}^{2}(\rho;\sigma)\leq\Delta(\rho;\sigma)\leq\sqrt{2}\Delta_{B}(\rho;\sigma).

Fact 11 (Data-processing).

Let $\rho,\sigma$ be quantum states and $\Phi$ be a CPTP map. Then

•

$\Delta(\Phi(\rho);\Phi(\sigma))\leq\Delta(\rho;\sigma).$
•

$\Delta_{B}(\Phi(\rho);\Phi(\sigma))\leq\Delta_{B}(\rho;\sigma).$
•

$\mathrm{D}_{\max}\>\!\!\left(\Phi(\rho)\middle\|\Phi(\sigma)\right)\leq\mathrm{D}_{\max}\>\!\!\left(\rho\middle\|\sigma\right).$
•

([Bei13]) For all $1\neq\alpha>0:~{}\mathrm{D}_{\alpha}\>\!\!\left(\Phi(\rho)\middle\|\Phi(\sigma)\right)\leq\mathrm{D}_{\alpha}\>\!\!\left(\rho\middle\|\sigma\right).$

Fact 12 ([HJPW04]).

A Markov-chain $(X-E-Y)_{\rho}$ can be decomposed as follows:

\rho_{XEY}=\sum_{t}\Pr(T=t)|t\rangle\langle t|\otimes\left(\rho^{t}_{XE_{1}}\otimes\rho^{t}_{YE_{2}}\right),

where $T$ is some classical register over a finite alphabet.

Fact 13 ([AHJ⁺21]).

For a Markov-chain $(X-E-Y)_{\rho}$ , there exists a CPTP map $\Phi:\mathcal{L}(\mathcal{H}_{E})\rightarrow\mathcal{L}(\mathcal{H}_{E}\otimes\mathcal{H}_{Y})$ such that $\rho_{XEY}=({\mathrm{I}_{X}}\otimes\Phi)\rho_{XE}$ .

Fact 14 (Hölder’s inequality).

For matrices $A,B$ , for any real $p,q>0$ and $\frac{1}{p}+\frac{1}{q}=1$ we have $|\mathrm{Tr}(A^{\dagger}B)|\leq\|A\|_{p}\|B\|_{q}.$

Fact 15 (Hölder’s inequality, special case).

For matrices $A,B:~{}\|BAB^{\dagger}\|_{1}\leq\|A\|_{2}\|B\|^{2}_{4}.$

Fact 16 (Cyclicity of trace).

For matrices $A,B,C:~{}\mathrm{Tr}(ABC)=\mathrm{Tr}(BCA)=\mathrm{Tr}(CAB).$

Fact 17.

Let $\rho_{AB}\in\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ be a state and $M\in\mathcal{L}(\mathcal{H}_{B})$ such that $M^{\dagger}M\leq\mathrm{I}_{B}$ . Let $\hat{\rho}_{AB}=\frac{M\rho_{AB}M^{\dagger}}{\mathrm{Tr}{M\rho_{AB}M^{\dagger}}}$ . Then,

\mathrm{D}_{\max}\>\!\!\left(\hat{\rho}_{A}\middle\|\rho_{A}\right)\leq\log\left(\frac{1}{\mathrm{Tr}{M\rho_{AB}M^{\dagger}}}\right).

Fact 18 (Stinespring isometry extension [Wat11]).

Let $\Phi:\mathcal{L}(\mathcal{H}_{X})\rightarrow\mathcal{L}(\mathcal{H}_{Y})$ be a CPTP map. There exists an isometry $V:\mathcal{H}_{X}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{Z}$ (Stinespring isometry extension of $\Phi$ ) such that $\Phi(\rho_{X})=\mathrm{Tr}_{Z}(V\rho_{X}V^{\dagger})$ for every state $\rho_{X}$ .

Fact 19 (Corollary 5.5 in [Wat11]).

Let $\rho_{AB}\in\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ be a pure state and $V_{B}:\mathcal{L}(\mathcal{H}_{B})\rightarrow\mathcal{L}(\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{C})$ be an isometry such that $|C|=1$ . Let $\sigma_{AB^{\prime}C}=(\mathrm{I}_{A}\otimes V_{B})\rho_{AB}(\mathrm{I}_{A}\otimes V_{B})^{\dagger}$ and $\Phi_{AB^{\prime}}=(\sigma_{AB^{\prime}C}|C=1)$ . There exists an operator $M_{B}$ such that $0\leq M^{\dagger}_{B}M_{B}\leq\mathrm{I}_{B}$ and

\Phi_{AB^{\prime}}=\frac{(\mathrm{I}_{A}\otimes M_{B})\rho_{AB}(\mathrm{I}_{A}\otimes M_{B})^{\dagger}}{\mathrm{Tr}(\mathrm{I}_{A}\otimes M_{B})\rho_{AB}(\mathrm{I}_{A}\otimes M_{B})^{\dagger}}\quad;\quad\Pr[C=1]=\mathrm{Tr}M_{B}\rho_{B}M_{B}^{\dagger}.

Fact 20 (Lemma 5.4.3 [Ren05]).

Let $\rho_{XM}$ be a c-q state ( $X$ classical). Let $Z=f(X)$ , where $f\leftarrow\mathcal{F}$ is drawn from a two-wise independent hash function family $\mathcal{F}$ . Let $\sigma_{M}\in\mathcal{D}(\mathcal{H}_{M})$ be any state. Then,

\displaystyle\mathbb{E}_{f\leftarrow\mathcal{F}}\left[\mathrm{Tr}\left((\mathrm{I}_{Z}\otimes\sigma_{M}^{-1/2})(\rho_{f(X)M}-U_{Z}\otimes\rho_{M})\right)^{2}\right]\leq\mathrm{Tr}\rho_{XM}(\mathrm{I}_{X}\otimes\sigma_{M}^{-1/2})\rho_{XM}(\mathrm{I}_{X}\otimes\sigma_{M}^{-1/2}).

Fact 21 ([Ren05]).

Let $p$ be a prime number and $n$ be a positive integer. Let $\rho_{XM}$ be a c-q state ( $X$ classical) with $\rho_{X}\in\mathbb{F}^{n}_{p}$ . Let $Z=f(X)$ , where $f\leftarrow\mathcal{F}$ is drawn from a two-wise independent hash function family $\mathcal{F}$ . Then,

\displaystyle\mathbb{E}_{f\leftarrow\mathcal{F}}\left[\mathrm{Tr}\left((\mathrm{I}_{Z}\otimes\rho_{M}^{-1/2})(\rho_{f(X)M}-U_{Z}\otimes\rho_{M})\right)^{2}\right]\leq 2^{-\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|M\right)_{\rho}}.

Proof.

Consider,

	$\displaystyle\mathbb{E}_{f\leftarrow\mathcal{F}}\left[\mathrm{Tr}\left((\mathrm{I}_{Z}\otimes\rho_{M}^{-1/2})(\rho_{f(X)M}-U_{Z}\otimes\rho_{M})\right)^{2}\right]$
	$\displaystyle\leq\mathrm{Tr}\rho_{XM}(\mathrm{I}_{X}\otimes\rho_{M}^{-1/2})\rho_{XM}(\mathrm{I}_{X}\otimes\rho_{M}^{-1/2})$	(Fact 20)
	$\displaystyle\leq\\|(\mathrm{I}_{X}\otimes\rho_{M}^{-1/2})\rho_{XM}(\mathrm{I}_{X}\otimes\rho_{M}^{-1/2})\\|_{\infty}$	(Fact 14)
	$\displaystyle=2^{-\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle\|M\right)_{\rho}}.$	(Definition 16 [13])

∎

Fact 22 (Uhlmann’s theorem [Uhl76]).

Let $\rho_{A},\sigma_{A}\in\mathcal{D}(\mathcal{H}_{A})$ . Let $\rho_{AB}\in\mathcal{D}(\mathcal{H}_{AB})$ be a purification of $\rho_{A}$ and $\sigma_{AC}\in\mathcal{D}(\mathcal{H}_{AC})$ be a purification of $\sigma_{A}$ . There exists an isometry $V$ (from a subspace of $\mathcal{H}_{C}$ to a subspace of $\mathcal{H}_{B}$ ) such that,

\mathrm{F}(|\theta\rangle\langle\theta|_{AB};|\rho\rangle\langle\rho|_{AB})=\mathrm{F}(\rho_{A};\sigma_{A}),

where $|\theta\rangle_{AB}=(\mathrm{I}_{A}\otimes V)|\sigma\rangle_{AC}$ .

Fact 23 (Rejection-sampling [JRS09]).

Let $X,Y$ be random variables such that $\mathrm{D}_{\max}\>\!\!\left(X\middle\|Y\right)\leq k$ . There exits a random variable $Z\in\{0,1\}$ , correlated with $Y$ such that $X\equiv(Y|Z=1)$ and $\Pr(Z=1)\geq 2^{-k}$ .

Fact 24 ([JRS09]).

Let $\rho_{A^{\prime}B},\sigma_{AB}$ be pure states such that $\mathrm{D}_{\max}\>\!\!\left(\rho_{B}\middle\|\sigma_{B}\right)\leq k$ . Let Alice and Bob share $\sigma_{AB}$ . There exists an isometry $V:A\rightarrow A^{\prime}C$ such that,

1.

$(V\otimes\mathrm{I}_{B})\sigma_{AB}(V\otimes\mathrm{I}_{B})^{\dagger}=\phi_{A^{\prime}BC}$ , where $C$ is a single qubit register.
2.

Let $C$ be the outcome of measuring $\phi_{C}$ in the standard basis. Then $\Pr(C=1)\geq 2^{-k}$ .
3.

Conditioned on outcome $C=1$ , the state shared between Alice and Bob is $\rho_{A^{\prime}B}$ .

We present a proof here for completeness.

Proof.

Since $\mathrm{D}_{\max}\>\!\!\left(\rho_{B}\middle\|\sigma_{B}\right)\leq k$ , let $\sigma_{B}=2^{-k}\rho_{B}+(1-2^{-k})\tau_{B}$ . Let $\tau_{A^{\prime}B}$ be a purification of $\tau_{B}$ . Consider,

\phi_{CA^{\prime}B}=\sqrt{(1-2^{-k})}|0\rangle_{C}\otimes\tau_{A^{\prime}B}+\sqrt{2^{-k}}|1\rangle_{C}\otimes\rho_{A^{\prime}B}.

Notice $\phi_{A^{\prime}BC}$ is purification of $\sigma_{B}$ . From Fact 22, there exists an isometry $V:A\rightarrow A^{\prime}C$ such that $(V\otimes\mathrm{I}_{B})\sigma_{AB}(V\otimes\mathrm{I}_{B})^{\dagger}=\phi_{A^{\prime}BC}.$ The desired properties can be readily verified. ∎

Fact 25 ([BJK22]).

Let $\rho_{ABC}\in\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C})$ be a state and $M\in\mathcal{L}(\mathcal{H}_{C})$ such that $M^{\dagger}M\leq\mathrm{I}_{C}$ . Let $\hat{\rho}_{ABC}=\frac{M\rho_{ABC}M^{\dagger}}{\mathrm{Tr}{M\rho_{ABC}M^{\dagger}}}$ . Then,

\mathrm{H}_{\min}\>\!\!\left(A\middle|B\right)_{\hat{\rho}}\geq\mathrm{H}_{\min}\>\!\!\left(A\middle|B\right)_{\rho}-\log\left(\frac{1}{\mathrm{Tr}{M\rho_{ABC}M^{\dagger}}}\right).

Furthermore ⁷⁷7The proof in [BJK22] can be easily modified to prove the inequality for $\mathrm{\tilde{H}}_{\min}\>\!\!\left(.\middle|.\right)$ . if $\hat{\rho}_{B}=\rho_{B}$ , we also get,

\mathrm{\tilde{H}}_{\min}\>\!\!\left(A\middle|B\right)_{\hat{\rho}}\geq\mathrm{\tilde{H}}_{\min}\>\!\!\left(A\middle|B\right)_{\rho}-\log\left(\frac{1}{\mathrm{Tr}{M\rho_{ABC}M^{\dagger}}}\right).

Fact 26 ([BJK22]).

Let $\rho_{ZA},\rho^{\prime}_{ZA}$ be states such that $\Delta(\rho;\rho^{\prime})\leq\varepsilon^{\prime}$ . If $d(Z|A)_{\rho^{\prime}}\leq\varepsilon$ then $d(Z|A)_{\rho}\leq 2\varepsilon^{\prime}+\varepsilon$ . ⁸⁸8Claim holds even when $\Delta_{B}()$ is replaced with $\Delta()$ .

Claim 1.

Let $\phi_{XX^{\prime}AB}$ be a pure state such that $\mathrm{H}_{\min}({X|B})_{\phi}\geq k$ . Let $X$ be a classical register (with copy $X^{\prime}$ ). Let $\theta_{X_{1}X_{2}}$ be the canonical purification of $\theta_{X_{2}}$ such that $\theta_{X_{2}}\equiv U_{X}$ . Let $\theta_{X_{1}X_{2}}$ be shared between Reference ( $X_{1}$ ) and Alice ( $X_{2}$ ). There exists a pure state $\sigma_{AB}$ such that when shared between Alice ( $A$ ) and Bob ( $B$ ), Alice can perform a measurement which succeeds with probability at least $2^{k-|X|}$ and on success joint shared state is $\phi_{X_{1}X^{\prime}AB}$ between Reference ( $X_{1}$ ), Alice ( $X^{\prime}A$ ) and Bob ( $B$ ) such that $\phi_{X_{1}X^{\prime}AB}\equiv\phi_{XX^{\prime}AB}$ .

Proof.

Since $\mathrm{H}_{\min}({X|B})_{\phi}\geq k$ , we have

\inf_{\sigma_{B}}\mathrm{D}_{\max}\>\!\!\left(\phi_{XB}\middle\|U_{X}\otimes\sigma_{B}\right)\leq|X|-k.

Let the infimum above be achieved by $\sigma_{B}$ and let $\sigma_{AB}$ be its purification shared between Alice ( $A$ ) and Bob ( $B$ ). The desired now follows from Fact 24 by treating Bob (in Fact 24) as Reference and Bob (here), state $\sigma_{AB}$ (in Fact 24) as $\theta_{X_{1}X_{2}}\otimes\sigma_{AB}$ (here) and state $\rho_{AB}$ (in Fact 24) as $\phi_{X_{1}X^{\prime}AB}$ (here). ∎

Claim 2.

Let $\phi_{XX^{\prime}AYY^{\prime}B}$ be a pure state such that

\mathrm{H}_{\min}({X|BYY^{\prime}})_{\phi}\geq k_{1}\quad\text{ and }\quad\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|XX^{\prime}A\right)_{\phi}\geq k_{2}.

Let $X,Y$ be classical registers (with copy $X^{\prime}$ and $Y^{\prime}$ respectively). Let $\theta_{X_{1}X_{2}}$ be a canonical purification of $\theta_{X_{2}}$ such that $\theta_{X_{2}}\equiv U_{X}$ . Let $\theta_{X_{1}X_{2}}$ be shared between Reference ( $X_{1}$ ) and Alice ( $X_{2}$ ). Let $\tau_{Y_{1}Y_{2}}$ be a canonical purification of $\tau_{Y_{2}}$ such that $\tau_{Y_{2}}\equiv U_{Y}$ . Let $\tau_{Y_{1}Y_{2}}$ be shared between Reference ( $Y_{1}$ ) and Bob ( $Y_{2}$ ). There exists a pure state $\sigma_{ABYY^{\prime}}$ such that when shared between Alice ( $A$ ) and Bob ( $BYY^{\prime}$ ), Alice and Bob can each perform a measurement which jointly succeeds with probability at least $2^{k_{1}+k_{2}-|X|-|Y|}$ and on success the joint shared state is $\phi_{X_{1}X^{\prime}AY_{1}Y^{\prime}B}$ between Reference ( $X_{1}Y_{1}$ ), Alice ( $X^{\prime}A$ ) and Bob ( $Y^{\prime}B$ ), such that $\phi_{X_{1}X^{\prime}AY_{1}Y^{\prime}B}\equiv\phi_{XX^{\prime}AYY^{\prime}B}$ .

Proof.

Since $\mathrm{H}_{\min}({X|BYY^{\prime}})_{\phi}\geq k_{1}$ , we have

\inf_{\sigma_{BYY^{\prime}}}\mathrm{D}_{\max}\>\!\!\left(\phi_{XBYY^{\prime}}\middle\|U_{X}\otimes\sigma_{BYY^{\prime}}\right)\leq|X|-k_{1}.

Let the infimum above be achieved by $\sigma_{BYY^{\prime}}$ and let $\sigma_{ABYY^{\prime}}$ be its purification shared between Alice ( $A$ ) and Bob ( $BYY^{\prime}$ ). From Claim 1, Alice can do a measurement such that on success $\phi_{X_{1}X^{\prime}AYY^{\prime}B}$ is shared between Reference ( $X_{1}$ ), Alice ( $X^{\prime}A$ ) and Bob ( $YY^{\prime}B$ ) (such that $\phi_{X_{1}X^{\prime}AYY^{\prime}B}\equiv\phi_{XX^{\prime}AYY^{\prime}B}$ ). Also, since $\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|AXX^{\prime}\right)_{\phi}\geq k_{2}$ , we have

\mathrm{D}_{\max}\>\!\!\left(\phi_{YAX_{1}X^{\prime}}\middle\|U_{Y}\otimes\phi_{AX_{1}X^{\prime}}\right)\leq|Y|-k_{2}.

Again from Claim 1, Bob can do a measurement such that on success $\phi_{X_{1}X^{\prime}AY_{1}Y^{\prime}B}$ is shared between Reference ( $X_{1}Y_{1}$ ), Alice ( $X^{\prime}A$ ) and Bob ( $Y^{\prime}B$ ) (such that $\phi_{X_{1}X^{\prime}AY_{1}Y^{\prime}B}\equiv\phi_{XX^{\prime}AYY^{\prime}B}$ ). This completes the proof by noting probability of success in the first and second steps as $2^{k_{1}-|X|}$ and $2^{k_{2}-|Y|}$ respectively. ∎

Claim 3.

Let $\phi_{XX^{\prime}AYY^{\prime}B}$ be a pure state such that

\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|BYY^{\prime}\right)_{\phi}\geq k_{1}\quad\text{ and }\quad\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|XX^{\prime}A\right)_{\phi}\geq k_{2}.

Let $X,Y$ be classical registers (with copy $X^{\prime}$ and $Y^{\prime}$ respectively). Let $\theta_{X_{1}X_{2}}$ be a canonical purification of $\theta_{X_{2}}$ such that $\theta_{X_{2}}\equiv U_{X}$ . Let $\theta_{X_{1}X_{2}}$ be shared between Reference ( $X_{1}$ ) and Alice ( $X_{2}$ ). Let $\tau_{Y_{1}Y_{2}}$ be a canonical purification of $\tau_{Y_{2}}$ such that $\tau_{Y_{2}}\equiv U_{Y}$ . Let $\tau_{Y_{1}Y_{2}}$ be shared between Reference ( $Y_{1}$ ) and Bob ( $Y_{2}$ ). There exists a pure state $\sigma_{ABYY^{\prime}}$ such that $\sigma_{BYY^{\prime}}\equiv\phi_{BYY^{\prime}}$ and when shared between Alice ( $A$ ) and Bob ( $BYY^{\prime}$ ), Alice and Bob can each perform a measurement which jointly succeeds with probability at least $2^{k_{1}+k_{2}-|X|-|Y|}$ and on success the joint shared state is $\phi_{X_{1}X^{\prime}AY_{1}Y^{\prime}B}$ between Reference ( $X_{1}Y_{1}$ ), Alice ( $X^{\prime}A$ ) and Bob ( $Y^{\prime}B$ ), such that $\phi_{X_{1}X^{\prime}AY_{1}Y^{\prime}B}\equiv\phi_{XX^{\prime}AYY^{\prime}B}$ .

Proof.

The proof follows in similar lines of Claim 2 after a simple modification. We state the modification required and do not repeat the entire argument. Considering $\sigma_{ABYY^{\prime}}$ to be any purification of $\sigma_{BYY^{\prime}}$ such that $\sigma_{BYY^{\prime}}\equiv\phi_{BYY^{\prime}}$ in Claim 2 and repeating the argument of Claim 2, the result follows. ∎

Lemma 1.

Let $\rho_{X\hat{X}NY\hat{Y}M}$ be a pure state such that $|X|=|\hat{X}|=|Y|=|\hat{Y}|=n$ , $XY$ classical (with copies $\hat{X}\hat{Y}$ respectively) and

\mathrm{H}_{\min}\>\!\!\left(X\middle|Y\hat{Y}M\right)_{\rho}\geq k_{1}\quad;\quad\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|X\hat{X}N\right)_{\rho}\geq k_{2}.

Then $\rho$ is also an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ (see Definition 3) for some $l\leq 2n-k_{1}-k_{2}.$

Proof.

Simulation of the state $\rho$ in the model of $l\mathchar 45\relax\mathsf{qma}$ follows from Claim 2. Using Claim 2, with the following assignment of registers (below the registers on the left are from Claim 2 and the registers on the right are the registers in this proof)

(X,Y,X^{\prime},Y^{\prime},A,B,\Phi)\leftarrow(X,Y,\hat{X},\hat{Y},N,M,\rho),

we have

l\leq\log(2^{n-k_{1}+n-k_{2}})=2n-k_{1}-k_{2}.

∎

Corollary 3.

Let $\rho$ be a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}$ such that $|X|=|Y|=n$ . Then $\rho$ is also an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ for the parameters $l\leq 2n-k_{1}-k_{2}$ .

Proof.

Note $\rho_{X\hat{X}NMY\hat{Y}}=\rho_{X\hat{X}NM}\otimes\rho_{Y\hat{Y}}$ , where $\rho_{X\hat{X}NM}$ is the purification of $\rho_{XM}$ such that $\mathrm{H}_{\min}\>\!\!\left(X\middle|M\right)_{\rho}\geq k_{1}$ and $\mathrm{H}_{\min}(Y)_{\rho}\geq k_{2}$ . Since $\rho_{X\hat{X}NMY\hat{Y}}=\rho_{X\hat{X}NM}\otimes\rho_{\hat{Y}Y},$ we have

\mathrm{H}_{\min}\>\!\!\left(X\middle|Y\hat{Y}M\right)_{\rho}\geq k_{1}

and

\mathrm{D}_{\max}\>\!\!\left(\rho_{YX\hat{X}N}\middle\|U_{Y}\otimes\rho_{X\hat{X}N}\right)\leq\log(\dim(\mathcal{H}_{Y}))-k_{2}=n-k_{2}.

The first inequality follows since $\rho_{YX\hat{X}N}=\rho_{Y}\otimes\rho_{X\hat{X}N}$ and $\mathrm{H}_{\min}(Y)_{\rho}\geq k_{2}.$ Thus, $\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|X\hat{X}N\right)_{\rho}\geq k_{2}$ . Simulation of the $(k_{1},k_{2})$ - $\mathsf{wqpa\mathchar 45\relax state}$ in the model of $l\mathchar 45\relax\mathsf{qma}$ now follows from Lemma 1. ∎

Extractors

Definition 17 (Quantum secure seeded extractor).

An $(n,d,m)$ -seeded extractor $\mathsf{Ext}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ is said to be $(k,\varepsilon)$ -quantum secure if for every state $\rho_{XES}$ , such that $\mathrm{H}_{\min}(X|E)_{\rho}\geq k$ and $\rho_{XES}=\rho_{XE}\otimes U_{d}$ , we have

\|\rho_{\mathsf{Ext}(X,S)E}-U_{m}\otimes\rho_{E}\|_{1}\leq\varepsilon.

In addition, the extractor is called strong if

\|\rho_{\mathsf{Ext}(X,S)SE}-U_{m}\otimes U_{d}\otimes\rho_{E}\|_{1}\leq\varepsilon.

$S$ is referred to as the seed for the extractor.

Fact 27 ([DPVR12] [CV17]).

There exists an explicit $(2m,\varepsilon)$ -quantum secure strong $(n,d,m)$ -seeded extractor $\mathsf{Ext}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ for parameters $d=O(\log^{2}(n/\varepsilon)\log m)$ .

Definition 18 ( $2$ -source extractor against an adversary [KK10, CLW14, AFPS16]).

An $(n,n,m)$ - $2$ -source extractor $2\mathsf{Ext}:\{0,1\}^{n}\times\{0,1\}^{n}\to\{0,1\}^{m}$ is $(\cdot,\varepsilon)$ -quantum ⁹⁹9 $"\cdot"$ in $(\cdot,\varepsilon)$ indicates the parameters of adversary model used to define $\rho_{XEY}$ . For example, $(l,\varepsilon)$ - quantum secure against $\mathsf{qma}$ (for $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ ’s chosen by $\mathsf{qma}$ ). secure against an adversary if for every $\rho_{XYE}$ (generated appropriately in the adversary model, adversary holds $E$ ), we have

\|\rho_{2\mathsf{Ext}(X,Y)E}-U_{m}\otimes\rho_{E}\|_{1}\leq\varepsilon.

The extractor is called $Y$ -strong if

\|\rho_{2\mathsf{Ext}(X,Y)EY}-U_{m}\otimes\rho_{EY}\|_{1}\leq\varepsilon,

and $X$ -strong if

\|\rho_{2\mathsf{Ext}(X,Y)EX}-U_{m}\otimes\rho_{EX}\|_{1}\leq\varepsilon.

Definition 19.

A function $\mathsf{MAC}:\{0,1\}^{2m}\times\{0,1\}^{m}\to\{0,1\}^{m}$ is an $\varepsilon$ -information-theoretically secure one-time message authentication code if for any function $\mathcal{A}:\{0,1\}^{m}\times\{0,1\}^{m}\to\{0,1\}^{m}\times\{0,1\}^{m}$ it holds that for all $\mu\in\{0,1\}^{m}$

\Pr_{k\leftarrow\{0,1\}^{2m}}\big{[}(\mathsf{MAC}(k,\mu^{\prime})=\sigma^{\prime})\,\wedge\,(\mu^{\prime}\neq\mu):(\mu^{\prime},\sigma^{\prime})\leftarrow\mathcal{A}(\mu,\mathsf{MAC}(k,\mu))\big{]}\,\leq\,\varepsilon.

Efficient constructions of $\mathsf{MAC}$ satisfying the conditions of Definition 19 are known. The following fact summarizes some parameters that are achievable using a construction based on polynomial evaluation.

Fact 28 (Proposition 1 in [KR09]).

For any integer $m>0$ , there exists an efficient family of $2^{-m}$ -information-theoretically secure one-time message authentication codes

\mathsf{MAC}:\{0,1\}^{2m}\times\{0,1\}^{m}\to\{0,1\}^{m}.

Quantum communication complexity

In a quantum communication protocol $\Pi$ for computing a function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ , the inputs $x\in\mathcal{X}$ and $y\in\mathcal{Y}$ are given to Alice and Bob respectively. They also start with an entangled pure state independent of the inputs. They perform local operations and exchange quantum messages. The goal is to minimize the communication between them. Please refer to preliminaries of [Yao93, CB97] for details of an entanglement-assisted quantum communication protocol. Let $O(x,y)$ refer to the output of the protocol, on input $(x,y)$ . Let $C_{i}$ (on $c_{i}$ qubits) refer to the $i$ -th message sent in the protocol.

Definition 20.

Define,

	Worst-case error:	$\displaystyle\quad\mathrm{err}(\Pi)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{(x,y)}\{\Pr[O(x,y)\neq f(x,y)]\}.$
	Communication of a quantum protocol:	$\displaystyle\quad\mathrm{QCC}(\Pi)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i}c_{i}.$
	Entanglement-assisted communication complexity of $f$ :	$\displaystyle\quad\mathcal{Q}_{\gamma}(f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min_{\Pi:\mathrm{err}(\Pi)\leq\gamma}\mathrm{QCC}(\Pi).$

Protocols with abort and efficiency

Consider the following zero-communication protocol with abort for a function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ . Let the inputs $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$ be given to Alice and Bob respectively according to distribution $\mu$ . They also start with an entangled pure state $\tau_{NM}$ independent of the inputs (Alice holds $N$ and Bob holds $M$ ). They apply local operations and measurements and are allowed to abort with some probability. Let the state shared between Alice and Bob after their local operations be $\tau_{XN^{\prime}M^{\prime}YAB}$ . Let $\perp$ represent the abort symbol. Let $\Pr(A=\perp\vee B=\perp)_{\tau}\leq 1-\eta,$ and

\Phi_{XN^{\prime}M^{\prime}YAB}=(\tau_{XN^{\prime}M^{\prime}YAB}|A\neq\perp\wedge B\neq\perp)\enspace,

where Alices holds $XN^{\prime}A$ and Bob holds $M^{\prime}YB$ . Let $\gamma>0$ . The goal of Alice and Bob is to maximize $\eta$ such that

\Pr(B\neq f(X,Y))_{\Phi}\leq\gamma.

Definition 21.

Define:

	Error of $\Pi$ under $\mu$ on non-abort:	$\displaystyle\quad\mathrm{err}(\Pi,\mu)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Pr(B\neq f(X,Y))_{\Phi}.$
	Efficiency of $\Pi$ under $\mu$ :	$\displaystyle\quad\tilde{\mathsf{eff}}(\Pi,\mu)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{1}{\eta}$
	Efficiency of $f$ under $\mu$ :	$\displaystyle\quad\tilde{\mathsf{eff}}_{\gamma}(f,\mu)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min_{\Pi:\mathrm{err}(\Pi,\mu)\leq\gamma}\tilde{\mathsf{eff}}(\Pi,\mu)$
	Efficiency of $f$ :	$\displaystyle\quad\tilde{\mathsf{eff}}_{\gamma}(f)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{\mu}\tilde{\mathsf{eff}}_{\gamma}(f,\mu).$

Fact 29 (Theorem 5 in [LLR12]).

For a function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ and $\gamma>0$ ,

\mathcal{Q}_{\gamma}(f)\geq\frac{1}{2}\log(\tilde{\mathsf{eff}}_{\gamma}(f)).

3 Inner-product is secure against $\mathsf{qma}$

We show that the inner-product extractor of Chor and Goldreich [CG85] is secure against $\mathsf{qma}$ (with nearly the same parameters as that of classical adversary). More generally we show any $\mathcal{X}$ -two-wise independent function (Definition 16 [4]) continues to be secure against $l\mathchar 45\relax\mathsf{qma}$ . We first show that the security of $\mathcal{X}$ -two-wise independent function against $l\mathchar 45\relax\mathsf{qma}$ .

Theorem 4.

Let $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ be a $\mathcal{X}$ -two-wise independent function such that $|\mathcal{X}|=|\mathcal{Y}|$ .

1.

Let $\tau=\tau_{XX_{1}}\otimes\tau_{NM}\otimes\tau_{YY_{1}}$ , where $\tau_{XX_{1}}$ is the canonical purification of $\tau_{X}$ (maximally mixed in $\mathcal{X}$ ), $\tau_{YY_{1}}$ is canonical purification of $\tau_{Y}$ (maximally mixed in $\mathcal{Y}$ ) and $\tau_{NM}$ is a pure state.
2.

Let $V_{A}:\mathcal{H}_{X_{1}}\otimes\mathcal{H}_{N}\rightarrow\mathcal{H}_{X_{1}}\otimes\mathcal{H}_{N^{\prime}}\otimes\mathcal{H}_{A}$ be a (safe) isometry. Let $\rho=(V_{A}\tau V^{\dagger}_{A}~{}|~{}A=1).$
3.

Let $V_{B}:\mathcal{H}_{Y}\otimes\mathcal{H}_{M}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{M^{\prime}}\otimes\mathcal{H}_{B}$ be a (safe) isometry. Let $\Theta=V_{B}\rho V^{\dagger}_{B}$ and $\Phi=(\Theta~{}|~{}B=1)$ .
4.

Let $Z=f(X,Y)\in\mathcal{Z}$ and $\varepsilon\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\|\Phi_{ZYM^{\prime}}-U_{Z}\otimes\Phi_{YM^{\prime}}\|_{1}$ .

Then

\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|M\right)_{\rho}-\log|\mathcal{Z}|+\log\left(\Pr(B=1)_{\Theta}\right)\leq 2\log\frac{1}{\varepsilon}.

Additionally if $\tau_{M}=\rho_{M}$ , we further have,

\log|\mathcal{X}|-\log|\mathcal{Z}|+\log\left(\Pr(A=1,B=1)_{(V_{A}\otimes V_{B})\tau(V_{A}\otimes V_{B})^{\dagger}}\right)\leq 2\log\frac{1}{\varepsilon}.

Symmetric results follow for a $\mathcal{Y}$ -two-wise independent function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ by exchanging $(N,A,X)\leftrightarrow(M,B,Y)$ above.

Proof.

From Fact 19, there exists operator $C_{YM}$ such that $0\leq C^{\dagger}_{YM}C_{YM}\leq\mathrm{I}_{YM}$ and,

\Phi_{ZXYM^{\prime}}=\frac{C_{YM}\rho_{ZXYM}C_{YM}^{\dagger}}{\mathrm{Tr}C_{YM}\rho_{ZXYM}C_{YM}^{\dagger}}\quad;\quad\Pr(B=1)_{\Theta}=\mathrm{Tr}C_{YM}\rho_{YM}C_{YM}^{\dagger}.

This implies,

\Phi_{ZYM^{\prime}}=\frac{C_{YM}\rho_{ZYM}C_{YM}^{\dagger}}{\mathrm{Tr}C_{YM}\rho_{ZYM}C_{YM}^{\dagger}}.

Define $C\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{I}_{Z}\otimes C_{YM}$ and $D\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{I}_{Z}\otimes\rho_{YM}^{1/4}$ . Consider (below we use cyclicity of trace, Fact 16, several times without mentioning),

$\displaystyle\\|CD\\|^{4}_{4}$	$\displaystyle=\mathrm{Tr}(\mathrm{I}_{Z}\otimes\rho_{YM}^{1/4}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/4})^{2}$	(Fact 3)
	$\displaystyle=\|\mathcal{Z}\|\cdot\mathrm{Tr}(\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM})$
	$\displaystyle\leq\|\mathcal{Z}\|\cdot\\|\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}\\|_{1}\\|C^{\dagger}_{YM}C_{YM}\\|_{\infty}$	(Fact 14)
	$\displaystyle\leq\|\mathcal{Z}\|\cdot\\|\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}\\|_{1}$	( $\\|C^{\dagger}_{YM}C_{YM}\\|_{\infty}\leq 1$ )
	$\displaystyle=\|\mathcal{Z}\|\cdot\mathrm{Tr}(\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2})$	( $\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}\geq 0$ )
	$\displaystyle=\|\mathcal{Z}\|\cdot\mathrm{Tr}(C_{YM}\rho_{YM}C^{\dagger}_{YM})$
	$\displaystyle=\|\mathcal{Z}\|\cdot\Pr(B=1)_{\Theta}.$

Consider,

	$\displaystyle\\|\Phi_{ZYM^{\prime}}-U_{Z}\otimes\Phi_{YM^{\prime}}\\|^{2}_{1}$
	$\displaystyle=\frac{1}{(\Pr(B=1)_{\Theta})^{2}}\\|C(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})C^{\dagger}\\|^{2}_{1}$
	$\displaystyle=\frac{1}{(\Pr(B=1)_{\Theta})^{2}}\\|CDD^{-1}(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})D^{-1}DC^{\dagger}\\|^{2}_{1}$
	$\displaystyle\leq\frac{1}{(\Pr(B=1)_{\Theta})^{2}}\\|CD\\|^{4}_{4}\ \\|D^{-1}(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})D^{-1}\\|^{2}_{2}$	(Fact 15)
	$\displaystyle\leq\frac{\|\mathcal{Z}\|\cdot\Pr(B=1)_{\Theta}}{(\Pr(B=1)_{\Theta})^{2}}\cdot\\|D^{-1}(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})D^{-1}\\|^{2}_{2}$
	$\displaystyle\leq\frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot\\|(\mathrm{I}_{Z}\otimes\rho_{YM}^{-1/4})(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})(\mathrm{I}_{Z}\otimes\rho_{YM}^{-1/4})\\|^{2}_{2}$
	$\displaystyle=\frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot\mathbb{E}_{y\leftarrow\rho_{Y}}\left[\\|(\mathrm{I}_{Z}\otimes\rho_{M}^{-1/4})(\rho^{y}_{ZM}-U_{Z}\otimes\rho_{M})(\mathrm{I}_{Z}\otimes\rho_{M}^{-1/4})\\|^{2}_{2}\right]$
	$\displaystyle=\frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot\mathbb{E}_{y\leftarrow\rho_{Y}}\left[\mathrm{Tr}\left((\mathrm{I}_{Z}\otimes\rho_{M}^{-1/2})(\rho^{y}_{ZM}-U_{Z}\otimes\rho_{M})\right)^{2}\right]$
	$\displaystyle\leq\ \frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot 2^{-\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle\|M\right)_{\rho}}.$	(Fact 21)

We get the first result by taking $\log$ on both sides and rearranging terms.

Now, let $\rho_{M}=\tau_{M}$ . Noting $\tau_{M}=(V_{A}\tau V^{\dagger}_{A})_{M}$ and using Fact 25, with the following assignment of terms (below the terms on the left are from Fact 25 and the terms on the right are from this proof)

(\rho_{ABC},\hat{\rho}_{AB})\leftarrow((V_{A}\tau V^{\dagger}_{A})_{XMA},\rho_{XM}),

we get

\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|M\right)_{\rho}\geq\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|M\right)_{(V_{A}\tau V^{\dagger}_{A})}+\log(\Pr(A=1)_{(V_{A}\tau V^{\dagger}_{A})})=\log|\mathcal{X}|+\log(\Pr(A=1)_{(V_{A}\tau V^{\dagger}_{A})}).

We get the second result now by noting,

\Pr(A=1)_{(V_{A}\tau V^{\dagger}_{A})}\cdot\Pr(B=1)_{\Theta}=\Pr(A=1,B=1)_{(V_{A}\otimes V_{B})(\tau)(V_{A}\otimes V_{B})^{\dagger}}.

∎

Lemma 2.

Let $p=2^{m}$ and $n^{\prime}=n\log p$ . Let $\rho_{X\hat{X}NY\hat{Y}M}$ be a pure state such that $|X|=|\hat{X}|=|Y|=|\hat{Y}|=n^{\prime}$ , $XY$ classical (with copies $\hat{X}\hat{Y}$ respectively) and

\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle|Y\hat{Y}M\right)_{\rho}\geq k_{1}\quad;\quad\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|X\hat{X}N\right)_{\rho}\geq k_{2}.

Let $Z=\mathsf{IP}^{n}_{p}(X,Y)$ . Then $\rho$ is also an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ (see Definition 3) for some $l\leq 2n^{\prime}-k_{1}-k_{2}.$ Furthermore,

\|\rho_{ZXN}-U_{m}\otimes\rho_{XN}\|_{1}\leq\varepsilon\quad;\quad\|\rho_{ZYM}-U_{m}\otimes\rho_{YM}\|_{1}\leq\varepsilon,

for parameters $k_{1}+k_{2}\geq n^{\prime}+m+2\log\left(\frac{1}{\varepsilon}\right).$

Proof.

Simulation of the state $\rho$ in the model of $l\mathchar 45\relax\mathsf{qma}$ follows from Claim 3. Using Claim 3, with the following assignment of registers (below the registers on the left are from Claim 3 and the registers on the right are the registers in this proof)

(X,Y,X^{\prime},Y^{\prime},A,B,\Phi)\leftarrow(X,Y,\hat{X},\hat{Y},N,M,\rho),

we have

l\leq\log(2^{n^{\prime}-k_{1}+n^{\prime}-k_{2}})=2n^{\prime}-k_{1}-k_{2}.

Let $X\in\mathcal{X},Y\in\mathcal{Y}$ . Note that $\mathsf{IP}^{n}_{p}$ is a $\mathcal{X}$ -two-wise independent function. Further state $\rho_{X\hat{X}NY\hat{Y}M}$ is an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ with $(\tau_{M},\rho_{M})$ in Theorem 4 equivalent to $(\rho_{Y\hat{Y}M},\rho_{Y\hat{Y}M})$ in the simulation of the state $\rho$ using Claim 3. Let $\varepsilon^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}2\Delta(\rho_{ZYM}\;;\;U_{Z}\otimes\rho_{YM})$ . Using Theorem 4, we get $\varepsilon^{\prime}\leq 2^{\frac{-(k_{1}+k_{2}-n^{\prime}-m)}{2}}$ . For the choice of parameters $k_{1}+k_{2}\geq n^{\prime}+m+2\log\left(\frac{1}{\varepsilon}\right),$ we get $\varepsilon^{\prime}\leq\varepsilon.$ Thus, $\|\rho_{ZYM}-U_{Z}\otimes\rho_{YM}\|_{1}\leq\varepsilon.$ Symmetric result follows noting $\mathsf{IP}^{n}_{p}$ is also a $\mathcal{Y}$ -two-wise independent function.

∎

Using Lemma 2 as a key ingredient, [BJK22] showed that inner-product extractor (in fact a general class of $\mathcal{X}$ -two-wise independent function (Definition 16 [4])) of Chor and Goldreich [CG85] is secure against $\mathsf{qpa\mathchar 45\relax state}$ . We state the result from [BJK22] as follows.

Fact 30 ([BJK22]).

Let $p=2^{m}$ and $n^{\prime}=n\log p$ . Let $\rho_{X\hat{X}NY\hat{Y}M}$ be a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ such that $|X|=|\hat{X}|=|Y|=|\hat{Y}|=n^{\prime}$ and $XY$ classical (with copies $\hat{X}\hat{Y}$ respectively). Let $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ be a $\mathcal{X}$ -two-wise independent function such that $\mathcal{X}=\mathcal{Y}=\mathbb{F}_{p}^{n}$ , $\mathcal{Z}=\mathbb{F}_{p}$ and $(X,Y)\in(\mathcal{X},\mathcal{Y})$ . Let $Z=f(X,Y)\in\mathcal{Z}$ . Then,

\|\rho_{ZYM}-U_{m}\otimes\rho_{YM}\|_{1}\leq\varepsilon,

for parameters $k_{1}+k_{2}\geq n^{\prime}+m+40+8\log\left(\frac{1}{\varepsilon}\right).$

Symmetric results follow for a $\mathcal{Y}$ -two-wise independent function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ by exchanging $(N,X)\leftrightarrow(M,Y)$ above.

Theorem 5.

\|\rho_{ZYM}-U_{m}\otimes\rho_{YM}\|_{1}\leq\varepsilon,

for parameters $l\leq\left(n^{\prime}-m-40+8\log\left(\varepsilon\right)\right)/2.$

Symmetric results follow for a $\mathcal{Y}$ -two-wise independent function $f:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$ by exchanging $(N,X)\leftrightarrow(M,Y)$ above.

Proof.

The proof follows from Fact 30 after noting Fact 1. ∎

We also get a tight efficiency (Definition 21) lower bound for a $\mathcal{X}$ -two-wise independent function.

Corollary 4 (Efficiency lower bound for a $\mathcal{X}$ -two-wise independent function).

\log\left(\tilde{\mathsf{eff}}_{\gamma}(f,U)\right)\geq\frac{1}{2}\left(\log|\mathcal{X}|-\log|\mathcal{Z}|-40+8\log\left(1-\gamma-\frac{1}{|\mathcal{Z}|}\right)\right).

Proof.

Let the inputs $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$ be given to Alice and Bob respectively according to distribution $U$ . Consider an optimal zero-communication protocol $\Pi$ with error of protocol under $U$ on non-abort being $\gamma$ . Let the state shared between Alice and Bob after their local operations be $\tau_{XN^{\prime}M^{\prime}YAB}$ . Let $\perp$ represent the abort symbol. Let $\Pr(A=\perp\vee B=\perp)_{\tau}\leq 1-\eta,$ and

\Phi_{XN^{\prime}M^{\prime}YAB}=(\tau_{XN^{\prime}M^{\prime}YAB}|A\neq\perp\wedge B\neq\perp)\enspace,

where Alices holds $XN^{\prime}A$ and Bob holds $M^{\prime}YB$ . We have,

\Pr(B\neq f(X,Y))_{\Phi}\leq\gamma\hskip 20.00003pt\implies\hskip 20.00003pt\Pr(B=f(X,Y))_{\Phi}\geq 1-\gamma.

Let $\|\Phi_{BYM^{\prime}}-U_{\log|\mathcal{Z}|}\otimes\Phi_{YM^{\prime}}\|_{1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\varepsilon$ . This implies, $1-\gamma\leq\Pr(B=f(X,Y))_{\Phi}\leq\frac{1}{|\mathcal{Z}|}+\varepsilon$ . Noting $A\neq\perp$ (here) as $A=1$ (in Definition 3), $B\neq\perp$ (here) as $B=1$ (in Definition 3), state $\Phi$ is an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ with $l=\log\left(\frac{1}{\Pr(A\neq\perp\wedge B\neq\perp)_{\tau}}\right).$ Since, $\|\Phi_{BYM^{\prime}}-U_{\log|\mathcal{Z}|}\otimes\Phi_{YM^{\prime}}\|_{1}=\varepsilon\geq 1-\gamma-\frac{1}{|\mathcal{Z}|}$ , using Theorem 5 we have

\log\left(\tilde{\mathsf{eff}}_{\gamma}(f,U)\right)\geq\log\left(\frac{1}{\Pr(A\neq\perp\wedge B\neq\perp)_{\tau}}\right)\geq\frac{1}{2}\left(\log|\mathcal{X}|-\log|\mathcal{Z}|-40+8\log\left(1-\gamma-\frac{1}{|\mathcal{Z}|}\right)\right)

which gives the desired.

∎

From Fact 29, and noting that the (generalized) inner-product function is a $\mathcal{X}$ -two-wise independent function (note $\mathcal{X}=\mathbb{F}^{n}_{p}$ ), we have,

Corollary 5.

Let $\mathsf{IP}^{n}_{p}:\mathbb{F}^{n}_{p}\times\mathbb{F}^{n}_{p}\to\mathbb{F}_{p}$ be defined as,

\mathsf{IP}_{p}^{n}(x,y)=\sum_{i=1}^{n}x_{i}y_{i}\mod p\enspace.

We have,

\mathcal{Q}_{\gamma}(\mathsf{IP}_{p}^{n})\geq\frac{(n-1)\log p}{4}+\log\left(1-\gamma-\frac{1}{p}\right)-20\enspace.

Corollary 6.

\|\rho_{ZXN}-U_{m}\otimes\rho_{XN}\|_{1}\leq\varepsilon\quad;\quad\|\rho_{ZYM}-U_{m}\otimes\rho_{YM}\|_{1}\leq\varepsilon,

for parameters $k_{1}+k_{2}\geq n^{\prime}+m+40+8\log\left(\frac{1}{\varepsilon}\right).$

Proof.

Let $X\in\mathcal{X},Y\in\mathcal{Y}$ such that $\mathcal{X}=\mathcal{Y}=\mathbb{F}_{p}^{n}$ . The result follows from Fact 30 and noting that $\mathsf{IP}^{n}_{p}$ is both $\mathcal{X}$ -two-wise independent function and $\mathcal{Y}$ -two-wise independent function. ∎

Corollary 7.

Let $p=2^{m}$ and $n^{\prime}=n\log p$ . Let $\sigma_{XEY}=\sigma_{XE}\otimes\sigma_{Y}$ such that $\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\sigma}\geq k_{1}$ , $\mathrm{H}_{\min}(Y)_{\sigma}\geq k_{2}$ and $|X|=|Y|={n^{\prime}}$ . Let $Z=\mathsf{IP}^{n}_{p}(X,Y)$ . Then,

\|\sigma_{ZXE}-U_{m}\otimes\sigma_{XE}\|_{1}\leq\varepsilon,

for parameters $k_{1}+k_{2}\geq n^{\prime}+m+40+8\log\left(\frac{1}{\varepsilon}\right).$

Proof.

Consider $\sigma_{X\hat{X}\hat{E}EY\hat{Y}}=\sigma_{X\hat{X}\hat{E}E}\otimes\sigma_{Y\hat{Y}}$ , the purification of $\sigma_{XEY}$ such that $\sigma_{X\hat{X}\hat{E}E}$ is the canonical purification of $\sigma_{XE}$ and $\sigma_{Y\hat{Y}}$ is the canonical purification of $\sigma_{Y}$ . Note $\sigma$ is a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ . Now, the result follows from Corollary 6. ∎

4 $\mathsf{qma}$ can simulate other adversaries

We show how $\mathsf{qma}$ can simulate all adversaries known in the literature and $\mathsf{qca}$ as well. By simulation we mean that the quantum side information of an adversary can be generated by $\mathsf{qma}$ . More precisely,

Definition 22 (Simulation).

Let $\rho_{XEY}$ be the final state generated appropriately in the adversary model, adversary holds $\rho_{E}$ . We say $\rho_{XEY}$ can be simulated by $\mathsf{qma}$ for parameter $l$ , if there exists an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state},$ $\Phi_{X\hat{X}NMEY\hat{Y}}$ ( $\mathsf{qma}$ gets registers $EM$ ¹⁰¹⁰10This amounts to giving more quantum side information ( $ME$ ) than other adversary model provide ( $E$ ).) and $\Phi_{XYE}=\rho_{XYE}$ . Analogously, we say $\rho_{XEY}$ can be simulated $\varepsilon\mathchar 45\relax$ approximately by $\mathsf{qma}$ for parameter $l$ , if there exists an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state},$ $\Phi_{X\hat{X}NMEY\hat{Y}}$ and $\Phi_{XYE}\approx_{\varepsilon}\rho_{XYE}$ .

Theorem 6.

Quantum side information of $(b_{1},b_{2})$ - $\mathsf{qbsa}$ (see Definition 23), $(k_{1},k_{2})$ - $\mathsf{qia}$ (see Definition 24), $(k_{1},k_{2})$ - $\mathsf{gea}$ (see Definition 25) acting on an $(n,k^{\prime}_{1},k^{\prime}_{2})$ -source can be simulated by an $l\mathchar 45\relax\mathsf{qma}$ for some $l\leq 2\min\{b_{1},b_{2}\}+2n-k^{\prime}_{1}-k^{\prime}_{2}$ , $l\leq 2n-k_{1}-k_{2}$ , $l\leq 2n-k_{1}-k_{2}$ respectively.

Proof.

The proof follows from Claims 4, 5, 6, 7 and 8. ∎

4.1 Quantum bounded storage adversary

Kasher and Kempe [KK10] introduced the quantum bounded storage adversary ( $\mathsf{qbsa}$ ) model, where the adversary obtains quantum side information of bounded memory from both sources.

Definition 23 ( $(b_{1},b_{2})$ - $\mathsf{qbsa}$ [KK10]).

Let $\tau_{X\hat{X}}$ , $\tau_{Y\hat{Y}}$ be the canonical purifications of independent sources $X,Y$ respectively (registers $\hat{X}\hat{Y}$ with Reference).

1.

Alice and Bob hold $X,Y$ respectively. They also share an entangled pure state $\phi_{NM}$ (Alice holds $N$ , Bob holds $M$ ).

Alice applies a CPTP map $\psi_{A}:\mathcal{L}(\mathcal{H}_{X}\otimes\mathcal{H}_{N})\rightarrow\mathcal{L}(\mathcal{H}_{X}\otimes\mathcal{H}_{N^{\prime}})$ and Bob applies a CPTP map $\psi_{B}:\mathcal{L}(\mathcal{H}_{Y}\otimes\mathcal{H}_{M})\rightarrow\mathcal{L}(\mathcal{H}_{Y}\otimes\mathcal{H}_{M^{\prime}})$ . Let

\rho_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}=(\psi_{A}\otimes\psi_{B})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}}).

3.

Adversary gets access to $\rho_{N^{\prime}M^{\prime}}$ with $\log\dim(\mathcal{H}_{N^{\prime}})\leq b_{1}$ , $\log\dim(\mathcal{H}_{M^{\prime}})\leq b_{2}$ respectively.

We show how to simulate a $(b_{1},b_{2})$ - $\mathsf{qbsa}$ in the model of an $l\mathchar 45\relax\mathsf{qma}$ .

Claim 4.

A $(b_{1},b_{2})$ - $\mathsf{qbsa}$ acting on an $(n,k_{1},k_{2})$ -source can be simulated by an $l\mathchar 45\relax\mathsf{qma}$ for some $l\leq 2\min\{b_{1},b_{2}\}+2n-k_{1}-k_{2}$ .

Proof.

Let $V_{A}:\mathcal{H}_{X}\otimes\mathcal{H}_{N}\rightarrow\mathcal{H}_{X}\otimes\mathcal{H}_{N^{\prime}}\otimes\mathcal{H}_{\hat{N^{\prime}}}$ , $V_{B}:\mathcal{H}_{Y}\otimes\mathcal{H}_{M}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{M^{\prime}}\otimes\mathcal{H}_{\hat{M^{\prime}}}$ be the Stinespring isometry extensions of CPTP maps $\psi_{A}$ , $\psi_{B}$ respectively i.e. $\psi_{A}(\theta)=\mathrm{Tr}_{\hat{N^{\prime}}}(V_{A}\theta V_{A}^{\dagger})$ for every state $\theta_{XN}$ and $\psi_{B}(\theta)=\mathrm{Tr}_{\hat{M^{\prime}}}(V_{B}\theta V_{B}^{\dagger})$ for every state $\theta_{YM}$ . Let

\rho^{A}_{X\hat{X}N^{\prime}\hat{N^{\prime}}M}=(V_{A}\otimes\mathrm{I})(\tau_{X\hat{X}}\otimes\phi_{NM})(V_{A}\otimes\mathrm{I})^{\dagger},

\rho_{X\hat{X}N^{\prime}\hat{N^{\prime}}M^{\prime}\hat{M^{\prime}}Y\hat{Y}}=(V_{A}\otimes V_{B})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}})(V_{A}\otimes V_{B})^{\dagger}.

Note $\rho^{A}_{\hat{X}N^{\prime}M}$ is such that $\rho^{A}_{\hat{X}M}=\tau_{\hat{X}}\otimes\phi_{M}.$ Thus, from Fact 5, we have $\mathrm{I}_{\max}(\hat{X}:N^{\prime}M)_{\rho^{A}}\leq 2\log(\dim(\mathcal{H}_{N^{\prime}}))\leq 2b_{1}$ . Let $\sigma_{N^{\prime}M}$ be such that

\mathrm{D}_{\max}\>\!\!\left(\rho^{A}_{\hat{X}N^{\prime}M}\middle\|\rho^{A}_{\hat{X}}\otimes\sigma_{N^{\prime}M}\right)\leq 2b_{1}.

Also, note $\rho^{A}_{\hat{X}}=\tau_{\hat{X}}\leq 2^{-k_{1}}\mathrm{I}_{\hat{X}}.$ The inequality follows since the min-entropy of $\tau_{X}$ is at least $k_{1}$ and $\tau_{\hat{X}}$ is canonical purification of $\tau_{X}$ . Thus, we further have

\mathrm{D}_{\max}\>\!\!\left(\rho^{A}_{\hat{X}MN^{\prime}}\middle\|\mathrm{I}_{\hat{X}}\otimes\sigma_{MN^{\prime}}\right)\leq 2b_{1}-k_{1}.

Thus $\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}M\right)_{\rho^{A}}=\mathrm{H}_{\min}\>\!\!\left(\hat{X}\middle|N^{\prime}M\right)_{\rho^{A}}\geq k_{1}-2b_{1}$ . Note the first equality is because $\rho^{A}_{XN^{\prime}M}=\rho^{A}_{\hat{X}N^{\prime}M}$ . Using Fact 8, we further have

\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}M^{\prime}\hat{M^{\prime}}Y\hat{Y}\right)_{\rho}\geq\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}M\right)_{\rho^{A}}\geq k_{1}-2b_{1}.

Note $\mathrm{D}_{\max}\>\!\!\left(\rho_{\hat{Y}X\hat{X}\hat{N^{\prime}}}\middle\|U_{\hat{Y}}\otimes\rho_{X\hat{X}\hat{N^{\prime}}}\right)\leq n-k_{2}$ since $\rho_{\hat{Y}X\hat{X}\hat{N^{\prime}}}=\tau_{\hat{Y}}\otimes\rho_{X\hat{X}\hat{N^{\prime}}}$ , the min-entropy of $\tau_{Y}$ is at least $k_{2}$ and $\tau_{\hat{Y}}$ is canonical purification of $\tau_{Y}$ . Thus $\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|X\hat{X}\hat{N^{\prime}}\right)_{\rho}=\mathrm{\tilde{H}}_{\min}\>\!\!\left(\hat{Y}\middle|X\hat{X}\hat{N^{\prime}}\right)_{\rho}\geq k_{2}$ . Note the first equality is because $\rho_{YX\hat{X}\hat{N^{\prime}}}=\rho_{\hat{Y}X\hat{X}\hat{N^{\prime}}}$ .

Simulation of the state $\rho$ in the model of $l\mathchar 45\relax\mathsf{qma}$ follows from Lemma 1. Using Lemma 1, with the following assignment of registers (below the registers on the left are from Lemma 1 and the registers on the right are the registers in this proof)

(X,Y,\hat{X},\hat{Y},N,M,\rho)\leftarrow(X,Y,\hat{X},\hat{Y},\hat{N^{\prime}},N^{\prime}M^{\prime}\hat{M^{\prime}},\rho),

we have $l\leq 2n+2b_{1}-k_{1}-k_{2}.$

A similar argument can be given by exchanging the roles of Alice and Bob. The desired follows. ∎

As a corollary, we reproduce the security of one-bit output inner-product against $(b_{1},b_{2})\mathchar 45\relax\mathsf{qbsa}$ acting on $(n,k_{1},k_{2})$ -source from [KK10] as follows.

Corollary 8 ([KK10]).

An $(n,n,1)$ - $2$ -source extractor $\mathsf{IP}^{n}_{2}:\{0,1\}^{n}\times\{0,1\}^{n}\to\{0,1\}$ is $(b_{1},b_{2},\varepsilon)$ -quantum secure against $\mathsf{qbsa}$ on $(n,k_{1},k_{2})$ -source for parameters $k_{1}+k_{2}-2\min{\{b_{1},b_{2}\}}\geq n+41+8\log(1/\varepsilon).$

Proof.

The proof follows from Claim 4 (noting $l\mathchar 45\relax\mathsf{qma}$ is also a $(k_{1}-2b_{1},k_{2})\mathchar 45\relax\mathsf{qpa}$ or $(k_{1},k_{2}-2b_{2})\mathchar 45\relax\mathsf{qpa}$ ) and Corollary 6. ∎

4.2 Quantum independent adversary

Kasher and Kempe [KK10] introduced the quantum independent adversary ( $\mathsf{qia}$ ) model, where the adversary obtains independent side information from both sources.

Definition 24 ( $(k_{1},k_{2})$ - $\mathsf{qia}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{qia\mathchar 45\relax state}$ [KK10]).

Let $\tau_{X\hat{X}}$ , $\tau_{Y\hat{Y}}$ be the canonical purifications of independent sources $X,Y$ respectively (registers $\hat{X}\hat{Y}$ with Reference).

1.

Alice and Bob hold $X,Y$ respectively. They also share a product state $\phi_{NM}=\phi_{N}\otimes\phi_{M}$ (Alice holds $N$ and Bob holds $M$ ).

Alice applies CPTP map $\psi_{A}:\mathcal{L}(\mathcal{H}_{X}\otimes\mathcal{H}_{N})\rightarrow\mathcal{L}(\mathcal{H}_{X}\otimes\mathcal{H}_{N^{\prime}})$ and Bob applies CPTP map $\psi_{B}:\mathcal{L}(\mathcal{H}_{Y}\otimes\mathcal{H}_{M})\rightarrow\mathcal{L}(\mathcal{H}_{Y}\otimes\mathcal{H}_{M^{\prime}})$ . Let

\rho_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}=(\psi_{A}\otimes\psi_{B})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}})\quad\quad;\quad\quad\rho_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}=\rho_{X\hat{X}N^{\prime}}\otimes\rho_{M^{\prime}\hat{Y}Y},

with $\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}\right)_{\rho}\geq k_{1}$ and $\mathrm{H}_{\min}\>\!\!\left(Y\middle|M^{\prime}\right)_{\rho}\geq k_{2}$ .

3.

Adversary gets access to $\rho_{N^{\prime}M^{\prime}}$ . The state $\rho$ is called a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qia\mathchar 45\relax state}$ .

We show how to simulate a $(k_{1},k_{2})$ - $\mathsf{qia}$ in the model of an $l\mathchar 45\relax\mathsf{qma}$ .

Claim 5.

A $(k_{1},k_{2})$ - $\mathsf{qia\mathchar 45\relax state}$ is an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ for some $l\leq 2n-k_{1}-k_{2}$ .

Proof.

Let $V_{A}:\mathcal{H}_{X}\otimes\mathcal{H}_{N}\rightarrow\mathcal{H}_{X}\otimes\mathcal{H}_{N^{\prime}}\otimes\mathcal{H}_{\hat{N^{\prime}}}$ , $V_{B}:\mathcal{H}_{Y}\otimes\mathcal{H}_{M}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{M^{\prime}}\otimes\mathcal{H}_{\hat{M^{\prime}}}$ be the Stinespring isometry extensions of CPTP maps $\psi_{A}$ , $\psi_{B}$ respectively. Let $\phi_{N\hat{N}M\hat{M}}=\phi_{N\hat{N}}\otimes\phi_{M\hat{M}}$ be the purification of $\phi_{NM}$ . Let

\rho_{X\hat{X}N^{\prime}\hat{N^{\prime}}\hat{N}M^{\prime}\hat{M^{\prime}}\hat{M}Y\hat{Y}}=(V_{A}\otimes V_{B})(\tau_{X\hat{X}}\otimes\phi_{N\hat{N}M\hat{M}}\otimes\tau_{Y\hat{Y}})(V_{A}\otimes V_{B})^{\dagger}.

Since $\rho_{X\hat{X}N^{\prime}\hat{N^{\prime}}\hat{N}M^{\prime}\hat{M^{\prime}}\hat{M}Y\hat{Y}}=\rho_{X\hat{X}N^{\prime}\hat{N^{\prime}}\hat{N}}\otimes\rho_{M^{\prime}\hat{M^{\prime}}\hat{M}\hat{Y}Y},$ we have the conditional-min-entropy bound

\mathrm{H}_{\min}\>\!\!\left(X\middle|Y\hat{Y}M^{\prime}\hat{M^{\prime}}\hat{M}N^{\prime}\right)_{\rho}=\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}\right)_{\rho}\geq k_{1}.

Also, since $\mathrm{H}_{\min}\>\!\!\left(Y\middle|M^{\prime}\right)_{\rho}\geq k_{2}$ , using Fact 8, we have $\mathrm{H}_{\min}({Y})_{\rho}\geq k_{2}$ . Since $\rho_{YX\hat{X}\hat{N^{\prime}}\hat{N}}=\rho_{Y}\otimes\rho_{X\hat{X}\hat{N^{\prime}}\hat{N}},$ we have

\mathrm{D}_{\max}\>\!\!\left(\rho_{YX\hat{X}\hat{N^{\prime}}\hat{N}}\middle\|U_{Y}\otimes\rho_{X\hat{X}\hat{N^{\prime}}\hat{N}}\right)\leq\log(\dim(\mathcal{H}_{Y}))-k_{2}=n-k_{2}.

Thus, $\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|X\hat{X}\hat{N^{\prime}}\hat{N}\right)_{\rho}\geq k_{2}$ .

(X,Y,\hat{X},\hat{Y},N,M,\rho)\leftarrow(X,Y,\hat{X},\hat{Y},\hat{N^{\prime}}\hat{N},M^{\prime}\hat{M^{\prime}}\hat{M}N^{\prime},\rho),

we have $l\leq 2n-k_{1}-k_{2}.$

∎

4.3 General entangled adversary

Chung, Li and Wu [CLW14] introduced general entangled adversary ( $\mathsf{gea}$ ) defined as follows:

Definition 25 ( $(k_{1},k_{2})$ - $\mathsf{gea}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{gea\mathchar 45\relax state}$ [CLW14]).

Let $\tau_{X\hat{X}}$ , $\tau_{Y\hat{Y}}$ be the canonical purifications of independent sources $X,Y$ respectively (registers $\hat{X}\hat{Y}$ with Reference).

1.

Alice and Bob hold $X,Y$ respectively. They also hold entangled pure state $\phi_{NM}$ (Alice holds $N$ , Bob holds $M$ ).

\rho^{A}_{X\hat{X}N^{\prime}MY\hat{Y}}=(\psi_{A}\otimes\mathrm{I})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}}),

\rho^{B}_{X\hat{X}NM^{\prime}Y\hat{Y}}=(\mathrm{I}\otimes\psi_{B})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}}),

\rho_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}=(\psi_{A}\otimes\psi_{B})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}})=(\mathrm{I}\otimes\psi_{B})\rho^{A}_{XN^{\prime}MY},

with $\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}M\right)_{\rho^{A}}\geq k_{1}$ and $\mathrm{H}_{\min}\>\!\!\left(Y\middle|NM^{\prime}\right)_{\rho^{B}}\geq k_{2}$ .

3.

Adversary gets access to $\rho_{N^{\prime}M^{\prime}}$ . The state $\rho$ is called a $(k_{1},k_{2})\mathchar 45\relax\mathsf{gea\mathchar 45\relax state}$ .

We show how to simulate a $(k_{1},k_{2})$ - $\mathsf{gea}$ in the model of an $l\mathchar 45\relax\mathsf{qma}$ .

Claim 6.

A $(k_{1},k_{2})$ - $\mathsf{gea\mathchar 45\relax state}$ is an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ for some $l\leq 2n-k_{1}-k_{2}$ .

Proof.

\rho_{X\hat{X}N^{\prime}\hat{N^{\prime}}M^{\prime}\hat{M^{\prime}}Y\hat{Y}}=(V_{A}\otimes V_{B})(\tau_{X\hat{X}}\otimes\phi_{NM}\otimes\tau_{Y\hat{Y}})(V_{A}\otimes V_{B})^{\dagger}.

Let

\rho^{A}_{X\hat{X}N^{\prime}\hat{N^{\prime}}M}=(V_{A}\otimes\mathrm{I})(\tau_{X\hat{X}}\otimes\phi_{NM})(V_{A}\otimes\mathrm{I})^{\dagger}\quad;\quad\rho^{B}_{NY\hat{Y}M^{\prime}\hat{M^{\prime}}}=(\mathrm{I}\otimes V_{B})(\phi_{NM}\otimes\tau_{Y\hat{Y}})(\mathrm{I}\otimes V_{B})^{\dagger}.

Note $\rho^{A}_{X\hat{X}N^{\prime}\hat{N^{\prime}}M}$ is the purification of $\rho^{A}_{X\hat{X}N^{\prime}M}$ . From $\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}M\right)_{\rho^{A}}\geq k_{1}$ and from Fact 8 it follows that

\mathrm{H}_{\min}\>\!\!\left(X\middle|N^{\prime}M^{\prime}\hat{M^{\prime}}Y\hat{Y}\right)_{\rho}\geq k_{1}.

Also, since $\mathrm{H}_{\min}\>\!\!\left(Y\middle|NM^{\prime}\right)_{\rho^{B}}\geq k_{2}$ , using Fact 8, we have $\mathrm{H}_{\min}({Y})_{\rho^{B}}\geq k_{2}$ . Noting $\rho^{B}_{YN}=\rho^{B}_{Y}\otimes\rho^{B}_{N}$ (since $V_{B}$ is safe on register $Y$ ), we have

\mathrm{D}_{\max}\>\!\!\left(\rho^{B}_{YN}\middle\|U_{Y}\otimes\rho^{B}_{N}\right)\leq\log(\dim(\mathcal{H}_{Y}))-k_{2}=n-k_{2}.

Using Fact 11, we have

\mathrm{D}_{\max}\>\!\!\left(\rho_{YX\hat{X}\hat{N^{\prime}}}\middle\|U_{Y}\otimes\rho_{X\hat{X}\hat{N^{\prime}}}\right)\leq n-k_{2}.

Thus, $\mathrm{\tilde{H}}_{\min}\>\!\!\left(Y\middle|X\hat{X}\hat{N^{\prime}}\right)_{\rho}\geq k_{2}$ .

(X,Y,\hat{X},\hat{Y},N,M,\rho)\leftarrow(X,Y,\hat{X},\hat{Y},\hat{N^{\prime}},N^{\prime}M^{\prime}\hat{M^{\prime}},\rho),

we have $l\leq 2n-k_{1}-k_{2}.$

∎

4.4 Quantum Markov adversary

Arnon-Friedman, Portmann and Scholz [AFPS16] introduced quantum Markov adversary
( $\mathsf{qMara}$ ), such that adversary’s side information forms a Markov-chain with the both sources.

Definition 26 ( $(k_{1},k_{2})$ - $\mathsf{qMara}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{qMara\mathchar 45\relax state}$ ) [AFPS16]).

Let $\rho_{XEY}$ be a Markov-chain $(X-E-Y)_{\rho}$ with $\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}\geq k_{1}$ and $\mathrm{H}_{\min}\>\!\!\left(Y\middle|E\right)_{\rho}\geq k_{2}$ . Adversary gets access to quantum register $E$ . The state $\rho$ is called a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qMara\mathchar 45\relax state}$ .

Claim 7.

A $(k_{1},k_{2})$ - $\mathsf{qMara\mathchar 45\relax state}$ can be simulated $\varepsilon$ -approximately by an $l\mathchar 45\relax\mathsf{qma}$ for some $l\leq 2n-k_{1}-k_{2}+25+6\log(1/\varepsilon)$ .

Proof.

From Fact 12,

\rho_{XEY}=\sum_{t}\Pr(T=t)|t\rangle\langle t|\otimes\left(\rho^{t}_{XE_{1}}\otimes\rho^{t}_{YE_{2}}\right),

where $T$ is some classical register over finite alphabet. Let $\rho_{X\hat{X}T\hat{T}E_{1}\hat{E_{1}}E_{2}\hat{E_{2}}Y\hat{Y}}$ be a pure state extension of $\rho_{XEY}\equiv\rho_{XE_{1}TE_{2}Y}$ such that,

\rho_{X\hat{X}T\hat{T}E_{1}\hat{E_{1}}E_{2}\hat{E_{2}}Y\hat{Y}}=\sum_{t}\sqrt{\Pr(T=t)}|tt\rangle_{T\hat{T}}|\rho\rangle_{X\hat{X}E_{1}\hat{E_{1}}E_{2}\hat{E_{2}}Y\hat{Y}}^{t},

\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}\geq k_{1}\quad;\quad\mathrm{H}_{\min}\>\!\!\left(Y\middle|E\right)_{\rho}\geq k_{2},

registers ( $XYT$ ) are classical (with copies $\hat{X}\hat{Y}\hat{T}$ ) and $|\rho\rangle_{X\hat{X}E_{1}\hat{E_{1}}E_{2}\hat{E_{2}}Y\hat{Y}}^{t}=|\rho\rangle_{X\hat{X}E_{1}\hat{E_{1}}}^{t}\otimes|\rho\rangle_{E_{2}\hat{E_{2}}Y\hat{Y}}^{t}$ . Additionally, note for every $T=t$ , $|\rho\rangle_{X\hat{X}E_{1}\hat{E_{1}}}^{t}\otimes|\rho\rangle_{E_{2}\hat{E_{2}}Y\hat{Y}}^{t}$ is the pure state extension of $\rho^{t}_{XE_{1}}\otimes\rho^{t}_{YE_{2}}$ with $|\rho\rangle_{X\hat{X}E_{1}\hat{E_{1}}}^{t},|\rho\rangle_{E_{2}\hat{E_{2}}Y\hat{Y}}^{t}$ canonical purifications of $\rho^{t}_{XE_{1}},\rho^{t}_{YE_{2}}$ respectively. Since $E\equiv E_{1}TE_{2}$ , using Fact 11, we have

\mathrm{H}_{\min}\>\!\!\left(X\middle|E_{1}T\right)_{\rho}\geq\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}\geq k_{1}\quad;\quad\mathrm{H}_{\min}\>\!\!\left(Y\middle|E_{2}T\right)_{\rho}\geq\mathrm{H}_{\min}\>\!\!\left(Y\middle|E\right)_{\rho}\geq k_{2}.

(1)

Consider,

	$\displaystyle\mathrm{H}_{\min}\>\!\!\left(X\middle\|Y\hat{Y}{E}_{2}E_{1}{T}\right)_{\rho}$	$\displaystyle\geq\mathrm{H}_{\min}\>\!\!\left(X\middle\|Y\hat{Y}\hat{E}_{2}E_{2}E_{1}{T}\right)_{\rho}$
		$\displaystyle=\mathrm{H}_{\min}\>\!\!\left(X\middle\|E_{1}T\right)_{\rho}$
		$\displaystyle\geq k_{1}.$

The first equality is because conditioned on every $T=t$ , $\rho^{t}_{XE_{1}E_{2}\hat{E}_{2}Y\hat{Y}}=\rho^{t}_{XE_{1}}\otimes\rho^{t}_{E_{2}\hat{E}_{2}Y\hat{Y}}$ . The first inequality follows from Fact 8 and second inequality follows from Eq. (1). Consider,

	$\displaystyle\mathrm{H}_{\min}\>\!\!\left(Y\middle\|X\hat{X}\hat{E}_{2}\hat{E}_{1}\hat{T}\right)_{\rho}$	$\displaystyle\geq\mathrm{H}_{\min}\>\!\!\left(Y\middle\|X\hat{X}\hat{E}_{2}E_{1}\hat{E}_{1}\hat{T}\right)_{\rho}$
		$\displaystyle=\mathrm{H}_{\min}\>\!\!\left(Y\middle\|\hat{E}_{2}\hat{T}\right)_{\rho}$
		$\displaystyle=\mathrm{H}_{\min}\>\!\!\left(Y\middle\|{E}_{2}T\right)_{\rho}$
		$\displaystyle\geq k_{2}.$

The first equality is because conditioned on every $\hat{T}=t$ , $\rho^{t}_{YE_{1}\hat{E}_{1}\hat{E}_{2}X\hat{X}}=\rho^{t}_{Y\hat{E}_{2}}\otimes\rho^{t}_{E_{1}\hat{E}_{1}X\hat{X}}$ . The second equality is because $\rho_{Y\hat{E}_{2}\hat{T}}\equiv\rho_{YE_{2}T}$ . The first inequality follows from Fact 8 and second inequality follows from Eq. (1).

For the state $\rho$ with the following assignment (terms on the left are from Definition 10 and on the right are from here),

(X,\hat{X},N,M,Y,\hat{Y})\leftarrow(X,\hat{X},\hat{E}_{2}\hat{E}_{1}\hat{T},{E}_{2}E_{1}{T},Y,\hat{Y}),

we have $\rho$ is a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ . Using Fact 2, we have an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ $\rho^{\prime}$ such that $l\leq 2n-k_{1}-k_{2}+25+6\log(1/\varepsilon)$ and $\rho^{\prime}\approx_{\varepsilon}\rho.$ ∎

4.5 Quantum communication adversary

We show how to simulate a $(k_{1},k_{2})$ - $\mathsf{qca}$ (see Definition 4) in the model of an $l\mathchar 45\relax\mathsf{qma}$ .

Claim 8.

A $(k_{1},k_{2})$ - $\mathsf{qca\mathchar 45\relax state}$ can be simulated $\varepsilon$ -approximately by an $l\mathchar 45\relax\mathsf{qma}$ for some $l\leq 2n-k_{1}-k_{2}+25+6\log(1/\varepsilon)$ .

Proof.

Let $\Phi_{X\hat{X}N^{\prime}M^{\prime}Y\hat{Y}}$ , be the end state after the action of $(k_{1},k_{2})$ - $\mathsf{qca}$ (adversary gets registers either $M^{\prime}Y$ or $N^{\prime}X$ of his choice).

We note to the reader that every $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca\mathchar 45\relax state}$ is a $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ . Now using Fact 2, we have an $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ $\rho^{\prime}$ such that $l\leq 2n-k_{1}-k_{2}+25+6\log(1/\varepsilon)$ and $\rho^{\prime}\approx_{\varepsilon}\rho.$ This completes the proof.

∎

5 A quantum secure weak-seeded non-malleable extractor and privacy-amplification

5.1 A quantum secure weak-seeded non-malleable extractor

Theorem 7.

Let $p\neq 2$ be a prime, $n$ be an even integer and $\varepsilon>0$ . The function $\mathsf{nmExt}(X,Y)$ as defined in Definition 9 is a $(k_{1},k_{2})$ -quantum secure weak-seeded non-malleable extractor against $\mathsf{qnma}$ for the parameters $k_{1}+k_{2}\geq(n+17)\log p+33+16\log\left(\frac{1}{\varepsilon}\right)$ .

Proof.

Let $\rho$ be a $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ . From [ACLV19] (see Theorem 1), to show,

\|\rho_{\mathsf{nmExt}(X,Y)\mathsf{nmExt}(X,Y^{\prime})YY^{\prime}M^{\prime}}-U_{\log p}\otimes\rho_{\mathsf{nmExt}(X,Y^{\prime})YY^{\prime}M^{\prime}}\|_{1}\leq\varepsilon,

for $\mathsf{nmExt}(X,Y)$ as defined in Definition 9 it is enough to show,

\|\rho_{\langle X,g(Y,Y^{\prime})\rangle YY^{\prime}M^{\prime}}-U_{\log p}\otimes\rho_{YY^{\prime}M^{\prime}}\|_{1}\leq\frac{2\varepsilon^{2}}{p^{2}},

where $g:\mathbb{F}^{n/2}_{p}\times\mathbb{F}^{n/2}_{p}\to\mathbb{F}^{n}_{p}$ is an (appropriately defined) function such that for any $z\in\mathbb{F}^{n}_{p}$ there are at most two possible pairs $(y,y^{\prime})$ and $y\neq y^{\prime}$ such that $g(y,y^{\prime})=z$ . Let $U:\mathcal{H}_{Y}\otimes\mathcal{H}_{Y^{\prime}}\rightarrow\mathcal{H}_{Y}\otimes\mathcal{H}_{Y^{\prime}}\otimes\mathcal{H}_{Z}\otimes\mathcal{H}_{\hat{Z}}$ be a safe isometry such that $Z=g(Y,Y^{\prime})$ . Let $\theta=U\rho U^{\dagger}.$ Noting $\theta_{XM^{\prime}YY^{\prime}}=\rho_{XM^{\prime}YY^{\prime}}$ , we have $\|\theta_{\langle X,Z\rangle YY^{\prime}M^{\prime}}-U_{\log p}\otimes\theta_{YY^{\prime}M^{\prime}}\|_{1}=\|\rho_{\langle X,g(Y,Y^{\prime})\rangle YY^{\prime}M^{\prime}}-U_{\log p}\otimes\rho_{YY^{\prime}M^{\prime}}\|_{1}.$ From Claim 9, for parameters

k_{1}+k_{2}\geq(n+1)\log p+41+8\log\left(\frac{p^{2}}{2\varepsilon^{2}}\right),

we get $\|\theta_{\langle X,Z\rangle YM^{\prime}Y^{\prime}}-U_{\log p}\otimes\theta_{YM^{\prime}Y^{\prime}}\|_{1}\leq\frac{2\varepsilon^{2}}{p^{2}}.$ Rearranging terms we get the desired which completes the proof.

∎

Claim 9.

$\|\theta_{\langle X,Z\rangle YM^{\prime}Y^{\prime}}-U_{\log p}\otimes\theta_{YM^{\prime}Y^{\prime}}\|_{1}\leq\varepsilon^{\prime\prime},$ for parameters,

k_{1}+k_{2}\geq(n+1)\log p+41+8\log\left(\frac{1}{\varepsilon^{\prime\prime}}\right).

Proof.

Note $\theta$ is a $(k_{1},k_{2})$ - $\mathsf{wqnm\mathchar 45\relax state}$ . Note,

\mathrm{H}_{\min}\>\!\!\left(X\middle|M^{\prime}YY^{\prime}\hat{Y}\hat{Y}^{\prime}Z\hat{Z}\right)_{\theta}\geq k_{1}.

Also,

\mathrm{D}_{\max}\>\!\!\left(\rho_{YY^{\prime}NX\hat{X}}\middle\|\mathrm{I}_{YY^{\prime}}\otimes\rho_{NX\hat{X}}\right)\leq\mathrm{D}_{\max}\>\!\!\left(\rho_{YNX\hat{X}}\middle\|\mathrm{I}_{Y}\otimes\rho_{NX\hat{X}}\right)\leq-k_{2}.

The first inequality follows from Fact 4. The second inequality follows since $\mathrm{H}_{\min}(Y)_{\rho}\geq k_{2}$ and $\rho_{YNX\hat{X}}=\rho_{Y}\otimes\rho_{NX\hat{X}}$ . Thus,

\rho_{YY^{\prime}NX\hat{X}}\leq 2^{-k_{2}+n\log p}(U_{YY^{\prime}}\otimes\rho_{NX\hat{X}}),

which from Fact 11 implies

\theta_{ZNX\hat{X}}\leq 2^{-k_{2}+n\log p}\left(\tau_{Z}\otimes\theta_{NX\hat{X}}\right),

where $\tau_{Z}=g(U_{YY^{\prime}})$ . Since there are at most two possible pairs $(y,y^{\prime})$ and $y\neq y^{\prime}$ such that $g(y,y^{\prime})=z$ , we have $\tau_{Z}\leq 2\cdot U_{Z}$ . Thus,

\mathrm{D}_{\max}\>\!\!\left(\theta_{ZNX\hat{X}}\middle\|U_{Z}\otimes\theta_{NX\hat{X}}\right)\leq n\log p-k_{2}+1.

This implies,

\mathrm{H}_{\min}\>\!\!\left(Z\middle|NX\hat{X}\right)_{\theta}\geq\mathrm{\tilde{H}}_{\min}\>\!\!\left(Z\middle|NX\hat{X}\right)_{\theta}\geq k_{2}-1.

We note that the state $\theta$ is a $(k_{1},k_{2}-1)\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ . Using Corollary 6, with the following assignment of registers (below the registers on the left are from Corollary 6 and the registers on the right are the registers in this proof)

(X,Y,\hat{X},\hat{Y},N,M,\rho)\leftarrow(X,Z,\hat{X},\hat{Z},N,M^{\prime}YY^{\prime}\hat{Y}\hat{Y}^{\prime},\theta),

we get $\|\theta_{\langle X,Z\rangle YM^{\prime}Y^{\prime}\hat{Y}\hat{Y}^{\prime}Z}-U_{\log p}\otimes\theta_{YM^{\prime}Y^{\prime}\hat{Y}\hat{Y}^{\prime}Z}\|_{1}\leq\varepsilon^{\prime\prime}$ for parameters,

k_{1}+k_{2}\geq(n+1)\log p+41+8\log\left(\frac{1}{\varepsilon^{\prime\prime}}\right).

Since $\|\theta_{\langle X,Z\rangle YM^{\prime}Y^{\prime}}-U_{\log p}\otimes\theta_{YM^{\prime}Y^{\prime}}\|_{1}\leq\|\theta_{\langle X,Z\rangle YM^{\prime}Y^{\prime}\hat{Y}\hat{Y}^{\prime}Z}-U_{\log p}\otimes\theta_{YM^{\prime}Y^{\prime}\hat{Y}\hat{Y}^{\prime}Z}\|_{1},$ we get the desired. ∎

5.2 Privacy-amplification with local weak-sources

Let $n,m,d,l$ be positive integers and $k,k_{1},k_{2},\varepsilon,\delta>0$ . We start with the definition of a quantum secure privacy-amplification protocol against active adversaries. The following description is from [ACLV19]. A privacy-amplification protocol $(P_{A},P_{B})$ is defined as follows. The protocol is executed by two parties Alice and Bob sharing a secret $X\in\{0,1\}^{n}$ , whose actions are described by $P_{A}$ , $P_{B}$ respectively ¹¹¹¹11It is not necessary for the definition to specify exactly how the protocols are formulated; informally, each player’s actions is described by a sequence of efficient algorithms that compute the player’s next message, given the past interaction.. In addition there is an active, computationally unbounded adversary Eve, who might have some quantum side information $E$ correlated with $X$ but satisfying $\mathrm{H}_{\min}(X|E)_{\rho}\geq k$ , where $\rho_{XE}$ denotes the initial state at beginning of the protocol.

Informally, the goal for the protocol is that whenever a party (Alice or Bob) does not reject, the key $R$ output by this party is random and statistically independent of Eve’s view. Moreover, if both parties do not reject, they must output the same keys $R_{A}=R_{B}$ with overwhelming probability.

More formally, we assume that Eve is in full control of the communication channel between Alice and Bob, and can arbitrarily insert, delete, reorder or modify messages sent by Alice and Bob to each other. At the end of the protocol, Alice outputs a key $R_{A}\in\{0,1\}^{l}\cup\{\perp\}$ , where $\perp$ is a special symbol indicating rejection. Similarly, Bob outputs a key $R_{B}\in\{0,1\}^{l}\cup\{\perp\}$ . For a random variable $R\in\{0,1\}^{l}\cup\{\perp\}$ , let $\mathsf{purify}(R)$ be a random variable on $l$ -bit strings that is deterministically equal to $\perp$ if $R=\perp$ , and is otherwise uniformly distributed over $\{0,1\}^{l}$ . The following definition generalizes the classical definition in [DLWZ14].

Definition 27.

Let $k,l$ be integer and $\varepsilon>0$ . A privacy-amplification protocol $(P_{A},P_{B})$ is a $(k,l,\varepsilon)$ -privacy-amplification protocol secure against active quantum adversaries if it satisfies the following properties for any initial state $\rho_{XE}$ such that $\mathrm{H}_{\min}(X|E)_{\rho}\geq k$ , and $\sigma$ being the joint state of Alice, Bob and Eve at the end of the protocol given by $(P_{A},P_{B})$ including $\mathsf{purify}(R_{A})$ and $\mathsf{purify}(R_{B})$ .

1.

Correctness. If the adversary does not interfere with the protocol, then $\Pr[R_{A}=R_{B}\land~{}R_{A}\neq\perp\land~{}R_{B}\neq\perp]_{\sigma}=1$ .
2.

Robustness. This property states that even in the presence of an active adversary, $\Pr[R_{A}\neq R_{B}\land~{}R_{A}\neq\perp\land~{}R_{B}\neq\perp]_{\sigma}\leq\varepsilon$ .

Extraction. Let $\sigma_{\tilde{E}}$ be the final quantum state possessed by Eve (including the transcript of the protocol). The following should hold:

\|\sigma_{R_{A}\tilde{E}}-\sigma_{\mathsf{purify}(R_{A})\tilde{E}}\|_{1}\leq\varepsilon~{}~{}~{}~{}\mbox{and}~{}~{}~{}~{}\|\sigma_{R_{B}\tilde{E}}-\sigma_{\mathsf{purify}(R_{B})\tilde{E}}\|_{1}\leq\varepsilon\;.

In other words, whenever a party does not reject, the party’s key is (approximately) indistinguishable from a fresh random string to the adversary.

The quantity $k-l$ is called the entropy loss.

Our protocol.

Alice: $X$	Eve: $E$	Bob: $X$
Sample local weak-source $A$		Sample local weak-source $B$
	$A\longrightarrow A^{\prime}$
$S=\mathsf{nmExt}(X,A)$		$S^{\prime}=\mathsf{nmExt}(X,A^{\prime})$
		$W^{\prime}=\mathsf{Ext}(X,B)$
	$W,T\longleftarrow W^{\prime},T^{\prime}=\mathsf{MAC}_{S^{\prime}}(W^{\prime})$
If $T\neq\mathsf{MAC}_{S}(W)$ reject
Set final $R_{A}=\mathsf{Tre}(X,W)$		Set final $R_{B}=\mathsf{Tre}(X,W^{\prime})$

Protocol 1: New

2

-round privacy-amplification protocol with weak local sources.

In Protocol 1, we describe a slight modification of the DW protocol [DW09], that achieves PA in the setting where Alice and Bob only have weak local randomness $A$ and $B$ respectively, such that $A,B,(X,E)$ are independent. Let $A$ be $(n/2,k_{1})\mathchar 45\relax$ source and $B$ be $(n,k_{2})\mathchar 45\relax$ source. We need the following primitives.

•

Let $\mathsf{nmExt}:\{0,1\}^{n}\times\{0,1\}^{n/2}\to\{0,1\}^{2m}$ be a $(k,k_{1},\varepsilon)$ -quantum secure $(n,n/2,2m)$ -weak-seeded non-malleable extractor against $\mathsf{qnma}$ . Then we have from Theorem 7,

$k+k_{1}\geq n+34m+33+16\log\left(\frac{1}{\varepsilon}\right).$
•

Let $\mathsf{Ext}:\{0,1\}^{n}\times\{0,1\}^{n}\to\{0,1\}^{m}$ be $\mathsf{IP}_{2^{m}}^{n/m}$ . For any state $\sigma_{XEB}$ such that $\sigma_{XEB}=\sigma_{XE}\otimes\sigma_{B}$ , $\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\sigma}\geq k$ and $\mathrm{H}_{\min}(B)_{\sigma}\geq k_{2}$ , we have

$\|\sigma_{\mathsf{Ext}(X,B)XE}-U_{m}\otimes\sigma_{XE}\|_{1}\leq\varepsilon,$

for the parameters $k+k_{2}\geq n+m+40+8\log\left(\frac{1}{\varepsilon}\right)$ from Corollary 7.
•

Let $\mathsf{MAC}:\{0,1\}^{2m}\times\{0,1\}^{m}\to\{0,1\}^{m}$ be a one-time $2^{-m}$ -information-theoretically secure message authentication code from Fact 28 for $m=O\left(\log^{3}(\frac{n}{\varepsilon})\right)$ . Note $2^{-m}\leq\varepsilon$ .
•

Let $\mathsf{Tre}:\{0,1\}^{n}\times\{0,1\}^{m}\to\{0,1\}^{\ell}$ be a $(2l,\varepsilon)$ -quantum secure strong $(n,m,l)$ -seeded extractor for $m=O(\log^{3}(n/\varepsilon))$ from Fact 27. Taking $l=(1-\delta)k$ for any small constant $\delta>0$ suffices for the privacy-amplification application.

In Protocol 1, there are only two messages exchanged, $A$ from Alice to Bob and $(W^{\prime},T^{\prime})$ from Bob to Alice. To each of these messages the adversary may apply an arbitrary transformation, that may depend on its side information.

Definition 28 (Active attack).

An active attack against PA protocol is described by 3 parameters.

•

A c-q state $\rho_{XE}$ (of adversary choice) such that $\mathrm{H}_{\min}\>\!\!\left(X\middle|E\right)_{\rho}\geq k$ .
•

A CPTP map $\mathsf{T}_{1}:\mathcal{H}_{E}\otimes\mathcal{H}_{A}\rightarrow\mathcal{H}_{E^{\prime}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{A^{\prime}}$ .
•

A CPTP map $\mathsf{T}_{2}:\mathcal{H}_{E^{\prime}}\otimes\mathcal{H}_{W^{\prime}}\otimes\mathcal{H}_{T^{\prime}}\rightarrow\mathcal{H}_{E^{\prime\prime}}\otimes\mathcal{H}_{W^{\prime}}\otimes\mathcal{H}_{T^{\prime}}\otimes\mathcal{H}_{W}\otimes\mathcal{H}_{T}$ .

Theorem 8.

For any active attack $(\rho_{XE},\mathsf{T}_{1},\mathsf{T}_{2})$ , Protocol 1 is $\left(k,\left(1-\delta\right)k,O({\varepsilon})\right)$ -secure as defined in Definition 27 as long as,

k+k_{2}\geq n+m+40+8\log\left(\frac{1}{\varepsilon}\right)\quad;\quad k+k_{1}\geq n+34m+33+16\log\left(\frac{1}{\varepsilon}\right)\quad;\quad m=O(\log^{3}(n/\varepsilon)).

Proof.

The security of Protocol 1 follows from the observation that the protocol is nearly identical to that in [ACLV19] [BJK22]. There are two main differences:

•

The seed $A$ for the non-malleable extractor is a weak-source. This is secure via Theorem 7.
•

In the protocol from [ACLV19] [BJK22], Bob has immediate access to uniform $W^{\prime}$ . Here, we obtain $W^{\prime}$ using strong extractor property of inner-product from Corollary 7. Since $B$ is independent of $X,A$ , we get that $W^{\prime}$ is independent of $X,A$ , and hence independent of $X,S$ , which is required in the proof of security in [ACLV19] [BJK22].

We refer the reader to Appendix.D of [BJK22] for the complete proof of privacy-amplification when the sources $A,B$ are completely uniform. The proof of security follows similar to that of [BJK22] privacy-amplification protocol, with the following assignment of terms (terms on left are from privacy-amplification protocol of [BJK22] and terms on right are from Protocol 1)

(X,Y,S,S^{\prime},B^{\prime},T^{\prime},B,T,R_{A},R_{B})\leftarrow(X,A,S,S^{\prime},W^{\prime},T^{\prime},W,T,R_{A},R_{B}).

∎

Open questions

1.

We have shown that the inner-product function is secure against $\mathsf{qma}$ . It is natural to ask if the other known $2$ -source extractors are secure against $\mathsf{qma}$ . For example is Bourgain’s extractor [Bou05], which works for $2$ -sources with min-entropy $(\frac{1}{2}-\delta)n$ (for constant $\delta$ ), secure against $\mathsf{qma}$ ?
2.

Are the multi-source extractor constructions of [Raz05, CZ19, Li19, BIW06, Li12, Li11, Li13, Rao09] secure against (a natural multi-source extension of) $\mathsf{qma}$ ?
3.

We have shown the security of Li’s non-malleable extractor against quantum side information. Recently [BJK22] have shown another non-malleable extractor secure against quantum side information in the $2$ -source setting. Several near optimal non-malleable extractor constructions are known in the classical setting, for example constructions of [Li12, Li17, Li19]. Are they secure against quantum side information?

Acknowledgment

The work of NGB was done while he was a graduate student at the Centre for Quantum Technologies, NUS, Singapore.

This work is supported by the NRF grants NRF-NRFF2013-13 and NRF2021-QEP2-02-P05; the Prime Minister’s Office and the Ministry of Education, Singapore, under the Research Centers of Excellence program and grants MOE2012-T3-1-009 and MOE2019-T2-1-145; the NRF2017-NRF-ANR004 VanQuTe grant and the VAJRA grant, Department of Science and Technology, Government of India.

References

[ABJ22] Divesh Aggarwal, Naresh Goud Boddu, and Rahul Jain. Quantum secure non-malleable codes in the split-state model. ArXiv:2202.13354, 2022.
[ACLV19] Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, and Thomas Vidick. A quantum-proof non-malleable extractor. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 442–469, Cham, 2019. Springer International Publishing.
[AFPS16] Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz. Quantum-Proof Multi-Source Randomness Extractors in the Markov Model. In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:34, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[AHJ⁺21] Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, and Dave Touchette. One-shot quantum state redistribution and quantum markov chains. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 130–135, 2021.
[BBCM95] C.H. Bennett, G. Brassard, C. Crepeau, and U.M. Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41(6):1915–1923, 1995.
[BBR88] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy amplification by public discussion. SIAM J. Comput., 17(2):210–229, April 1988.
[Bei13] Salman Beigi. Sandwiched rényi divergence satisfies data processing inequality. Journal of Mathematical Physics, 54(12):122202, December 2013.
[Bel64] J. S. Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika, 1:195–200, November 1964.
[BIW06] Boaz Barak, Russell Impagliazzo, and Avi Wigderson. Extracting randomness using few independent sources. SIAM J. Comput., 36(4):1095–1118, December 2006.
[BJK22] Naresh Goud Boddu, Rahul Jain, and Upendra Kapshikar. Quantum secure non-malleable-extractors. Contributed talk at 17th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2022. ArXiv:2109.03097, 2021.
[BJL23] Naresh Goud Boddu, Rahul Jain, and Han-Hsuan Lin. On relating one-way classical and quantum communication complexities. Quantum, 7:1010, May 2023. Contributed talk at 21th Asian Quantum Information Science Conference.
[Bou05] J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 01:1–32, 2005.
[BW92] Charles H. Bennett and Stephen J. Wiesner. Communication via one- and two-particle operators on einstein-podolsky-rosen states. Phys. Rev. Lett., 69:2881–2884, November 1992.
[CB97] Richard Cleve and Harry Buhrman. Substituting quantum entanglement for communication. Phys. Rev. A, 56:1201–1204, Aug 1997.
[CG85] B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 429–442, 1985.
[CG14] Mahdi Cheraghchi and Venkatesan Guruswami. Non-malleable coding against bit-wise and split-state tampering. In Proceedings of Theory of Cryptography Conference (TCC), pages 440–464, 2014. Extended version in Journal of Cryptology.
[CLW14] Kai-Min Chung, Xin Li, and Xiaodi Wu. Multi-source randomness extractors against quantum side information, and their applications. CoRR, abs/1411.2315, 2014.
[CV17] Gil Cohen and Thomas Vidick. Privacy amplification against active quantum adversaries. ArXiv:1608.06318, 2017.
[CZ19] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Annals of Mathematics, 189(3):653–705, 2019.
[Dat09] Nilanjana Datta. Min- and max- relative entropies and a new entanglement monotone. IEEE Transactions on Information Theory, 55:2816–2826, 2009.
[DLWZ14] Yevgeniy Dodis, Xin Li, Trevor D. Wooley, and David Zuckerman. Privacy amplification and nonmalleable extractors via character sums. SIAM Journal on Computing, 43(2):800–830, 2014.
[DPVR12] Anindya De, Christopher Portmann, Thomas Vidick, and Renato Renner. Trevisan’s extractor in the presence of quantum side information. SIAM Journal on Computing, 41(4):915–940, 2012.
[DV10] Anindya De and Thomas Vidick. Near-optimal extractors against quantum storage. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, page 161–170, New York, USA, 2010. Association for Computing Machinery.
[DW09] Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, page 601–610, New York, USA, 2009. Association for Computing Machinery.
[FS] Lance Fortnow and Ronen Shaltiel. Recent developments in explicit constructions of extractors.
[FvdG06] C. A. Fuchs and J. van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Trans. Inf. Theor., 45(4):1216–1227, September 2006.
[GKK⁺07] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, page 516–525, New York, USA, 2007. Association for Computing Machinery.
[HJPW04] Patrick Hayden, Richard Jozsa, Dénes Petz, and Andreas Winter. Structure of States Which Satisfy Strong Subadditivity of Quantum Entropy with Equality. Communications in Mathematical Physics, 246(2):359–374, 2004.
[ILL89] R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, page 12–24, New York, USA, 1989. Association for Computing Machinery.
[JK22] Rahul Jain and Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent QKD. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1285–1295, 2022.
[JRS09] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A property of quantum relative entropy with an application to privacy in quantum communication. J. ACM, 56(6):33:1–33:32, September 2009.
[KK10] Roy Kasher and Julia Kempe. Two-source extractors secure against quantum adversaries. In Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 656–669, Berlin, Heidelberg, 2010. Springer.
[KLR09] Y. T. Kalai, X. Li, and A. Rao. 2-source extractors under computational assumptions and cryptography with defective randomness. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 617–626, 2009.
[KLRZ08] Y. T. Kalai, X. Li, A. Rao, and D. Zuckerman. Network extractor protocols. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 654–663, 2008.
[KMR05] R. Konig, U. Maurer, and R. Renner. On the power of quantum memory. IEEE Transactions on Information Theory, 51(7):2391–2401, 2005.
[KR09] Bhavana Kanukurthi and Leonid Reyzin. Key agreement from close secrets over unsecured channels. In Proceedings of the 28th Annual International Conference on Advances in Cryptology - EUROCRYPT 2009 - Volume 5479, page 206–223, Berlin, Heidelberg, 2009. Springer-Verlag.
[KT08] R. T. Konig and B. M. Terhal. The bounded-storage model in the presence of a quantum adversary. IEEE Transactions on Information Theory, 54(2):749–762, 2008.
[Li11] X. Li. Improved constructions of three source extractors. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 126–136, 2011.
[Li12] X. Li. Non-malleable extractors, two-source extractors and privacy amplification. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 688–697, 2012.
[Li13] Xin Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 100–109, 2013.
[Li15] X. Li. Three-source extractors for polylogarithmic min-entropy. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 863–882, 2015.
[Li17] Xin Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, page 1144–1156, New York, USA, 2017. Association for Computing Machinery.
[Li19] Xin Li. Non-malleable extractors and non-malleable codes: Partially optimal constructions. In Proceedings of the 34th Computational Complexity Conference, Dagstuhl, DEU, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[LLR12] Sophie Laplante, Virginie Lerays, and Jérémie Roland. Classical and quantum partition bound and detector inefficiency. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 617–628, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[Mau92] Ueli M Maurer. Conditionally-perfect secrecy and a provably-secure randomized cipher. Journal of Cryptology, 5(1):53–66, 1992.
[MW97] Ueli Maurer and Stefan Wolf. Privacy amplification secure against active adversaries. In Burton S. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, pages 307–321, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
[NC00] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, UK, 2000.
[Rao06] Anup Rao. Extractors for a constant number of polynomially small min-entropy independent sources. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, page 497–506, New York, USA, 2006. Association for Computing Machinery.
[Rao09] A. Rao. Extractors for low-weight affine sources. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 95–101, 2009.
[Raz05] Ran Raz. Extractors with weak random seeds. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 11–20, 2005.
[Ren05] Renato Renner. Security of quantum key distribution. PhD Thesis, ETH Zurich, Diss. ETH No. 16242, ArXiv:0512258, 2005.
[RK05] Renato Renner and Robert König. Universally composable privacy amplification against quantum adversaries. In Joe Kilian, editor, Theory of Cryptography, pages 407–425, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[Tre01] Luca Trevisan. Extractors and pseudorandom generators. J. ACM, 48(4):860–879, July 2001.
[TS09] Amnon Ta-Shma. Short seed extractors against quantum storage. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 401–408, New York, NY, USA, 2009. Association for Computing Machinery.
[Uhl76] A. Uhlmann. The “transition probability” in the state space of a *-algebra. Reports on Mathematical Physics, 9:273–279, 1976.
[Wat11] John Watrous. Chapter 5, naimark’s theorem; characterizations of channels. Lecture notes on Theory of Quantum Information, 2011.
[Wat18] John Watrous. The theory of quantum information. Cambridge University Press, 2018.
[Wil12] Mark M. Wilde. Quantum Information Theory. Cambridge University Press, Cambridge, December 2012.
[Yao93] Andrew Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS 1993), pages 352–360, 1993.
[Zuc90] D. Zuckerman. General weak random sources. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 534–543 vol.2, 1990.

$\displaystyle\\|CD\\|^{4}_{4}$	$\displaystyle=\mathrm{Tr}(\mathrm{I}_{Z}\otimes\rho_{YM}^{1/4}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/4})^{2}$	(Fact 3)
	$\displaystyle=\|\mathcal{Z}\|\cdot\mathrm{Tr}(\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM})$
	$\displaystyle\leq\|\mathcal{Z}\|\cdot\\|\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}\\|_{1}\\|C^{\dagger}_{YM}C_{YM}\\|_{\infty}$	(Fact 14)
	$\displaystyle\leq\|\mathcal{Z}\|\cdot\\|\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}\\|_{1}$	( $\\|C^{\dagger}_{YM}C_{YM}\\|_{\infty}\leq 1$ )
	$\displaystyle=\|\mathcal{Z}\|\cdot\mathrm{Tr}(\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2})$	( $\rho_{YM}^{1/2}C^{\dagger}_{YM}C_{YM}\rho_{YM}^{1/2}\geq 0$ )
	$\displaystyle=\|\mathcal{Z}\|\cdot\mathrm{Tr}(C_{YM}\rho_{YM}C^{\dagger}_{YM})$
	$\displaystyle=\|\mathcal{Z}\|\cdot\Pr(B=1)_{\Theta}.$

	$\displaystyle\\|\Phi_{ZYM^{\prime}}-U_{Z}\otimes\Phi_{YM^{\prime}}\\|^{2}_{1}$
	$\displaystyle=\frac{1}{(\Pr(B=1)_{\Theta})^{2}}\\|C(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})C^{\dagger}\\|^{2}_{1}$
	$\displaystyle=\frac{1}{(\Pr(B=1)_{\Theta})^{2}}\\|CDD^{-1}(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})D^{-1}DC^{\dagger}\\|^{2}_{1}$
	$\displaystyle\leq\frac{1}{(\Pr(B=1)_{\Theta})^{2}}\\|CD\\|^{4}_{4}\ \\|D^{-1}(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})D^{-1}\\|^{2}_{2}$	(Fact 15)
	$\displaystyle\leq\frac{\|\mathcal{Z}\|\cdot\Pr(B=1)_{\Theta}}{(\Pr(B=1)_{\Theta})^{2}}\cdot\\|D^{-1}(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})D^{-1}\\|^{2}_{2}$
	$\displaystyle\leq\frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot\\|(\mathrm{I}_{Z}\otimes\rho_{YM}^{-1/4})(\rho_{ZYM}-U_{Z}\otimes\rho_{YM})(\mathrm{I}_{Z}\otimes\rho_{YM}^{-1/4})\\|^{2}_{2}$
	$\displaystyle=\frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot\mathbb{E}_{y\leftarrow\rho_{Y}}\left[\\|(\mathrm{I}_{Z}\otimes\rho_{M}^{-1/4})(\rho^{y}_{ZM}-U_{Z}\otimes\rho_{M})(\mathrm{I}_{Z}\otimes\rho_{M}^{-1/4})\\|^{2}_{2}\right]$
	$\displaystyle=\frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot\mathbb{E}_{y\leftarrow\rho_{Y}}\left[\mathrm{Tr}\left((\mathrm{I}_{Z}\otimes\rho_{M}^{-1/2})(\rho^{y}_{ZM}-U_{Z}\otimes\rho_{M})\right)^{2}\right]$
	$\displaystyle\leq\ \frac{\|\mathcal{Z}\|}{\Pr(B=1)_{\Theta}}\cdot 2^{-\mathrm{\tilde{H}}_{\min}\>\!\!\left(X\middle\|M\right)_{\rho}}.$	(Fact 21)

	$\displaystyle\mathrm{H}_{\min}\>\!\!\left(X\middle\|Y\hat{Y}{E}_{2}E_{1}{T}\right)_{\rho}$	$\displaystyle\geq\mathrm{H}_{\min}\>\!\!\left(X\middle\|Y\hat{Y}\hat{E}_{2}E_{2}E_{1}{T}\right)_{\rho}$
		$\displaystyle=\mathrm{H}_{\min}\>\!\!\left(X\middle\|E_{1}T\right)_{\rho}$
		$\displaystyle\geq k_{1}.$

	$\displaystyle\mathrm{H}_{\min}\>\!\!\left(Y\middle\|X\hat{X}\hat{E}_{2}\hat{E}_{1}\hat{T}\right)_{\rho}$	$\displaystyle\geq\mathrm{H}_{\min}\>\!\!\left(Y\middle\|X\hat{X}\hat{E}_{2}E_{1}\hat{E}_{1}\hat{T}\right)_{\rho}$
		$\displaystyle=\mathrm{H}_{\min}\>\!\!\left(Y\middle\|\hat{E}_{2}\hat{T}\right)_{\rho}$
		$\displaystyle=\mathrm{H}_{\min}\>\!\!\left(Y\middle\|{E}_{2}T\right)_{\rho}$
		$\displaystyle\geq k_{2}.$

Quantum Measurement Adversary

Abstract

1 Introduction

Definition 1 ([Zuc90]).

Definition 2 ([Zuc90, CLW14]).

Definition 3 (l−𝗊𝗆𝖺l\mathchar 45\relax\mathsf{qma}, l−𝗊𝗆𝖺−𝗌𝗍𝖺𝗍𝖾l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}).

Definition 4 ((k1,k2)−𝗊𝖼𝖺(k_{1},k_{2})\mathchar 45\relax\mathsf{qca}, (k1,k2)−𝗊𝖼𝖺−𝗌𝗍𝖺𝗍𝖾(k_{1},k_{2})\mathchar 45\relax\mathsf{qca\mathchar 45\relax state}).

Remark.

Our results

𝗊𝗆𝖺\mathsf{qma} can simulate other adversaries

Theorem 1.

Inner-product is secure against 𝗊𝗆𝖺\mathsf{qma}

Definition 5.

Theorem 2.

Corollary 1 (Efficiency lower bound for a 𝒳\mathcal{X}-two-wise independent function).

Corollary 2.

A quantum secure weak-seeded non-malleable extractor

Definition 6 ((k1,k2)−𝗐𝗊𝗉𝖺−𝗌𝗍𝖺𝗍𝖾(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}).

Definition 7 ((k1,k2)−𝗐𝗊𝗇𝗆−𝗌𝗍𝖺𝗍𝖾(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}).

Definition 8 (Quantum secure weak-seeded non-malleable extractor).

Definition 9 ([Li12]).

Theorem 3.

Privacy-amplification with weak-sources

Proof overview

Comparison with [ACLV19]

Other related works

Subsequent works

Definition 10 ((k1,k2)−𝗊𝗉𝖺−𝗌𝗍𝖺𝗍𝖾(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}).

Fact 1 ([BJK22]).

Fact 2 ([BJK22]).

Organization

2 Preliminaries

Quantum information theory

Definition 11 (Classical register in a pure state).

Definition 12 (Copy of a classical register).

Definition 13 (Conditioning).

Definition 14 (Extension).

Definition 15 (Safe maps).

Definition 16.

Fact 3.

Fact 4 ([BJL23]).

Fact 5 ([BJL23]).

Fact 6.

Fact 7 ([BJK22]).

Fact 8 ([CLW14]).

Fact 9.

Fact 10 ([FvdG06]).

Fact 11 (Data-processing).

Fact 12 ([HJPW04]).

Fact 13 ([AHJ+21]).

Fact 14 (Hölder’s inequality).

Fact 15 (Hölder’s inequality, special case).

Fact 16 (Cyclicity of trace).

Fact 17.

Fact 18 (Stinespring isometry extension [Wat11]).

Fact 19 (Corollary 5.5 in [Wat11]).

Fact 20 (Lemma 5.4.3 [Ren05]).

Fact 21 ([Ren05]).

Proof.

Fact 22 (Uhlmann’s theorem [Uhl76]).

Fact 23 (Rejection-sampling [JRS09]).

Fact 24 ([JRS09]).

Proof.

Fact 25 ([BJK22]).

Fact 26 ([BJK22]).

Claim 1.

Proof.

Claim 2.

Proof.

Claim 3.

Proof.

Lemma 1.

Proof.

Corollary 3.

Proof.

Extractors

Definition 17 (Quantum secure seeded extractor).

Fact 27 ([DPVR12] [CV17]).

Definition 18 (22-source extractor against an adversary [KK10, CLW14, AFPS16]).

Definition 19.

Definition 3 ( $l\mathchar 45\relax\mathsf{qma}$ , $l\mathchar 45\relax\mathsf{qma\mathchar 45\relax state}$ ).

Definition 4 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{qca\mathchar 45\relax state}$ ).

$\mathsf{qma}$ can simulate other adversaries

Inner-product is secure against $\mathsf{qma}$

Corollary 1 (Efficiency lower bound for a $\mathcal{X}$ -two-wise independent function).

Definition 6 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqpa\mathchar 45\relax state}$ ).

Definition 7 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{wqnm\mathchar 45\relax state}$ ).

Definition 10 ( $(k_{1},k_{2})\mathchar 45\relax\mathsf{qpa\mathchar 45\relax state}$ ).

Fact 13 ([AHJ⁺21]).

Definition 18 ( $2$ -source extractor against an adversary [KK10, CLW14, AFPS16]).

3 Inner-product is secure against $\mathsf{qma}$

Corollary 4 (Efficiency lower bound for a $\mathcal{X}$ -two-wise independent function).

4 $\mathsf{qma}$ can simulate other adversaries

Definition 23 ( $(b_{1},b_{2})$ - $\mathsf{qbsa}$ [KK10]).

Definition 24 ( $(k_{1},k_{2})$ - $\mathsf{qia}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{qia\mathchar 45\relax state}$ [KK10]).

Definition 25 ( $(k_{1},k_{2})$ - $\mathsf{gea}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{gea\mathchar 45\relax state}$ [CLW14]).

Definition 26 ( $(k_{1},k_{2})$ - $\mathsf{qMara}$ , $(k_{1},k_{2})\mathchar 45\relax\mathsf{qMara\mathchar 45\relax state}$ ) [AFPS16]).