In
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 ...
.
See also
*
Quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
*
Decisional composite residuosity assumption The decisional composite residuosity assumption (DCRA) is a mathematical assumption used in cryptography. In particular, the assumption is used in the proof of the Paillier cryptosystem.
Informally, the DCRA states that given a composite n and an ...
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