Re: First quantum byte!

Unruh wrote: 
wwhyte@xxxxxxxxx writes:



Joseph Ashwood wrote:

"Mike Amling" <nospam@xxxxxxxxxxx> wrote in message
news:R67lf.795$Ql1.392@xxxxxxxxxxxxxxxxxxxx

 Is the public-key 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 no-one'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
.

Relevant Pages

  • Re: Help SYN Flood Detection
    ... I am not so worried about stopping the attack as I am about ... My biggest problem is I can't detect it. ... WorldCom engineers post :-) I'm pretty sure this is entirely possible ... > most discussions in this news groups refers to personal firewalls and not ...
    (comp.security.firewalls)
  • Re: Help SYN Flood Detection
    ... I am not so worried about stopping the attack as I am about ... > My biggest problem is I can't detect it. ... > WorldCom engineers post :-) I'm pretty sure this is entirely possible ... >> most discussions in this news groups refers to personal firewalls and ...
    (comp.security.firewalls)
  • Re: *Quantum Computing* expert Bill Munro
    ... develop ciphers resistant to attack by quantum computers. ... To clarify: there is, of course, nothing odd about a quantum computing ... *cryptography* researchers that their call to arms appeared strange, ...
    (sci.crypt)