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

Groups > alt.folklore.computers > #160842 > unrolled thread

Quantum computers and encryption

Back to article view | Back to alt.folklore.computers

Contents

  Quantum computers and encryption isw <isw@witzend.com> - 2016-03-10 23:14 -0800
    Re: Quantum computers and encryption Ahem A Rivet's Shot <steveo@eircom.net> - 2016-03-11 07:45 +0000
      Re: Quantum computers and encryption jmfbahciv <See.above@aol.com> - 2016-03-11 13:08 +0000
        Re: Quantum computers and encryption scott@slp53.sl.home (Scott Lurndal) - 2016-03-11 14:13 +0000
          Re: Quantum computers and encryption jmfbahciv <See.above@aol.com> - 2016-03-12 13:34 +0000

#160842 — Quantum computers and encryption

Not sure this is the right group, but there seems to be a lot of random 
knowledge here ...

I just saw an article on some recent "breakthrough" in quantum 
computing, where the author was yet again predicting the imminent demise 
of encryption, just as soon as they "get the bugs out" of their 
superfast CPU. Or whatever.

Anyhow, as I understand it, a quantum computer can sort of "test all the 
keys at once" to find the right one to decrypt an encrypted file.

Now, AES-256, say, involves a rather large(!) number of possible keys. 
Presumably, all but one of them will be "wrong" (I understand the 
cryptographic notion of wrong keys that nevertheless deliver the "right" 
result, but that's not where I'm going here).

Encryption is not like a physical lock, where a wrong key won't even 
turn the barrel -- any key you try will produce an output of the proper 
length, but with the wrong "content". Further, with a keyspace as large 
as 2^256, I would expect that a *lot* of "wrong" keys would deliver 
sort-of-right-looking output.

