Great Ideas in Theoretical Computer Science Lectures 16-19
In the next-to-last GITCS installment, we cover some of the greatest hits of the 70’s and 80’s.
- Lecture 16: Private-Key Cryptography
- Lecture 17: Public-Key Cryptography
- Lecture 18: Cryptographic Protocols (including: how computer scientists date!)
- Lecture 19: Interactive Proofs / Machine Learning
(Something tells me Lecture 18 is going to get more hits than the other three combined…)
The course itself ended two weeks ago; last week was the final exam. Thanks so much to all of my students for signing up for a brand-new course, asking probing questions, enduring my excruciating jokes, and doing a fantastic job with the notes. (Of course, thanks also to my eagle-eyed readers for spotting errors.) Thanks above all to my TA, Yinmeng Zhang, who went way beyond her job description to work with students individually, tell me when I was being a doofus, etc. Because of the input of everyone who participated, this course will be better when I teach it the second time around.
Also, for anyone who might want to teach a similar course, the recipe is simple (much simpler than I expected, actually):
- Start with a standard, off-the-shelf, undergraduate computability and complexity theory course.
- Cut out the most boring parts, like pushdown automata, context-free grammars, and 105000 NP-completeness reductions. (Yes, I know these things can be taught in a non-boring way, but why make it hard on yourself?)
- Fill in the gaps with more interesting material, like zero-knowledge proofs, computational learning theory, or quantum computing.
- Add a pinch (to taste) of mindblowing results that can’t be covered in detail, like the PCP Theorem, the independence of the Continuum Hypothesis, or cosmological limits on computation.
Serves 10-100.
Follow
Comment #1 May 27th, 2008 at 7:42 pm
In lecture 18, it’s not quite accurate to say that there are *trapdoor* OWFs based on elliptic curves. There are plenty of useful things on can do cryptographically (like public-key encryption), but we don’t know whether there is a “trapdoor” allowing for, say, efficient inversion of the one-way exponentiation operation.
Comment #2 May 27th, 2008 at 8:01 pm
Chris: Interesting, thanks! I was vaguely imagining that your work with Waters could be used to turn elliptic-curve PKC’s into elliptic-curve TDOWF’s (under some definition of TDOWF), but I’ll certainly take your word that it can’t.
Comment #3 May 27th, 2008 at 8:06 pm
Scott: OK, you got me, it is true — under a somewhat different notion of TDOWFs. (Or at least for inverting a different kind of problem than modular exponentiation.)
The main point is that RSA has a very special kind of “natural” trapdoor that discrete log systems don’t have (at least, not that we know of).
Comment #4 May 27th, 2008 at 8:40 pm
Hm, it sounds like computer scientists won’t be able to date any more if we build a quantum computer. Thanks for brightening my day.
Comment #5 May 27th, 2008 at 9:07 pm
Sydney: No, we believe there are one-way functions secure against quantum attack; hence the dating protocol could presumably still be implemented in a world with quantum computers.
Incidentally, here’s a question just that occurred to me: can the dating problem be solved quantumly even without computational assumptions? At least with nontrivial success probability? We know that quantum bit commitment is impossible with no computational assumptions, but maybe it’s possible to solve the dating problem without using bit commitment as a primitive. Any experts care to comment — does an answer to my question follow from known results (or maybe from tweaking the no-go theorem for bit commitment)?
Comment #6 May 27th, 2008 at 9:28 pm
* Lecture 18: Cryptographic Protocols (including: how computer scientists date!)
Wait. Computer scientists actually date?
Comment #7 May 27th, 2008 at 9:41 pm
Wait: the bit commitment assumption in the classical dating problem only arises in the zero-knowledge version, right? Or am I missing something?
If I’m not missing something, then it seems like no-go for bit commitment would have no direct bearing on the possibility of a quantum protocol for the dating problem, at least without the zero-knowledge assumption. But of course I’m not an expert, and the proof might be modifiable.
Comment #8 May 27th, 2008 at 9:57 pm
Harrison, even in the honest-but-curious model, you could see Alice as doing bit commitment in the very first step, when she sends Bob x3 mod N and y3 mod N.
Comment #9 May 27th, 2008 at 10:37 pm
Oh, duh.
Alright, I’m not sure if this is what you meant by “trivial success probability,” but here’s an idea. Alice and Bob each hold half of an EPR pair; they perform measurements based on their interest in each other as in the protocol in the proof of Bell’s theorem.
Alice and Bob then each have a classical bit; with some probability p, the xor of these two bits is equal to the AND of their “interest bits.” They can compute the xor of their bits without revealing the bits to each other (although do they even have to hide the measurement results?) and by repeating the process they can know to within any certainty whether they’re interested in each other.
Obviously there are about 1500 places in this protocol where either Alice or Bob could “cheat.” But shouldn’t this work under the honest-but-curious assumption?
Comment #10 May 27th, 2008 at 11:23 pm
Harrison, I don’t even know how to formalize “honest-but-curious” in the quantum setting, in a way that doesn’t let the players trivially do everything. (I.e. why not just force the players to encode everything in quantum states in some trivial way, and then stipulate that “following the protocol” entails not measuring the states except when directed to?)
So the goal would be to implement the dating protocol in the dishonest model.
Comment #11 May 28th, 2008 at 2:02 am
I really appreciate your unique high level, non-technical synthesis of entire subfields of CS. These lectures really tie a lot of cryptography stuff together for me, even though I’ve seen a lot of it before in more detail. Your Democritus notes about complexity had the same effect on me last year.
Comment #12 May 28th, 2008 at 4:42 am
Step 2 is genius.
That is all.
Comment #13 May 28th, 2008 at 1:12 pm
In Lecture 18, a student suggested the protocol “face each other with your eyes closed and open them if interested” for resloving the “dating problem”. I don’t think you should have dismissed it so easily, surely there can be a way to make that work.
In real life, of course, the problem is addressed by the similar protocol “if interested/uninterested, when eye contact is made hold it for epsilon seconds longer/shorter than last time, where epsilon is sufficiently small that the eye contact cannot be taken as evidence of interest, but after sufficiently many rounds mutual confidence will be attained if there is mutual interest”. The reason nerds fail at this is either a lack of ocular dexterity or an inability to intuit the correct value of epsilon from previous social experience.
I once thought of writing a science fiction story about a society where it was possible to “ping” someone you were interested in, in such a way that they could only query whether you had pinged them by pinging you (in effect there would be a mental tunnel between each pair of people which each person could leave his door to open or closed).
Comment #14 May 28th, 2008 at 2:32 pm
Sydney: No, we believe there are one-way functions secure against quantum attack; hence the dating protocol could presumably still be implemented in a world with quantum computers.
Scott: Implementing a protocol for the dating problem from a one-way function may not be as simple as it seems, even in the honest-but-curious model. We know that: (1) any protocol for the dating problem implies a protocol for oblivious transfer, and (2) coming up with a protocol for oblivious transfer from a one-way function may be a challenging task (as shown by Impagliazzo and Rudich, there is no black-box construction of oblivious transfer from one-way function).
(Actually, some may regard (2) as the biggest challenge in cryptography, except perhaps the challenge of proving the existence of one-way functions unconditionally).
So while it is indeed true that the dating protocol could presumably be implemented in a quantum world, one has to keep in mind that having a one-way function that is secure against a quantum attack may not be sufficient (unless one also overcomes the barrier of implementing oblivious transfer from a one-way function).
This is a suble distinction, but I think that it is worth pointing out. The question here is whether the quantum world corresponds to minicrypt, in which case there are one-way functions that are secure against quantum attacks but no protocols for dating, or to cryptomania, in which case there are protocols for oblivious transfer (and hence also for dating).
Disclaimer: the above discussion is based on what I know is going on in the “classical” world. In fact, I am not even sure what is a one-way function that is secure against a quantum attack, and it could very well be the case that such functions do imply oblivious transfer in a quantum world (if this is true then it would make a quite intriguing state of affairs).
Incidentally, here’s a question just that occurred to me: can the dating problem be solved quantumly even without computational assumptions? At least with nontrivial success probability? We know that quantum bit commitment is impossible with no computational assumptions, but maybe it’s possible to solve the dating problem without using bit commitment as a primitive. Any experts care to comment — does an answer to my question follow from known results (or maybe from tweaking the no-go theorem for bit commitment)?
Kilian showed in 1988 how to construct bit commitment from a black-box that implements oblivious transfer. This, combined with the fact that any protocol for dating can be used to implement oblivious transfer seems to imply that any protocol for dating can be used to implement bit commitment. I haven’t though about this argument carefully, and it may be irrelevant in the quantum world, but it seems to indicate that the dating problem would require assumptions also in the quantum world.
Comment #15 May 28th, 2008 at 3:03 pm
Scott: In lecture 18 you use the interactive proof for GNI as an example for a zero-knowledge proof. I am not sure, but this may be a little bit confusing, given that it is zero-knowledge only for an honest verifier (and given that you motivate the idea of zero-knowledge via verifiers that may be acting dishonestly).
I assume you chose to present things this way in order to keep things simple (and to avoid the presentation of the interactive proof for GI). In such a case, it may be worth emphasizing the distinction upfront. I saw that you did mention this distinction at a later stage when you talk about honest-but-curious, so perhaps you may as well mention it early on.
Note that the GMW protocol is zero-knowledge against arbitrary verifiers, so emphasizing the difference between honest verifier and a general verifier may be appropriate in any case.
Comment #16 May 28th, 2008 at 4:15 pm
Thanks so much, Alon! I’ll add something about the GI protocol being only honest-verifier when I get a chance.
If I can bother you for a couple more clarifications:
1. Do I understand correctly that bit commitment is known to be implementable from arbitrary OWFs, but oblivious transfer (and hence secure multiparty computation) is only known to be implementable from, e.g., TDOWPs or homomorphic public-key encryption? In the notes, I think I just said that GMW can be implemented using an arbitrary OWF. Of course GMW is just one component of the dating protocol (for the other component I explicitly used the RSA assumption). Still, I agree that this should be clarified explicitly.
2. How do you get oblivious transfer from a dating protocol? Is there a good reference that has these reductions in one place? (More and more, I’ve been feeling the same sort of resigned confusion in trying to keep straight the vast lattice of crypto assumptions, that I felt about complexity classes prior to making the Complexity Zoo. I might have to set up a Cryptorium…)
Comment #17 May 28th, 2008 at 4:32 pm
Here’s another question, which attempts to formalize Joe Shipman’s insightful comment #13. Could the dating protocol be implemented with information-theoretic security using a noisy channel? I.e. if Alice is interested in Bob, she sends a message that (because of the physical noise in the channel) yields only ε evidence of her interest; then Bob can (if he chooses) respond with a message that yields ε evidence of his interest, and they can keep escalating in probability increments of ε until they reach 1. Or can one show that any such protocol will fail?
Comment #18 May 28th, 2008 at 5:32 pm
1. Do I understand correctly that bit commitment is known to be implementable from arbitrary OWFs, but oblivious transfer (and hence secure multiparty computation) is only known to be implementable from, e.g., TDOWPs or homomorphic public-key encryption?
That’s about right. There are some other fundamental primitives from which we know how to construct oblivious transfer (single server private information retrieval comes to mind), but none of them is known to be implementable from a one-way function.
In the notes, I think I just said that GMW can be implemented using an arbitrary OWF. Of course GMW is just one component of the dating protocol (for the other component I explicitly used the RSA assumption). Still, I agree that this should be clarified explicitly.
Yes. It may be a good idea to say something explicit about it (as well as about the fact that the RSA assumption is known to imply many primitives that seem “stronger” than plain one-way functions). Note that the issue of oblivious transfer vs. one-way functions arises already in the honest-but-curious model, so in some sense it is orthogonal to the “compilation” to the malicious model using zero-knowledge proofs.
2. How do you get oblivious transfer from a dating protocol? Is there a good reference that has these reductions in one place?
Getting oblivious transfer from a dating protocol is quite simple, and is in fact a special case of a more general “all or nothing” phenomenon that occurs in two-party computation (even in the honest but curious model). Specifically, given any two party function f(x,y), either f can be computed securely unconditionally, or any protocol for securely implementing f can be used to obtain a protocol for oblivious transfer. (In turn, oblivious transfer is “complete” for secure two-party computation, in the sense that given a protocol for oblivious transfer one can securely compute any two party function f(x,y).)
Here is how it works for the dating example: An alternative way of viewing a dating protocol is simply as a protocol for securely computing the function f(x,y) = x AND y. A protocol for securely computing this function may be viewed as a secure implementation of Rabin’s variant of oblivious transfer in the semi honest model (Rabin’s variant is simply a protocol in which Alice sends a bit that is correctly received by Bob with probability 1/2, and at the end of which Alice does not know whether Bob has correctly received the bit or not). In turn, Crépeau has shown how to convert a secure protocol for Rabin oblivious transfer into a protocol for the more “traditional” 1-out-2 oblivious transfer.
I am not sure if you could find all references in one place, but here is a list of the most relevant publications in this area (sorry about the length!):
Claude Crépeau: Equivalence Between Two Flavours of Oblivious Transfers. CRYPTO 1987 (shows how to transform Rabin oblivious transfer to 1-out-2 oblivious transfer).
Joe Kilian: Founding Cryptography on Oblivious Transfer STOC 1988 (shows how to implement commitment and zero-knowledge given a black-box for oblivious transfer).
Joe Kilian: A General Completeness Theorem for Two-Party Games STOC 1991 (shows how to implement oblivious transfer given any protocol for computing a function for which the matrix f(x,y) contains an “imbedded OR” — i.e. a 2×2 submatrix with an OR like structure).
Benny Chor, Eyal Kushilevitz: A Zero-One Law for Boolean Privacy (extended abstract) STOC 1989 (observe the all-or-nothing nature of secure two-party computation for Boolean functions).
Amos Beimel, Tal Malkin, Silvio Micali: The All-or-Nothing Nature of Two-Party Secure Computation. CRYPTO 1999 (observe the all-or-nothing nature of secure two-party computation for non Boolean functions as well).
Joe Kilian: More general completeness theorems for secure two-party computation. STOC 2000 (generalizes the completeness results to other settings such as cases in which both parties receive an output and for randomized functions).
(More and more, I’ve been feeling the same sort of resigned confusion in trying to keep straight the vast lattice of crypto assumptions, that I felt about complexity classes prior to making the Complexity Zoo. I might have to set up a Cryptorium…)
Actually, we call it the “crypto jungle.” One may be tempted to think of oblivious transfer as the “king of the jungle” (in the sense that it implies many other cryptographic primitives), but this may be an inappropriate name, since there are some crypto primitives that are not known to be implied by oblivious transfer. (One example that comes into mind is collision resistant hash functions.)
Interestingly, the work by Peikert and Waters that you mentioned in the discussion with Chris gives us a new candidate for the king of the jungle. It is called “lossy trapdoor functions.”
By the way, for some time now I have been toying with the idea of imitating your “complexity zoo” and to compile a “crypto jungle.” But I don’t see that happening in the foreseeable future (also, it seems like the crypto jungle wouldn’t end up being nearly as diverse and interesting as the complexity zoo).
Comment #19 May 28th, 2008 at 5:41 pm
Is your argument that unconditionally secure dating is impossible clear? I wonder if it might be possible using a protocol with an unbounded number of rounds, but finite in expectation depending on the utility functions, as in “Games for Exchanging Information” (Gillat Kol and Moni Naor, STOC 2008).
Comment #20 May 28th, 2008 at 5:46 pm
Edit: Add “classical” and “with a trusted dealer” somewhere to the above post. Or does having a trusted dealer make the problem trivial?
Comment #21 May 28th, 2008 at 5:46 pm
Here’s another question, which attempts to formalize Joe Shipman’s insightful comment #13. Could the dating protocol be implemented with information-theoretic security using a noisy channel? I.e. if Alice is interested in Bob, she sends a message that (because of the physical noise in the channel) yields only ε evidence of her interest; then Bob can (if he chooses) respond with a message that yields ε evidence of his interest, and they can keep escalating in probability increments of ε until they reach 1. Or can one show that any such protocol will fail?
It is actually known how to implement oblivious transfer (and hence all of cryptography) given a noisy channel. So I guess this answers your question about implementing the dating protocol with information theoretic security affirmatively.
I cannot resist the urge to quote Kilian’s immortal opening sentences of the abstract of his “Founding Cryptography on Oblivious Transfer” paper:
“Suppose your netmai is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage?…”
Comment #22 May 28th, 2008 at 5:53 pm
Edit: Add “classical” and “with a trusted dealer” somewhere to the above post. Or does having a trusted dealer make the problem trivial?
Sydney: Yes. It makes the problem trivial. The whole goal of secure two-party computation is to emulate a trusted party that is (privately) handed the parties’ inputs and gives back to each party its corresponding outputs.
Kol and Naor’s paper deals with the issue of “fairness.” In our context this is a “second order” issue (all the discussion above remains relevant even if only one party obtains an output from the protocol).
Comment #23 May 28th, 2008 at 5:53 pm
On further reflection, Alice and Bob can always just simulate a noisy channel using their own randomness, and the fact that a noisy channel forces them to add noise doesn’t seem like it should increase their capabilities. (Sure, if Alice gets a message from Bob saying “please sleep with me” over a noisy channel, she can assume the message was corrupted by the channel and still think well of him. But she could do the same, were they running a protocol where they both corrupted their messages artificially. Alice’s Bayesian update is the same in both cases.)
So that takes us back to the noiseless case, where it seems clear that there’s some constant tradeoff between what Alice can learn and what Bob can learn assuming they’re not interested. (I didn’t write out a formal proof; it would be interesting to do so and to work out the exact bound).
The conclusion, unless I’m mistaken, is that Joe’s idea of solving the dating problem by “escalating signs of interest” doesn’t work, assuming the signs we’re talking about are just noisy indicators of a Boolean variable (“interested” or “not interested”). For such a protocol to work, it seems you have to assume that interest level is actually a continuum, and that what’s embarrassing is just revealing an interest level too far above the interest level that the other person has revealed. In that case an escalation protocol does work.
Comment #24 May 28th, 2008 at 5:56 pm
I’ll add something about the GI protocol being only honest-verifier when I get a chance.
I was referring to the GNI protocol, not the GI protocol.
Comment #25 May 28th, 2008 at 6:04 pm
Oops! Our comments went past each other. I see my argument about a noisy channel not helping is completely wrong then.
Comment #26 May 28th, 2008 at 6:18 pm
I was referring to the GNI protocol, not the GI protocol.
Sorry, that’s what I meant.
Comment #27 May 28th, 2008 at 7:52 pm
To elaborate on Alon’s “king of the jungle” comment:
Lossy trapdoor functions imply a host of important cryptographic primitives, including: trapdoor functions (in the ‘standard’ sense, if there is one), collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure encryption. As Alon mentioned, OT is not known to imply collision-resistant hash functions, nor chosen-ciphertext security (as far as I’m aware).
However, the true king of the jungle may still be hiding in its cave. As far as we know, lossy trapdoor functions don’t imply homomorphic encryption, private information retrieval, or identity-based encryption, to name a few “advanced” applications in cryptography.
Comment #28 May 28th, 2008 at 10:03 pm
Just to lower the level of discourse, here’s a treatment of interactive proofs in cartoon format.
Comment #29 May 28th, 2008 at 10:46 pm
Blake, that Gonick strip is one of my favorites, possibly the best TCS popularization of all time! The level of discourse cannot be but raised.
Comment #30 May 28th, 2008 at 11:42 pm
Lecture 17 reminded me of a nice puzzle that an Afghani friend told me; maybe it’s well-known in other cultures, but I’d never heard it before.
A man is travelling with two sheep and a partly tamed wolf. If he leaves the wolf unaccompanied with one or more sheep, it will kill them, but it won’t harm them if he’s there to keep it in check.
He comes to a river, and there’s a boat on the riverbank big enough to carry him and a single animal. How does he get himself and all three animals safely to the other side?
(Confession: I didn’t work it out myself before my friend lost patience with me and told me the answer. Hint: Don’t waste your time thinking of gimmicky strategies that violate the spirit of the puzzle, like making anyone swim.)
Comment #31 May 28th, 2008 at 11:57 pm
Greg, when I’ve heard that puzzle it’s usually a wolf or fox, a sheep or chicken, and some sort of plant (which the sheep/chicken will eat if left untended). At least in North America, this puzzle seems to be well-enough known that people reference it ironically in jokes and cartoons (oh, all right, the link is to PhD Comics).
Anyway, you’re right, it is reminiscent of the Diffie-Hellman locked-box problem.
Comment #32 May 29th, 2008 at 12:44 am
Thanks, Scott! Given what you say, I’m not sure why it took me so long to hear of this; most such memes spread rapidly through the Anglosphere (and across language barriers), so maybe I was just freakishly unlucky. But I’ll have to test my friend with the variation where one herbivore is replaced by a plant.
Comment #33 May 29th, 2008 at 1:16 am
On the puzzle, the man can:
– take the wolf to the other side of the river
– return, pick up one of the sheep
– take the sheep to the other side, exchange it for the wolf
– bring the wolf back, exchange it for the last sheep
– take the last sheep to the other side
– go back for the wolf
Score!
Comment #34 May 29th, 2008 at 3:00 am
In Lect. 17, Sect. 3, you describe RSA using the example of credit card numbers and a public exponent e=3. But it is well-known that this simplified description is insecure. Indeed, in practice, the credit card number x is typically a 16-digit number, while the modulus N is much larger than 200 digits (which is the current factorization record for RSA numbers). This means that there is actually no modular reduction in y=x^3 mod N, and therefore, anyone can recover x in polynomial time from the ciphertext y, without quantum computers.
So perhaps it should be pointed out that in practice, the plaintext x is actually transformed before being raised to the power 3 mod N.
Comment #35 May 29th, 2008 at 7:03 am
The wolf, sheep, and grain question is featured in series 1, episode 4 of the original UK “The Office.” A management consultant is hired to run an on-site training day for all employees, and this problem is used as a team-building exercise. It doesn’t go too well.
Comment #36 May 29th, 2008 at 10:30 am
Phong: Yes, we certainly discussed the importance of padding the messages in class, and if it’s not in the lecture notes I’ll put it there.
Comment #37 May 29th, 2008 at 9:11 pm
What are good sources to read about cosmological limits on computation?
The class of all physically possible computations gotta be one very interesting class.
Comment #38 May 29th, 2008 at 11:22 pm
Why are the pdfs of lectures 16-18 in directories that don’t match the pattern of all the others?
Comment #39 May 30th, 2008 at 12:29 am
Aaron: Because there was a numbering mistake, so I had to delete the files and recreate them, at which point the “Stellar” course management software I’m using made up new directory names. (Shorter answer: because “Stellar” is anything but.) Sorry about that.
Comment #40 May 30th, 2008 at 12:34 am
Oleg: Try this paper by Seth Lloyd, and this one by Raphael Bousso. At some point I’ll try to write a more popular account.
Comment #41 June 8th, 2008 at 5:43 pm
i am curious i personally use the pgp whole disk encryption. what i wonder is if that is truely flawless or are there potential breaches possible. i remember hearing years ago that it would take computers 20 years etc. but today that computing power is available in a cell phone, i wonder what the number is now.
Comment #42 June 10th, 2008 at 6:33 am
re: comment #42 by “Apple MacBook”
LOL! It appears that “SkyNet came alive on June 10th, 2008 at 6:10 am” … but not in the form we expected … spambots have risen to sentience ! 🙂
Comment #43 June 14th, 2008 at 9:54 pm
The last sentence of Section 1 of Lecture 19 is confusing — you claim a zero-knowledge proof that proves *any* statement with a short conventional proof, assuming the existence of one-way functions. But if you are referring to the GMW proof of 3-coloring, that is an *interactive* proof, surely not “conventional”…