I am now reading a paper 'The Exact Security of Digital Signatures - How to Sign with RSA and Rabin' and there is an equation e = (q_sig + q_hash) * e' on page 401. (e : success probability of RSA, e' : success probability of RSA-FDH)

What I want to know is the relation between query count(q_sig, q_hash) and security parameter k. Is query count is proportional to poly(k) or 2^k?

In case of RSA, k is the bit length of modulus. So I feel like it should be proportional to 2^k. And if it is proportional to 2^k, how is e is guaranteed to be negligible in case e' is be negligible?

Thanks in advance.


1 Answer 1


It is proportional to $poly(k)$. Here $k$ is the security parameter (or more strictly speaking it should be $(1^k)$) and intuitively the adversary's can only be allowed to query polynomial times (since it is a PPT algorithm) bounded in terms of $k$. Then $e$ and $e'$ only differs by a polynomial factor, and thus allows you to reduce what you want to prove to the RSA problem.

The subtle technicality is that when modeling the adversary as a Turing machine and reasoning complexity (which is based on the size of input), the integer $k$'s length is only $log_2 k$, which will cause some formality problem. The more rigorous way is to supply $1^k$, a bit string of length $k$ that contains all 1s.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.