Strong RSA assumption

From Wikipedia, the free encyclopedia

Please help improve this article or section by expanding it.
Further information might be found on the talk page or at requests for expansion.
This article has been tagged since 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 $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 and Birgit Pfitzmann, Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees, EUROCRYPT 1997, pp480–494.
Ronald L. Rivest and Burt Kaliski. RSA Problem. pdf file