Paper 2022/1261

Breaking RSA Generically is Equivalent to Factoring, with Preprocessing

Dana Dachman-Soled, University of Maryland
Julian Loss, CISPA Helmholtz Center for Information Security
Adam O'Neill, University of Massachusetts Amherst
Abstract

We investigate the relationship between the classical RSA and factoring problems when preprocessing is considered. In such a model, adversaries can use an unbounded amount of precomputation to produce an “advice” string to then use during the online phase, when a problem instance becomes known. Previous work (e.g., [Bernstein, Lange ASI- ACRYPT ’13]) has shown that preprocessing attacks significantly im- prove the runtime of the best-known factoring algorithms. Due to these improvements, we ask whether the relationship between factoring and RSA fundamentally changes when preprocessing is allowed. Specifically, we investigate whether there is a superpolynomial gap between the run- time of the best attack on RSA with preprocessing and on factoring with preprocessing. Our main result rules this out with respect to algorithms in a careful adaptation of the generic ring model [Aggarwal and Maurer, Eurocrypt 2009] to the preprocessing setting. In particular, in this setting we show the existence of a factoring algorithm with polynomially related parameters, for any setting of RSA parameters.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
generic ring modelpreprocessingRSAfactoring
Contact author(s)
danadach @ umd edu
loss @ cispa de
amoneill @ gmail com
History
2023-03-05: last of 3 revisions
2022-09-23: received
See all versions
Short URL
https://ia.cr/2022/1261
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1261,
      author = {Dana Dachman-Soled and Julian Loss and Adam O'Neill},
      title = {Breaking RSA Generically is Equivalent to Factoring, with Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1261},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1261}},
      url = {https://eprint.iacr.org/2022/1261}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.