%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Version de travail pour resoumission a PRL.

%\documentstyle[aps,prl,preprint]{revtex} 
\documentstyle[aps,prl]{revtex} 
%\tighten

\begin{document}
%\clubpenalty 10000
%\widowpenalty 10000


%\draft
\twocolumn
\narrowtext
%July 25 1996
\title{Unconditionally secure quantum bit commitment is impossible}
\author{Dominic Mayers}
\address{D\'epartement IRO, Universit\'e de Montr\'eal \\
C.P. 6128, succursale Centre-Ville,Montr\'eal (Qu\'ebec), Canada H3C 3J7.}
\date{\today}
\maketitle

\begin{abstract}
The claim of quantum cryptography has always been that it can provide
protocols that are unconditionally secure, that is, for which the
security does not depend on any restriction on the time, space or
technology available to the cheaters.  We show that this claim does
not hold for any quantum bit commitment protocol.  Since many
cryptographic tasks use bit commitment as a basic primitive, this
results implies a severe setback for quantum cryptography. We claim
that the model used encompasses all reasonable implementations of
quantum bit commitment protocols in which the participants have not
met before, including those that make use of the theory of special
relativity.
\end{abstract}

\pacs{1994 PACS numbers: 03.65.Bz, 42.50.Dv, 89.70.+c}


\paragraph{Introduction}
Quantum cryptography is often associated with a task called key
distribution and it has obtained a lot of success in this area.
However, quantum cryptographers have also proposed quantum protocols
for other tasks and bit commitment is a basic primitive that has been
used in most if not all of these other proposals.  For a review on
quantum key distribution and on quantum cryptography in general
see~\cite{bc96}.  Here, we focus on bit commitment.  

We introduce bit commitment in terms of quantum states which is not
standard in cryptography but is appropriate for our purposes.  A bit
commitment state is a random state $|\psi_b\rangle \in_R
\{|\psi_0\rangle, |\psi_1\rangle\}$ of a system $H_A \times H_B \times
H_E$ such that the two following conditions hold.  First, a party
usually called Bob having access to $H_B$ only should not be able to
obtain any information at all about the bit $b$.  We say that a bit
commitment state must be {\em concealing}.  Second, another 
participant usually called Alice having only access to $H_A$ can
unveil the bit $b$ to Bob, but she should not be able to change her
mind about the value of the bit $b$.  We say that a bit commitment
state must be {\em binding}.  Note that this definition encompasses the
classical notion of bit commitment.  The system $H_E$ stands for the
environment and his necessary to include the notion of classical bits,
mixtures, etc.\ in the picture.  

Many cryptographic applications such
as the zero knowledge proofs are based on bit commitment. 
In a zero knowledge proof, Alice wants to
convince Bob that she knows at the least one element $x$ in a fixed
set $L$ which is known by both participants.  For instance, $L$ could
be the set of all possible proofs for a given theorem.  The difficulty
is that Alice wants to convince Bob that she knows $x$ without
unveiling any information or almost any information about it.  This
amazing task has been shown to be possible on top of bit commitment
for a large class of sets $L$.

Also, the work of Kilian and many
others~\cite{kilian88,gmw87,cdg87,cgt95} has shown that any
multi-party computation can be built on top of oblivious
transfer~\cite{bbcs92,crepeau94} which can itself be executed by a
quantum protocol on top of bit commitment~\cite{yao95,mayers96c}.  An
example of multi-party computation is the {\em millionaire's problem}.
In this task, two millionaires want to find out who is the richest,
but they do not want to unveil any additional information about their
respective fortune.  

All the known protocols that attempt to realize this kind of tasks via
exchange of classical informations only are based upon a restriction
on the amount of time available to the cheater.  This is what we call
computational security.  Furthermore, on top of it, they are all based
on some unproven computational assumptions such as the assumption that
no algorithm can factorize a large number in a reasonable number of
steps.

In quantum cryptography, we want to realize this kind of tasks even
against a cheater that has unlimited computational power! This means
that there should be no restriction on the amount of time, on the
amount of space or on the technology available to the cheater. A
protocol that works even against such a powerful cheater is said to be
unconditionally secure.

A quantum protocol has been proposed in 1993 to realize bit
commitment~\cite{bcjl93}, and the unconditional security of this
protocol has been generally accepted for around two or three years. At
this time, much optimisism prevailed.  Then, Salvail get interested in
the design of possibly more efficient quantum bit commitment
protocols~\cite{salvail95}.  In all these protocols, Alice sent a
mixture to Bob to commit a bit $b$. The mixture was different when $b
=0$ than when $b =1$, but to make sure that these protocols were secure
against Bob, these two mixtures had a same density
matrix.  However, it was noticed that in these protocols Alice could
change her mind via a transformation on her side only.  This problem
has been presented to Wootters and he made the point that it was the
immediate consequence of a general theorem~\cite{hjw93} which says
that because the two density matrices are identical, Alice can change
her mind via a transformation on her side.  The connection with the
BCJL protocol was made later in the fall of 1995.  After the discovery
that BCJL was insecure, researchers have tried to find alternative
protocols.  Some of them were based on the theory of special
relativity.  For additional historical information see~\cite{bc96}.
See also~\cite{lc96a}.
       
Here, it is shown that, if no component in the protocol can be
simultaneously trusted by both participants, an unconditionally secure
bit commitment protocol is impossible.  It is assumed that the
protocol begins in some standard initial state, but the proof can be
easily extended to any initial state where Alice's system and Bob's
system are not entangled.  We claim that the model used encompasses
all reasonable protocols, including those based on the theory of
special relativity.

 
\paragraph{The model}
In our model, every quantum bit commitment protocol is described in
terms of quantum registers that are acted upon by quantum
gates~\cite{bbcdmsssw95}.  At every step, every register is an input
for one and only one gate, possibly a gate that executes the identity
transformation.

For simplicity, we assume that all quantum registers are two dimensional
quantum systems.  This is not really a restriction on the set of
protocols because higher dimensional systems can be simulated via two
dimensional registers~\cite{bbcdmsssw95}.

If one needs a random classical bit in this model, one must transform a
quantum register which is initially in a state $|\phi\rangle = \alpha
|0\rangle + \beta |1\rangle$ into a mixture.  So, one introduces
another register in the state $|0\rangle^{(E)}$ and executes a
controlled-not $(|y\rangle^{(E)} |x\rangle \mapsto | y \oplus
x\rangle^{(E)} |x\rangle)$ and throws the additional register away in
an area called the environment. The environment has the property that
any register that is thrown away in this area is lost for ever.  The
resulting state $\alpha |0\rangle^{(E)} |0\rangle + \beta
|1\rangle^{(E)} |1\rangle$ corresponds to a random classical bit with
probability distribution $p_0 = |\alpha|^2$ and $p_1 = |\beta|^2$.

If we assume that the cheater is so powerful that he can reverse any
process that may occur when a quantum register interacts with a real
environment, then it may be that there exists no area in which quantum
registers are lost for ever.  However, we need an area of this kind to
include classical bits and the classical world in general in our
model.

Communication is made by exchange of quantum registers in a
deterministic manner.  In our model, a register cannot be in a
superposition of being sent and not being sent.  Intuitively, we claim
that there is no loss of generality because the same physical
processes can be expressed in terms of a register that is
systematically sent, but is in a surperposition of containing the
information or not.  Similarly, a participant cannot choose at random
whether or not he will send a register.


\paragraph{The BB84 quantum bit commitment protocol}
It is well known that no protocol can allow the creation of a bit
commitment state via exchange of classical information between
Alice and Bob only.  This is true even if the participants are honest and
have the best will in the world. So, it is of interest that a
two-party quantum protocol has been proposed in 1984 that realizes bit
commitment when the participants are honest~\cite{bb84}.  The protocol
fails when Alice cheats.  In fact, the authors themselves have first
explained their protocol together with an attack.

The BB84 bit commitment protocol makes use of the BB84 coding scheme.
In this scheme, every bit is coded either in a so called rectilinear
basis $(\,|0\rangle_+,\, |1\rangle_+ \,)$ or in the diagonal basis
$(\,|0\rangle_\times,\, |1\rangle_\times \,)$, where $|0\rangle_\times
= 1/\sqrt{2} ( |0\rangle_+ + |1\rangle_+)$ and $|1\rangle_\times =
1/\sqrt{2} ( |0\rangle_+ - |1\rangle_+)$.

In this protocol, Alice creates a string of random bits $w = w_1
\ldots w_n$.  Then she codes each bit $w_i$ using the BB84 coding
scheme. She always uses the rectilinear basis $\theta = +$ if she
wants to commit a $0$ and the diagonal basis $\theta =
\times$ if she wants to commit a $1$.  She sends these registers to
Bob.  Then, Bob chooses a string of random bases $\hat{\theta} =
\hat{\theta}_1 \ldots \hat{\theta}_n \in \{+,\times\}^n$, measures the
register $i$ in the basis $\hat{\theta}_i$ and notes the outcomes
$\hat{w}_i$.  To unveil the bit $b$, Alice has simply to announce the
string $w$.  Bob can figure out what is $b$ by looking at positions
$i$ where $w_i \neq \hat{w}_i$: at each of these positions it must be
that $\theta \neq \hat{\theta}_i$.

Before the opening, the bit commitment state is concealing because
both $b = 0$ and $b = 1$ correspond to the same fully mixed density
matrix on Bob's side.  Also, it is binding because to change her mind
Alice would have to guess what are the bits obtained by Bob when
$\hat{\theta}_i \neq \theta$. These bits are perfectly random.  She
could guess what these bits are, but she would only succeed with a
very small probability.  This is fine: unconditional security does not
mean a perfect protocol.  As explained previously, it only means
that the protocol should do what it claims to do 
against a cheater that has unlimited computational power.

Now, in our model, this protocol will look slightly more
complicated because each random bit must be created using two quantum
registers.  Here is the state that Alice must create for each $i$:
\[
1/\sqrt{2}( |0\rangle_\theta^{(E)} |0\rangle_\theta^{(A)}
|0\rangle_\theta^{(B)} + |1\rangle_\theta^{(E)}
|1\rangle_\theta^{(A)}\ |1\rangle_\theta^{(B)} ).
\]
The first register to the left is the one that she throws away in the
environment, the second corresponds to the random classical bit that
she keeps on her side and the third one is the register that she sends
to Bob.  For simplicity, we have assumed that the basis $\theta$ is
not only used to encode the random classical bit in the third register
which is sent to Bob, but also to compute it in the first two
registers which Alice keeps on her side.  


\paragraph{The attack against the BB84 bit commitment}
A dishonest Alice executes the honest commit algorithm
for $b = 0$, except that she never throws anything away in the
environment.  In other words, she creates the state:
\[
1/\sqrt{2}( |0\rangle_+^{(A)} |0\rangle_+^{(A)} |0\rangle_+^{(B)} +
|1\rangle_+^{(A)} |1\rangle_+^{(A)}\ |1\rangle_+^{(B)} ).
\]
This is cheating 
because there exists a unitary transformation that
Alice can execute on her side that will transform this state into the
state:
\[
1/\sqrt{2}( |0\rangle_\times^{(A)} |0\rangle_\times^{(A)}
|0\rangle_\times^{(B)} + |1\rangle_\times^{(A)}
|1\rangle_\times^{(A)}\ |1\rangle_\times^{(B)} ),
\]
which is exactly the state that she would have created with a $1$ in
mind.  The transformation is simple. She simply executes a 
controlled-not 
on the first two photons using the rectilinear basis, and then
another controlled-not on the same photons but, this time, using the
diagonal basis.

\paragraph{The main result}
To obtain the impossibility
of bit commitment we need to make some
assumptions about the initial state.  
Otherwise, in the extreme case, the initial state could
be a bit commitment state.  
We claim that all protocols that start 
in a product state of Alice's system and
Bob's system are insecure.  
However, for simplicity we deal only with protocols
where initially all quantum
registers are set to $|0\rangle$ and the environment is empty.  We
prove that no quantum bit commitment protocol that starts in this
state is unconditionally secure, unless one or more gates can be
trusted by both participants simultaneously. A gate or a set of gates
trusted by both participants is called a {\em trusted party}.  
We do not accept trusted party in our proof.  

We can assume that the protocol is unconditionally secure against Bob,
because otherwise the proof is done.  As suggested by the BB84
example, the main idea of Alice's strategy is to execute the honest
algorithm with the bit $b$ of her choice, but never to throw anything
away in the environment except when she must send a classical bit $x$
to Bob.  When Alice sends a classical bit $x$ to Bob, we have a term
of the form $|x\rangle^{(E)}|x\rangle^{(A)} |x\rangle^{(B)}$ which can
be factorized out.  Similarly, one can factorize the terms that are
associated with the classical bits that Bob sends to Alice.  Let $\xi$
represents all these terms associated with classical bits which are
shared between Alice and Bob.  At the end of the commit phase, for a
given $\xi$, the state of the overall system has collapsed into a
state $|\xi\rangle |\psi_b\rangle$.  In the remainder of this letter,
we do not consider the registers which have been factorized out as a
part of the overall quantum system that remains after the commit
phase.  Also, the state $|\psi_b\rangle$ depends on $\xi$, but we have
suppressed this dependence in the notation.  Note that, once we have
factorized out $|\xi\rangle$, there is nothing in the environment on
Alice's side.  So, on her side of the quantum system, Alice is free to
execute the transformation of her choice.  However, because Bob is
honest, he might have thrown some registers away in the environment on
his side.

Now we must argue that the two density matrices
$\rho_B(|\psi_0\rangle)$ and $\rho_B(|\psi_1\rangle)$ on Bob's side,
associated with $b=0$ and $b=1$ respectively, are identical or almost
identical.  We would like to use the fact that Bob can cheat using the
same strategy that has been used by Alice.  However, the rule of the
game to attack a protocol 
in cryptography is that Alice and Bob cannot cheat at the same
time.
Fortunately, the overall algorithm that is executed when Alice does
{\em not} cheat and Bob does cheat is exactly the same as when Alice
cheats and Bob does {\em not} cheat.  Therefore, the density matrices
$\rho_B(|\psi_0\rangle)$ and $\rho_B(|\psi_1\rangle)$ are the same in
both cases.  So, we can use the fact that Bob cannot obtain much
information when he cheats, to conclude that the density matrices must
be identical or almost identical when he does not cheat.  For
simplicity, we first deal with the case where the density matrices are
identical.

In this case, Alice can change her mind about the value of $b$ because
the work of Hughson, Jozsa and Wootters \cite{hjw93} implies that if
\[
\rho_B(|\psi_0\rangle) = \rho_B(|\psi_1\rangle) \stackrel{def}{=}
\rho_B
\]
on Bob's side, then there exists a unitary transformation on Alice's
side which maps $|\psi_0\rangle$ into $|\psi_1\rangle$. We give the
proof of this theorem.  Consider the respective Schmidt decomposition
\cite{hjw93,schmidt06} of $|\psi_0\rangle$ and $|\psi_1\rangle$
given by
\begin{eqnarray*}
|\psi_0 \rangle & = & \sum_i \sqrt{\lambda_i} |e^{(0)}_i\rangle
\otimes |f_i\rangle \\
|\psi_1 \rangle & = & \sum_i \sqrt{\lambda_i} |e^{(1)}_i\rangle
\otimes |f_i\rangle.
\end{eqnarray*}
In the above formula, $\lambda_i$ are eigenvalues of the three density
matrices $\rho_B$, $\rho_A(|\psi_0\rangle)$ and
$\rho_A(|\psi_1\rangle)$.  The fact that these three density matrices
share the same positive eigenvalues with the same multiplicity is part
of the Schmidt decomposition theorem \cite{hjw93,schmidt06}.  The
states $|e^{(b)}_i\rangle$ and $|f_i\rangle$ are respectively
eigenstates of $\rho_A(|\psi_b\rangle)$ and $\rho_B$ associated with
the same eigenvalue $\lambda_i$.  The coefficients $\sqrt{\lambda_i}$
are real numbers, but any phase can be included in the choice of
$|e^{(b)}_i\rangle$.  Clearly, the same unitary transformation that
maps $|e^{(0)}_i\rangle$ into $|e^{(1)}_i\rangle$ also maps
$|\psi_0\rangle$ into $|\psi_1\rangle$.  The cheater can compute the
states $e^{(b)}_i$ and thus this unitary transformation with an
arbitrary level of precision.  This concludes the proof.


\paragraph{The non ideal case}
In the ideal case, the cheater could transform $|\psi_0\rangle$ into
$|\psi_1\rangle$ because the two density matrices
$\rho_B(|\psi_0\rangle)$ and $\rho_B(|\psi_1\rangle)$ were identical.
This was sufficient to conclude that the protocol is insecure.  Now,
we must use the fact that the distinguishability $D$ between these two
density matrices must be small, to obtain that the cheater can
transform $|\psi_0\rangle$ into a state $|\psi_{01}\rangle$ which is
very close to $|\psi_1\rangle$.  This is exactly what a theorem of
Uhlmann says.  Any state $|\psi_{01}\rangle$ of the overall system
such that $\rho_B(|\psi_{01}\rangle) = \rho_B(|\psi_0\rangle)$ is
called a purification of the density matrix $\rho_B(|\psi_0\rangle)$.
Uhlmann's theorem~\cite{jozsa94}  says that there exists a purification
$|\psi_{01}\rangle$ of $\rho_B(|\psi_0\rangle)$ such that
\begin{equation} \label{Uhlmann_inequality}
\langle \psi_{01} | \psi_1 \rangle \geq 1 - D.
\end{equation}  
The fact that $|\psi_{01}\rangle$ is a purification of
$\rho_B(|\psi_0\rangle)$ implies that Alice can transform
$|\psi_0\rangle$ into $|\psi_{01}\rangle$ as in the ideal case.
Inequality \ref{Uhlmann_inequality} says that $|\psi_{01}\rangle$ is
close to $|\psi_1\rangle$.  This result is sufficient
to conclude that the protocol is insecure against Alice.  

However, it is also useful to express the result in other terms.  
In \cite{gm96}, our result 
is translated in a language that do not involve quantum mechanics.
More precisely, Bob's information about the bit $b$ is measured in
terms of the probability $p_E$ that the best guess that Bob can
make about the bit $b$ turns out to be wrong.  One must also take into
account the probability $p_H$ that the bit $b$ is accepted by Bob when
Alice is honest.  Normally, $p_H$ should be $1$ or very close to $1$
and $p_E$ should be $\frac{1}{2}$ or very close to $\frac{1}{2}$.
A lower bound on the probability $p_C$ with which Alice can
successfully change her mind must be given in terms of $p_E$ and
$p_H$.  The result of \cite{gm96} is $p_C > p_H - 4\sqrt{|p_E
-\frac{1}{2}|}$.


\paragraph{Generality of the result}
One could think that, if we could constraint the cheater to do what is
requested by the protocol, then we would have a secure protocol.
However, the problem is that in our attack the cheater does what is
requested by the protocol, except that he does not throw anything away
unless it is expected by the other.  Therefore, no verification
whatsoever can be used to detect such a cheater.  In particular, 
any verfication based on the theory of special relativity is useless.

The above argument make sense in our model, but is our model really
general?  We claim that it is, but it is not possible to rigorously
prove this kind of statements because there will always be some
arbitrariness in the concept of protocols itself.  An issue that needs
to be discussed is the concept of communication via a deterministic
exchange of registers. This issue has already been briefly discussed
when we have introduced the model.  Another issue is the impact
of the superselection rules in quantum mechanics. 


\paragraph{Conclusions}
Because we have shown that bit commitment is impossible, we can only
hope to realize cryptographic 
tasks which are not known to be powerful enough to obtain
bit commitment.  For instance, coin tossing and most multi-party
computations are possible candidates because it is not known how
to build bit commitment on top of them.  
However, some tasks might not be powerful enough to obtain
bit commitment and yet be impossible.  
%%%%%%%%%%%%%%%%%%%% Don't know??? %%%%%%%%%%%%%%%%%%%
What are the
fundamental principles that make some tasks possible and other tasks
impossible?  One could think that all the tasks which involve only two
parties are impossible.  This would explain why quantum key
distribution is possible and bit commitment impossible.  However,
there might be other principles involved.  For instance, in bit
commitment an asymmetry is created.  It could be that only the
asymmetrical tasks are impossible.  In this case, coin tossing would
be possible.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
What tasks are possible is a fundamental question which
yet remain to be answered.

\paragraph{Acknowledgments}  I acknowledge fruitful discussions with
%Charles Bennett, 
%Gilles Brassard, 
%Claude Cr\'epeau, 
Lior Goldenberg, 
Jeroen van de Graaf,
Tal Mor, 
Lev Vaidman, 
and William Wootters. 

{\small 

\begin{thebibliography}{99}


\bibitem{bbcdmsssw95}
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo,
Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin,
and Harald Weinfurter, 
%``Elementary gates for quantum computation'',
PRA, Volume 52, Issue 5 - November 1995, pp. 3457-3467.


\bibitem{bb84} 
Charles~H.~Bennett and Gilles~Brassard,
%Quantum cryptography: Public key distribution and coin tossing,
{\em Proceedings of IEEE International Conference on Computers,
Systems and Signal Processing},
Bangalore, India, December~1984, \mbox{pp.~175\,--\,179}.

\bibitem{bbbss90} C.H.~Bennett, F.~Bessette, G.~Brassard, L.~Salvail
and J.~Smolin, 
%``Experimental quantum cryptography'', 
{\em Journal of Cryptology}, vol.~5, no.~1, 1992,
\mbox{pp.~3\,--\,28}.

\bibitem{bbcs92} 
Charles~H.~Bennett and Gilles~Brassard, 
Claude~Cr\'epeau, Marie-H\'el\`ene~Skubiszewska,
%Practical Quantum Oblivious Transfer,
{\em Proceedings} {\em of CRYPTO'91}, vol.~576, Springer\,--\,Verlag,
Berlin, 1992, \mbox{pp.~351\,--\,366}.


\bibitem{bc96}
G. Brassard,
%``Cryptology column --- 25 years of quantum cryptography'',
Sigact News, Vol. 27, no. 3, September 1996, pp. 13-24.

%ATTENTION!!!  PRL risque d'enlever ET "no. 3" ET "September",
%ce qui rendra la reference ambigue car il y a 4 numeros dans
%Vol 27 et chaque numero commence a la page 1 !


\bibitem{bcjl93} 
Gilles~Brassard, Claude Cr\'epeau, Richard 
Jozsa, Denis Langlois,
%A~quantum bit commitment scheme provably unbreakable by both
%parties'',
in {\em Proceeding of the 34th \mbox{annual} IEEE Symposium on
foundations of Computer Science},
November 1993, \mbox{pp.~362\,--\,371}.

\bibitem{cdg87}
D.~Chaum, I.~B.~Damg{\aa}rd  and J.~van de Graaf,
%Multiparty computations ensuring privacy of each
%party's input and correctness of the result,
{\em Advances in Cryptology\,--\,Crypto'87 Proceedings},
august~1987, Springer\,--\,Verlag, \mbox{pp.~87\,--\,119}.


\bibitem{crepeau94}
Claude~Cr\'epeau
%Quantum oblivious transfer, 
{\em Journal of Modern Optics}, vol.~41, no.~12, December~1994,
\mbox{pp.~2445\,--\,2454}.

\bibitem{cgt95} 
Claude~Cr\'epeau,
Jeroen~van~de~Graaf,  
Alain~Tapp,
%Committed Oblivious Transfer and Private Multi-Party Computation,
{\em Advances in Cryptology: Proceeding of Crypto~'95},
Vol 963, Springer\,--\,Verlag, Berlin, 1995, \mbox{pp.~110\,--\,123}.


\bibitem{gmw87}
O.~Goldreich, S.~Micali and  A.~Wigderson, 
%How to play any mental game, or: A completeness theorem
%for protocols with honest majority,
{\em Proceedings of 19th ACM Symposium on Theory of
Computing}, may~1987, \mbox{pp.~218\,--\,229}.

\bibitem{gm96} ..., D.~Mayers,..., ``Title to be determined''
Submitted to Journal of Cryptology.  
 
\bibitem{hjw93}
L.~P.~Hughston,
Richard~Jozsa and William~K.~Wootters, 
%A complete classification of quantum ensembles having a given 
%density matrix'', 
{\em Physics Letters A}, vol.~183, \mbox{pp.~14\,--\,18}, 1993.


\bibitem{jozsa94}
Richard~Jozsa,
Fidelity for mixed quantum states, 
{\em Journal of Modern  Optics}, 
vol.~41, no.~12, \mbox{pp.~2315\,--\,2323}, 1994.

\bibitem{kilian88}
Joe~Kilian,
%Founding cryptography on oblivious transfer,
{\em Proceedings of the 20th symposium on Theory of Computing}, 
may~1988, \mbox{pp.~20\,--\,31}.

\bibitem{lc96a} 
H-K.~Lo and H.~F.Chau, 
Is~quantum bit commitment really possible?,
Los~Alamos preprint archive {\tt quant-ph/9603004}, March~1996.


\bibitem{mayers96c}
D.~Mayers,
``Quantum key distribution and string oblivious transfer on noisy
channels'',
{\em Advances in Cryptology: Proceeding of Crypto'96}, ao\^ut~1996,
Springer\,--\,Verlag, \mbox{pp.~343\,--\,357}.


% \bibitem{new_york_times}
% Kirk~Johnson, The New York Times, 13 May 1993. 

\bibitem{salvail95} L.~Salvail, personal communication.

\bibitem{schmidt06}
E.~Schmidt,
Math. Ann. 63 (1906) 433.

\bibitem{yao95}
Andrew~Yao,
In {\em Proceedings of the 26th Symposium on the Theory
of Computing}, June~1995;
\mbox{pp.~67\,--\,75}.

%\bibitem{yao95b}
%Andrew~Yao,
% ``Quantum circuit complexity'',
%{\em Proceedings of the 34th IEEE Symposium on Foundations of
%Computer Science}, IEEE Press, 1993, \mbox{pp.~352\,--\,361}.

\end{thebibliography}}

\end{document}     
   


