Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.security.misc > #1127 > unrolled thread

Researches in quantum computing seem to progress only extremely slowly

Back to article view | Back to comp.security.misc

Contents

  Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 13:09 +0200
    Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 14:23 +0000
      Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 20:00 +0200
        Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 18:43 +0000
          Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 10:56 +0200
            Re: Researches in quantum computing seem to progress only extremely slowly William Unruh <unruh@invalid.ca> - 2015-09-02 16:24 +0000
              Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 05:58 +0200
                Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 18:34 +0200
                  Re: Researches in quantum computing seem to progress only extremely slowly William Unruh <unruh@invalid.ca> - 2015-09-04 18:32 +0000
                    Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-05 20:50 +0200
                    Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-28 11:30 +0200
                      Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-10-08 18:28 +0200
    Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-01 13:23 -0700
      Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 11:04 +0200
    Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:22 -0500

#1127 — Researches in quantum computing seem to progress only extremely slowly

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

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

[toc] | [next] | [standalone]

#1128

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-computing/
>
> 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!

[toc] | [prev] | [next] | [standalone]

#1129

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-computing/
>>
>> 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

[toc] | [prev] | [next] | [standalone]

#1130

["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-computing/
>>>
>>> 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.

[toc] | [prev] | [next] | [standalone]

#1133

[For completeness I send a copy nonetheless to this group]

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-computing/
 >>>>
 >>>> 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/7234475/1/) 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

[toc] | [prev] | [next] | [standalone]

#1135

