CS 276 Lecture 18 (draft)


Today we discuss the three ways in which definitions of security given in class differ from the way they are given in the Katz-Lindell textbook,.

Then we study the security of hybrid encryption schemes, in which a public-key scheme is used to encode the key for a private-key scheme, and the private-key scheme is used to encode the plaintext.

We also define RSA and note that in order to turn RSA into an encryption scheme we need a mechanism to introduce randomness.

Continue reading


CS276 Lecture 17 (draft)


Today we begin to talk about public-key cryptography, starting from public-key encryption.

We define the public-key analog of the weakest form of security we studied in the private-key setting: message-indistinguishability for one encryption. Because of the public-key setting, in which everybody, including the adversary, has the ability to encrypt messages, this is already equivalent to CPA security.

We then describe the El Gamal cryptosystem, which is message-indistinguishable (and hence CPA-secure) under the plausible Decision Diffie-Hellman assumption.

Continue reading

Changes I’d like to see in STOC/FOCS

  • Create a “test of time award” going to the paper from the STOC/FOCS ten years prior which has best stood the test of time;
  • Reverse the trend of theoretical cryptography becoming the new computational geometry, splitting off into a self-contained community;
  • Increase the size of the program committee so that no PC member has to review more than 30 papers;
  • Allow PC members to submit papers;
  • Videotape the talks and post them on the web;
  • Hold either STOC or FOCS in Asia at least once;
  • Hold STOC and FOCS in Canada more often;
  • Always have beer at the business meeting and drinks at the reception. No exceptions;
  • Make it a rule that the PC Chair and the local organizer can present at most one piece of statistical data each at the business meeting; their presentations cannot exceed five minutes in total.

On a more practical note:

  • Let a substantial part of the discussion at the physical PC meeting be “caucus” groups in which clusters of papers in a related areas are discussed by the experts, and the controversial papers can be discussed at a technical level. There are about 15 hours of work in a two-day meeting, devoted to the discussion of 100+ papers plus several meta-questions, so most papers must be discussed in less than 10 minutes. With such time constraints, and with a group of 20+ people, the discussion of a controversial paper becomes a debate, in which the point is winning. In a smaller context, in which everybody understands the paper, it is easier to reach a consensus.

CS 276 Lecture 11: One-Way Functions


Today we begin a tour of the theory of one-way functions and pseudorandomness.

The highlight of the theory is a proof that if one-way functions exist (with good asymptotic security) then pseudorandom permutations exist (with good asymptotic security). We have seen that pseudorandom permutations suffice to do encryption and authentication with extravagantly high levels of security (respectively, CCA security and existential unforgeability under chosen message attack), and it is easy to see that if one-way functions do not exist, then every encryption and authentication scheme suffers from a total break.

Thus the conclusion is a strong “dichotomy” result, saying that either cryptography is fundamentally impossible, or extravagantly high security is possible.

Unfortunately the proof of this result involves a rather inefficient reduction, so the concrete parameters for which the dichotomy holds are rather unrealistic. (One would probably end up with a system requiring gigabyte-long keys and days of processing time for each encryption, with the guarantee that if it is not CCA secure then every 128-bit key scheme suffers a total break.) Nonetheless it is one of the great unifying achievements of the asymptotic theory, and it remains possible that a more effective proof will be found.

In this lecture and the next few ones we shall prove the weaker statement that if one-way permutations exist then pseudorandom permutations exist. This will be done in a series of four steps each involving reasonable concrete bounds. A number of combinatorial and number-theoretic problems which are believed to be intractable give us highly plausible candidate one-way permutations. Overall, we can show that if any of those well-defined and well-understood problems are hard, then we can get secure encryption and authentication with schemes that are slow but not entirely impractical. If, for example, solving discrete log with a modulus of the order of {2^{1,000}} is hard, then there is a CCA-secure encryption scheme requiring a {4,000}-bit key and fast enough to carry email, instant messages and probably voice communication. (Though probably too slow to encrypt disk access or video playback.)

Continue reading