I believe that parallelizable authentication schemes are superior from an aesthetic perspective and because most non-recursive calculations (e.g., CTR, ECB, PMAC, etc.) are better than recursive ones (e.g., CBC, OFB, CFB, CBC-MAC, etc.).

Most of the CAESAR candidates, i.e. GCM, OCB mode, PMAC, XOR-MACs, and protected counter sum provide parallelizable authentication while HMAC is not parallelizable.

One paper out there says that many schemes used by the CAESAR candidates, GCM, and XOR-MACs can be trivially broken by an incredibly unrealistic quantum attack (it turns the complexity from $O(2^{n})$ to $O(n)$ but requires a quantum entangled state that can only be generated with the key). Additionally, with or without quantum computers, many of these parallelizable authentication schemes only provide security up the birthday bound. This makes it seem like a lot of the known parallelizable modes of authentication are not as strong as an HMAC construction.

Am I mistaken? Is there anything about most particular parallelizable methods that have drawbacks/weaknesses relative to HMACs? If so, what are they? And why do we seek parallelizable methods if that is the case?


1 Answer 1


If you have a vector unit on your CPU that can be used only by a single thread at a time but remains powered whether you're using it or not, it takes less time, and is therefore cheaper, to compute a parallelizable function using the entire vector unit than to compute nonparallelizable function using only a part of the vector unit.

If you have only three cycles per byte to spare in your computing budget, there is no way you will fit HMAC-SHA256 in that. But you can easily fit Poly1305. The more parallelizable the function, the more flexibility you have to adapt it to vector units of different sizes to maximize throughput subject to your power constraints.

The alleged quantum threat to these constructions posits the asinine model where the legitimate user reveals quantum superpositions of secret function evaluations to the adversary. If you do your cryptography on a classical computer on ordinary bits, then the model is irrelevant. If, under the currently unrealistic premise that quantum computers were actually capable of it, you did your cryptography on a quantum computer and enabled this attack model, you would be an idiot. This model gives amusing theoretical results, but it is totally irrelevant to the real world.

  • $\begingroup$ This model does show that it is impossible to create a quantum-safe white-box implementation of GCM. Other than that, I agree that it is irrelevant to the real world... $\endgroup$
    – poncho
    Jun 8, 2018 at 17:35
  • $\begingroup$ Indeed. It remains unclear, of course, whether it's even possible to create a classical-safe white-box implementation of AES-GCM! $\endgroup$ Jun 8, 2018 at 17:38
  • $\begingroup$ Or if it's possible to make a whitebox implementation of anything symmetric; attempts at whitebox AES tended to be unexpected easy to break. However, it might be possible in most cases, in the postquantum GCM case, we know that's not the case... $\endgroup$
    – poncho
    Jun 8, 2018 at 17:53
  • $\begingroup$ So this attack model is similar to giving an adversary DSA signatures that use the same per-message value? $\endgroup$
    – Melab
    Jun 21, 2018 at 18:13
  • $\begingroup$ @Melab More like a quantum superposition of DSA signatures on an attacker-specified quantum superposition of messages, under a single per-signature secret. A classical set is not the same as a quantum superposition, but a quantum superposition is definitely a lot more information than a single value. $\endgroup$ Jul 10, 2018 at 2:17

Your Answer

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

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