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 <[email protected]
<mailto:[email protected]>> wrote:
On Sun, Jan 25, 2015 at 11:11 AM, Tao Effect <[email protected]
<mailto:[email protected]>> 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
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
_______________________________________________
Messaging mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
