I'm trying to encrypt a plain text (of length l) and output a ciphertext of length t, where t does not equal to l. How do i get a ciphertext that is shorter than the plaintext input? How about if I want a ciphertext that is longer than the plaintext?

Also, assume if I already have a encryption function E, such that E takes l bit plain text as input, and outputs a l bit ciphertext. How can I use E to create a new encryption G, such that G solves the above problem?

  • $\begingroup$ You need a compression. $\endgroup$ – marshal craft Feb 6 '17 at 11:16

It is impossible to have a ciphertext shorter than the plaintext, while still being able to decrypt it. This is quite obvious: an $\ell$-bit ciphertext contains at most $\ell$-bit of information, so as long as the messages have more than $\ell$ bits of entropy, some information is lost (and if it is longer than $\ell$ bit but has very little entropy, then you can compress the message before sending it).

In the case of public key encryption, in fact, if your message is $\ell$ bit long, you cannot even have a ciphertext of length $\ell$ if you want some important security properties: encryptions schemes are usually required to satisfy semantic security, which states that if a ciphertext encrypts one of two messages, it is infeasible to determine which one it encrypts (even knowing the plaintexts). But this implies that many ciphertexts must correspond to a same plaintext: if a plaintext is associated to a single ciphertext, one can break this property just by encrypting the two messages and checking equality with the ciphertext. Therefore, to get a probability, say, at most $1/2^{80}$ for the encryption scheme to be broken, a ciphertext will be at least 80 bits longer than the maximum size of a plaintext.

If you want a longer ciphertext, just pad with zeroes. You can make the ciphertext as long as you want that way.

  • $\begingroup$ To be precise, you can't have all ciphertexts be shorter than the corresponding plaintexts. It is possible for some ciphertexts to be shorter than the plaintext, but this necessarily implies that some other ciphertext must be longer than its plaintext. Also, if you're not careful, the length of the ciphertext may leak information about the plaintext. (Of course, that's true even for a length-preserving scheme; in that case, the length of the ciphertext leaks the length of the plaintext.) $\endgroup$ – Ilmari Karonen Feb 6 '17 at 3:11

In TLS you would use an optional compression method. This is signaled in an implementation defined connection state which contains the null compression by default along with other things like current cipher sweet and is negotiated in the handshake. This would enable what you ask.

In TLS compression comes before encryption.

  • $\begingroup$ The compression method would have to be lossless, e.g. entropy encoding with Huffmann codes or arithmetic coding. However, if the input has full entropy, on average this doesn't help reduce the size at all (the average Kologomorov complexity is (almost) equal to the entropy - mathemtically speaking, it is the same for almost all inputs) $\endgroup$ – tylo Feb 7 '17 at 12:23
  • $\begingroup$ Sorry, I know very little about entropy or compression. Are you saying the compressed plain text will not necessarily be of shorter length? I guess you are correct. $\endgroup$ – marshal craft Feb 7 '17 at 15:35
  • $\begingroup$ Language has really low entropy compared to the length of the string itself, so that compression works. For things like random binary data, it will most likely not work (depends on "how random" it actually is). What you wrote "compression before encryption" - that is a given (with current encryption schemes), because if you could compress it, it would not be secure. $\endgroup$ – tylo Feb 7 '17 at 17:15

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.