Re: First quantum byte!
- From: Unruh <unruh-spam@xxxxxxxxxxxxxx>
- Date: 7 Dec 2005 21:25:02 GMT
Mike Amling <nospam@xxxxxxxxxxx> writes:
>> wwhyte@xxxxxxxxx writes:
>>>Joseph Ashwood wrote:
>>>>"Mike Amling" <nospam@xxxxxxxxxxx> wrote in message
>>>>> 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.
>>>It looks like the best attack against Bram's algorithm would use
>>>reduction -- it's essentially a neat variant on knapsacks, very
>>>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
>>>studied how secure it is against classical algorithms, so it's a bit
>>>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.
- Prev by Date: Re: gnupg / rsa padding question
- Next by Date: Re: cyber money laundering
- Previous by thread: Re: First quantum byte!
- Next by thread: Re: First quantum byte!