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

[Tao Effect]

> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150125/1577c9fe/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/1577c9fe/attachment.sig>