There are situations where a single connection (or file) may require additional throughput available. While network bandwidth and CPU cores are available, they cannot be utilised. (Aside from means that are external to the algorithm as is)

Some examples:

  • VPN - when encryption is done only on the tunnel connection that internally encapsulates packets of multiple flows.

Typically, it is thought that an encryption algorithm itself is a sequential process, that relies on the previous block or bit(s) in order to accomplish effective cipher strength. This means the algorithms cannot be multi-threaded.

Is this true of all encryption? Does this apply equally to modern common algorithms (block and stream)?

Is there a way to purpose-make an encryption algorithm that works on multiple threads (cores)? Are there any existing algorithms (perhaps not common or academic only) that would work across multiples cores?

Usually, this isn't a problem, because machines may make use of multiple connections (HTTPS), but it means a single connection is limited by the cipher transform speed of a single CPU core. Also, when multiplexing is used (like VPN), this might be a particularly limiting issue.

  • $\begingroup$ In theory, sub-streams can be used, each seeded from the parent key/state. OR, more directly for a block cipher, this can be done neatly, with a larger block size 16Bx8cores that is split between the cores (each with a different sequence number) transformed, then combined in order, with framing (effectively muxing). $\endgroup$ Mar 25 at 15:02
  • $\begingroup$ Perhaps with a streaming cipher, I believe the pseudo-key and transform are usually easy to separate. So a single pseudo-key is generated by 6 cores by diverging from 6 starting points, and then muxing to form the single key. Then 1 core to apply the key (and more cores possible by also using muxing). $\endgroup$ Mar 25 at 15:05
  • 1
    $\begingroup$ have you ever heard the CTR mode. $\endgroup$
    – kelalaka
    Mar 25 at 15:05
  • $\begingroup$ @kelalaka I am aware of a range of modes, but not deeply. When I say "modern" I expect something like AES-GCM or ChaCha20 with all the trimmings for message integrity. Anything less, and I'm improving bandwidth at the expense of security. (As far as I understand) $\endgroup$ Mar 25 at 16:27

Typically, it is thought that an encryption algorithm is a sequential process, that relies on the previous block or bit(s) in order to accomplish effective cipher strength. This means the algorithms cannot be multi-threaded.

This is only true for "heavy-handed" operations like CBC-MAC (and its variants), HMAC and CBC. For most of modern cryptography as implemented, parallelizability is both a feature an a necessity for high performance implementations.

Before jumping to the schemes that are relevant to you in this context, let me clarify why parallelism is actually a necessity. You might have heard of the AES-NI. These are instructions that perform one AES round per instruction. However, the instructions don't have a latency of 1 CPU cycle but of 3-7 CPU cycles even though they have a throughput of at least 1 instruction per cycle. Latency in this context means that if instruction B depends on the result of instruction A, B must wait for the full latency of A. So, what you need to do to optimally use your hardware is to have 8 data-independent AES operations be run in parallel which is quite tricky with request-level parallelism. So instead what schemes do, is they use a parallelizable scheme and don't compute one block of AES data at a time, but rather 8 or however many is optimal for the implementation.

But how can this be done, you surely ask yourself:

  1. If you want CPA-secure encryption, CTR-mode transforms a block cipher into a stream cipher by encrypting a counter.
  2. If you want a nonce-based MAC, GMAC can be parallelized - which is commonly exploited to reduce the number of reductions to compute.
  3. If you want a full-blown parallel PRF, PMAC is the way to go, though it is not seen as often in practice due to the prominence of HMAC or single-block AES where needed.
  4. If you want a parallel hash algorithm, you can use tree-hashing.
  5. If you want authenticated encryption, AES-GCM can be parallelized - as it is essentially composed of GMAC and CTR.
  6. If you want nonce-misuse-resistant authenticated encryption, the generic SIV transform and AES-GCM-SIV both require two passes but each pass can be parallelized - at least for the encryption, the decryption is natively parallel.

In the public key setting there are additionally rather easy examples of highly parallelizable encryption schemes. Namely, learning with errors (LWE) based encryption schemes [1] generally boil down to encrypting via computing a number of matrix operations (multiplications/additions), which are highly parallelizable. LWE based cryptography is currently one of the leading candidates for post-quantum cryptography, and will likely see broader usage in practice over the next few years (assuming nothing catastrophic happens to it).

Even in the private-key setting this can lead to parallelizable constructions that are still rather efficient. One of the best-known examples is the SWIFT hash function, which only had mildly (~15%, I mean mildly as SWIFT is based on a "public key" hardness assumption) slower throughput than SHA256. A modified version of it was submitted to the SHA3 competition, but did not make it past the first round (I do not know the history of this time period to know why this happened, perhaps it was for performance reasons --- I would be interested if someone more knowledgeable could comment).

[1] I think this is also true for code-based cryptography, but I am less familiar with this area.

  • $\begingroup$ Thanks Mark this is a good perspective I didn't think of - Asymmetric Cryptography. However, I will update the title of my question to focus more clearly on the goal - "higher bandwidth" primarily, but also "efficiency" secondarily. $\endgroup$ Mar 26 at 3:22

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.