[messaging] Do quantum attacks/algos also lead to compromise of PFS?

[Tao Effect]

> The problem with this algorithm (and with other attempts to solve SAT with a quantum computer) is that nobody knows how to build the quantum function "completely_zero".

That's not very reassuring.

-g

--
Please do not email me anything that you are not comfortable also sharing with the NSA.

On Jan 25, 2015, at 12:39 PM, Mike Hamburg <mike at shiftleft.org> wrote:

> The problem with this algorithm (and with other attempts to solve SAT with a quantum computer) is that nobody knows how to build the quantum function "completely_zero".
> 
> -- Mike
> 
> On 01/25/2015 12:25 PM, Tao Effect wrote:
>>> Is he referring to this?
>>> 
>>> http://library.lanl.gov/cgi-bin/getfile?27-06.pdf
>> 
>> Nice find, I hadn't seen this link before.
>> 
>> Yeah, it seems to be talking about the same thing, but without the explicit algorithm from the 2600 article, which is shown below for "DES-type block ciphers":
>> 
>> Instantiate a quantum register which contains 56 qubits, called the key.
>> 
>> Instantiate a classical register which contains 64 bits, called the plaintext.
>> 
>> Instantiate a classical register which contains 64 bits, called the cyphertext.
>> 
>> Build a quantum function called decrypt, which accepts a key and a cyphertext, such that
>> 
>> it returns a 64-bit quantum word containing the decryption. (This decrypts the cyphertext
>> 
>> using the key, according to the DES algorithm.)
>> 
>> Build a quantum function called match, which accepts one quantum register input called
>> 
>> qdata and one classical register input called cdata, which returns a single quantum bit.
>> 
>> (This outputs a 1 bit if the two input words are identical, and outputs a 0 if they are not
>> 
>> (This outputs a 1 bit if the two input words are identical, and outputs a 0 if they are not
>> 
>> identical.)
>> 
>> Build a quantum function called completely_zero, which accepts a single qubit and
>> 
>> returns a classical bit value of 1 if and only if the input was a pure |0> state. Return 0
>> 
>> otherwise.
>> 
>> Iteration 0: Load the key register with a superposition of all possible keys, such that bit
>> 
>> 0 (the ls bit) of the key is equal to 1. (This will be a superposition of 2**55 keys).
>> 
>> Send key and cyphertext into the decrypt function. The output will be a superposition of
>> 
>> 2**55 different decryptions of the cyphertext.
>> 
>> Send cyphertext and the output of the decrypt function into the match function. (The
>> 
>> output will be mostly zero, since most of the trial keys are not valid.)
>> 
>> Send the output of the match function into the completely_zero function.
>> 
>> If the output of completely_zero is 1, then bit 0 (the ls bit) of the result is equal to 0.
>> 
>> Iteration 1: Load the key register with a superposition of all possible keys, such that bit
>> 
>> 1 of the key is equal to 1. (This will be a superposition of 2**55 keys).
>> 
>> Send key and cyphertext into the decrypt function. The output will be a superposition of
>> 
>> 2**55 different decryptions of the cyphertext.
>> 
>> Send cyphertext and the output of the decrypt function into the match function. (The
>> 
>> output will be mostly zero, since most of the trial keys are not valid.)
>> 
>> Send the output of the match function into the completely_zero function.
>> 
>> If the output of completely_zero is 1, then bit 1 of the result is equal to 0.
>> 
>> Iteration 2-55: Repeat the above steps until Iteration 55.
>> 
>> Complete. You now have all 56 bits of the cipher-key.
>> 
>> 
>> --
>> Please do not email me anything that you are not comfortable also sharing with the NSA.
>> 
>> On Jan 25, 2015, at 11:38 AM, Tony Arcieri <bascule at gmail.com> wrote:
>> 
>>> On Sun, Jan 25, 2015 at 11:11 AM, Tao Effect <contact at taoeffect.com> wrote:
>>> The document I'm looking at [1] is quite damning and indicates QM systems break traditional symmetric ciphers like DES and AES in no time at all using "20 questions" algorithm
>>> 
>>> Is he referring to this?
>>> 
>>> http://library.lanl.gov/cgi-bin/getfile?27-06.pdf
>>> 
>>> I'm not sure where "breaks AES-256 in less than one second" is coming from, and it's hard to tell without the rest of the article being online.
>>> 
>>> --
>>> Tony Arcieri
>> 
>> 
>> 
>> _______________________________________________
>> Messaging mailing list
>> Messaging at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/messaging
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150125/69c8af94/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 841 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150125/69c8af94/attachment.sig>