Regularity of Lossy Exponentiation and Applications

Speaker: Adam Smith , Penn State

Date: Friday, April 04, 2014

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-449

Event Type:

Room Description:

Host: Vinod Vaikuntanathan, CIS, TOC, CSAIL, MIT

Contact: Holly A Jones,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Regularity of Lossy Exponentiation and Applications

We study of how ``lossiness'' of the RSA trapdoor permutation under the $\Phi$-Hiding Assumption can be used to understand the security of classical RSA-based cryptographic systems. Under Phi-hiding, several questions or conjectures about the security of such systems can be reduced to bounds on the regularity (the distribution of the primitive e-th roots of unity mod N) of the ``lossy'' RSA map (the mape x -> x^e where e divides phi(N)).

Specifically, this is the case for: (i) showing that large consecutive runs of the RSA input bits are simultaneously hardcore, (ii) showing the widely-deployed PKCS #1 v1.5 encryption is semantically secure, (iii) improving the security bounds of Kiltz et al. (2010) for RSA-OAEP.

We prove several results on the regularity of the lossy RSA map using both classical techniques and recent estimates on Gauss sums over finite subgroups, thereby obtaining new results in the above applications. Our results deepen the connection between ``combinatorial'' properties of exponentiation in Z_N and the security of RSA-based constructions.

This is based on joint work with Adam O'Neill and Mark Lewko and Ye Zhang. Some of these results appeared at Eurocrypt 2013.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security Seminar Seminars Fall 2013 / Spring 2014.

Created by Holly A Jones Email at Tuesday, April 01, 2014 at 2:07 PM.