Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank has access to a giant table of random numbers, and that banknotes can be brought back to the bank for verification. In Wiesner's scheme, each banknote consists of a classical "serial number" $s$, together with a quantum money state $|\psi_s\rangle$ consisting of $n$ unentangled qubits, each one either

$$|0\rangle,\ |1\rangle,\ |+\rangle=(|0\rangle+|1\rangle)/\sqrt{2},\ \text{or}\ |-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}.$$

The bank remembers a classical description of $|\psi_s\rangle$ for every $s$. And therefore, when $|\psi_s\rangle$ is brought back to the bank for verification, the bank can measure each qubit of $|\psi_s\rangle$ in the correct basis (either $\{|0\rangle,|1\rangle\}$ or ${|+\rangle,|-\rangle}$), and check that it gets the correct outcomes.

On the other hand, because of the uncertainty relation (or alternatively, the No-Cloning Theorem), it's "intuitively obvious" that, if a counterfeiter who doesn't know the correct bases tries to copy $|\psi_s\rangle$, then the probability that both of the counterfeiter's output states pass the bank's verification test can be at most $c^n$, for some constant $c<1$. Furthermore, this should be true regardless of what strategy the counterfeiter uses, consistent with quantum mechanics (e.g., even if the counterfeiter uses fancy entangled measurements on $|\psi_s\rangle$).

However, while writing a paper about other quantum money schemes, my coauthor and I realized that we'd never seen a rigorous proof of the above claim anywhere, or an explicit upper bound on $c$: neither in Wiesner's original paper nor in any later one.

So, has such a proof (with an upper bound on $c$) been published? If not, then can one derive such a proof in a more-or-less straightforward way from (say) approximate versions of the No-Cloning Theorem, or results about the security of the BB84 quantum key distribution scheme?

Update: In light of the discussion with Joe Fitzsimons below, I should clarify that I'm looking for more than just a reduction from the security of BB84. Rather, I'm looking for an explicit upper bound on the probability of successful counterfeiting (i.e., on $c$)---and ideally, also some understanding of what the optimal counterfeiting strategy looks like. I.e., does the optimal strategy simply measure each qubit of $|\psi_s\rangle$ independently, say in the basis

$$\{ \cos(\pi/8)|0\rangle+\sin(\pi/8)|1\rangle, \sin(\pi/8)|0\rangle-\cos(\pi/8)|1\rangle \}?$$

Or is there an entangled counterfeiting strategy that does better?

