DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2024.8

Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing

Authors: Dana Dachman-Soled, Julian Loss, and Adam O'Neill

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

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 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.

Cite as

Dana Dachman-Soled, Julian Loss, and Adam O'Neill. Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dachmansoled_et_al:LIPIcs.ITC.2024.8,
  author =	{Dachman-Soled, Dana and Loss, Julian and O'Neill, Adam},
  title =	{{Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{8:1--8:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.8},
  URN =		{urn:nbn:de:0030-drops-205163},
  doi =		{10.4230/LIPIcs.ITC.2024.8},
  annote =	{Keywords: RSA, factoring, generic ring model, preprocessing}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.36

Strong Separations Between Broadcast and Authenticated Channels

Authors: Julian Loss, Ueli Maurer, and Daniel Tschudi

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract

In the theory of distributed systems and cryptography one considers a setting with n parties, (often) connected via authenticated bilateral channels, who want to achieve a certain goal even if some fraction of the parties is dishonest. A classical goal of this type is to construct a broadcast channel. A broadcast channel guarantees that all honest recipients get the same value v (consistency) and, if the sender is honest, that v is the sender's input (validity). Lamport et al. showed that it is possible to construct broadcast if and only if the fraction of cheaters is less than a third. A natural question, first raised by Lamport, is whether there are weaker, still useful primitives achievable from authenticated channels. He proposed weak broadcast, where the validity condition must hold only if all parties are honest, and showed that it can be achieved with an unbounded number of protocol rounds, while broadcast cannot, suggesting that weak broadcast is in a certain sense weaker than broadcast. The purpose of this paper is to deepen the investigation of the separation between broadcast and authenticated channels. This is achieved by proving the following results. First, we prove a stronger impossibility result for 3-party broadcast. Even if two of the parties can broadcast, one can not achieve broadcast for the third party. Second, we prove a strong separation between authenticated channels and broadcast by exhibiting a new primitive, called XOR-cast, which satisfies two conditions: (1) XOR-cast is strongly unachievable (even with small error probability) from authenticated channels (which is not true for weak broadcast), and (2) broadcast is strongly unachievable from XOR-cast (and authenticated channels). This demonstrates that the hierarchy of primitives has a more complex structure than previously known. Third, we prove a strong separation between weak broadcast and broadcast which is not implied by Lamport's results. The proofs of these results requires the generalization of known techniques for impossibility proofs.

Cite as

Julian Loss, Ueli Maurer, and Daniel Tschudi. Strong Separations Between Broadcast and Authenticated Channels. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{loss_et_al:LIPIcs.DISC.2018.36,
  author =	{Loss, Julian and Maurer, Ueli and Tschudi, Daniel},
  title =	{{Strong Separations Between Broadcast and Authenticated Channels}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.36},
  URN =		{urn:nbn:de:0030-drops-98252},
  doi =		{10.4230/LIPIcs.DISC.2018.36},
  annote =	{Keywords: cryptography, multi-party computation, broadcast, impossibility}
}

Search Results

Documents authored by Loss, Julian

Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing

Abstract

Cite as

Strong Separations Between Broadcast and Authenticated Channels

Abstract

Cite as

Thanks for your feedback!

Could not send message