[4786] in cryptography@c2.net mail archive
Re: quantum codebreaker
daemon@ATHENA.MIT.EDU (Enzo Michelangeli)
Mon May 24 12:16:13 1999
From: "Enzo Michelangeli" <em@who.net>
To: "dmolnar" <dmolnar@hcs.harvard.edu>
Cc: <coderpunks@toad.com>, <cryptography@c2.net>
Date: Sun, 23 May 1999 09:20:41 +0800
Sure, I did not intend to belittle the theoretic significance of those
papers, which are surely very interesting. I just meant that:
1. Converting a generic codebreaking problem into an NP-complete one with a
transformation of polynomial complexity, while probably possible, is not
trivial at all. For example, the factoring problem MIGHT be NP-complete, as
the best known algorithms are of exponential complexity, and the
verification is polynomial: but, so far, nobody has either disproved the
hypothesis, or proved it by transforming it into an NP-complete problem. And
we can't say that nobody tried! The transformation NP->NP-Complete may well
run in polynomial time, but FINDING it in the general case is probably
intractable, and finding it in particular cases is very difficult
(especially with complicated encryption algorithms involving arbitrary
s-boxes and such).
2. As James D. noted, away from strong gravitational fields the equations of
Quantum Mechanics, which are linear, appear extremely consistent with the
measured reality. Close to strong gravitatational fields there are NO known
versions of Q.M. that work, and the integration of Q.M. with General
Relativity (which is essentially a theory of gravitation) is the most
important open issue in contemporary physics. But in any case, we can't go
close to a black hole to run our (still non-existent) qubit cruncher.
So, by no means Abrams' and Gossett's papers are uninteresting (and I can't
wait to see more from them!), but I think that their immediate applicability
to concrete cases is very limited. Even if (2) were solved, by extending the
result to linear evolution of quantum states, in most cases we would still
be stuck with (1).
Cheers --
Enzo
----- Original Message -----
From: dmolnar <dmolnar@hcs.harvard.edu>
To: Enzo Michelangeli <em@who.net>
Cc: <coderpunks@toad.com>; <cryptography@c2.net>
Sent: Saturday, May 22, 1999 12:20 PM
Subject: Re: quantum codebreaker
>
>
> 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
>
>
