RSA-FDH and random oracle query count

Question

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.

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.