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)$?
$\begingroup$
$\endgroup$
5
-
5$\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$– NatanaelCommented Feb 20, 2019 at 1:59
-
1$\begingroup$ @Natanael That's a nice answer deserving a better place than a comment. $\endgroup$– DannyNiuCommented Feb 20, 2019 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 ♦Commented Feb 20, 2019 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$– NatanaelCommented Feb 20, 2019 at 11:15
-
$\begingroup$ @DannyNiu it's been posted as a answer now $\endgroup$– NatanaelCommented Feb 20, 2019 at 14:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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)$.
