# Perfectly secret cipher can leak about the key?

As defined by Shannon, a cipher is perfectly secure if ciphertext leaks no information about the plain text.

Under this definition, can ciphertext leak something about the key? Are there any ciphers for which this is true?

-

## 5 Answers

Sure, it can leak something about the key as long as that doesn't leak anything about the plaintext.

Consider the following cipher, I'll call it 2-OTP. 2-OTP takes as input a message $M$ and two keys $K_1$ and $K_2$. Each key must be truly random, independent of one another, and each the same length as the message $M$. Define encryption as $ENC(M,K_1,K_2)=K_1,M\oplus K_1 \oplus K_2$. Notice that encryption leaks the entire $K_1$.

Clearly this leaks nothing about the message $M$ as with the information given, we can compute $M\oplus K_2$, but that leaks nothing about $M$.

As an example of something a that won't work (i.e., leaking something about the key leaks something about the plaintext), consider OTP' where OTP' is just the one-time-pad but leaks the first bit of the key. Clearly this leaks the first bit of the message, so it is no longer perfectly secure.

-
This sound's like a cheater's answer as we can simply to a form that doesn't leak any key without losing strength. –  Joshua Nov 13 at 17:29
@Joshua, if you know of a cipher that does leak key bits while still retaining perfect secrecy that can not easily be converted to a form that doesn't leak key information and is still informational theoretically secure, by all means, post it as an answer. –  mikeazo Nov 13 at 17:38

mikeazo's answer clearly covers what the question asks. However, I want to go further and answer this:

How much information does a perfectly secure cipher leak about the key?

Exactly all the excessive information of the key that does not help in finding anything about the message.

In simple words: if the key length is $k$ bits and the message is $m$ bits long then in case of a perfectly secure cipher by knowing the ciphertext you know exactly $(k-m)$ bits of the key.

Formally: By knowing a ciphertext which is ciphered using a perfectly secure cipher the uncertainty about the key is exactly equal to the uncertainty about the message.

Or using entropy function:

$$H(K|C)=H(M)$$

Where $H(K)$ is the entropy of the key, $H(C)$ is the entropy of the ciphertext, and $H(M)$ is the entropy of the message.

The equation above can be deduced from the following equations:

$H(M)=H(M|C)$, $H(M|C,K)=0$

-

The one-time pad is perfectly secure. It will also leak the complete key to any attacker who knows the message (and will leak some information about the key to any attacker who knows something about the message).

It's important to note that there's nothing in the definition of perfect security that says that the attacker can't already know something, or even everything, about the message. On the contrary, the definition explicitly allows for the possibility that an attacker might already have some information about the message, and merely requires that observing the ciphertext will not give the attacker any new information about the message.

In fact, against a computationally unbounded attacker who already knows the message, any encryption scheme will leak either the key or a set of equivalent keys. This is because the attacker can simply test all possible keys, attempting to decrypt the ciphertext with each of them, and discard those that don't yield the correct message.

-

A theoretically secure cypher that leaks bits is OTP over a short message where naive message extension is used to prevent length-based attacks.

All the key bits after the end of the message are leaked. If your pad random source is good there is no attack.

Example:

PAD: 1 4 3 7 2 9 4 3
MSG: 3 1 2 3
ENC: 4 5 5 0 2 9 4 3


If the attacker were to learn the length of the message is 3 digits (say by a timing attack), it is now obvious the whole rest of the pad was leaked.

-
Let me make sure I understand, you pad a message with random data, then encrypt with OTP. Leak the key bits that encrypt the padding? –  mikeazo Nov 13 at 17:52
You pad with constant data then encrypt with OTP. This leaks the remaining key bits. Yes, you should be padding with random, but that's not the point. –  Joshua Nov 13 at 18:15
@Joshua I am finding it difficult to understand how will the remaining key bits will be leaked? –  Pratik Soni Nov 14 at 3:37

For a Public-Key cryptosystem (e.g. RSA), the ciphertext could presumably leak the whole Public-Key if desired (e.g. by appending it to the "usual" ciphertext).

(Assuming a perfectly secure Public-Key cryptosystem is theoretically possible).

Would be interested to know if Habib's equation can be extended to the relationship between the Public and Private Keys in such a cryptosystem.

-
Perfectly secure Public Key encryption is impossible. Because in the theory of computer science it has been proven that any turing machine (even a quantum turing machine) that does not "throw away information" is reversible. An encryption algorithm should not throw away information since the information is required for decryption. As a result, in case of public key encryption we only stand against a computationally bounded attacker. And, the only possible security is computational security. –  Habib Nov 15 at 12:45