# 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 ${{\mathbb Z}^*_p}$, although it is conjectured to hold in the subgroup of quadratic residues of ${{\mathbb Z}^*_p}$.

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 19 (draft)

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 ${{\mathbb Z}^*_p}$, although it is conjectured to hold in the subgroup of quadratic residues of ${{\mathbb Z}^*_p}$.

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.