2026-07-23T08:19:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20516 2024-08-06T05:20:07Z ddc:004 open_access

Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing Dachman-Soled, Dana Loss, Julian O'Neill, Adam RSA factoring generic ring model preprocessing 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 ASIACRYPT '13]) has shown that preprocessing attacks significantly improve 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 runtime of the best attack on RSA with preprocessing and on factoring with preprocessing. Our main result rules this out with respect to algorithms that perform generic computation on the RSA instance x^e od N yet arbitrary computation on the modulus N, namely a careful adaptation of the well-known generic ring model of 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. Our main technical contribution is a set of new information-theoretic techniques that allow us to handle or eliminate cases in which the Aggarwal and Maurer result does not yield a factoring algorithm in the standard model with parameters that are polynomially related to those of the RSA algorithm. These techniques include two novel compression arguments, and a variant of the Fiat-Naor/Hellman tables construction that is tailored to the factoring setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dana Dachman-Soled and Julian Loss and Adam O'Neill 2024 Is Part Of LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2024.8 urn:nbn:de:0030-drops-205163 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode