Hard Quantum Extrapolations in Quantum Cryptography

Unfortunately, not every efficient distribution can be quantum sampled unless, for example, $\mathsf{SZK}\subseteq\mathsf{BQP}$ [AT07]. Thus we want to also handle the case where $s$ can be arbitrarily distributed, which could be the case for a general quantum money scheme.

A first idea is that maybe starting from the $0$-commitment state, we can “effectively” remove $\ket{\psi_{s}}$ from the committer’s view (or equivalently, its register $\mathsf{D}$). Naïvely we could simply assign the state $\ket{\psi_{s}}$ to the $\mathsf{C}$ register. However, the resulting commitment scheme would be not hiding, so some care has to be taken.

The next idea, then, is to maybe employ some encryption scheme to do this. More specifically, our second attempt is as follows:

for some encryption scheme $Enc$.

Now, what encryption scheme would work? The most natural candidate, quantum one-time pad, turns out not to work: if $\ket{\psi_{s}}$ are all encoded in Hadamard basis then the resulting scheme would again not be hiding.

Nevertheless, we make the crucial observation: this attack appears to rely on the secret quantum state being encoded in a specific basis. If we attempt to encrypt, instead of only in two bases, in exponentially many bases, then the probability that we hit such a bad basis would be negligible. To make this efficient, let us say that we just pick one of bases to encrypt uniformly at random. Since adding random phases to a basis is equivalent to measuring it, this gives us the following random-measurement commitment scheme.

In the encryption perspective, this is equivalently using a random encryption scheme indexed by some public randomness $k$, and secret random phases are added to the basis specified by $k$. Moving forward, we will use the measurement perspective since it is more convenient for the analysis.

We now need to argue that the commitment is hiding and binding and neither is obvious at this point. Intuitively, hiding should hold as our intuition above indicates that a sufficiently random set of bases should evade the bad distinguishing attack with overwhelming probability. On the other hand, giving the adversary a complete measurement of the state in a probably useless basis should not help the adversary to swap the state out with the zero state — or in the encryption perspective, the encryption should be secure enough that the adversary could only build the state from scratch instead of extracting useful information from the encryption.

As observed above, the family of measurement bases must be sufficiently large, and different bases need to be “independent” enough to avoid the attack above. Given these criteria, we consider a few candidates: (1) mutually unbiased bases (MUBs); (2) unitary $t$-designs; (3) stripped down $t$-designs such as binary phase bases [MPSY24]. It turns out that both MUBs and $t$-designs for $t\geq 2$ work, while $1$-designs and binary phase bases do not necessarily work. For comparison, MUBs have very good randomness complexity ($n$ bits of randomness for hiding $n$ qubits) while $2$-designs or random Cliffords are more efficient (can be applied in quasi-linear time). For interested readers, we explain the counterexamples in Appendix A.

On a high level, the hiding proof can be reduced the following question: given any two mixed states $\rho_{0},\rho_{1}$ that could be statistically far; is it true that the states after measuring them in a random basis $k$, $(\rho_{0}^{(k)},k),(\rho_{1}^{(k)},k)$ are somewhat statistically close? This also might be an independently interesting question on its own beyond this application: traditionally, tomography asks for a set of measurements that preserves the quantum information; here, we ask for a set of measurements that destroys quantum information with respect to statistical distance.

