CS276 Lecture 19: Trapdoor Permutations

Scribed by Cynthia Sturton

Summary

Today we continue to discuss number-theoretic constructions of CPA-secure encryption schemes.

First, we return to the Decision Diffie Hellman assumption (the one under which we proved the security of the El Gamal encryption scheme) and we show that it fails for , although it is conjectured to hold in the subgroup of quadratic residues of .

Then we introduce the notion of trapdoor permutation and show how to construct CPA-secure public-key encryption from any family of trapdoor permutations. Since RSA is conjectured to provide a family of trapdoor permutations, this gives a way to achieve CPA-secure encryption from RSA.

CS276 Lecture 23 (draft)

Summary

Today we show how to construct an efficient CCA-secure public-key encryption scheme in the random oracle model using RSA.

As we discussed in the previous lecture, a cryptographic scheme defined in the random oracle model is allowed to use a random function which is known to all the parties. In an implementation, usually a cryptographic hash function replaces the random oracle. In general, the fact that a scheme is proved secure in the random oracle model does not imply that it is secure when the random oracle is replaced by a hash function; the proof of security in the random oracle model gives, however, at least some heuristic confidence in the soundness of the design.

CS276 Lecture 17: El Gamal

Scribed by Matt Finifter

Summary

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.

CS276 Lecture 17 (draft)

Summary

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.