Editing Strong RSA assumption

In [[cryptography]],  the '''strong [[RSA (algorithm)|RSA]] assumption''' states that the [[RSA problem]] is intractable even when the solver is allowed to choose the public exponent ''e'' (for ''e''&nbsp;≥&nbsp;3).  More specifically, given a modulus ''N'' of unknown factorization, and a ciphertext ''C'', it is infeasible to find any pair (''M'',&nbsp;''e'') such that&nbsp;''C''&nbsp;≡&nbsp;''M''<sup>&nbsp;''e''</sup>&nbsp;mod&nbsp;''N''.

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

== See also ==
* [[Quadratic residuosity problem]]
* [[Decisional composite residuosity assumption]]

==References==
* Barić N., Pfitzmann B. (1997) Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees. In: Fumy W. (eds) Advances in Cryptology – EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg. {{doi|10.1007/3-540-69053-0_33}}
* Fujisaki E., Okamoto T. (1997) Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski B.S. (eds) Advances in Cryptology – CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. {{doi|10.1007/BFb0052225}}
* [[Ronald Cramer]] and [[Victor Shoup]]. 1999. Signature schemes based on the strong RSA assumption. In ''Proceedings of the 6th ACM conference on Computer and communications security'' (''CCS ’99''). Association for Computing Machinery, New York, NY, USA, 46–51. {{doi|10.1145/319709.319716}}
* [[Ronald L. Rivest]] and [[Burt Kaliski]]. 2003. ''RSA Problem''. [http://theory.lcs.mit.edu/~rivest/RivestKaliski-RSAProblem.pdf pdf file]

{{Cryptography navbox | public-key}}
{{Computational hardness assumptions}}

[[Category:Computational hardness assumptions]]


{{crypto-stub}}