<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><blockquote type="cite"><div bgcolor="#FFFFFF" text="#000000">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".<br></div></blockquote><div><br></div>That's not very reassuring.<div><br></div><div>-g<br><div>
<br class="Apple-interchange-newline"><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;">--</span><br style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;">Please do not email me anything that you are not comfortable also sharing</span><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; display: inline !important; float: none;"> with the NSA.</span>
</div>
<br><div style=""><div>On Jan 25, 2015, at 12:39 PM, Mike Hamburg <<a href="mailto:mike@shiftleft.org">mike@shiftleft.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type">
<div bgcolor="#FFFFFF" text="#000000">
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".<br>
<br>
-- Mike<br>
<br>
<div class="moz-cite-prefix">On 01/25/2015 12:25 PM, Tao Effect
wrote:<br>
</div>
<blockquote cite="mid:7BF62E41-39BE-4C01-9176-655D8FBD51F3@taoeffect.com" type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div>Is he referring to this?</div>
<div><br>
</div>
<div>
<div class="gmail_quote"><a moz-do-not-send="true" href="http://library.lanl.gov/cgi-bin/getfile?27-06.pdf">http://library.lanl.gov/cgi-bin/getfile?27-06.pdf</a><br>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<div dir="ltr">
<div class="gmail_extra">
<div><br>
</div>
<div>Nice find, I hadn't seen this link before.</div>
<div><br>
</div>
<div>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":</div>
<div><br>
</div>
<div>
<div class="page" title="Page 2">
<div class="section" style="background-color:
rgb(100.000000%, 100.000000%, 100.000000%)">
<div class="layoutArea">
<div class="column">
<ol>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Instantiate
a quantum register which contains 56
qubits, called the key.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Instantiate
a classical register which contains 64
bits, called the plaintext.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Instantiate
a classical register which contains 64
bits, called the cyphertext.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Build a
quantum function called decrypt, which
accepts a key and a cyphertext, such that
</span></p><p><span style="font-size: 10pt;">it returns a
64-bit quantum word containing the
decryption. (This decrypts the cyphertext
</span></p><p><span style="font-size: 10pt;">using the
key, according to the DES algorithm.)
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Build a
quantum function called match, which
accepts one quantum register input called
</span></p>
</li>
</ol>
</div>
</div>
<div class="layoutArea">
<div class="column"><p><span style="font-size: 10.000000pt;
font-family: 'Verdana'">qdata and one
classical register input called cdata, which
returns a single quantum bit.
</span></p>
</div>
</div>
</div>
<div class="layoutArea">
<div class="column"><p><span style="font-size: 10.000000pt; font-family:
'Verdana'">(This outputs a 1 bit if the two
input words are identical, and outputs a 0 if
they are not
</span></p>
</div>
</div>
</div>
<div class="page" title="Page 3">
<div class="layoutArea">
<div class="column"><p><span style="font-size: 10.000000pt; font-family:
'Verdana'">(This outputs a 1 bit if the two
input words are identical, and outputs a 0 if
they are not
</span></p>
</div>
</div>
<div class="section" style="background-color:
rgb(100.000000%, 100.000000%, 100.000000%)">
<div class="layoutArea">
<div class="column"><p><span style="font-size: 10.000000pt;
font-family: 'Verdana'">identical.)
</span></p>
<ol start="6">
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Build a
quantum function called completely_zero,
which accepts a single qubit and
</span></p><p><span style="font-size: 10pt;">returns a
classical bit value of 1 if and only if
the input was a pure |0> state. Return
0
</span></p><p><span style="font-size: 10pt;">otherwise.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt; font-weight:
700;">Iteration 0</span><span style="font-size: 10pt;">: Load the key
register with a superposition of all
possible keys, such that bit
</span></p><p><span style="font-size: 10pt;">0 (the ls
bit) of the key is equal to 1. (This will
be a superposition of 2**55 keys).
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Send key and
cyphertext into the decrypt function. The
output will be a superposition of
</span></p><p><span style="font-size: 10pt;">2**55
different decryptions of the cyphertext.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Send
cyphertext and the output of the decrypt
function into the match function. (The
</span></p><p><span style="font-size: 10pt;">output will
be mostly zero, since most of the trial
keys are not valid.)
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Send the
output of the match function into the
completely_zero function.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">If the
output of completely_zero is 1, then bit 0
(the ls bit) of the result is equal to 0.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt; font-weight:
700;">Iteration 1</span><span style="font-size: 10pt;">: Load the key
register with a superposition of all
possible keys, such that bit
</span></p><p><span style="font-size: 10pt;">1 of the key
is equal to 1. (This will be a
superposition of 2**55 keys).
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Send key and
cyphertext into the decrypt function. The
output will be a superposition of
</span></p><p><span style="font-size: 10pt;">2**55
different decryptions of the cyphertext.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Send
cyphertext and the output of the decrypt
function into the match function. (The
</span></p><p><span style="font-size: 10pt;">output will
be mostly zero, since most of the trial
keys are not valid.)
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Send the
output of the match function into the
completely_zero function.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">If the
output of completely_zero is 1, then bit 1
of the result is equal to 0.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt; font-weight:
700;">Iteration 2-55</span><span style="font-size: 10pt;">: Repeat the
above steps until Iteration 55.
</span></p>
</li>
<li style="font-size: 10.000000pt; font-family:
'Verdana'"><p><span style="font-size: 10pt;">Complete.
You now have all 56 bits of the
cipher-key. </span></p>
</li>
</ol>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div>
<br class="Apple-interchange-newline">
<span style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">--</span><br style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">
<span style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;">Please do not email me
anything that you are not comfortable also sharing</span><span style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;"> with the NSA.</span>
</div>
<br>
<div>
<div>On Jan 25, 2015, at 11:38 AM, Tony Arcieri <<a moz-do-not-send="true" href="mailto:bascule@gmail.com">bascule@gmail.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">On Sun, Jan 25, 2015 at 11:11 AM,
Tao Effect <span dir="ltr"><<a moz-do-not-send="true" href="mailto:contact@taoeffect.com" target="_blank" onclick="window.open('https://mail.google.com/mail/?view=cm&tf=1&to=contact@taoeffect.com&cc=&bcc=&su=&body=','_blank');return
false;">contact@taoeffect.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0px 0px
0px 0.8ex; border-left-width: 1px; border-left-color:
rgb(204, 204, 204); border-left-style: solid;
padding-left: 1ex; position: static; z-index: auto;">
<div style="word-wrap:break-word">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">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</div>
</div>
</div>
</div>
</blockquote>
</div>
<div><br>
</div>
<div>Is he referring to this?</div>
<div><br>
</div>
<div>
<div class="gmail_quote"><a moz-do-not-send="true" href="http://library.lanl.gov/cgi-bin/getfile?27-06.pdf">http://library.lanl.gov/cgi-bin/getfile?27-06.pdf</a><br>
</div>
</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
-- <br>
<div class="gmail_signature">Tony Arcieri<br>
</div>
</div>
</div>
</blockquote>
</div>
<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Messaging mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Messaging@moderncrypto.org">Messaging@moderncrypto.org</a>
<a class="moz-txt-link-freetext" href="https://moderncrypto.org/mailman/listinfo/messaging">https://moderncrypto.org/mailman/listinfo/messaging</a>
</pre>
</blockquote>
<br>
</div>
</blockquote></div><br></div></body></html>