0
$\begingroup$

Assume you want to calculate the blake2 hash function for an arbitrary input of $n$ bytes. I am wondering about the runtime, in particular:

  1. Does the runtime of scale linearly with the input length, i.e., can the runtime of blake2 be estimated as O(n)?
  2. Is the landau even something that is sensible here, given how optimized cryptographic operations are on modern day processors (say on an intel-i7)
Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

Blake2 takes (in either variant) the input, processes it in fixed-size blocks, padding the last block with zeroes to the full block size if required. The processing operation happens in constant time (it takes a constant number of cycles, big-O notation is meaningless since the input size is fixed). The initialization and finalization steps also take constant time. Therefore, the overall operation takes $O(n)$ time.

Improve this answer
$\endgroup$
0
$\begingroup$

Blake2 and many other popular hash functions exploit parallelism. So while theoretically the time complexity is $O(n)$ but practically you'd see something like this for Blake2b on 2017 Intel Core i7-8700; 6 x 3200MHz; bitvise, supercop-20190910

bytes Cycles/Byes Total Cycles
8 53.8 430
64 6.7 428
576 3.57 2016
1536 3.50 5376
4096 3.18 13025

Source: http://bench.cr.yp.to/results-hash.html

As you can see, for smaller input size, cycles dont scale linearly but for larger sizes it nearly does.

PS: I listed third quartile measurements for cycles/bytes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Big O notation is asymptotic, and doesn't count wall time, it counts the number of operations. Parallelizing an algorithm doesn't decrease its big-O complexity. Sometimes the distinction does get made, but typically using an alternate notation. $\endgroup$
    – SAI Peregrinus
    Jan 28, 2021 at 21:10
  • $\begingroup$ @SAIPeregrinus Thanks for that. Edited to phrase it better. $\endgroup$
    – Jaskaran Veer Singh
    Jan 28, 2021 at 21:18
  • $\begingroup$ Big-O notation is confusing for many people. It's even worse when cryptographers talk about "constant time" to mean "constant cycle count" and not $O(1)$, since something can be "constant time" by the Big-O meaning but still have varying cycle counts. Or can have constant cycle counts per input byte/block (so cryptographic "constant time" but $O(n)$ complexity (asymptotic linear time). Or worse, since "constant cycle count" really depends on the input values and doesn't care about the input length. So you could have a cryptographic constant-time O(2^n) algorithm. $\endgroup$
    – SAI Peregrinus
    Jan 28, 2021 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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