> 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 <[email protected]> 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 <[email protected]> wrote: >> >>> On Sun, Jan 25, 2015 at 11:11 AM, Tao Effect <[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 >
signature.asc
Description: Message signed with OpenPGP using GPGMail
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
