[5921] in cryptography@c2.net mail archive
Re: Almost-Everywhere Superiority for Quantum Computing
daemon@ATHENA.MIT.EDU (Ben Laurie)
Mon Oct 18 11:08:08 1999
Message-ID: <380AED59.386C1C7E@algroup.co.uk>
Date: Mon, 18 Oct 1999 10:50:17 +0100
From: Ben Laurie <ben@algroup.co.uk>
MIME-Version: 1.0
To: Russell Nelson <nelson@crynwr.com>
Cc: cryptography@c2.net
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Russell Nelson wrote:
>
> Julian Assange writes:
> > Simon as extended by Brassard and H{\o}yer shows that there are
> > tasks on which quantum machines are exponentially faster than
> > each classical machine infinitely often. The present paper shows
> > that there are tasks on which quantum machines are exponentially
> > faster than each classical machine almost everywhere.
>
> Okay, then can I ask a silly question (I prefer to contribute good
> answers, but in this case hopefully the question is good enough)? If
> quantum computers make brute-force cryptanalysis tasks easier, don't
> they also make brute-force cryptographic tasks easier as well? Put
> another way, is there something special about quantum computers that
> is different from Intel's next process shrink? That is, apart from
> the havoc it plays with key lifetime expectations?
Well, for example, if it makes public key cryptography no longer one
way, regardless of keysize, then we'd have to think of a new way to do
things. Which may be possible, of course. But PK was possible for a long
time before anyone thought of it.
If I understand the theory correctly, this is precisely what is going to
happen, too.
Cheers,
Ben.
--
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
