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

[Mike Hamburg]

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":
>
> 1.
>
>     Instantiate a quantum register which contains 56 qubits, called
>     the key.
>
> 2.
>
>     Instantiate a classical register which contains 64 bits, called
>     the plaintext.
>
> 3.
>
>     Instantiate a classical register which contains 64 bits, called
>     the cyphertext.
>
> 4.
>
>     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.)
>
> 5.
>
>     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.)
>
> 6.
>
>     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.
>
> 7.
>
>     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).
>
> 8.
>
>     Send key and cyphertext into the decrypt function. The output will
>     be a superposition of
>
>     2**55 different decryptions of the cyphertext.
>
> 9.
>
>     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.)
>
>10.
>
>     Send the output of the match function into the completely_zero
>     function.
>
>11.
>
>     If the output of completely_zero is 1, then bit 0 (the ls bit) of
>     the result is equal to 0.
>
>12.
>
>     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).
>
>13.
>
>     Send key and cyphertext into the decrypt function. The output will
>     be a superposition of
>
>     2**55 different decryptions of the cyphertext.
>
>14.
>
>     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.)
>
>15.
>
>     Send the output of the match function into the completely_zero
>     function.
>
>16.
>
>     If the output of completely_zero is 1, then bit 1 of the result is
>     equal to 0.
>
>17.
>
>     Iteration 2-55: Repeat the above steps until Iteration 55.
>
>18.
>
>     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 
> <mailto:bascule at gmail.com>> wrote:
>
>> On Sun, Jan 25, 2015 at 11:11 AM, Tao Effect <contact at taoeffect.com 
>> <mailto: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/24573c89/attachment.html>