On the Regularity of Lossy RSA

We provide new bounds on how close to regular the map

x

↦

x

e

is on arithmetic progressions in ℤ

N

, assuming

e

|Φ(

N

) and

N

is composite. We use these bounds to analyze the security of natural cryptographic problems related to RSA, based on the well-studied Φ-Hiding assumption. For example, under this assumption, we show that RSA PKCS #1 v1.5 is secure against chosen-plaintext attacks for messages of length roughly

$\frac{\log N}{4}$

bits, whereas the previous analysis, due to [19], applies only to messages of length less than

$\frac{\log N}{32}$

.

In addition to providing new bounds, we also show that a key lemma of [19] is incorrect. We prove a weaker version of the claim which is nonetheless sufficient for most, though not all, of their applications.

Our technical results can be viewed as showing that exponentiation in ℤ

N

is a deterministic extractor for every source that is uniform on an arithmetic progression. Previous work showed this type of statement only on average over a large class of sources, or for much longer progressions (that is, sources with much more entropy).