Please, I got the question "what is the computational complexity of SHA-3 (SHAKE128)"?

What does that mean and how can I calculate that??

*I am using SHA-3 (SHAKE128) in my mechanism to hash fix input (100-bits).

Thanks in advance...

  • $\begingroup$ What is the source of that sentence? $\endgroup$ – kelalaka Dec 10 '18 at 8:20
  • $\begingroup$ I am a degree student and I proposed a mechanism using SHA-3 (SHAKE128) to hash 100-bits. When I submit my paper to a journal I got this question: "So what is the computational complexity proposed methodology using SHAKE128?" $\endgroup$ – Al-Ani Dec 10 '18 at 8:22
  • $\begingroup$ I think the answer requires your mechanism, too. $\endgroup$ – kelalaka Dec 10 '18 at 8:36
  • 1
    $\begingroup$ Since SHAKE128 allows an arbitrary output length, this obviously cannot be answered without knowing the output size. $\endgroup$ – gammatester Dec 10 '18 at 8:43
  • 1
    $\begingroup$ SHA3 and SHAKE128 are related but not the same. $\endgroup$ – WDS Dec 10 '18 at 8:45

Strictly speaking, computational complexity is certainly not the right term. It is an asymptotic notion, describing the approximate behaviour of the cost for "large enough" inputs. SHAKE is an "extensible output function" (XOF) and its computational complexity is $O(m + n)$ where $m$ is the size of the input, and $n$ the size of the output. I.e., it's "linear". However, this does not apply to your case, where the input size is fixed (100 bits) and I suspect that your output size is also fixed. The "complexity" is when the input size "tends towards infinity", and 100 will never go toward infinity; it's fixed.

Therefore, we have to assume that reviewer of that journal uses the expression "computational complexity" in a loose, technically incorrect sense, to express the notion of "cost". In simple words: if somebody implemented your proposed protocol on some specific hardware (e.g. a PC), and ran it, to what extent would your specific choice of SHAKE would impact overall performance metrics of the system?

To take an example: consider SSL/TLS. That protocol starts with a complicated process call the "handshake", through which a client and server agree on a common shared secret, used thereafter to encrypt data. The bulk of the cost is in the data encryption, which does not use a hash function (if a proper ciphersuite was negotiated). Hash functions are involved in the handshake, but in conjunction with asymmetric cryptographic stuff which is, in practice, a lot more expensive. In the TLS protocol, you can therefore say that the choice of the hash function in the handshake has negligible impact on the performance metrics of bandwidth, CPU usage and latency, as long as you do not use a stupidly slow hash function. On the other hand, for embedded system with strong constraints on, for instance, ROM size, the choice of hash function matters because if you already have an implementation of a hash function somewhere in the system software, then reusing that implementation yields smaller code than including a new one.

My bet is that the reviewer wants something similar to the above analysis.(*)

(*) It's a lie. My real bet is that the reviewer is an unpaid student who did not know what to write in his review, and has only little idea what he is talking about.


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.