# What is the time complexity of computing a cryptographic hash function/random oracle?

I'm wondering what's the computational complexity of computing a hash function/random oracle when doing complexity analysis. For example, what's the computational complexity of computing $$H(b\|r)$$? where $$b$$ is a bit and $$r$$ is a random string of length of security parameter $$\lambda$$. If $$b$$ is a string (i.e., a string message), what's the computational complexity? In my opinion, we can just take it as taking $$poly(\lambda)$$ time, but can we take it as computing in constant time? say, $$O(1)$$?

• With relatively insignificant overhead for anything above kilobyte sized for most hash algorithms, the complexity is close to linear with full input length. O(N) with N being bits. In many cases, this is insignificant compared to other elements of a larger algorithm involving hashes, and might therefore not even be counted in the complexity analysis. Also, when input sizes are fixed you may simply assume a constant value (essentially rounding to O(1)). – Natanael Feb 20 '19 at 1:59
• @Natanael That's a nice answer deserving a better place than a comment. – DannyNiu Feb 20 '19 at 2:29
• Natanael's nice answer/comment applies for practical fixed-width fixed-security hashes like SHA-512. The width $h$ of the hash output (which can be variable, e.g. in some modes of SHA-3) and the desired security level $\lambda$ in bits (so that finding a collision has cost $O(2^\lambda)$, with $h\ge2\lambda$ ) also have an influence on the cost. Perhaps, $\mathcal O((N+h)\,\lambda^k)$ for some $k$ with $1<k\le2$? – fgrieu Feb 20 '19 at 6:57
• @fgrieu i posted it as an answer. I also referenced your comment on variable output. Feel free to suggest edits for better formatting – Natanael Feb 20 '19 at 11:15
• @DannyNiu it's been posted as a answer now – Natanael Feb 20 '19 at 14:35

Most hash functions are designed with an initialization stage (with a fixed performance overhead), a compression function and state update function that process the input in blocks (with a fixed per-block performance overhead), and a finalization stage (with a fixed performance overhead).

Typically that means you can consider initialization and finalization as a single constant when evaluating computational complexity of a hash function, and the per-block compression and state update can likewise be considered as a single constant.

You could approximate this as $$\mathcal{O}(c+xn)$$, where $$n$$ is the number of blocks required to fit the input (accounting for padding), $$x$$ is the constant for per-block overhead, and $$c$$ is the constant for initialization and finalization.

For longer messages of arbitrary length, it would typically be simplified as just $$\mathcal{O}(n)$$ where $$n$$ is the length.

In many cases, this complexity is insignificant compared to other elements of a larger algorithm involving hashes, and might therefore not even be counted in the complexity analysis.

Also, when input sizes are fixed you may simply assume a constant value, which essentially means rounding to $$\mathcal{O}(1)$$.

In the case of variable width outputs (technically not a hash, but still the same family of symmetric functions) like SHA3 SHAKE256, a XOF (extensible output function), the computational complexity is approximately equivalent to combining a hash with a stream cipher. In this case, you have $$n_1$$ for the input size and $$n_2$$ for the output size, and the complexity would approximately be $$\mathcal{O}(c+x n_1+y n_2)$$ where $$x$$ is the overhead per input block and $$y$$ is the overhead for the bit stream output per output block. This may be simplified as $$\mathcal{O}(n_1+n_2)$$.

Again, when both sizes are fixed (such as if you use the XOF for a fixed purpose in a protocol, like hashing a key to produce a bitmask for a digital signature function, like in some RSA implementations), it can be approximated as $$\mathcal{O}(1)$$.

• @kelalaka and I have no idea how to use it. Feel free do suggest edits – Natanael Feb 20 '19 at 11:55
• @kelalaka edited now. Anything else to fix? – Natanael Feb 20 '19 at 12:13