[messaging] Do quantum attacks/algos also lead to compromise of PFS?
Tao Effect
contact at taoeffect.com
Sun Jan 25 12:50:53 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".
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>
More information about the Messaging
mailing list