2
$\begingroup$

Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys.

However I have never heard about the size (or length) of its ciphertext. ("Ciphertext expansion".) For example, McEliece offers the linear code of length 1024 and of dimension 524. That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency?

$\endgroup$
  • $\begingroup$ you can do the encryption with McEliece indeed really fast. And indeed the ratio $\beta=n/k$ defines the ciphertext expansion you'll observe. IIRC this value usually is $1.25\leq \beta \leq 1.5$. The ciphertext is then of size $n$ and the input of size $k$. $\endgroup$ – SEJPM Sep 7 '15 at 12:27
5
$\begingroup$

That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency?

Not really; or at least, that's not an inefficiency we care about.

A length of 1024 means, in this context, 1024 bits (or 128 bytes). This compares favorably to RSA (for which a key with a 1024 bit ciphertext has questionable security). More importantly, a ciphertext of 1024 bits is fairly cheap to transport; it fits extremely easy in an IP packet (if we're communicating over IP); over wireless (which we tend to be sensitive to message length due to power reasons), it's still not too bad.

The reason we don't use McEliece now is the "expense"; that is, those parts of the cipher that make it costly to implement. And, the expensive part of McEliece is the public key (which is circa 200kbytes); we could fit it into a certificate, or pass it as an authenticated part of the key negotiation protocol, but it would be painful. Most everything else about McEliece (the ciphertext size, the computational effort) are things we can easily live with (with the possible exception of the private key; we don't have to worry about transporting that around, but we still need to store it securely).

$\endgroup$
  • $\begingroup$ Actually I don't have much information about applied aspects of cryptography. As far as I understand, you say: McEliece cryptosystem has a fast algorithm such that it would not really important if the length was doubled during encryption. $\endgroup$ – faith Sep 8 '15 at 11:35
  • $\begingroup$ @faith: for a symmetric system, yes, that would be a cost which would be hard to justify. However, McEliece is an asymmetric system; for one, all asymmetric encryption systems have some ciphertext expansion, and secondly, in practice, it's used to transport the symmetric keys, hence we use it only once for an entire protocol exchange (and an expansion of less than 100 bytes is quite tolerable). $\endgroup$ – poncho Sep 8 '15 at 11:40
  • $\begingroup$ Now I can see better. Thank you. Can I ask one more question? How does RSA make ciphertext expansion? $\endgroup$ – faith Sep 8 '15 at 11:55
  • $\begingroup$ @faith: because, whenever we use RSA to encrypt a message, we apply randomized padding (RSA without padding is insecure; at least, it makes it easy to test if a particular plaintext and ciphertext correspond), and this randomized padding expands the message. $\endgroup$ – poncho Sep 8 '15 at 12:00

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.