Comparison of Hashing and Modular Exponentiation

Question

Suppose we want to compare two protocols on the computational costs. One of the protocols is designed using random oracle model (we call it the first protocol) and the other protocol uses is designed over common reference string (we call it the second protocol).

Now if we want to compare these two, we have to rely on the most costly operation in them. In the first protocol it is the hashing operation and in the second, the modular exponentiation. How can I compare these two protocols assuming both of them work over the same length of security parameter.

For simplicity, assume that the first protocol uses "n" hashing operation to complete and the second protocol uses "2n" modular exponentiation to output the result.

Is there any way to compare these two? What measures should I consider when comparing these protocols?

To give a little background on the models, the Common Reference String (CRS) is the model which a global coin is assumed, which means a reference string (mostly a random one) is distributed among the parties. The random oracle model is the model which is essentially formalizing the hash functions. In this model, every party has oracle access to a random function (i.e., they submit the query to a function (oracle) some where and get the results, which in this case is a random string). When implementing a protocol with this model, the queries are replaced by calculating a hash function.

Answer 1

Hashing is much cheaper than modular exponentiation, so much so that it is often taken as "free" in efficiency analysis that uses modular arithmetic. My suggestion would be to do a rough comparison, like you said: protocol 1 uses m hashes, protocol 2 uses n exponentiations.

If n>m, protocol 1 is much faster. If m>a*n, I wouldn't start investigating further until a gets to be around 10^2 or 10^3. It seems unlikely that protocol 1 would use this many, unless if it is using a hash tree or similar data structure requiring lots of hashes.

There is no quick rule because the speed of an exponentiation at this level of scrutiny is dependent on the underlying group. Elliptic curves will be much faster than the integers mod p, and elliptic curve speed will depend on the type of curve.

Similarly, the speed of the hash function depends on how long the input message is. Does it fit into a single block, or does the hash need to iterate over it?

As one ballpark figure, a 100MHz FPGA can do about 100 ModExps (1024 bit with 160 bit subgroup) in one second, while it can hash about 5000 message blocks (SHA256) in a second.