Quantum Passwords
Christian Weedbrook
A quantum password is a quantum mechanical analogue of the classical password. Our proposal is completely quantum mechanical in nature, i.e. at no point is information stored and manipulated classically. We show that, in contrast to quantum protocols that encode classical information, we are able to prevent the distribution of reusable passwords even when Alice actively cooperates with Eve. This allows us to confront and address security issues that are unavoidable in classical protocols.
Quantum_Passwords_arxiv.tex
\documentclass[10pt,pra,twocolumn,superscriptaddress]{revtex4}

\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{times}
\usepackage{amsmath}

\newcommand{\bra}[1]{\langle#1|}
\newcommand{\ket}[1]{|#1\rangle}

%\renewcommand{\baselinestretch}{2}


\begin{document}


\title{Quantum Passwords}


\author{Christian Weedbrook}

\author{Mile Gu}

\address {Department of Physics, University of Queensland, St
Lucia, Queensland 4072, Australia}


\date{\today}


\begin{abstract}

A quantum password is a quantum mechanical analogue of the
classical password. Our proposal is completely quantum mechanical
in nature, i.e. at no point is information stored and manipulated
classically. We show that, in contrast to quantum protocols that
encode classical information, we are able to prevent the
distribution of reusable passwords even when Alice actively
cooperates with Eve. This allows us to confront and address
security issues that are unavoidable in classical protocols.

\end{abstract}

\pacs{03.67.Dd, 42.50.Dv, 89.70.+c}

\maketitle



\section{Introduction}

Alice, a physicist, decides to purchase a subscription to a well
known online physics journal that is run by an entity we shall call
Bob. Once the transaction is complete, she is given a password that
allows her access to the journal, a password that can be distributed
at will. In particular, Alice gives the password to her friend Eve,
who then resells it to the horde of independent physicists
interested only in obtaining the journal at a cheaper price. Even if
Alice were only to distribute the password to three of her closest
friends, Bob's income would be a quarter of what it should be. Yet,
there is no guaranteed method in which Bob can prevent and detect
such behavior.

In this new age of information, passwords have become an essential
part of everyday life, used for e-mails, bank accounts, CD-keys and
a multitude of online products. Yet such passwords are often saved
on a customer's computer, easily vulnerable to viruses and trojan
attacks. Once such information is extracted by Eve, she is free to
mass distribute it, exacerbating everything from piracy, unlawful
reselling to the more serious cases of identity theft. For example,
CD-keys are often used as a method to prevent piracy, especially for
programs that involve an online service. Yet, nothing prevents a
person from purchasing the software and copying it, writing down the
key and returning it under a standard money back guarantee.

Classically, the only proven method to prevent password sharing is
the use of one-time passwords, where a different password is
required each time Alice accesses the system. Such a protocol
creates a number of inconveniences, such as the unsuitability for
group licenses, where a service is sold to a specified number of
people. Also, Eve can steal one-time passwords at no risk, as she
does not disturb Alice or Bob's system until she uses the password.

{\it Can the laws of quantum mechanics guarantee the security of
Alice's information, even from herself?} So that there always
exists a test that Alice can make to determine if Eve has taken
her password before Eve makes use of it. In this way Bob can be
fully confident that the service he sells cannot be distributed or
resold to multiple people. In this paper, we propose a quantum
analogue of the classical password, whose security is guaranteed
by the no-cloning theorem \cite{WZ82}. In contrast to the
classical one-time password scheme, our quantum password is not
one time. Also the fact that Eve can be detected as soon as she
takes the password, discourages any attempt to do so.

While our proposal shares some similarities in aim with quantum
identification schemes \cite{Cre95,GG05} and quantum cryptography
protocols \cite{BB84}, it has one critical distinction. We do not
assume Alice's station is secure, or even that she is on Bob's side.
In particular, all of the aforementioned protocols involve a
password stored as classical information which is encoded into a
quantum state for transmission. While they guarantee security during
transmission, Alice's password, stored at her station, can always be
cloned without detection. The only previous proposal \cite{Mih01} in
this area was one time, and demonstrated to be equivalent to
proposals based on classical correlations \cite{dam03}. In this
paper, we argue that a password can be verified using an entirely
physical process, and unlike classical documents, need not be read
by a human being. Therefore it is not necessary for a password to be
an encoding of classical information.

{\it We propose a quantum password represented entirely by a quantum
state that has no set basis of measurement and encodes no classical
information}. Since our protocol does not require Alice to have any
knowledge of this quantum state, the no-cloning theorem can be
easily employed. Thus Alice cannot distribute her password to
anyone, short of giving it away and consequently losing her only
copy. Therefore there is only one quantum password existing, per
person, at any one time. In addition, the quantum nature of the
password means that it cannot be measured exactly, and allows our
protocol to retain its security even when Bob's login server in
vulnerable. That is, even if Eve has access to Bob's login server,
she still cannot access the restricted content without detection.
This is not possible classically and is a further distinction from
the one-time password protocol.

\begin{figure*}[!ht]
\begin{center}
\includegraphics[width = 16cm,height = 9cm]{figure1}
\caption{{\bf The quantum password protocol can be broken up into
three stages: (a) setting up the account (b) using the quantum
password and (c) the verification by Bob. Here Alice's quantum
password is given by $\phi$ and Bob's stored copy of the password
given by $\psi$.}}\label{figure_quantum_passwords}
\end{center}
\end{figure*}
%


\section{Quantum Password Protocol}

The standard protocols of classical passwords can be divided into
various stages: the creation of an account when Alice signs up for
a service provided by Bob, the distribution of the password from
Alice to Bob, and the process of password verification by Bob.
More explicitly, Alice would purchase the password from Bob, which
is used for verification each time she wishes to access Bob's
product. In the quantum version of this protocol, all three steps
are kept intact (see Fig.~\ref{figure_quantum_passwords}). The
major difference is that the password itself will be a quantum
object, and the process of transmission and verification are both
done quantum mechanically.

\subsection{Assumptions}

Since the passwords featured within this protocol are not
encodings of classical information, we are able to make several
significant relaxations to the assumptions made in quantum
cryptography \cite{BB84}. As aforementioned, we assume that
Alice's server is insecure, and in addition, Eve also has the
ability to extract information from Bob's log-in server. These
conditions are realistic, given that it is no harder, and often
easier to install viruses into another's computer than to extract
information during transmission.

However we do assume that there exists an unjammable classical
public channel between Alice and Bob, such that Alice is able to
contact Bob should her password be compromised. When these
conditions are met, the protocol is completely secure, where
security is defined by the fact that Eve cannot take the password
without disturbing the system, and hence cannot escape detection.
Explicitly, if Eve gains any information about the quantum password,
there exists a finite probability that she will be detected.

\subsection{Setting up the Quantum Password}

Alice contacts Bob who organizes to give Alice her own quantum
password (along with a classical username which will be omitted in
further discussion). For simplicity, we consider that each
password consists of only one qubit. In practice, the quantum
password would consist of many qubits, so that the probability of
a successful random guess is negligible. Bob generates a random
password given by
%
\begin{eqnarray} |\psi\rangle = c_1|0\rangle + c_2
|1\rangle
\end{eqnarray}
%
where $|c_1|^2 + |c_2|^2 = 1$, and creates an identical clone
$\ket{\phi}$ - this does not violate the no-cloning theorem as the
state is known to Bob. Bob stores his cloned qubit in quantum
memory and sends the other qubit to Alice through an insecure
quantum channel.

\subsection{Using the Quantum Password}

In order for Alice to use her quantum password, she sends it back
along the quantum channel to Bob. Bob then needs to compare his
stored copy of Alice's quantum password $|\phi\rangle$ with the
quantum password Alice has sent to him $|\psi\rangle$. If both
passwords are identical, then Bob will allow Alice access to his
computer.

\subsection{Verifying the Quantum Password}

To compare the two quantum passwords $|\phi\rangle$ and
$|\psi\rangle$, Bob performs a controlled-SWAP operation
\cite{Buh01} using a Fredkin gate \cite{Nie00} to determine if
they are identical (see Fig.~\ref{cswap}). The advantage is that
this operation can be performed without explicit knowledge of
either of the quantum passwords. Explicitly, Bob introduces an
ancilla qubit and performs the operation
%
\begin{eqnarray}\label{SWAP equation}
|\gamma \rangle = (\hat{H}\otimes \hat{I}) {\rm
(c-SWAP)}(\hat{H}\otimes \hat{I})|0\rangle
|\phi\rangle|\psi\rangle
\end{eqnarray}
%
where $\hat{H}$ is the Hadamard operator that transforms $|{\rm
a}\rangle \rightarrow \frac{1}{\sqrt2} (|0 \rangle + (-1)^{{\rm
a}}|1 \rangle)$ with ${\rm a}\in (0,1)$ and acts only on the Hilbert
space of the ancilla qubit $|0 \rangle$.  $\hat{I}$ is the identity
operator acting only on $|\phi\rangle |\psi\rangle$. The
controlled-SWAP is the operation which swaps the states
$|\phi\rangle$ and $|\psi\rangle$ depending on the parity of the
ancilla qubit. That is, it performs the SWAP operation
%
\begin{eqnarray}\label{SWAP position}
|\phi\rangle |\psi\rangle \rightarrow |\psi\rangle |\phi\rangle
\end{eqnarray}
%
if the state of the ancilla qubit is $|0\rangle$ and acts as the
identity if the qubit is $|1\rangle$. The resulting state of the
system can be written as
\begin{eqnarray}
|\gamma \rangle = \frac{1}{2} |0\rangle (|\phi \rangle |\psi \rangle
+ |\psi \rangle |\phi \rangle) + \frac{1}{2} |1\rangle (|\phi
\rangle |\psi \rangle - |\psi \rangle |\phi \rangle).
\end{eqnarray}
%
Bob will now measure the ancilla qubit in the computational basis
$|0\rangle$ and $|1\rangle$ with outcome probabilities given by
\begin{eqnarray}\label{P(1)}
P(1) = |\langle 1|\gamma \rangle|^2 = \frac{1}{2}(1 - |\langle \phi
| \psi \rangle|^2),\\\label{P(0)} P(0) = |\langle 0|\gamma
\rangle|^2 = \frac{1}{2}(1 + |\langle \phi | \psi \rangle|^2),
\end{eqnarray}
If the two quantum passwords are identical, i.e. $|\phi\rangle =
|\psi\rangle$, then from Eqs.~(\ref{P(1)},\ref{P(0)}) we have $P(1)
= 0$ and $P(0) = 1$. Thus if Bob were to measure 1, he knows with
certainty that the supplied password is incorrect. However if he
were to measure $0$, he would assume the password to be correct and
allow access. Note that since $P(0) < 1$ when the states are not
identical, extending the length of the quantum password will ensure
that Eve cannot achieve success through a random guess.
Additionally, should the passwords be\ identical, this measurement
process will leave the quantum passwords unchanged. Therefore the
quantum password is reusable and not a one-time password equivalent.
%
\begin{figure}[!ht]
\begin{center}
\includegraphics[width = 8cm]{figure2}
\caption{{\bf Schematic of the quantum circuit used by Bob to
verify Alice's quantum password; where H is a Hadamard gate and
the controlled-SWAP is achieved using a Fredkin
gate.}}\label{cswap}
\end{center}\
\end{figure}
%

\section{Security of Quantum Passwords}


The security of the quantum password scheme is due to the
no-cloning theorem \cite{WZ82} which states that an unknown
quantum state cannot be perfectly cloned. In addition, any
measurement made on such a state will in general disturb it. In
order for Eve to steal Alice's password without any chance of
detection, she would be required to take it from Alice's station
or intercept it during transmission, clone it perfectly and then
return the original password without detection. Since we assume
Alice's station is not secure, Eve is free to perform the first
and final steps, but can only perform an approximation of the
second.

Suppose Eve were to make an attempt in breaching the security of the
quantum password protocol. That is, she desires to create a quantum
state $\ket{\phi'}$ that is a good approximation to the true
password $\ket{\phi}$ without detection from Alice or Bob. Eve is
forbidden to modify Alice's password significantly, since doing so
would cause Alice's password to fail during the SWAP verification
and hence reveal her actions. Let us first assume Eve uses the
symmetric universal quantum cloning machine \cite{Buz96}. Given an
input state $\ket{\phi}$, the cloning machine would output two
identical cloned quantum passwords with a fidelity of $5/6$ with
respect to the original input. For qubit states, the two clones can
be described by the same density operator
%
\begin{equation}
\hat{\rho}_{out} = \frac{5}{6}\ket{\phi}\bra{\phi} +
\frac{1}{6}\ket{\psi}\bra{\psi}
\end{equation}
%
where $\ket{\psi}$ is a quantum state containing the errors of the
cloning machine and is orthogonal to $\ket{\phi}$, i.e. $\langle
\psi| \phi\rangle = 0$.

In order for Eve to steal the password successfully, two events must
occur. Firstly, Alice's quantum password must not be disturbed to
the point where she can no longer access Bob's network, and
secondly, the clone she has created must be accepted by Bob's
server. Clearly, for a quantum password consisting of a single
qubit, Eve chance of successfully using a clone is given by $(5/6)^2
\approx 69\%$ (see Fig.~\ref{plot_quantum_passwords}). Thus, for a
quantum password of $N$ qubits in length, Eve's success rate is
reduced exponentially to $(5/6)^{2N}$.

In the more general case where Eve utilizes two nonidentical clones
from an asymmetrical quantum cloning machine \cite{Niu98}, it can be
demonstrated that the fidelity of the clone $F_S$, and the password
after measurement with respect to the original input $F_S'$, must
satisfy the relation $F_S F_S' \leq 5/6$ \cite{Filo4}. Thus Eve's
success rate is always bounded by $(5/6)^{2N}$. Therefore, provided
we use a quantum password of sufficient length, the security of the
protocol is guaranteed against such an attack.

Additionally, by assuming that Bob's login server is also
insecure, Eve has the option of cloning Bob's quantum password
instead. However, since Bob has knowledge of what the password is,
he can always check whether it has been modified by comparing it
to an offline (and thus secure) copy of the password. Should such
a comparison fail at any time, he would generate a new quantum
password and eliminate any information Eve may have gained from
the state. Thus, the analysis of security for such an attack is
reduced to the previous case.
%
\begin{figure}[!ht]
\begin{center}
\includegraphics[width = 8cm]{figure3}
\caption{{\bf Probability that Eve can successfully use a clone of
a quantum password verses the number of qubits contained in the
password. Eve's success rate is bounded by $(5/6)^{2N}$ due to the
fidelity of her quantum cloning machine. If Bob uses $13$ or more
qubits, then he is guaranteed that a fraudulent password will be
detected at least $99.9\%$ of the time.
}}\label{plot_quantum_passwords}
\end{center}
\end{figure}
%

\section{Applications of Quantum Passwords}

Passwords were designed with the intention of providing secure
services, in the sense that such services can only be used by
authorized parties. The ability to clone and distribute a password
clearly violates this intention, and, is greatly detrimental to any
service which involves the use of such devices. As quantum passwords
cannot be cloned, it is potentially applicable to any protocol that
involves a variation of the classical password. For example:

\begin{enumerate}
    \item CD-keys are currently a widely used method to prevent
piracy, used to validate the authenticity of a program whenever a
user attempts to access some related online service. Suppose Alice
runs a cybercafe with such programs installed. CD-key grabbers are
commonly available for a visitor, Eve, to steal the key. If the
passwords were made quantum, any such attempts can by easily
detected by quantum password verification prior to Eve's departure
from the cybercafe. Therefore, the chance of being caught on the
spot will severely discourage such attempts.
%There
%is currently very little she can do to prevent a customer, Eve, from
%extracting the CD-key from one of her computers, and effectively
%stealing the program itself.


    \item Credit Card numbers are a variation of
classical passwords. If Alice were to purchase concert tickets over
the phone, she would need to give the information required to access
her account to a third party operator, effectively cloning her
password. The operator, can now retain and distribute this knowledge
at her leisure. This problem cannot be circumvented using either
classical or quantum cryptography since the operator, by definition,
must have all the necessary knowledge to access Alice's account. A
quantum password prevents this problem, as the operator must return
the password back to Alice, and any attempt to extract information
during the process could be detected.

    \item Variations of the quantum password protocol can be
implemented for ATM transactions where we need not assume security
of either the client Alice, or even the login server, i.e. the ATM
itself. Alice's quantum bank card stores a quantum state, which is
matched by a clone on the bank's central server. Upon a
transaction request, Bob sends his quantum password to the
appropriate ATM and performs the verification protocol. Even if
Eve had access to the ATM, she would still be unable to use it
without detection. Classical solutions, such as the S/Key one-time
password scheme \cite{Lam81}, based on the computational
difficulty
    of inverting the cryptographic hash function, are not formally
    secure.
\end{enumerate}


\section{Discussion}

Quantum passwords adopt a purely quantum approach to password
identification, and in doing so, provides security that no classical
protocol, or quantum protocol that involves the encoding of
classical information, can offer. The implementation of quantum
passwords will require reliable quantum memory and quantum gates.
However, there is no explicit need for universal quantum processors
and is a protocol that can be achieved in the medium term.

In this paper, we have outlined the idea of quantum passwords in
the simplest possible implementation using a string of qubits,
though in reality, this need not be so. One can note that the
verification process does not assume that the quantum password
lives in any specific Hilbert space, and thus, one can envision
encoding such passwords in higher dimensions. For example, a
continuous variable version would be able to take advantage of the
high detection efficiencies and higher information bandwidths.

Future work could also be done in the analysis of how information
loss due to noise or decoherence would affect the security of the
protocol. In this case, Bob would need to take into account the
natural losses during storage and transmission, and accept Alice's
password provided a certain proportion of the qubits matched
according to the SWAP protocol. Of course, this leeway would give a
greater chance of using a cloned password, and one would be
interested in the region where the protocol remains secure against
such losses.

\section{Conclusion}

In conclusion, we have introduced a quantum password scheme whose
security is guaranteed by the no-cloning theorem. When
implemented, such a protocol would allow consumers to purchase
items over the phone without worry, knowing that they could check
if the operators on the other end have copied down their credit
card details. It would give subscription services the peace of
mind that the passwords they sell cannot be distributed over the
internet. It also bestows the added security when the login server
itself becomes vulnerable, such as an ATM. Such security is made
possible since our password is not a quantum encryption of
classical information, but simply a quantum state. In short, we
take advantage of the fact that passwords are meant to be used,
not read.

We would like to thank Tim Ralph, Mark Dowling and Henry Haselgrove
for comments and useful discussions.


\begin{thebibliography}{99}

\bibitem{WZ82} W.K. Wooters and W.H. Zurek, {\it Nature} {\bf
299}, 802 (1982).

\bibitem{Cre95} C. Crepeau and L. Salvail in {\it Advances in
Cryptography: Proceedings of Eurocrypt '95} (Springer, Berlin,
1995), p. 133.

\bibitem{GG05} H. Guang-Qiang and Z. Gui-Hua, {\it Chinese
Physics}, {\bf 14}, 0541-05, (2005).

\bibitem{BB84} C.H. Bennett and G.Brassard, in {\it Proceedings IEEE International Conference on Computers, Systems and Signal Proceedings
(Bangalore)} (IEEE, New York, 1984), pp. 175-179.

\bibitem{Mih01} T. Mihara, Phys. Rev. A {\bf 65}, 052326, (2002).

\bibitem{dam03} W. van Dam, Phys. Rev. A {\bf 68}, 026301 (2003).

\bibitem{Buh01} H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, {\it \prl},
{\bf 87}, 167902, (2001).

\bibitem{Nie00} M.A. Nielsen and I.L. Chuang, {\it Quantum Computation and Quantum Information}
(Cambridge University Press, 2000).

\bibitem{Buz96} V. Bu${\rm \check{z}}$ek and M.Hillery, Phys. Rev. A {\bf 54}, 1844 (1996).

\bibitem{Niu98} C.-S. Niu and R. B. Griffiths, Phys. Rev. A {\bf 58}, 4377
(1998); V. Bu${\rm \check{z}}$ek {\it et al.}, Acta Phys. Slov.
{\bf 48}, 177 (1998); N. J. Cerf, Acta Phys. Slov. {\bf 48}, 115
(1998); N. Cerf, {\prl} {\bf 84}, 4497 (2000).

\bibitem{Filo4} R. Filip, Phys. Rev. A {\bf 69}, 032309 (2004).

\bibitem{Lam81} L. Lamport, Communications of the ACM, 770-772, (1981).


\end{thebibliography}

\end{document}

quant-ph0506255.extracted_bib
\begin{thebibliography}{99}

\bibitem{WZ82} W.K. Wooters and W.H. Zurek, {\it Nature} {\bf
299}, 802 (1982).

\bibitem{Cre95} C. Crepeau and L. Salvail in {\it Advances in
Cryptography: Proceedings of Eurocrypt '95} (Springer, Berlin,
1995), p. 133.

\bibitem{GG05} H. Guang-Qiang and Z. Gui-Hua, {\it Chinese
Physics}, {\bf 14}, 0541-05, (2005).

\bibitem{BB84} C.H. Bennett and G.Brassard, in {\it Proceedings IEEE International Conference on Computers, Systems and Signal Proceedings
(Bangalore)} (IEEE, New York, 1984), pp. 175-179.

\bibitem{Mih01} T. Mihara, Phys. Rev. A {\bf 65}, 052326, (2002).

\bibitem{dam03} W. van Dam, Phys. Rev. A {\bf 68}, 026301 (2003).

\bibitem{Buh01} H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, {\it \prl},
{\bf 87}, 167902, (2001).

\bibitem{Nie00} M.A. Nielsen and I.L. Chuang, {\it Quantum Computation and Quantum Information}
(Cambridge University Press, 2000).

\bibitem{Buz96} V. Bu${\rm \check{z}}$ek and M.Hillery, Phys. Rev. A {\bf 54}, 1844 (1996).

\bibitem{Niu98} C.-S. Niu and R. B. Griffiths, Phys. Rev. A {\bf 58}, 4377
(1998); V. Bu${\rm \check{z}}$ek {\it et al.}, Acta Phys. Slov.
{\bf 48}, 177 (1998); N. J. Cerf, Acta Phys. Slov. {\bf 48}, 115
(1998); N. Cerf, {\prl} {\bf 84}, 4497 (2000).

\bibitem{Filo4} R. Filip, Phys. Rev. A {\bf 69}, 032309 (2004).

\bibitem{Lam81} L. Lamport, Communications of the ACM, 770-772, (1981).


\end{thebibliography}