tag:blogger.com,1999:blog-3722233.post8913346816793700392..comments2020-04-02T14:59:58.018-04:00Comments on Computational Complexity: A short History of CryptoLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-10213679795693148952014-01-15T21:38:31.661-05:002014-01-15T21:38:31.661-05:00It sounds like it would have been a great summer c...It sounds like it would have been a great summer course to attend! It's definitely important to show both math and practical relevance and how unnoticed assumptions can change everything. Hope both you and the kids enjoyed it and that you do it again.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79980937429721322582014-01-15T16:48:00.484-05:002014-01-15T16:48:00.484-05:00Addendum: the third and most unfortunate possibili...Addendum: the third and most unfortunate possibility is:<br /><br />Eve: No, I found a bug in your proof.<br /><br />A&B: Whoops.Chrishttps://www.blogger.com/profile/03327470068256472110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4219142859214166042014-01-15T16:44:24.849-05:002014-01-15T16:44:24.849-05:00Regarding the "i=1 to infinity" history ...Regarding the "i=1 to infinity" history of crypto, that may have been accurate as ancient history, i.e., before 1980. Today the conversation goes:<br /><br />Alice and Bob: We have a cipher that we have PROVEN nobody can break, <i>if</i> the attacker is constrained by this particular formal attack model, and <i>if</i> these unproved-but-not-yet-falsified complexity assumptions hold.<br /><br />Eve: I just cracked it.<br /><br />Alice and Bob: Interesting! Did you falsify (one of) our complexity assumption(s)?<br /><br />Eve: Yes!<br /><br />A&B: Wow, that's a tremendous and unexpected algorithmic breakthrough, congratulations. We'll have to design a new scheme based on some other complexity assumption.<br /><br />OR, MUCH MORE LIKELY:<br /><br />Eve: No, I circumvented your attack model by doing something realistic that your model doesn't allow.<br /><br />Alice and Bob: That's clever! We'll strengthen our model to allow the attacker that kind of extra power -- and ideally much much more, since we don't want to have this kind of conversation with you again! Now we have a new scheme that we have PROVEN nobody can break ... etc. etc.Chrishttps://www.blogger.com/profile/03327470068256472110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85768358459823078132014-01-15T16:42:14.866-05:002014-01-15T16:42:14.866-05:00This was a fine post (as it seems to me). History...This was a fine post (as it seems to me). History shows us too that parallel computational considerations apply to dynamical simulation:<br /><br />--------<br />For i=1 to Infinity<br /><br />1: <b>Consensus</b> "X" is a class of dynamical systems that nobody can simulate.<br /><br />2: <b>Alice and Bob</b> We have PROVEN that X-class systems can't be simulated.<br /><br />3: <b>Eve</b> I just simulated the X-class.<br /><br />4: <b>Alice and Bob</b> Whoops<br />--------<br /><br />Scott Aaronson's slides to his lecture "The cryptographic hardness of decoding Hawking radiation" explains the origin of "whoops" concisely:<br /><br />--------<br /><b>Worst Case</b> (slide 6) "We can argue that a natural formalization of Alice's decoding task is 'generically' hard. We can't rule out that a future theory would make her task easy, for deep reasons not captured by our formalization."<br />--------<br /><br /><b>Conclusion</b> To paraphrase <b><a href="http://books.google.com/books?id=-YsWNfTXU7oC&pg=PA105" rel="nofollow">Ed Wilson's celebrated aphorism</a>:</b> "Much of the history of complexity theory consists of failed claims of generic computational difficulty."<br /><br />We all have reason to rejoice that (historically speaking) difficulty-claims have so often failed. Because if past claimed "unbreakable" cryptographic protocols *had* turned out to be unbreakable, and past claimed "unsimulable" quantum dynamical systems *had* turned out to be unsimulable, then the present job market for young computer science professionals would be far less vibrant than it is! John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77727125946963193212014-01-15T16:17:33.961-05:002014-01-15T16:17:33.961-05:00Good point. I should have written ` ``gave an argu...Good point. I should have written ` ``gave an argument''<br />or even ``gave an informal argument'' instead of ``proof''<br />Or perhaps I should have written proof in quotes. <br />(This IS bill, but I am using my CAAR-REU account righ tnow<br />so that what my name is. Just like you ARE Jon Katz but choose<br />to go by Anonymous this time.)Anonymoushttps://www.blogger.com/profile/00496057724536630931noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91628007808774491752014-01-15T13:43:02.077-05:002014-01-15T13:43:02.077-05:00OK, but in your blog post you kept on saying "...OK, but in your blog post you kept on saying "PROOF." My point was exactly that these schemes do NOT have proofs. So at best these arguments highlight the importance of proofs in some well-defined model.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81256337293677677462014-01-15T10:01:39.759-05:002014-01-15T10:01:39.759-05:00(Gee, its odd having he discussion over a blog whe...(Gee, its odd having he discussion over a blog when your office is about<br />30 feet from mine.)<br /><br />1) PERM--- I pointed out that there are 26! possiblities so IF the model<br />says ALICE MUST GO THROUGH ALL OF THEM then its hard.<br />However, Alice can do other things.<br /><br />2) Matrix Cipher- if you have a (say) 200x200 matrix and its cipher-test<br />ONLY then the freq analsysi washes out so it SEEMS as though you need to go through all possible matrices. NO I didn't say this was proven. But<br />I wonder- can one prove that? Not sure what the assumptions should be.<br /><br />3) I didn't mention 1-time pad i my post (though I did in class) so I<br />don't know what you are getting to. My point in class was that since<br />VIG with a long key obscures Freq analysis one might think it is<br />uncrackable- in fact people DID think this. But then I showed how you<br />could crack it.<br /><br />4) My POINT of all this I would think you WOULD approve of--- that to prove things UNCRACKABLE you need to do it in a model, and Eve need<br />not work in your model. Hence you need to be careful.<br /><br />5) My examples are fatous? Here they are in summary:<br /><br />PERM- large key space so if you had to look through it too hard, but<br />there are other ways<br /><br />MATRIX- if ciphertext only seems hard (though not known) but people<br />usually have other attacks<br /><br />VIG- once thought uncrackable beause it washes out freq dist, but<br />is actually crackable. (This is Vigenere.)<br /><br />objections?<br /><br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10122097011970905762014-01-15T07:14:17.873-05:002014-01-15T07:14:17.873-05:00I think this is a terrible misrepresentation of cr...I think this is a terrible misrepresentation of crypto to give to students. (Maybe you did it differently in class.) It is true that schemes can be proven secure in one model and broken in a stronger model, and an honest discussion with real-world examples could have been great. But the examples you gave were fatuous:<br /><br />- You didn't prove that PERM is unbreakable -- I guess all you proved is that it has lots of keys. If anything, this shows the importance of coming up with a meaningful definition. (To illustrate that large keyspace does not imply security, you could have also given the example of the null encryption scheme that uses 1000-bit random keys but outputs the plaintext in the clear.)<br /><br />- I'm not sure in what sense you can prove that matrix ciphers are unbreakable. <br /><br />- The nice thing about the one-time pad/Vernam cipher (which is not the same as the Vigenere cipher, by the way) is that it *is* provable, with respect to a strong notion of secrecy and without making *any* assumptions about the behavior of the adversary. Yes, it is under the assumption that the parties only use the key once; yes, it can be broken completely if the key is used twice. But in scenarios where one-time use can be ensured, the one-time pad might be a perfectly reasonable choice.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.com