[DLO24] Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing

Authors: Dana Dachman-Soled, Julian Loss, Adam O’Neill | Venue: ITC 2024 | Source

Abstract

We show that in the generic ring model, breaking RSA — i.e., computing $e$-th roots modulo $n$ — is equivalent to factoring $n$, even when the adversary is allowed arbitrary preprocessing. Concretely, we consider adversaries that run in two phases: an unbounded preprocessing phase that produces an advice string, followed by an efficient online phase that uses the advice to break RSA. We prove that any such adversary can be converted into a factoring adversary with polynomially related online complexity and only a polynomial loss in the advice length. This rules out a superpolynomial separation between RSA and factoring in the generic ring model with preprocessing, strengthening prior results that held only for preprocessing-free adversaries.

BibTeX

Copy

@Inproceedings{ITC:DacLosONe24,
  author = {Dana {Dachman-Soled} and Julian Loss and Adam O'Neill},
  title = {Breaking {RSA} Generically Is Equivalent to Factoring, with Preprocessing},
  pages = {8:1--8:24},
  editor = {Divesh Aggarwal},
  booktitle = {ITC 2024: 5th Conference on Information-Theoretic Cryptography},
  volume = {304},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  address = {Stanford, CA, USA},
  month = {aug~14--16},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year = {2024},
  doi = {10.4230/LIPIcs.ITC.2024.8},
}