On the Regularity of Lossy RSA: Improved Bounds and Applications to Padding-Based Encryption

Adam Smith; Ye Zhang

Paper 2015/027

On the Regularity of Lossy RSA: Improved Bounds and Applications to Padding-Based Encryption

Adam Smith and Ye Zhang

Abstract

We provide new bounds on how close to regular the map x |--> x^e is on arithmetic progressions in Z_N, assuming e | Phi(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 Phi-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 (log N)/4 bits, whereas the previous analysis, due to Lewko et al (2013), applies only to messages of length less than (log N)/32. In addition to providing new bounds, we also show that a key lemma of Lewko et al. 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 Z_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).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in TCC 2015
Keywords: PKCS Phi-Hiding Regularity
Contact author(s): yxz169 @ cse psu edu
History: 2015-01-14: received
Short URL: https://ia.cr/2015/027
License: CC BY

BibTeX

@misc{cryptoeprint:2015/027,
      author = {Adam Smith and Ye Zhang},
      title = {On the Regularity of Lossy RSA: Improved Bounds and Applications to Padding-Based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/027},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/027}},
      url = {https://eprint.iacr.org/2015/027}
}