Strong RSA assumption

From Wikipedia, the free encyclopedia

In cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent $e$ (for $e \ge 3$ ). More specifically, given a modulus $N$ of unknown factorization, and a ciphertext $C$ , it is infeasible to find any pair $(M, e)$ such that $C \equiv M^e~mod~N$ .

The strong RSA assumption was first used for constructing signature schemes provably secure against existential forgery without resorting to the random oracle model.

[edit] 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