Tomorrow, we will be discussing Practical Chosen Ciphertext Secure Encryption from Factoring. I feel like I can guide us through the main proof of this paper, but it would be helpful to review a couple of the following preliminaries. By the way, I will probably be skimming some of the gross math (ex. the correctness of the {\textnormal{\textsf{KEM}}}), but I will still be talking about it a high level.

  1. Quadratic residues are essential to this paper. A number {q} is called a quadratic residue if there exists an {x} such that {x^2 \equiv q \pmod n}. If we know {x}, it is easy to find {q}, but it is hard in general to find the {x}. There are all sorts of really deep mathematics having to do with quadratic residues (and quadratic reciprocity), but the most important for our discussion will be that we can use the Chinese remainder theorem to calculate {x} given the factorization of a composite {n}. I’m not sure if I will touch upon the Chinese remainder theorem or not.
  2. This paper is about a public key cryptoscheme that is CCA secure. The authors of this paper provide their own definition of CCA-security for the key encapsulation method (pp 5, def 2). Does it seem reasonable to use this definition for CCA-security?
  3. Take a look at the key encapsulation method and try to figure out how it works. Also, try and figure out how the {\textnormal{\textsf{BBS}}} random generator (section 3.1) works. I’ll go over these, but it will helpful to have seen them.