Abstract: One of the most fundamental problems in number-theoretic cryptography is to prove that breaking the RSA system is as hard as the problem of integer factorization. In this talk, I will overview a result by Aggarwal and Maurer (Eurocrypt, 2009) that shows breaking RSA generically is as hard as factoring an integer (namely, the RSA modulus). This result provides evidence towards the soundness of (plain) RSA. An algorithm breaks RSA generically if the algorithm is described in the generic ring model. The generic ring model is a model of computation such that no algorithm can exploit any property of the representation of the elements. I will overview the generic ring model and the reduction in both the special and general cases.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.