Crucially, we need to bound the statistical distance even if the basis choice $k$ is revealed. This is problematic for the proof of $t$-designs, since $t$-designs generally do not guarantee anything if the secret key $k$ is revealed: everyone can check that the specific unitary corresponding to $k$ is applied instead of a Haar random unitary. However, there is a simple trick we can apply: the statistical distance we need to bound above can be equivalently expressed as $\operatorname*{\mathbb{E}}_{k}[TD(\rho_{0}^{(k)},\rho_{1}^{(k)}]$, as the distribution over $k$ is identical. Furthermore, here the key is no longer given to the distinguisher. Even though trace distance is not a polynomial (due to the absolute value), we can nevertheless bound it by an appropriate degree-$2$ polynomial and then invoke the security of $2$-designs. In the end, we prove that the average statistical distance under $2$-designs is at most $1/\sqrt{2}$. Curiously, it appears that even measurements under Haar random unitaries would still leave behind $1/2$ statistical distance.

To prove MUBs work, we leverage a useful fact by Ivanovic [Iva81, Iva92] that any density matrix can be decomposed into the sum of its post-measurement states over all MUBs; furthermore, each pair of states are orthogonal with respect to the Hilbert–Schmidt inner product after appropriate renormalization. Utilizing the orthogonality, we can translate the average ($L^{1}$) statistical distance to ($L^{2}$) Hilbert–Schmidt distance to invoke the decomposition, and then back to statistical distance without losing too much. In the end, we can compute that the average statistical distance under MUBs is at most $1/\sqrt{2}$ as well.

We refer interested readers to the later sections for a more detailed proof.

To show (honest) binding, we show that any adversary who is given register $\mathsf{D}$ of $\ket{\mathsf{com}_{0}}$ and successfully opens to $1$ can be used to solve the classical$\rightarrow$quantum extrapolation problem. In the classical$\rightarrow$quantum extrapolation game, the reduction is essentially given a mixed state $\sum_{s}\alpha_{s}^{2}\ket{s}\!\bra{s}$. In order to meaningfully invoke the binding adversary, the reduction must produce the reduced density matrix on $\mathsf{D}$ of $\mathsf{com}_{0}$, which looks like

when $\mathsf{C}$ is traced out, where $\rho_{k,s}$ denotes the mixed state resulting from measuring $\ket{\psi_{s}}$ in the basis $k$. Observe that since the canonical-form commitment receiver is going to project on to the $\ket{\mathsf{com}_{1}}$ state, the adversary’s output must (at the very least) be the following form:

for some $\rho^{\prime}_{k,s}$. This is true since the committer already holds a copy of $k$ and $s$. Therefore, as long as we can mimic the distribution on $k$ and $\rho_{k,s}$, the reduction would work.

Recall our intuition above that $\rho_{k,s}$ should disclose very little information so that it would not help the adversary to prepare $\ket{\psi_{s}}$. This suggests that maybe the reduction can just put there maybe a maximally mixed state and hope that the adversary would not notice. However, recall from above that $\rho_{k,s}$ is only weakly hiding. In other words, it may contain some information about $\ket{\psi_{s}}$. It is not clear that the reduction can generate such a state without already violating the hardness of the extrapolation problem.

Our solution is to simply generate $\rho_{k,0}$, a measurement of $\ket{\vec{0}}$ in the basis $k$, and feed it to the binding adversary instead. In other words, we are again measuring all zeroes and expect the adversary to not see a difference. This turns out to work. Although $\rho_{k,0}$ only matches $\rho_{k,s}$ to a limited degree, it does match register $\mathsf{C}$ from $\ket{\mathsf{com}_{0}}$. Since register $\mathsf{C}$ in $\ket{\mathsf{com}_{1}}$ would contain $\rho_{k,s}$ instead of $\rho_{k,0}$, the support states where $\rho_{k,s}$ significantly differs from $\rho_{k,0}$ precisely cover the case where the commitment is statistically binding. Thus, the assumed binding adversary’s advantage must be entirely on the portion of $\rho_{k,s}$ which matches $\rho_{k,0}$. In order for the substitution to work, the receiver’s view of $\rho_{k,0}$ in $\ket{\mathsf{com}_{0}}$ must be symmetric with the sender’s view of $\rho_{k,s}$ in $\ket{\mathsf{com}_{1}}$. Therefore if the choice of basis $k$ appears in one view, it must appear in both.

It is not hard to see that both public-key quantum money and commitments imply hard quantum extrapolation tasks. In the case of public-key quantum money, we may regard the serial number as $\ket{B_{i}}$ and the banknote as $\ket{A_{i}}$; thus, any adversary mapping $\ket{B_{i}}\mapsto\ket{A_{i}}$ counterfeits banknotes using their serial numbers.

The case of commitments is only slightly more complicated. A perfectly hiding commitment in canonical quantum form has a Schmidt decomposition

Note that because the commitment is perfectly hiding, the left hand side of the two decompositions are the same. Thus, if an adversary could coherently map $\ket{d_{i,0}}\mapsto\ket{c_{i}}\mapsto\ket{d_{i,1}}$, they could open $\ket{\mathsf{com}_{0}}$ to $\ket{\mathsf{com}_{1}}$ by operating only on the opening register, breaking computational binding.

Handling statistical hiding is essentially the same reduction, but the analysis is more difficult. Essentially, we need to argue that statistical hiding implies that the two target states are close. We prove this by establishing that the closeness of the target states is captured by the Holevo fidelity and then utilizing a tight connection between Holevo fidelity and trace distance [Hol72].

It is natural to wonder whether our construction from cloneable$\rightarrow$quantum extrapolation can be extended to the more general quantum extrapolation task. A natural attempt is to prepare the extrapolation state in the opening register $\mathsf{D}$, then “destroy” either $\ket{A_{i}}$ or $\ket{B_{i}}$, depending on the message bit, by measuring it and copying it in a random basis to the commitment register $\mathsf{C}$. This results in a commitment which looks like the following:

In order to open $\ket{\mathsf{com}_{1}}$ to $\ket{\mathsf{com}_{0}}$, it would suffice to map $\ket{B_{i}}\mapsto\ket{A_{i}}$ and let the statistical hiding take care of the differences between $M_{k}(A_{i})$ and $M_{k}(B_{i})$. Unfortunately, it is not clear whether this mapping is necessary to break binding. In particular, the commitment register only contains partial information about $\ket{A_{i}}$, so the adversary is not necessarily bound to any particular $i$ when breaking binding. instead, it could potentially map $\ket{B_{i}}$ onto a superposition of $\ket{A_{j}}$’s.

For a more concrete example, consider the state $\sum_{x}\ket{x}\otimes H\ket{x}=\sum_{xy}(-1)^{x\cdot y}\ket{x}\otimes\ket{y}$ and the fixed measurement of measuring in the computational basis (note that our binding proof before works for any family of measurement bases). Then the resulting commitment has identical commitment states: $\sum_{xy}(-1)^{x\cdot y}\ket{x}\otimes\ket{y,x}=\sum_{xy}(-1)^{x\cdot y}\ket{y}\otimes\ket{x,y}$. This means that the action to break binding is the identity unitary, whereas we would expect the adversary to apply the Hadamard gates.

In general, the result of applying $\mathsf{Rand}_{k}$ can be expressed as

for some complex coefficient $\alpha$’s. Using these, we can write the commitment states as

Here, $\mathsf{C}$ contains the commitment (sent to the receiver) and $\mathsf{D}$ contains the opening (kept by the sender).

Say the adversary consists of a unitary $U_{A}$ and an auxiliary quantum input $\ket{\mathsf{aux}}_{\mathsf{A}}$. It applies $U_{A}$ to registers $\mathsf{C}$ and $\mathsf{A}$. We assume the adversary always prepares a state $\ket{k,s,\phi_{k,s,x},x}$ in register $D$ along with potentially another private register. This is without loss of generality since not preparing a state like this form can only decrease the binding attack advantage since when the challenger projects onto $\ket{\mathsf{com}_{1}}$ it necessarily projects $k,s,x$ to the correct value; furthermore, in our reduction, we also perform this check so the amplitude outside would not affect the reduction either. More formally, we can account for this by considering the residual state to be potentially sub-normalized when the adversary does not comply. The output of the adversary is

The state $\ket{\phi_{k,s,x}}:=\sum_{y}\ket{y}\ket{\mathsf{aux}_{k,s,y,x}}$ might be subnormalized but the remaining component will never contribute (in either direction) to the binding advantage. From this we can see that the adversary’s action can be seen as first swapping $\mathsf{M}_{0}\mathsf{M}_{1}$ and then prepare a (possibly subnormalized) quantum state on the registers $\mathsf{M}_{0}\mathsf{A}$ controlled on $k,s,x$.

We now consider the state after projecting $\mathsf{M}_{0}$ to $\ket{\psi_{s}}$ to be

where $\ket{\mathsf{aux}_{k,s,x}}:=\sum_{y}\left\langle\psi_{s}\middle|y\right\rangle\ket{\mathsf{aux}_{k,s,y,x}}$. Note that this projection again contains both the commitment receiver’s projection as well as the extrapolation verification projection. As a consequence, we can for simplicity consider the overlap with this state, which will be a lower bound on the success probability.

Let $\Pr[s]=\beta_{s}^{2}$ be the probability of sampling a challenge $s$. Define $p_{k,s}(x)=|\alpha_{k,s,x}|^{2}$ to be the probability that a measurement of $\ket{\psi_{s}}$ in the basis $k$ outputs $x$. Similarly define $q_{k}(x)=|\alpha_{k,x}|^{2}$. $w(k,s,x)$ denotes the probability that the adversary, given $\ket{k,\mathsf{chal}_{s},x}$, successfully produces $\ket{\psi_{s}}$. In other words,