On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
> [For completeness I send a copy nonetheless to this group]
>
>
> In my code PROVABLEPRIME
> (http://s13.zetaboards.com/Crypto/topic/7234475/1/) 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

No. It is known to be very insecure. You might get 10-20  bits of randomness
that way but not more. 

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

Rot 13 cannot be proven to be secure, AES 256 cannot be proven to be
secure. Therefor Rot13 is as strong as AES 256. Can you see something
wrong with that logic?

[toc] | [prev] | [next] | [standalone]

#1136

Am 02.09.2015 um 18:24 schrieb William Unruh:
> On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>>
>> [For completeness I send a copy nonetheless to this group]
>>
>>
>> In my code PROVABLEPRIME
>> (http://s13.zetaboards.com/Crypto/topic/7234475/1/) 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
>
> No. It is known to be very insecure. You might get 10-20  bits of randomness
> that way but not more.

I have in comment lines in my code already indicated how one could use
Python's random.SystemRandom() instead of the normal random module.
I am now preparing an update that actually uses random.SystemRandom().

>> 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.
>
> Rot 13 cannot be proven to be secure, AES 256 cannot be proven to be
> secure. Therefor Rot13 is as strong as AES 256. Can you see something
> wrong with that logic?

I am conscious that I could never exclude the possibility of having
security problems in my codes (seeing that even professional code
writers could make errors) and therefore I always ask for critiques
and comments.

I think it is interesting to report here that, after Kylheku has
set follow-ups to comp.programming, there were a few persons who
discussed there with me. The last post I wrote to Kylheku was
asking him to clearly resolve a paradox of mine (concerning AES in
CTR), which seems to indicate in my view some posssible problems
with security arguments based on entropy in general. I hope that he
would reply to that soon. Another person, Wessel, agreed with my
calculation of entropy in the paradox but asked about my intention
in that. I explained and it seems that he has no more questions.
A third person, bartekltg, wrote (especially in his more recent
posts) arguments that IMHO are quite strange. Since he continued
to claim that my calculation in the paradox is wrong, I asked him
in a last post to similarly refute Wessel and I'll delay further
discussions with him before seeing his post to Wessel. (He nonetheless
wrote a last post to me, which I didn't answer.)

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#1137

Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
[snip]
> I have in comment lines in my code already indicated how one could use
> Python's random.SystemRandom() instead of the normal random module.
> I am now preparing an update that actually uses random.SystemRandom().

The update, PROVABLEPRIME Version 1.2, has just been released.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#1138

On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
> Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
> [snip]
>> I have in comment lines in my code already indicated how one could use
>> Python's random.SystemRandom() instead of the normal random module.
>> I am now preparing an update that actually uses random.SystemRandom().
>
> The update, PROVABLEPRIME Version 1.2, has just been released.

The advantages of a provable prime are overhyped. The probability of not
finding a prime if you use a probablistic approach are extremely small,
and algorithm for proving primality AFAIK is very slow. Already
generating primes is slow enough that people do not want to do it. 
And, AFAIK if you use a non-prime in RSA you will not get the right
answers when you try to decrypt. So you will soon discover that you do
not have a real prime. Ie, speed is probably more important that
provability in this case. 
So what is the speed of your implimentation vs the speed of
probabilistic approaches?

[toc] | [prev] | [next] | [standalone]

#1139

Am 04.09.2015 um 20:32 schrieb William Unruh:
> On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>> Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
>> [snip]
>>> I have in comment lines in my code already indicated how one could use
>>> Python's random.SystemRandom() instead of the normal random module.
>>> I am now preparing an update that actually uses random.SystemRandom().
>>
>> The update, PROVABLEPRIME Version 1.2, has just been released.
>
> The advantages of a provable prime are overhyped. The probability of not
> finding a prime if you use a probablistic approach are extremely small,
> and algorithm for proving primality AFAIK is very slow. Already
> generating primes is slow enough that people do not want to do it.
> And, AFAIK if you use a non-prime in RSA you will not get the right
> answers when you try to decrypt. So you will soon discover that you do
> not have a real prime. Ie, speed is probably more important that
> provability in this case.
> So what is the speed of your implimentation vs the speed of
> probabilistic approaches?

As I noted in Epilogue of the software, the time for generation
of RSA keys with moduli of the order of even 8000 bits (current
practice 2000) is well acceptable for my targeted users.

On the other hand, I am not blindly ignoring the efficiency issue.
Having better efficiency is anyway a desirable property to be
strived at for any software. Please however kindly be patient at
the moment. I am writing code to perform an extensive comparison
of the cpu-times of generation of provable primes vs generation
with the probabilistic method. But I need yet some time to collect
sufficient results, analyze them, eventually learn something
useful from them and provide some good arguments for the pros and
cons of employing the two approaches. You'll hear from me in due
course of time.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#1142

Am 04.09.2015 um 20:32 schrieb William Unruh:
> On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>> Am 03.09.2015 um 05:58 schrieb Mok-Kong Shen:
>> [snip]
>>> I have in comment lines in my code already indicated how one could use
>>> Python's random.SystemRandom() instead of the normal random module.
>>> I am now preparing an update that actually uses random.SystemRandom().
>>
>> The update, PROVABLEPRIME Version 1.2, has just been released.
>
> The advantages of a provable prime are overhyped. The probability of not
> finding a prime if you use a probablistic approach are extremely small,
> and algorithm for proving primality AFAIK is very slow. Already
> generating primes is slow enough that people do not want to do it.
> And, AFAIK if you use a non-prime in RSA you will not get the right
> answers when you try to decrypt. So you will soon discover that you do
> not have a real prime. Ie, speed is probably more important that
> provability in this case.
> So what is the speed of your implimentation vs the speed of
> probabilistic approaches?

I have done a comparison. With my Python codes the mean values of 
runtime obtained are as follows, where nb is the bit size of the primes
generated, tprov is the time with Maurer's algorithm and tprob is that
with Miller-Rabin test (with prior sieving with trial divisions,
different sizes of the table of small primes employed were tried and
the least runtime values listed).

          nb=1000     nb=1500     nb=2000

tprov:  0.493 sec   1.739 sec   4.648 sec

tprob:

t=1     0.324 sec   1.228 sec   3.462 sec
t=2     0.340 sec   1.282 sec   3.567 sec
t=5     0.357 sec   1.297 sec   3.534 sec
t=10    0.394 sec   1.436 sec   3.926 sec
t=20    0.450 sec   1.594 sec   4.191 sec
t=30    0.517 sec   1.801 sec   4.670 sec
t=40    0.570 sec   1.945 sec   5.035 sec

It can be seen that my implementation of Maurer's algorithm starts to
have a runtime shorter than with the Miller-Rabin test at t=30 and is
superior for higher values of t. Even for t values less then 30, the
differences are only moderate and certainly not extreme.

Thus with additional consideration of the benefit of obtaining primes
that are definitely prime, the results obtained support in my view the
general use of Maurer's algorithm for generation of random primes of
the said sizes in case my coding is employed.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#1144

Am 28.09.2015 um 11:30 schrieb Mok-Kong Shen:
[snop]
> I have done a comparison. With my Python codes the mean values of
> runtime obtained are as follows ..........

The code for the comparison is in Post #31 of the thread
http://s13.zetaboards.com/Crypto/topic/7234475/1/

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#1131

> "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-computing/

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

[toc] | [prev] | [next] | [standalone]

#1134

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-computing/
>>
>
>> 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.dwavesys.com

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

[toc] | [prev] | [next] | [standalone]

#1132

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.security.misc

csiph-web