McEliece for streaming data

Question

Under the assumption that there exists a real-world implementation of the McEliece scheme, could it be applied to streaming data as is? By that I mean in 'block cipher mode'? I've read that McEliece is very fast in encryption and decryption, hence calculating a session key for a symmetric stream cipher might be unnecessary. Since random errors are introduced into the plaintext while encrypting, could it then be used in 'block cipher mode'?

Answer 1

While McEliece could be used like a block cipher, in practice it would much must slower than the standard hybrid approach. McEliece might be relatively fast compared to other public key primitives, it is still quite slow compared to a symmetric cipher.

On the Ecrypt performance page, they list the performance of McEliece on various hardware platforms; the fastest median time they list to encrypt a block of data is 48937 cycles, and to decrypt is 827864 cycles.

Now, I can't find where they list the value of $k$ they used (which the size of the message being encrypted in bits); if we assume a $k$ of 2048 (which is somewhat larger than the current recommendations), a block of data would be 256 bytes, so we're encrypting at 191 cycles per byte, and decrypting at 3233 cycles per bytes.

Obviously, a symmetric algorithm can do considerably better.

In addition, as for the block cipher mode, well, it's not as straightforward as you might have hoped; McEliece isn't a block cipher; it's nondetermanistic and it has a larger ciphertext size than plaintext size. Straightforward ECB may sound attractive with McEliece's randomization property, however encryptions of the same text still resemble each other, and so ECB would still have problems with repeated plaintext blocks. As for CBC, well, you probably could truncate the previous ciphertext to make it match the plaintext size when doing the exclusive-or. You might be able to define a variant of OCB modified to work with the differing plaintext/ciphertext block sizes. That other standard modes look pretty hopeless; CTR, CFB, OFB all have both sides run the block cipher in encrypt; this won't work both because we would lose the public key characteristic of McEliece, and in any case, they rather assume that encryption is determanistic.

In addition, McEliece has the property of expanding the ciphertext (making it perhaps 30% larger than the plaintext). While this is not unusual for a public key algorithm (indeed, most public key algorithms expand the ciphertext rather more), for a long message this would be considerably more expansion than with a standard symmetric cipher (which generally adds a fixed amount of data for IVs, padding, and MAC tags).

As for your question about random errors, well, that's not actually a problem. Yes, random errors are inserted during encryption, but they are removed during the decryption phase. Hence, the decryptor gets exactly the same message that the encryptor sent, and so there's nothing prohibiting you from using some type of block cipher mode (assuming you use one that can live with McEliece's not-particularly-like-a-block-cipher characteristics).