# How can a cryptosystem be unconditionally secure?

The definition of an unconditionally secure cryptosystem states that the cryptosystem cannot be broken even with infinitely computational ressources and time. However, since most books define the keyspace $\mathcal K$ to be finite, then with infinite time any computational device can perform an exhaustive keysearch.

Why are perfect secrecy cryptosystems unconditionally secure? I mean, how can the one-time pad with a small keyspace be considered to be unconditionally secure (take ${\mathcal K} = \{0,1\}^n$ for some small $n$)?

Are unconditionally secure cryptosystems the same as perfect secrecy cryptosystems?

In order to define computational security, one makes the relaxations of unconditional security, that it is possible to break the cryptosystem in superpolynomial time and with neglible probability. Why are these relaxations of unconditional security? Any cryptosystem can be broken with small probability by taking a key at random, even an unconditionally secure one?

The term unconditional security was (as far as I know) coined by Diffie and Hellman in their seminal paper New Directions in Cryptography. Here is the snippet

[... ] a system which can resist any cryptanalytic attack, no matter how much computation is allowed, is called unconditionally secure. Unconditionally secure systems are discussed in  and  and belong to that portion of information theory, called the Shannon theory, which is concerned with optimal performance obtainable with unlimited computation.

The reason why a perfect implementation of one time pad (OTP) can be considered to be unconditional secure is because of Shannon's insight which may be succinctly described by
$$Pr_{\mathbf{k}\leftarrow \mathcal{K}}\left[\mathbf{c} = \mathcal{E}\left(\mathbf{m}_0,\mathbf{k}\right)\right] = Pr_{\mathbf{k}\leftarrow \mathcal{K}}\left[\mathbf{c} = \mathcal{E}\left(\mathbf{m}_1,\mathbf{k}\right)\right],$$

i.e. given a ciphertext $$\textbf{c}$$, the probability that it was the encryption of some plaintext $$\textbf{m}_0$$ is equal to the probability that it was the encryption of another plaintext $$\textbf{m}_1$$; and this holds true for all possible plaintexts and ciphertexts.

Note that it does not say anything about how big or small the keyspace is; for OTP, the only requirement is that the key be at least as large as the message.

Thinking purely from an adversarial perspective, the content of the message can be ANYTHING but there is nothing in the ciphertext that makes one message seem more probable than the other. I have tried to explain this with a cartoon image. Exhaustively searching for the original plaintext (by brute-force cryptanalysis) is an exercise in vain because every plaintext is equally likely! The world war II pigeon discovery is a case study of this kind.

Of course, in case the adversary has some side information that makes the context more specific, the actual message (or parts of it) may be correctly guessed. But it is important to know that any such information is not leaked by the OTP at least.

• Why is it possible to break the cryptosystem in the case of a computational security with neglible probability ? I mean, if every string is decoded, what can be said about which plaintext is correct ? How, can one say "This plaintext is the correct one with absolute certainty" ? – Shuzheng Dec 21 '14 at 11:57
• Imagine a $n$-bit message encrypted by a $m << n$-bit key of a computationally-secure cipher (e.g., a 1 MB long message encrypted with 56-bit DES key means $n \approx 8000000$ and $m=56$). Exhaustively searching for $M=2^{m}$ keys would yield $M <<<< N = 2^n$ potential messages (and $N$ is what you get if you had used OTP instead). The chances of getting the correct message out of the $M$ decryptions is clearly much much higher than from $N$. – jayann Dec 21 '14 at 12:53
• But still the adversary cannot say, if he has found the correct message ? If one cannot say "this is the correct message" given a decrypted plaintext with 100 % certainty, then what does it help to have a high chance of getting the correct message, if one cannot differtiate it from the wrongs ? – Shuzheng Dec 21 '14 at 18:19
• The user will typically be encrypting multiple messages with a single key. Although this would vary from cipher to cipher, my conjecture is that the brute-force cryptanalysis on just a handful of ciphertexts should generally suffice for the adversary to pin-point the correct key. Once that is cracked, all past, present, and future plaintexts encrypted with that key are known to the adversary. – jayann Dec 21 '14 at 20:46
• is brute force a cryptanalytic attack? – yamm Jun 2 '15 at 11:57

