[4784] in cryptography@c2.net mail archive
Re: quantum codebreaker
daemon@ATHENA.MIT.EDU (dmolnar)
Mon May 24 12:11:12 1999
Date: Sat, 22 May 1999 00:20:51 -0400 (EDT)
From: dmolnar <dmolnar@hcs.harvard.edu>
To: Enzo Michelangeli <em@who.net>
Cc: coderpunks@toad.com, cryptography@c2.net
In-Reply-To: <008801bea3f1$ae0101e0$87004bca@home>
On Sat, 22 May 1999, Enzo Michelangeli wrote:
> In any event, resolution of cryptosystems is generally not an NP-complete
> problem, and the paper seems to discuss only the reduction of NP-complete to
> P.
I'm not sure I follow.
You may be thinking of the fact that cryptosystems aren't
explicitly based on the assumption P != NP -- which is true. Well,
modulo possible results with lattice cryptosystems.
The assumptions which most of our favorite public-key systems
are based on all concern problems in NP. If we can solve an
NP-complete problem efficiently, then we can solve those problems
by the fact that any problem in NP can be reduced in polynomial
time in the size of the input to an instance of one of those
problems.
If you want me to exhibit the reduction to factoring from an
NP-complete language like boolean satisfiability, I'll have
to think for a bit, though. I know one exists because of
more general arguments which tell me that it must exist. :-)
Then we have to consider whether the problem of solving block
ciphers is in NP and so vulnerable in the same fashion. It seems
to me that it is, because we can efficiently check whether a
candidate key is correct using a single decryption.
Grover's quantum algorithm for searching an array of values
for the `right' entry depends on this property to construct
something called a ``controlled-U" operation, where U is the test
for correctness. It runs in time O(sqrt(n) ) on what I guess is the
`linear' case for a quantum computer. That's a nice speedup,
but can be compensated for by adding extra bits to the keys
(smart card manufacturers may suffer).
If I read this right, then if this nonlinearity fits the criteria
required in the other two papers, then we can run something
like Grover's algorithm to solve any NP problem in O(log_2 (n) )
steps. That means we'd need to use keys which are 2**128 bits long
to get the same level of assurance which 128-bit block cipher
keys provide today. I think (I always get the number and the size of
a number confused in O(n) ).
Will it really work this way ? I don't know -- I'm not an expert
on quantum. In particular, I haven't yet read the papers to see if
the nonlinearity created by this last paper will satisfy the conditions
needed by the other two.
Still, if it does, and this way the class BQP of
problems solvable efficiently on a quantum computer is shown to
include NP, then it seems to me that yes, this is a big deal.
ObCoderpunks : there's C++ libraries available to simulate what a
(linear) quantum computer might work like.
Check http://www.openqubit.org for the latest code and some
papers which explain its workings + introduce QM and quantum
computing. David Crick noted recently on sci.crypt that he
is working on an overview of this and other simulation libraries;
presumably he'll post that when it's done.
Thanks,
-David Molnar
