[4957] in cryptography@c2.net mail archive
Quantum Computation Papers, some on cryptography
daemon@ATHENA.MIT.EDU (Zombie Cow)
Thu Jun 24 12:34:55 1999
Date: Thu, 24 Jun 1999 15:56:58 +0300 (EEST)
From: Zombie Cow <waste@zor.hut.fi>
To: cryptography@c2.net
Cc: cypherpunks@toad.com
Thought these might be of interest here, as similar papers have been..
---------- Forwarded message ----------
point your www client at http://xxx.lanl.gov/
------------------------------------------------------------------------------
Submissions to: Cryptography and Security
------------------------------------------------------------------------------
------------------------------------------------------------------------------
\\
Paper (*cross-listing*): quant-ph/9604007
From: Christophe.Durr@lri.fr (Christophe Durr)
Date: Tue, 9 Apr 1996 19:05:26 +0200 (18kb)
Date (revised): Fri, 12 Jul 1996 10:22:15 MDT
Date (revised): Mon, 28 Oct 1996 05:16:34 MST
Date (revised): Tue, 11 Nov 1997 19:57:45 GMT
Date (revised): Mon, 21 Jun 1999 14:02:52 GMT
Title: A decision procedure for unitary linear quantum cellular automata
Authors: Christoph Durr (LRI), Miklos Santha (CNRS)
Comments: Updated for submission to SIAM Journal on Computing. Improved
slightly the algorithm
Subj-class: Quantum Physics; Computational Complexity
Journal-ref: Proceeding of the 37th IEEE Symposium on Foundations of Computer
Science, 38--45, 1996
\\
Linear quantum cellular automata were introduced recently as one of the
models of quantum computing. A basic postulate of quantum mechanics imposes a
strong constraint on any quantum machine: it has to be unitary, that is its
time evolution operator has to be a unitary transformation. In this paper we
give an efficient algorithm to decide if a linear quantum cellular automaton is
unitary. The complexity of the algorithm is O(n^((3r-1)/(r+1))) = O(n^3) in the
algebraic computational model if the automaton has a continuous neighborhood of
size r, where $n$ is the size of the input.
\\ ( http://xxx.lanl.gov/abs/quant-ph/9604007 , 18kb)
------------------------------------------------------------------------------
\\
Paper (*cross-listing*): quant-ph/9603004
From: "Hoi-Kwong Lo" <hkl@hplb.hpl.hp.com>
Date: Mon, 4 Mar 1996 15:57:53 -0500 (10kb)
Date (revised): Wed, 2 Apr 1997 20:10:25 +0100
Title: Is Quantum Bit Commitment Really Possible?
Authors: Hoi-Kwong Lo and H. F. Chau
Comments: Major revisions to include a more extensive introduction and an
example of bit commitment. Overlap with independent work by Mayers
acknowledged. More recent works by Mayers, by Lo and Chau and by Lo are also
noted. Accepted for publication in Phys. Rev. Lett
Subj-class: Quantum Physics; Cryptography and Security
\\
We show that all proposed quantum bit commitment schemes are insecure because
the sender, Alice, can almost always cheat successfully by using an
Einstein-Podolsky-Rosen type of attack and delaying her measurement until she
opens her commitment.
\\ ( http://xxx.lanl.gov/abs/quant-ph/9603004 , 10kb)
------------------------------------------------------------------------------
\\
Paper (*cross-listing*): quant-ph/9611031
From: "Hoi-Kwong Lo" <hkl@hplb.hpl.hp.com>
Date: Tue, 19 Nov 1996 10:08:47 +0000 (18kb)
Date (revised): Mon, 28 Apr 1997 19:00:14 +0100
Title: Insecurity of Quantum Secure Computations
Author: Hoi-Kwong Lo (HP Labs, Bristol and University of Santa Barbara)
Comments: The discussion on the insecurity of even non-ideal protocols has been
greatly extended. Other technical points are also clarified. Version accepted
for publication in Phys. Rev. A
Subj-class: Quantum Physics; Cryptography and Security
\\
It had been widely claimed that quantum mechanics can protect private
information during public decision in for example the so-called two-party
secure computation. If this were the case, quantum smart-cards could prevent
fake teller machines from learning the PIN (Personal Identification Number)
from the customers' input. Although such optimism has been challenged by the
recent surprising discovery of the insecurity of the so-called quantum bit
commitment, the security of quantum two-party computation itself remains
unaddressed. Here I answer this question directly by showing that all
``one-sided'' two-party computations (which allow only one of the two parties
to learn the result) are necessarily insecure. As corollaries to my results,
quantum one-way oblivious password identification and the so-called quantum
one-out-of-two oblivious transfer are impossible. I also construct a class of
functions that cannot be computed securely in any ``two-sided'' two-party
computation. Nevertheless, quantum cryptography remains useful in key
distribution and can still provide partial security in ``quantum money''
proposed by Wiesner.
\\ ( http://xxx.lanl.gov/abs/quant-ph/9611031 , 18kb)
------------------------------------------------------------------------------
\\
Paper (*cross-listing*): quant-ph/9904091
From: Hoi-Kwong Lo <hkl@hplb.hpl.hp.com>
Date: Tue, 27 Apr 1999 08:49:27 GMT (14kb)
Title: A simple proof of the unconditional security of quantum key distribution
Authors: Hoi-Kwong Lo (Hewlett-Packard Labs, Bristol)
Comments: 13 pages, extended abstract. Comments will be appreciated
Subj-class: Quantum Physics; Cryptography and Security
\\
Quantum key distribution is the most well-known application of quantum
cryptography. Previous proposed proofs of security of quantum key distribution
contain various technical subtleties. Here, a conceptually simpler proof of
security of quantum key distribution is presented. The new insight is the
invariance of the error rate of a teleportation channel: We show that the error
rate of a teleportation channel is independent of the signals being
transmitted. This is because the non-trivial error patterns are permuted under
teleportation. This new insight is combined with the recently proposed quantum
to classical reduction theorem. Our result shows that assuming that Alice and
Bob have fault-tolerant quantum computers, quantum key distribution can be made
unconditionally secure over arbitrarily long distances even against the most
general type of eavesdropping attacks and in the presence of all types of
noises.
\\ ( http://xxx.lanl.gov/abs/quant-ph/9904091 , 14kb)
------------------------------------------------------------------------------
\\
Paper (*cross-listing*): quant-ph/9607014
From: Christophe.Durr@lri.fr (Christophe Durr)
Date: Thu, 18 Jul 1996 21:12:42 +0200 (4kb)
Date (revised): Thu, 7 Jan 1999 16:50:45 GMT
Title: A Quantum Algorithm for Finding the Minimum
Authors: Christoph Durr and Peter Hoyer
Comments: 2 pages
Subj-class: Quantum Physics; Data Structures and Algorithms
\\
We give a quantum algorithm to find the index y in a table T of size N such
that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.
\\ ( http://xxx.lanl.gov/abs/quant-ph/9607014 , 4kb)
%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%
------------------------------------------------------------------------------
