1
$\begingroup$

Pretty much every cipher or hash I've seen has multiple rounds the are designed to be run serially one after the other. Has anyone ever designed a fully parallel cipher or hash? This would be one where all rounds are executed in parallel and then the results are combined in some way such as addition or XOR.

It's mostly a theoretical question. It just occurred to me that I've never seen nor heard of such a thing.

It would be interesting from a performance perspective since you could use wide SIMD instructions to compute many rounds at once. It would also be easier to implement in hardware to run in one clock cycle.

Improve this question
$\endgroup$
8
  • $\begingroup$ Related is this question. Notice asker. Generally instead hash trees are used (although they have the downside that the data hashed by the leafs is configured for a specific block size, so they cannot be easily configured for a certain CPU / buffer / IO speed). $\endgroup$
    – Maarten Bodewes ♦
    Dec 1, 2020 at 19:17
  • $\begingroup$ ParallelHash256 of SHA3 is not enough for you? $\endgroup$
    – kelalaka
    Dec 1, 2020 at 19:29
  • $\begingroup$ @kelalaka Cannot find much info on ParallelHash, I presume it also uses tree hashing? I see the reduced round versions do anyway. $\endgroup$
    – Maarten Bodewes ♦
    Dec 1, 2020 at 21:42
  • $\begingroup$ @MaartenBodewes No, not a tree. ParallelHash of the SHA3 see page 14 on NIST SP 800-185 , I was going to write an answer, however, Adam, requires parallel within rounds. ParallelHash is paralleled by; Each part hashed by cSHAKE256 and then combined with a single call of cSHAKE256. Blake3 is based on tree. $\endgroup$
    – kelalaka
    Dec 1, 2020 at 21:47
  • 3
    $\begingroup$ I think that this question has a bit of a problem, as a round implies a sequential action by definition, at least if you ask me. If that's not necessarily the case then please let us know or write an answer. $\endgroup$
    – Maarten Bodewes ♦
    Dec 1, 2020 at 22:15

1 Answer 1

Reset to default
2
$\begingroup$

Rounds in block ciphers, and in the inner compression or sponge function of a hash, are run sequentially for a security reason: it increases diffusion, which is necessary for security. Examples include the 10, 12 or 14 rounds of AES-128, -192 or -256; and the 64 or 80 rounds of SHA-2. We just do not know how to make a secure cryptographic primitive operating on a moderate-sized block that's secure, deeply parallel, and not very much more costly than what we use today.

Parallelism can and is used at a higher level. One of the virtues of CTR is that parallel implementations compatible with sequential implementations is easy. That applies to AES (in multi threaded implementations or parallel hardware), ChaCha, Gimli (which are amenable to SIMD implementation). Modern hashes often have a provision for parallel implementation using Merkle hash trees (often, just two-levels; e.g. ParallelHash of NIST SP 800-185), but that's at the cost of increasing complexity of non-parallel implementations, which I think is part of why it so far did not catch up in daily practice.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Rounds are serial, but datum operations can be parallel. e.g. SIMD implementation of Gimli, ChaCha. $\endgroup$
    – DannyNiu
    Dec 2, 2020 at 10:10
  • 1
    $\begingroup$ Sounds like an interesting research topic: is there a way to achieve diffusion of the sort we get from serial rounds through a parallel set of operations and a final combining step? $\endgroup$
    – Adam Ierymenko
    Dec 4, 2020 at 15:30

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.