Imagine a one-bit message $m$. Attacker knows that $m = 0$ with probability $p$ and $m=1$ with probability $1-p$. (In many cases, $p=0.5$.)

With one-time pad (Vernam's cipher) encryption, the attacker can't guess anything. If the ciphertext is 0, the plaintext is 0 with probability $p$ (and the plaintext is 1 with the probability $1-p$). Attacker can't learn anything. When the ciphertext is 1, attacker is in the same situation. In other words, attacker knows only the information he knew in advance.

In this case, the attacker has done an exhaustive key search. He has found a correct plaintext during the exhaustive key search. He however does not have an idea which of all the possible plaintexts are correct. The one-time pad has thus provided unconditional secrecy in this case. (The unconditional secrecy would be lost when the key is not random enough or once the key is reused, though.)

You can even encrypt in this way a 1 terabyte message with a SHA-256 hash with one-time pad. You would need at least $8\cdot2^{40} + 256$ bits of the key for encrypting both the message and its hash. (For unconditional secrecy, it is essential to have the hash encrypted.)

• You may want to mention that for a otp you have $p=0.5$. – DrLecter Dec 21 '14 at 11:15
• Ahh, so he observe all plaintexts but have no idea which one is correct. I'd the wrong idea, that the plaintext making "sense" was the correct one, but I see this is completely, as the correct plaintext could be anything. – Shuzheng Dec 21 '14 at 11:48
• Exactly, thats the point. – DrLecter Dec 21 '14 at 11:56
• Is there cryptosystems that provide perfect secrecy if the same key is used more than once ? I know this is not the case for the OTP, but without proof. Is it in the definition of perfect secrecy that the key is used once ? – Shuzheng Dec 21 '14 at 11:58
• @DrLecter: Although $p$ might be $0.5$, it is not necessary. For example, if attacker knows that 0 as a plaintext is more likely than 1, then $p > 0.5$. – v6ak Dec 21 '14 at 12:29

However, since most books define the keyspace $$\mathcal{K}$$ to be finite, then with infinite time any computational device can perform an exhaustive keysearch.

The thing is that it isn't sufficient to perform an exhaustive key search. You must also have a procedure to evaluate the candidate decryptions that the key search produces and judge which ones are likelier to be the actual plaintext.

You might think to do this by, for example, applying statistics to the candidate decryption to see if it looks like natural language text (or whatever you expect the plaintext to look like). But here's the huge catch: to break the encryption scheme, your procedure can't just be a generic evaluation of the candidate decryptions—it must use the ciphertext as evidence in favor of some and against others. That's the part that a perfectly secret encryption scheme renders impossible.

One way to visualize this: given a ciphertext $$C$$ as input, you're thinking of an algorithm like this:

1. Loop over every possible key $$K_i$$;
2. Compute the candidate decryption $$P_i = C \oplus K_i$$;
3. Perform some evaluation $$\mathrm{eval}(P_i, C)$$ that judges how likely it is that $$P_i$$ is the real plaintext, given ciphertext $$C$$;
4. After doing this for all possible keys, output the list of plaintexts ranked by their evaluations in step #3;

But the problem is that you need to explain how this would be any more accurate than an algorithm like this one that completely ignores the ciphertext:

1. Loop over every possible plaintext $$P_i$$;
2. Perform an evaluation $$\mathrm{eval}'(P_i)$$ that judges how likely it is that $$P_i$$ is the real plaintext (and doesn't look at $$C$$ at all);
3. After doing this for all possible messages, output the list of candidate plaintexts ranked by their evaluations in step #2.

Apart from that, it's worth pointing out that unconditional security ≠ perfect secrecy, just because security ≠ secrecy to start with. For example, there is such a thing as unconditionally secure message authentication codes, but for these the probability of generating a forgery isn't zero.

The terms are often used loosely, though.