Trapdoor Permutation Polynomials of Z/nZ and Public Key Cryptosystems

In this talk, we will define new algorithmic problems, derived from the RSA assumption, and discuss their properties (in particular, we will present a careful study of their computational complexity). We will apply the new problems to design public key encryption protocols with semantic security relative to their decisional variants. We will then show how to provide efficient schemes that are semantically secure under adaptive chosen ciphertext attacks in the random oracle model. Finally, we will present the most efficient scheme semantically secure under non-adaptive chosen ciphertext attacks in the standard security model.

(joint work with Guilhem Castagnos)