Re: First quantum byte!
 From: Mike Amling <nospam@xxxxxxxxxxx>
 Date: Wed, 07 Dec 2005 19:27:09 GMT
Unruh wrote:
wwhyte@xxxxxxxxx writes:
Joseph Ashwood wrote:
"Mike Amling" <nospam@xxxxxxxxxxx> wrote in message news:R67lf.795$Ql1.392@xxxxxxxxxxxxxxxxxxxx
Is the publickey system described at http://bitconjurer.org/simple_public_key.html subject to attack by quantum computers like RSA and elliptic curves are?
Almost certainly yes, although I haven't delved that deep into it, and probably won't. The biggest problem with it is that while it is published so anyone can break it, it isn't published in a respected form (there isn't even a paper, just Bram's somewhat scattered thoughts, and a rather complete lack of fundamentals) so no one respectable is likely to look at it. Joe
It looks like the best attack against Bram's algorithm would use lattice reduction  it's essentially a neat variant on knapsacks, very efficient but with bad message expansion properties. If that's the case, Shor's algorithm wouldn't apply. However, as Joe says the problem with making a statement about the security of this algorithm is that noone's closely studied how secure it is against classical algorithms, so it's a bit early to start saying how quantum computers might affect it.
Remember that the attacker does not need to find p. He just needs to find some p such that the known k integers mod p are less than p/2k. Any such p will do. It is not necessarily unique. Also, the number of "knapsacks" is finite ( about 2^k at most), so if k is small, then one can simply list them all and does not need to know what p is at all just look to see if the answer is one of them or is minus one of them. And if k is large then p/2k is small finding p such that anyof the numbers is less than p/2k again is not hard.
Well, that's not really a problem. If k is >=80 and p>=2**1000, then neither 2**k nor p/2k is small.
It is also horribly inefficient. One has to send a number of bits far greater than the number of bits in p simply to encode a single bit.
Yep.
Mike Amling .
 FollowUps:
 Re: First quantum byte!
 From: Unruh
 Re: First quantum byte!
 References:
 Re: First quantum byte!
 From: Mike Amling
 Re: First quantum byte!
 From: Joseph Ashwood
 Re: First quantum byte!
 From: wwhyte
 Re: First quantum byte!
 From: Unruh
 Re: First quantum byte!
 Prev by Date: Re: PGP Lame question
 Next by Date: Re: PGP Lame question
 Previous by thread: Re: First quantum byte!
 Next by thread: Re: First quantum byte!
 Index(es):
Relevant Pages
