0
$\begingroup$

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)$?

$\endgroup$
  • 3
    $\begingroup$ 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)). $\endgroup$ – Natanael Feb 20 at 1:59
  • 1
    $\begingroup$ @Natanael That's a nice answer deserving a better place than a comment. $\endgroup$ – DannyNiu Feb 20 at 2:29
  • 2
    $\begingroup$ 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$? $\endgroup$ – fgrieu Feb 20 at 6:57
  • $\begingroup$ @fgrieu i posted it as an answer. I also referenced your comment on variable output. Feel free to suggest edits for better formatting $\endgroup$ – Natanael Feb 20 at 11:15
  • $\begingroup$ @DannyNiu it's been posted as a answer now $\endgroup$ – Natanael Feb 20 at 14:35
2
$\begingroup$

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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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