[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

Researches in quantum computing seem to progress only extremely slowly

Mok-Kong Shen

9/1/2015 11:09:00 AM


http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...

The article doesn't seem to be much more optimistic than reports on
other well-known currently running big projects of physics, e.g.
nuclear fusion.

This means that there is in the foreseeable future no danger of the
currently used asymmetric encryption schemes being broken by quantum
computers and one could consequently concentrate one's efforts in
attempting to improve the practical security of these schemes, e.g.
in authentication of the public keys and in prevention of eventually
possible backdoors being implanted in the software or hardware involved.

M. K. Shen
84 Answers

Kaz Kylheku

9/1/2015 2:23:00 PM

0

On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
> http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...
>
> The article doesn't seem to be much more optimistic than reports on
> other well-known currently running big projects of physics, e.g.
> nuclear fusion.
>
> This means that there is in the foreseeable future no danger of the
> currently used asymmetric encryption schemes being broken by quantum

Phew! Your python-PRNG-based security schemes is safe!

Mok-Kong Shen

9/1/2015 6:01:00 PM

0

Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
> On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>>
>> http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...
>>
>> The article doesn't seem to be much more optimistic than reports on
>> other well-known currently running big projects of physics, e.g.
>> nuclear fusion.
>>
>> This means that there is in the foreseeable future no danger of the
>> currently used asymmetric encryption schemes being broken by quantum
>
> Phew! Your python-PRNG-based security schemes is safe!

In another thread I asked you to provide a reference to support your
claim there but you still kept silence on that!

M. K. Shen

Kaz Kylheku

9/1/2015 6:43:00 PM

0

["Followup-To:" header set to comp.programming.]
On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
> Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
>> On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>>>
>>> http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...
>>>
>>> The article doesn't seem to be much more optimistic than reports on
>>> other well-known currently running big projects of physics, e.g.
>>> nuclear fusion.
>>>
>>> This means that there is in the foreseeable future no danger of the
>>> currently used asymmetric encryption schemes being broken by quantum
>>
>> Phew! Your python-PRNG-based security schemes is safe!
>
> In another thread I asked you to provide a reference to support your
> claim there but you still kept silence on that!

The reference is that the entire sequence coming out of a PRNG only contains as
much information as its seed. For instance, a 32 bit seed means that the
entire sequence contains at most 32 bits of information. (This is true even if
the PRNG is a good one with a big state vector, and a long period.)
The seed is effectively a selector which chooses one of 2**32 different
sequences.

If you generate, say, a 1024 bit key with a PRNG that is seeded with, say, 64
bits, then it's effectively a 64 bit key. Given a known plaintext and
ciphertext pair, we only have to search a 64 bit space to recover the key.
The encryption algorithm might be RSA-1024, but it's not really because
of the weak seeding; it is a misleading lie and "security through obscurity"---
you hope that the scheme is secure because the attacker doesn't know
that a particular weekly-seeded PRNG was used.

Do you also require a reference for the claim that water is wet?

Moreover, a PRNG may have other problems with it even if the state space is
large enough and the seed has enough entropy for the given crypto use.


About stream ciphers; yes they are lot like PRNG's where the encryption key
is a seed. The seed has an appropriate size to achieve a given security
level, and no misleading claims are made about the space from which it
is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
that uses a 32 bit seed, we have the same problem: the cipher is effectively
32 bit (but the users are duped into believing that it's the 256
bit real thing).

No, key entropy does not dilute with the increasing length of an encrypted
message. Suppose we have a very good symmetric cipher against which there is
no known attack other than brute force. Suppose the attacker knows all of our
plaintext. It does not help the attacker to have a large quantity of known
plaintext. In fact using more plaintext/ciphertext pairs only slows down the
brute force search. For each key which is tried, it is enough to try a single
known ciphertext/plaintex pair.

Encryption does not work by spreading key entropy across a message.
The entropy in a key is important, however, for obvious reasons:
more entropy means a larger key space.

If an encryption algoirthm requires keys with a certain amount of entropy,
and is given less entropy, it is incompetently implemented. Its security
is weakened.

Darren Jackson

9/1/2015 8:23:00 PM

0

> "Mok-Kong Shen" wrote in message news:ms4114$nal$2@news.albasani.net...


> http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...

> The article doesn't seem to be much more optimistic than reports on
> other well-known currently running big projects of physics, e.g.
> nuclear fusion.

AFAICT, the following project has some promise:

http://www.dw...

robertwessel2@yahoo.com

9/2/2015 7:23:00 AM

0

On Tue, 1 Sep 2015 13:09:25 +0200, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:

>
>http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...
>
>The article doesn't seem to be much more optimistic than reports on
>other well-known currently running big projects of physics, e.g.
>nuclear fusion.
>
>This means that there is in the foreseeable future no danger of the
>currently used asymmetric encryption schemes being broken by quantum
>computers and one could consequently concentrate one's efforts in
>attempting to improve the practical security of these schemes, e.g.
>in authentication of the public keys and in prevention of eventually
>possible backdoors being implanted in the software or hardware involved.


Even if significant progress in quantum computing does occur, a number
of public key algorithms, for example the lattice-based schemes, are
known not to be vulnerable to quantum computing (or at least not any
more than to conventional computing).

As for private key algorithms, most of those will not be hit worse
than halving their effective key length by quantum algorithms, so
AES-256 should be fine (although it would be no stronger than AES-128
is now).

IOW, should quantum computing actually become practical, cryptographic
implementations will need some updates, but it will hardly be the end
of the world. Especially since we'll likely have considerable advance
notice as quantum machines start to grow large enough to be
meaningful.

Mok-Kong Shen

9/2/2015 8:48:00 AM

0

Am 01.09.2015 um 20:43 schrieb Kaz Kylheku:
> ["Followup-To:" header set to comp.programming.]
> On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>> Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
>>> On 2015-09-01, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>>>>
>>>> http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...
>>>>
>>>> The article doesn't seem to be much more optimistic than reports on
>>>> other well-known currently running big projects of physics, e.g.
>>>> nuclear fusion.
>>>>
>>>> This means that there is in the foreseeable future no danger of the
>>>> currently used asymmetric encryption schemes being broken by quantum
>>>
>>> Phew! Your python-PRNG-based security schemes is safe!
>>
>> In another thread I asked you to provide a reference to support your
>> claim there but you still kept silence on that!
>
> The reference is that the entire sequence coming out of a PRNG only contains as
> much information as its seed. For instance, a 32 bit seed means that the
> entire sequence contains at most 32 bits of information. (This is true even if
> the PRNG is a good one with a big state vector, and a long period.)
> The seed is effectively a selector which chooses one of 2**32 different
> sequences.
>
> If you generate, say, a 1024 bit key with a PRNG that is seeded with, say, 64
> bits, then it's effectively a 64 bit key. Given a known plaintext and
> ciphertext pair, we only have to search a 64 bit space to recover the key.
> The encryption algorithm might be RSA-1024, but it's not really because
> of the weak seeding; it is a misleading lie and "security through obscurity"---
> you hope that the scheme is secure because the attacker doesn't know
> that a particular weekly-seeded PRNG was used.
>
> Do you also require a reference for the claim that water is wet?
>
> Moreover, a PRNG may have other problems with it even if the state space is
> large enough and the seed has enough entropy for the given crypto use.
>
>
> About stream ciphers; yes they are lot like PRNG's where the encryption key
> is a seed. The seed has an appropriate size to achieve a given security
> level, and no misleading claims are made about the space from which it
> is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
> that uses a 32 bit seed, we have the same problem: the cipher is effectively
> 32 bit (but the users are duped into believing that it's the 256
> bit real thing).
>
> No, key entropy does not dilute with the increasing length of an encrypted
> message. Suppose we have a very good symmetric cipher against which there is
> no known attack other than brute force. Suppose the attacker knows all of our
> plaintext. It does not help the attacker to have a large quantity of known
> plaintext. In fact using more plaintext/ciphertext pairs only slows down the
> brute force search. For each key which is tried, it is enough to try a single
> known ciphertext/plaintex pair.
>
> Encryption does not work by spreading key entropy across a message.
> The entropy in a key is important, however, for obvious reasons:
> more entropy means a larger key space.
>
> If an encryption algoirthm requires keys with a certain amount of entropy,
> and is given less entropy, it is incompetently implemented. Its security
> is weakened.

In my code PROVABLEPRIME
(http://s13.zetaboards.com/Crypto/topic/...) there is no seed
to be input by the user at all. When the Python session starts, the
system employs the current time to seed its built-in PRNG. So each
time one uses the code to e.g. generate RSA keys, one gets a different
pair by chance. Certainly one could question the security of that from
an "exact" standpoint (I mean in the sense of proofs of pure math),
but there is in "practical" crypto in general IMHO no way to take that
exact standpoint and yet have useful things done. Does e.g. AES have
an exact proof of its security? There is none, at least to my humble
knowledge.

To repeat a few points of mine in another thread: (1) if a CSPRNG were
required in the implementation of Maurer's algorithm (detailed in HAC),
the authors of HAC would have explicitly mentioned it according to the
common style of writing in such contexts, (2) the algorithm given in
HAC of implementing a CSPRNG via RSA would barely have had any
practical sense (since one has a "need" of a CSPRNG "only" in
situations where one doesn't yet have one).

BTW, I like to mention (though this is certainly not any argument of
mine here) that a copy of my code was sent to the authors of HAC
since, if I don't err, it is the first publically available
implementation of Maurer's algrorithm in any popular programming
language.

M. K. Shen

Mok-Kong Shen

9/2/2015 9:05:00 AM

0

Am 01.09.2015 um 22:23 schrieb Chris M. Thomasson:
>> "Mok-Kong Shen" wrote in message news:ms4114$nal$2@news.albasani.net...
>
>
>> http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-...
>>
>
>> The article doesn't seem to be much more optimistic than reports on
>> other well-known currently running big projects of physics, e.g.
>> nuclear fusion.
>
> AFAICT, the following project has some promise:
>
> http://www.dw...

Google has a machine from D-Wave. The mention of it in the given
link isn't very clear (positive? negative?) in my understanding.

M. K. Shen

Kaz Kylheku

9/2/2015 1:00:00 PM

0

On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
> In my code PROVABLEPRIME
> (http://s13.zetaboards.com/Crypto/topic/...) there is no seed
> to be input by the user at all. When the Python session starts, the
> system employs the current time to seed its built-in PRNG. So each
> time one uses the code to e.g. generate RSA keys, one gets a different
> pair by chance. Certainly one could question the security of that from
> an "exact" standpoint (I mean in the sense of proofs of pure math),

The "exact standpoint" here is quite obvious and it is that a sample of the
current time (even if it includes micro or nanoseconds from a high resolution timer,
and not only the "seconds sine epoch" or whatever) simply has too few bits of
entropy to generate good RSA keys.

> but there is in "practical" crypto in general IMHO no way to take that
> exact standpoint and yet have useful things done. Does e.g. AES have
> an exact proof of its security? There is none, at least to my humble
> knowledge.

So if some crypto has no "exact proof of its security", then it's okay to
implement it idiotically so that it is guaranteed to insecure?

"This car wasn't put through rigorous crash tests, so I'm not going
to bother wearing its seat belt!"

> To repeat a few points of mine in another thread: (1) if a CSPRNG were
> required in the implementation of Maurer's algorithm (detailed in HAC),

It has already been explained to you that a CSPRNG is not in fact
(specifically) required. What's required is enough bits of entropy from some
good source.

> the authors of HAC would have explicitly mentioned it according to the

I'm pretty sure that HAC teaches that all randomly generated keys require
sufficient entropy from a good source.

(By the way, since you don't understand HAC, why should anyone
waste their time giving you additional references?)

> common style of writing in such contexts, (2) the algorithm given in
> HAC of implementing a CSPRNG via RSA would barely have had any
> practical sense (since one has a "need" of a CSPRNG "only" in
> situations where one doesn't yet have one).

It's been explained to you that there is no such "chicken or egg" problem. A
CSPRNG needs a quality seed from a random source. If you have that, you can do
the necessary key generation to bootstrap a PRNG which is based on RSA.

Mok-Kong Shen

9/2/2015 8:51:00 PM

0

Am 02.09.2015 um 15:00 schrieb Kaz Kylheku:
> On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>> In my code PROVABLEPRIME
>> (http://s13.zetaboards.com/Crypto/topic/...) there is no seed
>> to be input by the user at all. When the Python session starts, the
>> system employs the current time to seed its built-in PRNG. So each
>> time one uses the code to e.g. generate RSA keys, one gets a different
>> pair by chance. Certainly one could question the security of that from
>> an "exact" standpoint (I mean in the sense of proofs of pure math),
>
> The "exact standpoint" here is quite obvious and it is that a sample of the
> current time (even if it includes micro or nanoseconds from a high resolution timer,
> and not only the "seconds sine epoch" or whatever) simply has too few bits of
> entropy to generate good RSA keys.

I must admit that I yet have doubt on such application of the entropy
argument (i.e. without regard to how an amount of entropy is actually
being employed in the processing) due to a paradox that I put up
and described in a recent another thread: AES-128 in counter mode has
an input of max 128 bits of entropy but its ouput is commonly used to
e.g. xor n plaintext bits with n >> 128. The average entropy that is
contained in one ciphertext bit thus can't be greater than 128/n,
which is negligible for even moderately large n. Does that imply that
AES in CTR mode is totally broken?

M. K. Shen

robertwessel2@yahoo.com

9/2/2015 9:14:00 PM

0

On Wed, 2 Sep 2015 10:48:15 +0200, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:
>
>In my code PROVABLEPRIME
>(http://s13.zetaboards.com/Crypto/topic/...) there is no seed
>to be input by the user at all. When the Python session starts, the
>system employs the current time to seed its built-in PRNG. So each
>time one uses the code to e.g. generate RSA keys, one gets a different
>pair by chance. Certainly one could question the security of that from
>an "exact" standpoint (I mean in the sense of proofs of pure math),
>but there is in "practical" crypto in general IMHO no way to take that
>exact standpoint and yet have useful things done. Does e.g. AES have
>an exact proof of its security? There is none, at least to my humble
>knowledge.


Assuming the time value was microsecond resolution, and the attacker
can localize the time when you generated the primes to about a year,
he'd have to test no more than about 2**45 possible sets of primes.
IOW, this is fundamentally broken.