TL;DR
This paper investigates the relationship between breaking RSA and factoring large numbers in a model where adversaries can perform extensive precomputation. The authors show that even with this powerful preprocessing capability, breaking RSA generically is still fundamentally equivalent to factoring, meaning no superpolynomial gap emerges. This is achieved by introducing a new computational model and developing novel information-theoretic techniques.
What Problem Does This Paper Address?
The security of RSA relies on the difficulty of factoring the large modulus $N = pq$. While it's trivial to break RSA if you can factor $N$, the reverse is not necessarily true in all computational models. Researchers have studied this relationship in idealized models, like the "generic ring model" (GRM), where algorithms treat the ring of integers modulo $N$ as a black box.
A key question arises when considering "preprocessing attacks." In this scenario, an adversary can spend a lot of time before seeing a specific RSA instance to create an "advice" string. This advice string can then be used to solve many RSA instances much faster than without it. Previous work has shown that preprocessing significantly speeds up factoring. This paper asks: does this preprocessing capability fundamentally change the relationship between breaking RSA and factoring? Specifically, does it create a superpolynomial gap where breaking RSA becomes much easier than factoring, even with preprocessing?
Methods
The authors introduce a new model called the "GRM-with-preprocessing" to capture the nuances of preprocessing attacks within the GRM framework. This model allows for representation-specific strategies that go beyond the purely generic computations of the standard GRM.
Their core technical contribution lies in developing new information-theoretic techniques to bridge the gap between RSA adversaries and factoring algorithms in this preprocessing setting. These techniques include:
- Novel Compression Arguments: These are used to efficiently encode information, which is crucial for reducing the space complexity of the factoring algorithm.
- A Variant of Fiat-Naor/Hellman Tables: This construction, adapted for the factoring context, helps to handle specific cases where standard reductions might fail to yield polynomially related parameters.
The paper then shows how to construct a factoring algorithm with polynomially related parameters from a generic RSA algorithm with preprocessing, demonstrating this equivalence in three different models:
- Random Injective Function Model (RIM): This is an intermediate step, showing that RSA with preprocessing implies factoring in this model.
- Random Oracle Model (ROM): They show how to convert the RIM result into the ROM, a more common model for cryptographic analysis.
- Plain Model: This is the ultimate goal, showing the equivalence in the standard, non-idealized model.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Preprocessing Doesn't Break the Equivalence: The most significant insight is that even with unbounded preprocessing, the fundamental equivalence between breaking RSA generically and factoring remains. This means that if you can break RSA efficiently with preprocessing, you can also factor efficiently with preprocessing.
- A More Realistic Preprocessing Model: The "GRM-with-preprocessing" model is a key contribution, capturing how adversaries might use representation-specific tricks (like hash tables) in conjunction with generic computations.
- Information-Theoretic Tools are Key: The paper highlights the power of compression arguments and adapted table-based constructions for proving these equivalences, especially in handling tricky edge cases.
- Bridging Idealized Models: The work demonstrates a clear path from the Random Injective Function Model to the Random Oracle Model and finally to the Plain Model, showcasing how techniques developed for one can be adapted for others.
Key Results
The paper establishes that for generic RSA algorithms with preprocessing, there exists a factoring algorithm with polynomially related parameters. Specifically, they show:
- RIM Result: An RSA adversary in the GRM-with-preprocessing model with space $S_r$ and time $(T_{1,r}, T_{2,r})$ implies a factoring adversary in the RIM with space $S_f = S_r + O(1)$ and time $T_f = \text{poly}(k, T_{1,r}, T_{2,r}, 1/\epsilon_r)$, where $\epsilon_r$ is the RSA adversary's success probability.
- ROM Result: This is converted to the ROM with similar parameter bounds.
- Plain Model Result: The most significant result is the plain model equivalence, showing a factoring algorithm with space $S_f = O(S_r)$ and time $T_f = \text{poly}(k, T_{1,r}, T_{2,r}, 1/\epsilon_r)$.
These results hold for any setting of RSA parameters, reinforcing the fundamental connection.
Limitations and Future Work
- Model Specificity: The results are primarily within the generic ring model and its extensions. It's an open question whether similar equivalences hold in more powerful models or for specific, non-generic RSA attacks.
- Jacobi Symbol Oracle: The authors mention that their results do not directly extend to scenarios where an adversary has access to a Jacobi symbol oracle, which is a decisional problem that is hard in the GRM but easy in the plain model. Extending their work to such settings is suggested as future work.
- Practical Implications: While the theoretical equivalence is shown, the practical efficiency of the derived factoring algorithms (especially the polynomial factors in time complexity) might still be too high for current real-world factoring challenges. Further research could focus on tightening these bounds.
Summary updated