Has anyone encountered an encryption method that compresses the cipher text to a single byte at the expense of inflating the key. If yes does it have a practical use?

  • $\begingroup$ A single byte can have 256 different values. If you only ever want to encrypt a maximum of 256 different messages then assign each message a numerical value in [0..255], which reduces the plaintext to a single byte. Then encrypt by a method that does not increase the size from one byte; an OTP for example. $\endgroup$ – rossum May 8 '20 at 18:00
  • $\begingroup$ @rossum, you still have to distribute the mapping of values to plaintexts. $\endgroup$ – mikeazo May 8 '20 at 18:45
  • 1
    $\begingroup$ Have a list of the allowed plaintexts, like a very old fashioned codebook. $\endgroup$ – rossum May 8 '20 at 21:17
  • $\begingroup$ You even can reduce the size of cipher text to 0 bytes at the cost of growing the key (to the size of the plain text): just make the plain text the key. $\endgroup$ – Curd Jun 9 '20 at 15:43

Single byte, no? How about 16 bytes? Sure. Encrypt using AES-128 with a random key. The key is now the "ciphertext" and the output of the encryption (what we normally call the ciphertext) is now the "key". Problem is, how do you distribute the "key"?

The thing is, from a real world perspective, the idea of shrinking the ciphertext and growing the key is a non-starter. Keys must be shared over a secure channel, ciphertexts do not. If you had a secure channel that was efficient enough to share large amounts of data, why not just share the plaintext directly over that channel and skip the whole encryption business?

  • $\begingroup$ What do you mean a non starter...... anyone can come up with one, it is useless, the idea of a single digit key has no value? $\endgroup$ – Jonathan Hutton May 7 '20 at 18:25
  • $\begingroup$ I tried to explain what I meant. It is useless because the key must be shared over a secure channel. $\endgroup$ – mikeazo May 8 '20 at 15:03

Such an encryption scheme would have to be fairly non-standard, for reasons sketched below.

Say that $\mathsf{Enc} : \mathcal{K}\times\mathcal{P}\to\mathcal{C}$ is encryption, and $\mathsf{Dec} : \mathcal{K}\times\mathcal{C}\to\mathcal{P}$ is decryption for key space $\mathcal{K}$, plaintext space $\mathcal{P}$, and cipher space $\mathcal{C}$.

Say that we want our encryption scheme to be perfectly correct, so: $$\forall k\in\mathcal{K}, \forall m\in\mathcal{P} : \mathsf{Dec}(k, \mathsf{Enc}(k, m)) = m$$ Say that we also want ciphertexts to be at most a byte. It immediately follows that $|\mathcal{C}| \leq 2^8 = 256$. Perfect correctness means that, for each possible choice of $k\in\mathcal{K}$, that $\mathsf{Enc}_k : \mathcal{P}\to\mathcal{C}$ must be injective. From this, we have that $|\mathcal{P}| \leq |\mathcal{C}| \leq 2^8 = 256$. So for such an encryption scheme, plaintexts must be at most a byte as well (so are "boring").

One should be able to remove the perfect correctness requirement by resorting to information-theoretic tools. Specifically, one can view encryption as a form of encoding, and decryption as a form of decoding. Then things like Shannon's Source Coding theorem state that we can only get correctness with high probability if the entropy of the distribution on our inputs is at most $256$. If we want to make no restrictions on our choice of inputs (use the maximum entropy distribution, which for a finite set is uniform), then we recover the argument that $|\mathcal{P}| \leq 256$, even when one moves away from perfect correctness.

The above treats a "uniform" version of the above scheme. One could hope to define a "non-uniform" version of the scheme, where we parameterize $\mathcal{P}$ by the choice of key $k$. In this scheme, we have that perfect correctness now states that:

$$\forall k\in\mathcal{K}, \forall m\in\mathcal{P}_k : \mathsf{Dec}(k, \mathsf{Enc}(k, m)) = m$$ The same injectivity argument now gets us that $\forall k \in\mathcal{K} : |\mathcal{P}_k| \leq 2^8$. So for each key we have a space of possible plaintexts $\mathcal{P}_k$, and one could hope that the "real plaintext space" $\mathcal{P} = \cup_k \mathcal{P}_k$ could therefore be "larger", allowing us to make the tradeoff that you describe.

One can do this, but security becomes unclear. The particular issue is as follows ---- Say that you want to encrypt some $m\in\mathcal{P}$. You then need to establish some key $k$ such that $m\in\mathcal{P}_k$ to share with the other party (note here that the key you establish depends on the message you want to communicate). I'm aware of formalizations of encryption where the message encrypted can be a function of the secret key (KDM security), but am not aware of this "reverse notion" where the secret key chosen is dependent on the message you want to communicate.

  • $\begingroup$ It will take me a while to work through your math. The reverse notion is a simple process, that took me a couple of years to come up with. I was looking at numbers only as their value but a number has numeric value and a place value I found a way to separate the two and manipulate one without effecting the other. which led to a reduction to one byte of the key expanding the cipher text into the plain text. I would be glad to share this, but am not sure where or with whom. Here is fine with me. One more note, because it manipulates place value, the numeric value is securely hidden. $\endgroup$ – Jonathan Hutton May 8 '20 at 23:12
  • $\begingroup$ Once again I have seen this as a puzzle for me to beat, but it seems its nothing more than a toy with no practical value? $\endgroup$ – Jonathan Hutton May 8 '20 at 23:17
  • $\begingroup$ If you want to share it, I suggest a blog of some sort (stackexchange is a Q&A forum, so unless you have particular questions it's out of scope for the forum). If you're worried about "precedence" related issues (as many amateurs often are), I would suggest briefly describing your ideas in a document, hashing this (say with SHA3, but any collision-resistant hash function suffices), then post it somewhere that's both public and has a time stamp feature, such as Twitter. $\endgroup$ – Mark May 9 '20 at 0:48
  • $\begingroup$ As for the math, it essentially says that any such solution must either be "boring" (only able to encrypt 1 byte's worth of different messages), be insufficient to encrypt "random messages", or to require the key to be chosen in a way dependent on the message (which is a highly non-standard idea, and seems less useful to me in practice although I haven't thought about it much). Assuming the math is correct (I'm fairly confident about it but there's always some risk of a mistake), these are the only options. Seeing which your scheme fits into might be an interesting exercise. $\endgroup$ – Mark May 9 '20 at 0:51
  • $\begingroup$ This method would work well with deniable encryption since it is possible to hide many messages in one ciphertext with different keys. The added security that if any change is made to the cyphertext the key would not work. $\endgroup$ – Jonathan Hutton May 13 '20 at 17:53

A basic example of this in action is a Play Call in football. Before the play starts, the quarterback announces a short number or word which will describe how everyone is expected to move once the play starts. These movements must be kept secret from the other team, or they would take advantage of it

The result of this is the "playbook" contains all of the content of the message.

Of course, this would rarely be considered cryptography, but it is the system you described.


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.