cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, the strong RSA assumption states that the

RSA problem In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a ''message'' to an '' exponent'', modulo a composite number ''N'' whose factors are not known. T ...

is intractable even when the solver is allowed to choose the public exponent ''e'' (for ''e'' ≥ 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'' ≡ ''M''^''e'' mod ''N''. The strong RSA assumption was first used for constructing

signature A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...

schemes

provably secure Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields. Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...

against

existential forgery In a cryptographic digital signature or MAC system, digital signature forgery is the ability to create a pair consisting of a message, m, and a signature (or MAC), \sigma, that is valid for m, but has not been created in the past by the legitimat ...

without resorting to the

random oracle model In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time t ...

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. * 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. *

Ronald Cramer Ronald John Fitzgerald Cramer (born 3 February 1968 in Haarlem) is a professor at the Centrum Wiskunde & Informatica (CWI) in Amsterdam and the University of Leiden. He obtained his PhD from the University of Amsterdam in 1997. Prior to returning t ...

and

Victor Shoup Victor Shoup is a computer scientist and mathematician. He obtained a PhD in computer science from the University of Wisconsin–Madison in 1989, and he did his undergraduate work at the University of Wisconsin-Eau Claire. He is a professor at ...

. 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. *

Ronald L. Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...

and Burt Kaliski. 2003. ''RSA Problem''
pdf file
Computational hardness assumptions {{crypto-stub

See also

References