<br><br>On Sunday, August 3, 2014, Bill Cox <<a href="mailto:waywardgeek@gmail.com">waywardgeek@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div><div>Does anyone on this list know anything about this story?  I heard it while I was a student at Berkeley in about 1983.  It was a story making it's way around the CS department.  Does anyone know the original source for this story?<br>

<br></div>The cool part is how this algorithm is so simple and easy to explain to just about anyone:<br><br>A CS professor at Berkeley taught one of the first crypto courses.  In a yes/no homework problem, he asked, "Alice wants to have a private conversation with Bob, and keep Eve out of it, but Eve is listening to everything Alice and Bob send to each other.  Without any shared secrets between Alice and Bob, but not Eve, is it possible for Alice to exclude Eve?"<br>

<br>The "correct" answer was "no".  One kid thought really hard about it.  This is the solution that he supposedly gave, and it's the best proof for believing public-key crypto isn't total BS ever:<br>

<br>Alice chooses 1,000,000 random strong passwords of 256 bits each.  Then she encrypts each of them with random 32-bit passwords.  She uses the strong passwords to encrypt the following message 1,000,000 times: "You guessed the right password!  Now send me a message starting with 'I love you more than anything', encrypted with it!"  Alice sends all 1,000,000 weakly encrypted passwords along with their strongly encrypted verification messages to Bob, tells him how to know when he has guessed the correct weak password, and to follow the decrypted instructions.<br>

<br>Bob then picks one of the 1,000,000 weakly encrypted strong passwords at random, and on average in 2^31 (2 billion) guesses, he has brute-force decrypted it.  He then sends Alice the message "I love you more than anything, except when Eve is in town, in which case I love her more" encrypted with the strong password.  Alice tries all 1,000,000 strong passwords and decrypts it in no time.  Then she starts her secret conversation with Bob while Eve is stuck decrypting the 1,000,000 passwords until she finds the one that decrypts Bob's message.  On average, that's 500,000 passwords she will have to crack brute force, giving Bob and Eve a security work factor of 500,000, or about 2^19.  If it takes both Bob and Eve 1 hour to crack one password, Bob has on average 500,000 hours to act on whatever  secret plans he forms with Alice before Eve finds out.<br>

<br>The funny part of this story is that supposedly the professor simply marked the student's answer wrong.  Does anyone know the origin of this story from 1983?<br></div><br>Bill<br></div></blockquote><div><br></div>
<div>This sounds similar to (though worse than) "Merkle puzzles," which date back to the '70s:</div><div>   <span style="font-family:Helvetica;line-height:19px;white-space:nowrap"><a href="http://en.m.wikipedia.org/wiki/Merkle's_Puzzles">http://en.m.wikipedia.org/wiki/Merkle's_Puzzles</a></span></div>