Update 2: Right now, the best counterfeiting strategies that I know are (a) the strategy above, and (b) the strategy that simply measures each qubit in the $\{|0\rangle,|1\rangle\}$ basis and "hopes for the best." Interestingly, both of these strategies turn out to achieve a success probability of (5/8)n. So, my conjecture of the moment is that (5/8)n might be the right answer. In any case, the fact that 5/8 is a lower bound on c rules out any security argument for Wiesner's scheme that's "too" simple (for example, any argument to the effect that there's nothing nontrivial that a counterfeiter can do, and therefore the right answer is c=1/2).

Update 3: Nope, the right answer is (3/4)n! See the discussion thread below Abel Molina's answer.

share|improve this question
3  
Welcome to TP.SE Scott! Good to see you here. –  Joe Fitzsimons Oct 24 '11 at 13:15
1  
It seems like Wiesner's scheme corresponds exactly to BB84 where you post select on Bob having chosen exactly the same bases of measurement as Alice has for preparation (since the bank is both Alice and Bob). Clearly the bank could instead chose the measurement basis randomly, and simulate BB84, which would yield strictly weaker security (since you would consider exactly the same measurements but only on a subset of qubits), so you can surely use a proof of BB84 to lower bound the security of the quantum money scheme. Perhaps I'm missing something though. –  Joe Fitzsimons Oct 24 '11 at 13:22
    
Thanks for the welcome and the answer, Joe! FWIW, I share your intuition that a security proof for Wiesner's scheme ought to be "strictly easier" than a security proof for BB84. However, with that argument (like with every other one), I keep coming back to the same question: "so then what's the upper bound on c?" –  Scott Aaronson Oct 24 '11 at 13:33
    
Surely it is upper bounded by the probability of determining the key in BB84. –  Joe Fitzsimons Oct 24 '11 at 13:36
    
Also, while it would be OK to deduce the security of Wiesner's scheme from the security of BB84 if that's the only/best alternative, I hold out the hope that there should be a more direct and informative proof. Furthermore, it seems plausible that a direct proof would be needed for getting an explicit upper bound on c, or for getting a "reasonable" such bound (more like 0.9 than like 0.99999). –  Scott Aaronson Oct 24 '11 at 13:38
show 5 more comments

migrated from physics.stackexchange.com May 7 '12 at 5:30

This question came from our site for active researchers, academics and students of physics.

3 Answers

up vote 28 down vote accepted

It seems like this interaction can be modeled in the following way:

  1. Alice prepares one of the states $|000\rangle$, $|101\rangle$,$(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$, $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$, according to a certain probability distribution, and sends the first qubit to Bob.
  2. Bob performs an arbitrary quantum channel that sends his qubit to two qubits, which are then returned to Alice.
  3. Alice performs a projective measurement on the four qubit on her possession.

If I am not wrong about this (and sorry if I am), this falls within the formalism from Gutoski and Watrous presented here and here, which implies that:

  1. From Theorem 4.9 in the second of those, it is optimal to Bob to act independently when Alice repeats this process with several qubits in an independent way, if the objective of Bob is to always fool Alice.
  2. It is possible to obtain the value of c from a small semidefinite program. You can find more details of how to obtain this program in Section 3 here. See the comments for the cvx code for the program and its value.
share|improve this answer
8  
Following Abel's suggestion, it appears that the optimal value is c = 3/4. –  John Watrous Oct 26 '11 at 19:22
3  
I did just obtain the same value of 3/4. Its explanatory power is small, but the computer code is at cs.uwaterloo.ca/~amolinap/scriptWeisner.m and cs.uwaterloo.ca/~amolinap/prtrace.m. –  Abel Molina Oct 26 '11 at 21:51
3  
The strategy is given by a quantum channel whose Choi-Jamielkowski representation is an optimal solution to the semidefinite program. See cs.uwaterloo.ca/~amolinap/optSolution.txt for a link to such a solution (the least significant qubit is the one received by Bob, and the other two are the ones he sends to Alice). If my calculations are correct, the corresponding channel sends |0> to (|01>+|10>)/√2 with probability 1/6, and to (3|00>+|11>)/√10 with probability 5/6. |1> is sent to (|01>+|10>)/√2 with probability 1/6, and to (|00>+3|11>)/√10 with probability 5/6 –  Abel Molina Oct 27 '11 at 0:13
3  
Similarly, (|0>+|1>)/√2 is sent to (|11>-|00>)/√2 with probability 1/6, and to (|00>+1/2|01>+1/2|10>+|11>)/√(5/2) with probability 5/6. Similarly, (|0>-|1>)/√2 is sent to (|11>-|00>)/√2 with probability 1/6, and to (|00>-1/2|01>-1/2|10>+|11>)/√(5/2) with probability 5/6. –  Abel Molina Oct 27 '11 at 0:23
2  
In fact, for any state $\alpha | 0 \rangle + \beta |1\rangle$, $\alpha$ and $\beta$ real, the strategy has 3/4 chance of success. I just did the calculations. –  Peter Shor Oct 27 '11 at 1:19
show 13 more comments

The question of cloning the BB84 states was covered in the paper "Phase covariant quantum cloning" by Dagmar Bruß, Mirko Cinchetti, G. Mauro D'Ariano, and Chiara Macchiavello [Phys Rev. A, 62, 012302 (2000), Eq. 36]. They give an optimal cloner for these states (which is also an optimal cloner for any states $\alpha |0\rangle + \beta |1\rangle$ with $\alpha$, $\beta\in \mathbb{R}\:$). They do not optimize using the same fidelity measure that you are asking about, but I suspect that their cloner is optimal for your question. Their cloner gives success probability $$\left(\frac{1}{2}+ \frac{1}{\sqrt{8}}\right)^{2n} \approx .72855^n$$ for counterfeiting $n$ BB84 states, quite a bit better than $(\frac{5}{8})^n$.

UPDATE: Bruß et al.'s optimal cloner is given by $\sum_{i=1}^2 A_i \rho A_i^\dagger$ where

$$A_1 = \left( \begin{array}{cc} \frac{1}{2}+\frac{1}{\sqrt{8}} & 0\\ 0 & \frac{1}{\sqrt{8}}\\ 0 & \frac{1}{\sqrt{8}}\\ \frac{1}{2}-\frac{1}{\sqrt{8}} & 0 \end{array} \right) \ \ \ \ A_2 = \left(\begin{array}{cc} 0& \frac{1}{2}-\frac{1}{\sqrt{8}} \\ \frac{1}{\sqrt{8}}&0\\ \frac{1}{\sqrt{8}}&0\\ 0&\frac{1}{2}+\frac{1}{\sqrt{8}} \end{array} \right) . $$

The optimal cloner found by the solution to Abel's semindefinite program is $\sum_{i=1}^2 A_i \rho A_i^\dagger$ where:

$$A_1 = \frac{1}{\sqrt{12}}\left( \begin{array}{cc} 3 & 0\\ 0 & 1\\ 0 & 1\\ 1 & 0 \end{array} \right) \ \ \ \ A_2 = \frac{1}{\sqrt{12}}\left(\begin{array}{cc} 0& 1 \\ 1&0\\ 1&0\\ 0&3 \end{array} \right) . $$

These clearly come from the same family of transformations, but have been optimized to satisfy different objective functions. This family of covariant transformations appears to be given by

$$A_1 = \frac{1}{\sqrt{2x^2+4y^2}}\left( \begin{array}{cc} x+y & 0\\ 0 & y\\ 0 & y\\ x-y & 0 \end{array} \right) \ \ \ \ A_2 = \frac{1}{\sqrt{2x^2+4y^2}}\left(\begin{array}{cc} 0& x-y \\ y&0\\ y&0\\ 0&x+y \end{array} \right) . $$

share|improve this answer
    
Thanks, Peter! It would be great to show optimality or even near-optimality of their cloner. For that, I guess the first step would be showing that the optimal attack is individual rather than collective. –  Scott Aaronson Oct 26 '11 at 12:40
    
If Abel Molina's approach works, it should demonstrate this. If not, you should be able to use the techniques in the optimal cloner papers to get an upper bound, but I don't immediately know what it would be. –  Peter Shor Oct 26 '11 at 13:09
    
By adding the states $(|0\rangle + i |1\rangle)/\sqrt{2}$ and $(|0\rangle - i |1\rangle)/\sqrt{2}$ to the original four, it seems that the optimum falls to $c = 2/3$. An optimal channel for Bob is again given by Peter's family of channels, with $x = y = 1$. –  John Watrous Oct 27 '11 at 3:19
    
@John: this transformation is the original quantum cloner of Bužek and Hillery. I think what's going on is that there's a one-parameter family of covariant quantum cloners for real-amplitude qubit states. If you require covariance for all states, not just real-amplitude ones, you get only the $x=y=1$ one. (Covariant here means: if you apply the same real rotation to the input and the output state spaces, you get the same transformation. Of course, this is still true if you apply a rotation to the input space first, so you have to also require that the overlap is maximized with no rotation.) –  Peter Shor Oct 27 '11 at 14:04
add comment

I don't know of a published security proof. I would think the simplest way and strongest bound would come from approximate no-cloning, but I guess you'd need a version specialized for the BB84 states. Even a reduction from BB84 is not obvious, since the security condition for BB84 is different.

I do think you can get a proof straightforwardly as a consequence of the security proof of uncloneable encryption (quant-ph/0210062). This won't get a tight upper bound on the cheating probability, but at least it gives security.

In uncloneable encryption, A sends B a classical message using quantum states. (A and B share a secret key.) The security condition is two-fold: a) When Eve intercepts the initial transmission, she gets no information about message. b) Whatever strategy Eve adopts, either she will be caught by Bob with very high probability, or her residual state $\rho_k$ when the key is k has almost no information about the message. b says that if Eve is unlikely to be caught, she retains no information about the message even if she later learns the key used by A and B. This is interpreted as a no-cloning result: Eve could steal the ciphertext, but she cannot copy it without messing up Bob's received message.

This can be used to create a quantum money scheme: Bank A uses uncloneable encryption to encrypt a random string the "message". There is an uncloneable encryption scheme which is basically BB84, so this could give Weisner's scheme. Eve intercepts the money, interacts with it, and sends the modified original on to Bank B. She also tries to make a copy, which goes to Bank C. Banks B and C accept if the state provided to them passes the uncloneable encryption eavesdropping test, and if they decode the correct random "message" string. Uncloneable encryption property b says that, with high probability, either B's copy fails the eavesdropping test or C's copy contains almost no information about the message. This is stronger than needed, but sufficient to prove security.

For best asymptotic attack, I would imagine, due to quantum de Finetti, that the best collective attack is the same as the best individual attack.

share|improve this answer
    
Thanks so much, Daniel! I'll continue looking for an argument that gives an explicit bound on c, but in the meantime, this is extremely helpful. I went ahead and marked your answer as "accepted." –  Scott Aaronson Oct 25 '11 at 10:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.