How can a cryptosystem be unconditionally secure?

Question

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?

Answer 1

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 [3] and [4] 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.

Answer 2

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.)

Answer 3

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.