Strong RSA assumption

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 ≥ 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 schemes provably secure against existential forgery without resorting to the random oracle model.