Quantum Computing Since Democritus Lecture 8: Crypto

Psst … one-way functions? Pseudorandom generators? Lattices? RSA? Come and get ‘em, in plaintext.

Gus Gutoski took notes for this “all about cryptography” lecture, and they were so good that I’ve posted them with only moderate editing and joke-reinsertion. I’ve thereby provided you, my readers, with the unique opportunity to experience my lecture as Gus himself experienced it — as if you actually were Gus, sitting in a real Waterloo classroom taking notes.

For those of you who feel the need to prepare yourselves for this experience, here’s a recap of all the lectures so far:

Update: Preparing these notes is a sh&tload of work for me. So dude — if you want me to keep doing it, please let me know in the comments section if you’re actually reading the notes and deriving any benefit therefrom. Constructive criticism would also be fantastic. Thanks very much!

48 Responses to “Quantum Computing Since Democritus Lecture 8: Crypto”

  1. Osias Says:

    Nice one! Good to know there will be classical cryptosystems unbreakable by QC, so I won’t have to make upgrades to be safe ^.^

  2. Bill Kaminsky Says:

    I’m not sure if this just a transitory server thing or if the links are mistyped, but as I write this (morning of December 11th), all the lecture links yield “404 Not Found: The requested URL /blog/lecX.html does not exist” error messages.

  3. John Sidles Says:

    In addition to Penrose’ Emperor’s New Mind (whose wonderfully enigmatic concluding paragraph is this: “Adam felt acutely embarrassed. Whatever they should have done, they should not have laughed.”) beginning students might enjoy David Deutsch’s highly readable Fabric of Reality.

    Admittedly, neither of these books will teach a student how to calculate.

    Also recommended is Jonathan Israel’s new Enlightenment Contested. Israel’s book is far too long to be assigned as a text, but any student who read the Preface, Introductory, and the Postscript would gain a solidly-grounded appreciation of the motivations and historical circumstances of people like Newton and Leibniz. Also, the chapter Newtonianism and Anti-Newtonianism in the Early Enlightenment: Science, Philosophy, and Religion is mandatory reading, due to the many evident parallels to the present era.

    The point being, our present era is surely not less interesting Newton’s! IMHO, Prof. Israel’s book provides an excellent remedy to the watered-down & thought-deadening histories of mathematics, science, and technology that students are usually assigned.

  4. John Sidles Says:

    With reference to Bill’s comment about the broken URL, all eight (to date) of Scott’s lectures are on-line here:

    http://www.scottaaronson.com/democritus/:

  5. Scott Says:

    Sorry about the broken URL’s! They’re fixed now.

  6. paraphrene Says:

    “Of course, being spooks, they couldn’t publish their work, so today they don’t get much credit! Let that be a lesson to you.”

    spook, n.
    Slang: Disparaging and Offensive. a black person.

    Thanks, Scott. I’ll try to remember that.

  7. Amit Kotwal Says:

    Hi,

    I’ve read upto Lecture 6 so far, and I’m finding them immensely enjoyable. The presentation, and the problems are way better than the classes I took years back. Clearest proof of Godel’s Incompleteness Theorem I’ve seen too.

    – Amit

  8. Nick Bornak Says:

    “…do we ever really talk about the continuum, or do we only ever talk about finite sequences of symbols that talk about the continuum?”

    It seems to me the latter. To talk about the continuum, we’d need \aleph_1 names, which we don’t have. I think I’m missing something, though.

    Thanks for posting these notes. I happen to be one of those naive mathematicians who used 2^n*3^m for (n, m) in CS 101, hehe.

  9. Christian Reitwießner Says:

    The notes are really great. I very much like the way you point out continuative topics. Most teachers only say something like “there is something very interesting you will perhaps encounter later” but don’t state its name so nobody is able to look it up. You instead present very concise teasers but fully state the name of the problem.
    Keep at it!

  10. Scott Says:

    spook, n.
    Slang: Disparaging and Offensive. a black person.

    Thanks. I honestly never knew that meaning of “spook” — I just looked it up, and found it in some dictionaries but not others. I assume you know full well that I meant an undercover agent or spy! Even though my sentence said exactly what I thought it did, I decided to change it. I’m reminded of the government employee who was inadvertently fired for using the word “niggardly”…

  11. Scott Says:

    “…do we ever really talk about the continuum, or do we only ever talk about finite sequences of symbols that talk about the continuum?”

    It seems to me the latter. To talk about the continuum, we’d need \aleph_1 names, which we don’t have. I think I’m missing something, though.

    Nick: I agree with you, but in the interest of full disclosure, I should tell you that there have been many great thinkers over the millennia who wouldn’t! The key question seems to be whether human beings can form a direct intuition of (say) the real number line, unmediated by any symbolic description of it. For what it’s worth, my own answer is simple: maybe Roger Penrose can form such an intuition, but I can’t! Sure, I can form an intuition of something that looks like the real number line, but then again, it might just be the rationals (the two look pretty similar to me).

  12. Jakob Says:

    Please “keep doing it”. The range of interesting topics,as well as your inimitable style, make each installment of your lecture notes a must-read

    Jakob

  13. Johan Richter Says:

    The notes are great Scott. Keep ‘em comin’!

    One thing I wondered about is what would P=BPP imply about the existence of good pseudo-random generators? You mentioned in the last lecture notes that a good enough pseudo-random generator would imply P=BPP but is there any form of converse?

  14. Nick Bornak Says:

    Scott: “The key question seems to be whether human beings can form a direct intuition of (say) the real number line, unmediated by any symbolic description of it.”

    Ah, so that’s how they’d go about doing it.

    I’ll have to take your seminar’s advice and reread Penrose; I’m afraid I read _Shadows of the Mind_ about three years ago — but I don’t remember any of it, so I can read only _The Emperor’s New Mind_ and still have a clean conscience. :)

  15. rrtucci Says:

    Keep those notes coming. For a Complexity Theorist, you ain’t that bad. (Next thing I know, you’ll be claiming that Feynman was a theoretical computer scientist.)

  16. Ryan Says:

    Scott, I love your notes, both for the subject and for the clarity with which you present the topics! Keep on churning them out–I’ll be reading!

  17. Osias Says:

    spook
    1 Someone unpleasantly strange or eccentric
    2 A mental representation of some haunting experience
    3 A person secretly employed in espionage for a government

    by wordweb, http://wordweb.info/

  18. ano Says:

    Scott,
    I think it’s great that you are taking the time to make these notes available for people who wouldn’t otherwise be able to learn this stuff. I haven’t read all of them yet, but I will do so over the holidays. Seriously though, don’t stress yourself out just to provide free education to anonymous strangers like me! You’re too kind ;)

  19. Felipe Says:

    Great lecture notes. I hope you’ll include a lecture on nullity too :)

  20. NoJoy Says:

    Great lecture notes. And thanks for being willing to call a spade a spade.

  21. Scott Says:

    Thanks so much, everyone! Alright, I’ll keep doing it. :)

  22. Martin Says:

    Scott, I’m glad to hear you’re continuing the series. It would be a shame if you stopped your series on Quantum Computing before you actually cover Quantum Computing.

  23. Scott Says:

    Johan:

    One thing I wondered about is what would P=BPP imply about the existence of good pseudo-random generators? You mentioned in the last lecture notes that a good enough pseudo-random generator would imply P=BPP but is there any form of converse?

    Excellent, excellent question! The short answer is that right now, we only know very weak converses. So for example, we know that if P=BPP (or more precisely PromiseP=PromiseBPP, which is almost the same), then NEXP requires circuits of half-exponential size (that is, size f(n) where f(f(n)) is exponential). And being a circuit lower bound, that will give you some sort of pseudorandom generator: maybe a PRG computable in nondeterministic half-exponential time? Whatever it is, it will be crappy but better than what we know now.

    The fundamental problem is that in principle, there might be a way to derandomize BPP that doesn’t involve going through a pseudorandom generator. BPP is a class of languages, and it would suffice to find P algorithms for all the languages that happen to be in it, whether or not one can “fool” the BPP machines themselves! Having said that, all the actual proposals we have for derandomizing BPP do involve going through a pseudorandom generator.

    Ask your question again in a few years, and we might know more!

  24. Scott Says:

    It would be a shame if you stopped your series on Quantum Computing before you actually cover Quantum Computing.

    :)

  25. paraphrene Says:

    “The key question seems to be whether human beings can form a direct intuition of (say) the real number line, unmediated by any symbolic description of it. For what it’s worth, my own answer is simple: maybe Roger Penrose can form such an intuition, but I can’t!”

    According to Dr. Ericsson, you can do anything you put your mind to.

  26. paraphrene Says:

    In the way of constructive criticism, I suggest adhering to the general standards of classic literature. That is, carry your words with poise and purpose, like a gentleman. Exhibit eloquence in every phrase and listen carefully to your own phonetic melody. Alternatively, the casual jesting, lightly musing, unpoetic tone detracts from your dignity, destroying the air of majesty which would normally surround your lecture notes.

  27. Scott Says:

    the casual jesting, lightly musing, unpoetic tone detracts from your dignity, destroying the air of majesty which would normally surround your lecture notes.

    :-)

    There’s a simple way to bring back the air of majesty: just imagine the notes being read by me in a high-pitched, faux-British accent.

  28. Benjamin Says:

    I read all your lecture notes soon after you post them, and find them every entertaining. I appreciate the time you spend on them. Thanks.

    I did have one piece of constructive criticism for your lecture notes, on your proof of Godel’s incompleteness theorem in lecture 3.

    The idea that “Godel’s incompleteness theorem basically boils down to the halting problem” is one I’ve heard from a few current and former CS grad students at Berkeley. I’m not sure where that perspective originates, but I think it misses something.

    Your notes mention something about translating the halting problem into a statement about integers, but just as a parenthetical remark. I think the “technical tour de force” part of proving Godel’s theorem lies there, with formally identifying proof checking, or program halting, (or any primitive recursive predicate) with sentences about natural numbers in the first order language with plus and times. The diagonalization proof at the end is just the punchline.

    The halting problem provides a good way to phrase the incompleteness theorem’s required diagonalization argument, simpler than Godel’s original proof, and maybe better than whatever way they do it in math class. My point would just be that the diagonalization argument is not the entire theorem. (You skipped the hard part).

  29. Scott Says:

    Benjamin: Thanks for the comment! Mathematically I completely agree with you; philosophically my disagreement couldn’t be sharper.

    For me, the greatest testament to Gödel’s legacy is that what you call “the hard part” of his theorem is no longer hard. From a CS perspective, it’s obvious that whether a computer program halts is a mathematical question, one that could ultimately be “compiled” into a question about integers — in exactly the same way it’s obvious that a C program can be compiled into assembly language. In both cases, formal proofs can be given (and verified by machine), but are unfit for human consumption.

    In other words: it took a while, but civilization eventually caught up to where Gödel was in 1931!

  30. Devin Smith Says:

    The lectures really only get better from here, and you should have reasonably good notes for most of them after lecture 8, no?

    To all: rest assured, Scott will be able to fit at least one complexity class into every lecture. It’s a shame these couldn’t’ve gotten done more ‘real-time’ so that the people actually taking the class could comment, but such is life.

  31. michael vassar Says:

    I really enjoy the notes. Thanks.

  32. Danielle Fong Says:

    I eagerly await each of the installments. They brighten my week.

    Already I have used some of the lecture notes as the -first- reference I send people towards if they want to understand something. Please keep it up. And then publish a book or something.

  33. Benjamin Says:

    Scott: Computer scientists use “obvious” a lot.

    Compiling a C program into assembly is conceptually easy because it just involves translating the syntax of one imperative language into a more basic one. The procedure is complicated only because there’s so much stuff to write down.

    On the other hand, I would argue that modeling an arbitrary computation by using a first order sentence about natural numbers is less obvious. The procedure is also less complicated in terms of what you need to write down to explain to someone else how to do it. The following example would likely suffice:

    Given a Turing program P, P halts iff there exists integers C and n, (C a code for a sequence of n integers, each of which codes a Turing machine configuration) such that
    – C_0 codes a configuration in the initial state, and
    – C_n codes a configuration in the halting state, and
    – For each j

  34. Benjamin Says:

    Damn Firefox ate the rest of my comment.

    – For each j

  35. Benjamin Says:

    hmm, guess your blog doesn’t like the “less than” symbol.

    – For each j less than n, the configuration coded by C_(j+1) is the result of applying P to the configuration coded by C_j.

    Now there’s still some work to do, (e.g. saying what it means for an integer to code a “configuration in the initial state”), but at least now you’ve given enough of a start so that the problem looks more like compiling.

    I’ve heard model theorists tell it that Godel’s most important result was showing that the first order language with plus and times can be used as a model of computation. Is there really a big picture perspective from whose point of view that part of the theorem is obvious? I’d enjoy being enlightened.

  36. Scott Says:

    Benjamin: Alright, I agree that it takes some ingenuity to show that first-order logic with plus and times can be used as a model of computation.

    But here’s what a computer scientist would say: if FOL with plus and times is too hard to prove universal, then just throw in some more operations (exponentials, division, the floor function, etc.) until it becomes obvious! If you do this, you’ll have answered the conceptual question of whether sufficiently powerful formal systems can talk about their own provability, leaving only the technical question of exactly how much power is sufficient.

  37. cody Says:

    I am enjoying the lectures very much, although I have fallen a few behind, I hope to catch up soon. I think I benefit from them a lot too, so thank you.

  38. Andy Says:

    Hi Scott,
    Maybe I’m missing the section or lecture where you do this, but you should really explain that ‘solving NP-complete problems on average’ means solving all NP-complete problems with respect to all P-sampleable distributions, not just e.g. solving 3-colorability with respect to the uniform distribution (which is easy).

    If you don’t make this distinction it’s problematic to assert (as in your diagram) that solving NP-complete problems on average is harder than breaking cryptosystems.

  39. Rahul Says:

    An elaboration of Scott’s response to Johan’s question: For the class MA, which is just NP with probabilistic verification, it is known that any non-trivial derandomization of MA with a small amount of advice implies non-trivial pseudo-random generators with a small amount of advice. So there are certainly indications that derandomization may be as hard as finding pseudo-random generators, which is rather surprising on the surface of things.

  40. Daniel Says:

    Scott, do you know that there is a sharper, O(1/n) solution to the red-and-blue-hats puzzle? By the way, as far as I know, the optimal success ratio for each n is an open question.

    Daniel

  41. Anonymous Says:

    Simply put: If, as Scott says , the Simpsons is what justifies the existence of television as a medium, then resources like these course notes are what justify the existence of the Internet as a medium.

    Seriously, where else can one get an entertaining introduction to set theory, mathematical logic, computability theory, complexity theory, quantum computing, cryptography, and the philosophy of mind and language all at once?

  42. Scott Says:

    Scott, do you know that there is a sharper, O(1/n) solution to the red-and-blue-hats puzzle?

    No, I didn’t know that!

  43. Scott Says:

    Maybe I’m missing the section or lecture where you do this, but you should really explain that ’solving NP-complete problems on average’ means solving all NP-complete problems with respect to all P-sampleable distributions, not just e.g. solving 3-colorability with respect to the uniform distribution (which is easy).

    Thanks, Andy! I inserted a remark to that effect.

  44. Daniel Says:

    Spoiler for the sharper (and nicer) solution to the colored hats puzzle: Search google for “this is assumed to have been due to a two”, quickly.

  45. alex Says:

    I don’t know if any of you read Philip Roth’s The Human Stain, but one summary of the plot is

    In April 1996, at 69, Coleman Silk is still professor of classical literature at Athena College…Silk is accused of having made a racist remark about two African-American students who were absent from his class and whom he had never seen before … He called them “spooks” — suggesting they were ghosts, but not considering that spooks is also an old-fashioned epithet for blacks. In the ensuing upheaval, several of his colleagues turn against Silk and support the African-American students. Silk feels monstrously wronged, and though he could have gone on teaching, he decides to resign…

    It didn’t seem realistic when I read it, but I may have to change my mind following this thread.

  46. Jon Sneyers Says:

    I’m reading your lecture notes. Please don’t stop making them. They are very interesting. Thanks.

  47. HTML Coder Says:

    Benjamin,

    For future reference, you can encode < as &lt;, > as &gt;, and & as &amp;. The problem you experienced will occur with any browser; the WordPress comment editor doesn’t automatically encode characters normally used in specifying HTML markup.

  48. trigman Says:

    minds and machines should at some point refer to the phrase that encompasses the concept you call upon…

    zero knowledge proofs… it’s important to teach the terminology and the overall concept