 |
Please help improve this article or section by expanding it. Further information might be found on the or at requests for expansion. (January 2007) |
In cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent <math>e</math> (for <math>e \ge 3</math>). More specifically, given a modulus <math>N</math> of unknown factorization, and a ciphertext <math>C</math>, it is infeasible to find any pair <math>(M, e)</math> such that <math>C \equiv M^e~mod~N</math>.
The strong RSA assumption was first used for constructing signature schemes provably secure against existential forgery without resorting to the random oracle model.
References
- Niko Bari´c and Birgit Pfitzmann. Collision-free accumulators and failstop signature schemes without trees. In Advances in Cryptology— EUROCRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 480–494. Springer-Verlag, 1997.
- Eiichiro Fujisaki and Tatsuaki Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In Burton S. Kaliski Jr., editor, Proc. CRYPTO ’97, volume 1294 of LNCS, pages 16–30. Springer-Verlag, 1997.
- Ronald Cramer and Victor Shoup. Signature schemes based on the strong RSA assumption. ACM Transactions on Information and System Security, 3(3):161–185, 2000.
- Ronald L. Rivest and Burt Kaliski. RSA Problem. pdf file
