15 December 1999
Date: Wed, 01 Dec 1999 08:46:01 +0000
From: Ben Laurie <ben@algroup.co.uk>
To: Coderpunks <coderpunks@toad.com>
Subject: Universal Quantum Computers
People may be interested in last week's Nature article, D. Gottesman and I.L. Chuang, "Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations", Nature 402, 390-392.
One thing that should make software authors jump for joy is that the method involves quantum software that is hard to make yet is consumed during the computation. Enforcable software leasing, woo! [1]
Whether it is of any significance that the authors work for Microsoft and IBM respectively I leave to the reader to decide.
Cheers,
Ben.
[1] No, I don't think this is a good thing.
--
http://www.apache-ssl.org/ben.html
"My grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the first group; there was less competition there." - Indira Gandhi
Date: Wed, 01 Dec 1999 09:08:50 +0000
To: Coderpunks <coderpunks@toad.com>
From: Stanley J Houghton <S.J.Houghton@Bradford.ac.uk>
Subject: Re: Universal Quantum Computers
I realise it was a comment in jest but this area is more significant than many of us may think.
If quantum computation comes of age, cryptography will have to change enormously since we are faced with potential new technology that overcomes classical limits underlying cryptographic systems, eg factorising very large numbers. I am referring to the enormous parallelism that may be achieved through superposition of values in quantum bit based registers.
See
http://eve.physics.ox.ac.uk/qcweb/intro/intro.html
and I believe
http://www.qubit.org
for relevant information.
Hope it is of interest
Stan
Date: Wed, 1 Dec 1999 17:42:26 -0600 (CST)
From: Mike Rosing <eresrch@mendota.terracom.net>
To: Bill Stewart <bill.stewart@pobox.com>
cc: coderpunks@toad.com
Subject: Re: Universal Quantum Computers
On Wed, 1 Dec 1999, Bill Stewart wrote:
> Mike - I don't know if you'd know this, or if not,
> I'd appreciate pointers to people who would -
Check out the Los Alamos papers:
http://hana-mana.lanl.gov/Quantum/quantum.html#contents
> Are quantum computers limited by the Heisenberg Uncertainty Principle?
Yes :-)
> If so, then their maximum precision is about Planck's Constant,
> which is about 140 bits (as opposed to the current precision of ~3 bits
:-)
Whoa!! What's the maximum precision of Plank's constant have to do with anything? Just because we can only measure it that well, doesn't mean it has any less than infinite number of bits to fully describe it.
> This means that we may have to add a few more bits to our key lengths,
> and cracking too-short keys becomes immensely faster,
> but it doesn't fundamentally change the usefulness of public-key
crypto,
> either factoring-based systems like RSA or discrete-log like DH.
> (I don't know if it means that primes need to be 140 bits longer,
> or if they need to be factoring-equivalent-workload-to-140-bits,
> which is probably about 1000-4000 more bits, but either way it doesn't
matter,
> because it's just a small multiplier to the workload.)
The uncertainty principle relates to the coherency problem. It has nothing to do with the number of qubits you can work on. Of course, the more qubits, the worse the coherency is. But at present people are thinking in terms of individual qubits and gates. In the future, we'll have all the qubits in one "gate". If we can get 1000 qubits in one gate, they all interact and we can set up the gate to solve a 1000 bit RSA (or ECDLP) problem in one "clock". I'm putting this stuff in quotes because they are conceptual, not presently realizable.
> The technical meaning of being limited by Heisenberg is that
> you have one device that can handle a waveform with
> 2**N superpositioned states and collapse it into the correct N bits.
> If you've got two devices in parallel, then probably they can do
> 2*2**N states, i.e. N+1 bit answers, which is no problem.
> But if there's a way to get them to do 2**N * 2**N,
> i.e. 2**2N states and 2N bits of answer,
> without violating Heisenberg's for large N, then you have results
> that violate the little I remember of college quantum,
> and they _can_ affect the use of public-key crypto.
Right. At the ECC '99 conference there was a talk by a professor who specializes in QC's. He said all PK's would fall if a QC could work. He also seemed to think that the number of qubits would grow at a rate of about 1 per year for the next 50 years. 50 qubits won't crack anything, so for all practical purposes QC's won't be a threat for any PK systems in the next 100 years.
I don't think that's correct, but the following is pure conjecture. Once we get gate sizes in the 10 angstrom level, we'll be doing quantum mechanics across the entire structure of a set of gates. We're now at the 100 nm == 1000 angstrom level. Since gates go as area, it takes 3 years by Moore's law to halve the linear dimension. So in 7*3 = 21 years we'll be down to the 10 angstrom level. I think we'll learn a lot about quantum effects at that point, and to keep Moore's law on track we'll start developing quantum computers. At the 1 angstrom level, we'll have to increase the number of bits per atom, and that's when quantum computers will be fully operational. That's only 30 years from now (give or take 3).
So I might live to see it, which would be really cool!
Patience, persistence, truth,
Dr. mike
Date: Wed, 1 Dec 1999 16:54:24 -0500 (EST)
To: Mike Rosing <eresrch@mendota.terracom.net>
cc: Coderpunks <coderpunks@toad.com>
Subject: Re: Universal Quantum Computers
On Wed, 1 Dec 1999, Mike Rosing wrote:
> It will eventually work and it will eventually be *very* important.
> Individual qubits make some things like factoring easier. A whole
lot
> of qubits in parallel will make molecular design easy (or at least
> doable).
I hear a lot about how cryptography is going to need to be changed around with the advent of quantum computing.
If a working quantum computer were invented today, what sort of crypto tools would need to get thrown away, and what sorts of stuff could we keep?
Off the top, we know that we get to keep Shamir's secret sharing scheme and the OTP -- they are perfect.
It seems to me that basically any symmetric algorithm with a large enough keyspace stays too: even a quantum computer is going to have trouble counting to 2^512, right? Even if we can search in a parallel fashion each operation takes energy.. and we can only burn so much of it.
As you noted, factoring gets to be a bit easier, so maybe we have to give up RSA?
Is there any work at developing PK systems that will be difficult for quantum computers?
Michael J. Graffam (mgraffam@idsi.net)
"Let your life be a counter-friction to stop the machine."
Henry David Thoreau "Civil Disobedience"
Date: Wed, 1 Dec 1999 17:13:22 -0600 (CST)
From: Mike Rosing <eresrch@mendota.terracom.net>
To: Coderpunks <coderpunks@toad.com>
Subject: Re: Universal Quantum Computers
On Wed, 1 Dec 1999 mgraffam@idsi.net wrote:
> If a working quantum computer were invented today, what sort of crypto
> tools would need to get thrown away, and what sorts of stuff could we
> keep?
We can keep all symmetric ciphers. They will be crackable as 2^(n/2), so a 256 bit key will work as well as a 128 bit key does today.
> Off the top, we know that we get to keep Shamir's secret sharing
scheme
> and the OTP -- they are perfect.
Right.
> It seems to me that basically any symmetric algorithm with a large
enough
> keyspace stays too: even a quantum computer is going to have trouble
> counting to 2^512, right? Even if we can search in a parallel fashion
> each operation takes energy.. and we can only burn so much of it.
Right again, see above. The trade off is in time vs states, the quantum computer will operate at very fast time scales (has too or you lose coherency) so you must do lots of operations in a short time. That will reduce your energy consumption, but still 2^128 ops is going to take a very long time even if you do 2^50/femtosecond!
> As you noted, factoring gets to be a bit easier, so maybe we have to
> give up RSA?
>
> Is there any work at developing PK systems that will be difficult for
> quantum computers?
All PK systems will fall (I'm not really sure about NTRU, but I suspect it will be "easy" to solve with a QC). We'll need quantum math systems. That will be a great deal of fun to work on, and to implement! I'll be long retired by the time it's important, but maybe my kids will get a chance :-)
Patience, persistence, truth,
Dr. mike
Date: Thu, 2 Dec 1999 23:49:02 -0500 (EST)
From: dmolnar <dmolnar@hcs.harvard.edu>
To: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
cc: coderpunks@toad.com
Subject: Re: Universal Quantum Computers
On 3 Dec 1999, lcs Mixmaster Remailer wrote:
> NTRU is a lattice based system. Solving these systems involves
some
> linear algebra and matrix operations. These are not known to be
> accelerated by quantum computers.
This is true. It's also true that the problem of finding shortest vectors in a lattice has recently been shown to be NP-complete. Also I've heard that there are arguments that quantum computers may not be "powerful enough" to decide all problems in NP.
So in that case NTRU and other cryptosystems based on lattice problems won't fall to quantum computing. Neither will any other public key systems based on NP-complete problems. In case we happen to find any worthwhile ones. :>
This doesn't mean they'll be secure. :-(
> There are also some PK algorithms involving coding theory which should
> be immune to QCs. They are not very efficient, but in a pinch
they could
> probably be made to work.
What else is there besides McElice ?
Do those fall into the same general problem area as the lattice-based cryposystems -- i.e. are there nice connections between coding theory and lattices which could threaten both at once?
> Ajtai Dwork is another lattice based system, broken for moderate key
> sizes but with large enough keys it might be workable.
Maybe. AFAIK we know even less about lattice basis reduction than we do about factoring. But I don't know much. :-\
I just noticed that Phong Nguyen's PhD thesis is up. He's the one who broke or helped break most of the lattice systems in recent years. Including Ajtai Dwork. (also a paper breaking, much to my dismay, this cool protocol by Beguin and Quisquater for a smartcard to do sigs with the aid of a server.)
The thesis is in French. The other papers are mostly in English, though.
http://www.dmi.ens.fr/~pnguyen/pub.html
> There are a number of such algorithms which have been lurking on the
> fringes for years, failing to attract much attention because they
> have disadvantages versus the widely used factoring and discrete log
> systems. But if these dinosaurs are wiped out by the comet of
quantum
> computing, the insignificant little algorithms will rise to dominate
> the cryptographic landscape.
True. With the recent track record of lattice cryptosystems, I'm not so sure that they will be the next big thing. At least NTRU still looks good.
-David
Date: Wed, 15 Dec 1999 05:52:14 +0200 (EET)
From: Helger Lipmaa <helger@cyber.ee>
To: coderpunks@toad.com
Subject: Re: Universal Quantum Computers
A somewhat late answer (been busy inbetween).
On Thu, 2 Dec 1999, dmolnar wrote:
> > There are also some PK algorithms involving coding theory which
should
> > be immune to QCs. They are not very efficient, but in a pinch
they could
> > probably be made to work.
>
> What else is there besides McElice ?
There're some less known systems that however are not known to be broken. One of them is by Gabidulin. As cryptanalyzed by Keith Gibson, Eurocrypt '96, the best known attacks against the Gabidulin cryptosystem are much less powerful than those against the McEliece's. Gibson suggests that a secure version of Gabidulin's system has key length 56,000 bits (as compared to 500,000 bits for McEliece's PKC).
... even if Gabidulin's system with key length 56,000 bits is secure on quantum computers, I have serious concerns about its practicality.
> do those fall into the same general problem area as the lattice-based
> cryposystems -- i.e. are there nice connections between coding
> theory and lattices which could threaten both at once?
Those connections are unknown to me, although in the NTRU paper (ANTS '98), the authors shortly mention that GGH (Goldreich Goldwasser Halevi lattice-based cryptosystem) is similar to McEliece's in principle ('both cases decryption is performed by recognizing and eliminating a small random contribution. Contrasting this, NTRU eliminates a much larger random contribution').
So, who knows?... There might be some similarities (I'm not a prof in lattice reductions nor in error-correcting codes).
> True. With the recent track record of lattice cryptosystems, I'm
> not so sure that they will be the next big thing. At least NTRU
> still looks good.
Agreed.
Helger Lipmaa