What does (block cipher) decryption parallelizable mean?

Question

I've tried searching this answer on here and on google, but I cant seem to find a succinct answer (maybe because its obvious).

1. My understanding from wiki/tutorialspoint/ppt is that for CBC/CFB, decryption parallelizable means a plaintext block can be recovered from two adjacent ciphertext block. Is this correct or is there more? I really don't see how the word parallel fits into this at all.

2. It is stated as advantage for the decryption to be parallelizable, but if an attacker has access to your ciphertext, then couldn't the attacker just decrypt it easily by using adjacent ciphertext blocks.

3. I've know about C threading, is this related to it? As in you can decrypt the from multiple threads. I don't see how this is possible either because it seems to be done from one chain.

Answer 1

plaintext block can be recovered from two adjacent ciphertext block

You also need the key. For example, for CBC mode, to decrypt block $i$, you need ciphertext block $i$, ciphertext block $i-1$, and the key. You do not have to have made any calls to the cipher on any previous or future blocks in order to decrypt block $i$.

Contrast this with OFB which is not parallelizable. In order to decrypt block $i$, you need to have run the cipher on block $i-1$ first.

if an attacker has access to your ciphertext, then couldn't the attacker just decrypt it easily by using adjacent ciphertext blocks

No, because the attacker does not have the key.

I've know about C threading, is this related to it?

Threading is one way to parallelize. In theory, with CBC or any other parallelizable mode, you could decrypt different blocks in different threads, processes, or even different machines.

Answer 2

I don't think parallel in the decryption context means anything more than just usual parallel computing, or speeding up the computation by using multiple processors. Parallelizable decryption just means that the ciphertext can be decrypted in parts, with the parts processed at the same time, on multiple processors, with multiple threads, processes, or whatnot.

For example, CBC decryption requires the previous and the current ciphertext block (and the key), to produce the current plaintext block:

$$ P_i = D_K(C_i) \oplus C_{i-1} $$

When decrypting, all the ciphertext blocks are available, and blocks before $C_{i-1}$ are not required to decrypt block $C_i$. So decrypting a large CBC chain can be done simultaneously in two parts, with one processor decrypting the beginning of the message, and another starting at the middle.

Similarly, CBC encryption also requires the previous ciphertext block:

$$ C_i = E_K(P_i \oplus C_{i-1}) $$

However, when encrypting, the ciphertext blocks are not available yet, and getting the previous block $C_{i-1}$ requires the one before that, and so on all the way to the start of the chain and the IV. So encryption in CBC mode cannot be done in parallel.

CFB mode is similar to CBC in this, and e.g. CTR mode is obviously parallelizable both ways, since all blocks depend on just the corresponding counter value.