Encryption algorithm multiple threads/cores for higher throughput

Question

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.

Answer 1

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.

Answer 2

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.