Faculty Recruiting Support CICS

Theory Seminar: Breaking RSA Generically is Equivalent to Factoring

05 Oct
Tuesday, 10/05/2021 4:00pm to 5:00pm
Computer Science Building, Room 140
Theory Seminar
Speaker: Nikki Sigurdson (UMass-Amherst)

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.