Re: First quantum byte!

Mike Amling <nospam@xxxxxxxxxxx> writes:

>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.

But this means that this public key cryptosystem has a "strength" of only
80 bits, which is not very good. ( and 2000 bits required for each bit sent
is pretty absurd.)



>> 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: what should "k-bit security" mean?
    ... What is the time t of an attack? ... algorithm to end of execution of the algorithm. ... Suppose the problem is inverting SHA1. ...
    (sci.crypt)
  • Re: yet another hash algorithm
    ... quality hash in much less than 64 rounds, as an attacker could attack ... used the novel techniques first" in this thread. ...  Rightward information flow is the ... blocks that, when hashed using that algorithm, produce hashes that are ...
    (sci.crypt)
  • Re: what should "k-bit security" mean?
    ... |>An algorithm that provides X bits of strength would, on average, take ... And this is the measure that we used in the NTRU paper ... because some keys take so much less time than others to attack ... Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org ...
    (sci.crypt)
  • Re: Algorithm Strength Scale
    ... therefore rendering it useless for serious purposes. ... It is arguable that this delivers an equivalent key in an equivalent algorithm, but it certainly does not recover the "functional key" of the original algorithm, and may not necessarily be possible to convert to the key itself. ... Admittedly, this is a significantly unusual form of attack, but it certainly violates the statement that there are "only ... ... It has no relation to reality, only serves to provide an appearance of thoughtfulness. ...
    (sci.crypt)
  • Re: QC-proof cipher?
    ... to quantum computation techniques? ... size, for long-term future-proofing. ... That will be fine against quantum crypto as well. ... function if you know what the plaintext is (known plaintext attack). ...
    (sci.crypt)