Remember the story about a roomful of monkeys whacking away on 
typewriters, where eventually they'll produce all of Shakespeare's works 
(even the ones he didn't like, wadded up, and threw in the trashcan).

In addition to *correct* versions of his works, you'd also get all of 
them with one typo in every possible location, or one pair of letters 
transposed, and on and on, so at the end you'd still be faced with the 
hugely difficult task of proofreading everything, hoping to be able to 
recognize the "correct" versions when you came across them.

So assuming that a quantum computer would implement a brute force attack 
by trying all the keys (which it could presumably do very rapidly) it 
seems to me that you're still stuck with the same problem as the monkey 
herders -- how do you know when you have the "correct" decryption?

I somehow can't believe that *every* key except the correct one would 
deliver pure gibberish which would be easy to reject. With 2^256 
possibilities, wouldn't some (large number) of the outputs look 
perfectly reasonable except all or some of the names (or addresses, or 
phone numbers) would be wrong? 

Seems to me that would have to happen, if you did 2^256 "decryptions" of 
a document, no matter how you did them.

So, am I misunderstanding something, or are quantum computers actually 
not so much of a risk to encryption at all, because of the difficulty of 
proving (in a court of law, say) that the decryption you got is the one, 
true, one? Because I don't think that just because it *looks like* 
English plain text (or terrorist-to-terrorist messages), that means that 
you hit the jackpot.

I guess an alternate way to ask the question is, what test can a quantum 
computer apply, to prove that the key it finds is in fact the *correct* 
one -- the one that produces a verbatim copy of the original document 
prior to encryption?

Isaac

[toc] | [next] | [standalone]

#160843

On Thu, 10 Mar 2016 23:14:34 -0800
isw <isw@witzend.com> wrote:

> Not sure this is the right group, but there seems to be a lot of random 
> knowledge here ...
> 
> I just saw an article on some recent "breakthrough" in quantum 
> computing, where the author was yet again predicting the imminent demise 
> of encryption, just as soon as they "get the bugs out" of their 
> superfast CPU. Or whatever.
> 
> Anyhow, as I understand it, a quantum computer can sort of "test all the 
> keys at once" to find the right one to decrypt an encrypted file.

	That would perhaps be possible but has all the problems you mention.
The main thing quantum computers do to encryption is fast factorisation.
Public key encryption depends on it being very difficult to factorise a
large number - if you can factorise the public key you can generate the
private key - so if you can factorise large numbers quickly then public key
encryption is broken.

-- 
Steve O'Hara-Smith                          |   Directable Mirror Arrays
C:>WIN                                      | A better way to focus the sun
The computer obeys and wins.                |    licences available see
You lose and Bill collects.                 |    http://www.sohara.org/

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

#160855

Ahem A Rivet's Shot wrote:
> On Thu, 10 Mar 2016 23:14:34 -0800
> isw <isw@witzend.com> wrote:
>
>> Not sure this is the right group, but there seems to be a lot of random
>> knowledge here ...
>>
>> I just saw an article on some recent "breakthrough" in quantum
>> computing, where the author was yet again predicting the imminent demise
>> of encryption, just as soon as they "get the bugs out" of their
>> superfast CPU. Or whatever.
>>
>> Anyhow, as I understand it, a quantum computer can sort of "test all the
>> keys at once" to find the right one to decrypt an encrypted file.
>
>     That would perhaps be possible but has all the problems you mention.
> The main thing quantum computers do to encryption is fast factorisation.
> Public key encryption depends on it being very difficult to factorise a
> large number - if you can factorise the public key you can generate the
> private key - so if you can factorise large numbers quickly then public key
> encryption is broken.
>
I don't think we'll know what quantum computers will do until a few
are constructed and kiddies begin to play with it.  Today's
computing is based on reproducibility which is not what quantum
computing does.

/BAH

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

#160858

jmfbahciv <See.above@aol.com> writes:
>Ahem A Rivet's Shot wrote:
>> On Thu, 10 Mar 2016 23:14:34 -0800
>> isw <isw@witzend.com> wrote:
>>
>>> Not sure this is the right group, but there seems to be a lot of random
>>> knowledge here ...
>>>
>>> I just saw an article on some recent "breakthrough" in quantum
>>> computing, where the author was yet again predicting the imminent demise
>>> of encryption, just as soon as they "get the bugs out" of their
>>> superfast CPU. Or whatever.
>>>
>>> Anyhow, as I understand it, a quantum computer can sort of "test all the
>>> keys at once" to find the right one to decrypt an encrypted file.
>>
>>     That would perhaps be possible but has all the problems you mention.
>> The main thing quantum computers do to encryption is fast factorisation.
>> Public key encryption depends on it being very difficult to factorise a
>> large number - if you can factorise the public key you can generate the
>> private key - so if you can factorise large numbers quickly then public key
>> encryption is broken.
>>
>I don't think we'll know what quantum computers will do until a few
>are constructed and kiddies begin to play with it. 

Where have you been?   Such computers _have_ been constructed and
_are_ being played with.   Which was the impetus for Isaac's post.
One of those experiments recently factored a product of  primes, which is the
key to defeating PKI (pun intended).

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

#160893

Scott Lurndal wrote:
> jmfbahciv <See.above@aol.com> writes:
>>Ahem A Rivet's Shot wrote:
>>> On Thu, 10 Mar 2016 23:14:34 -0800
>>> isw <isw@witzend.com> wrote:
>>>
>>>> Not sure this is the right group, but there seems to be a lot of random
>>>> knowledge here ...
>>>>
>>>> I just saw an article on some recent "breakthrough" in quantum
>>>> computing, where the author was yet again predicting the imminent demise
>>>> of encryption, just as soon as they "get the bugs out" of their
>>>> superfast CPU. Or whatever.
>>>>
>>>> Anyhow, as I understand it, a quantum computer can sort of "test all the
>>>> keys at once" to find the right one to decrypt an encrypted file.
>>>
>>>     That would perhaps be possible but has all the problems you mention.
>>> The main thing quantum computers do to encryption is fast factorisation.
>>> Public key encryption depends on it being very difficult to factorise a
>>> large number - if you can factorise the public key you can generate the
>>> private key - so if you can factorise large numbers quickly then public
key
>>> encryption is broken.
>>>
>>I don't think we'll know what quantum computers will do until a few
>>are constructed and kiddies begin to play with it.
>
> Where have you been?   Such computers _have_ been constructed and
> _are_ being played with.   Which was the impetus for Isaac's post.
> One of those experiments recently factored a product of  primes, which is
the
> key to defeating PKI (pun intended).

I didn't think those were computers but were (stretching the definition
of) devices.

/BAH

[toc] | [prev] | [standalone]

Back to top | Article view | alt.folklore.computers

csiph-web