[messaging] Do quantum attacks/algos also lead to compromise of PFS?
Mike Hamburg
mike at shiftleft.org
Sun Jan 25 12:39:08 PST 2015
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>
More information about the Messaging
mailing list