Rigorous security proof for Wiesner's quantum money? 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&lt;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.
It seems like this interaction can be modeled in the following way:


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.
Bob performs an arbitrary quantum channel that sends his qubit to two qubits, which are then returned to Alice.
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:


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.
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.