- For a type of cryptosystem with a security goal, like a 128-bit authentication tag on a message aiming to prevent forgery, perfect security is the best security we could possibly hope for with any cryptosystem of that type.
- For a model or family of cryptosystems of a particular type aiming for some security goal, like CBC-MAC, an information-theoretic or unconditional security theorem is a theorem in terms of probability theory about the advantage of any adversary against the model with idealized components.
- For an instance of a model with particular primitives like AES-CBC-MAC, a computational or conditional security theorem is a theorem relating the cost of breaking the composition AES-CBC-MAC with a certain advantage to the cost of breaking the primitive AES with some advantage.
Some authors will loosely use the terms ‘information-theoretic security’ and ‘perfect security’ interchangeably when they're talking about one-time pads, but there's more to them than that.
An information-theoretic or unconditional security theorem is a statement about the advantage—e.g., forgery probability, or distinguishing success probability over a fair coin toss—of any attack algorithm on some cryptosystem. Example of a theorem about universal hashing MACs, specifically polynomial evaluation:
Theorem 1. Let $r, s$ be secret independent uniform random elements of $\operatorname{GF}(2^{128})$. Let a message $m$ be a polynomial of degree 2 with zero constant term over $\operatorname{GF}(2^{128})$, $m(x) = m_1 x^2 + m_2 x$.
The probability that a forgery algorithm $A(m, a)$ given a message $m$ and its authenticator $a = m(r) + s = m_1 r^2 + m_2 r + s$ succeeds at finding any $(\hat m, \hat a)$ pair with $\hat m \ne m$ and $\hat a = \hat m(r) + s = \hat m_1 r^2 + \hat m_2 r + s$ is at most $2/2^{128}$.
Proof: For any $m \ne \hat m$, $a$, and $\hat a$, there are at most two roots in $r$ to the polynomial $(m - \hat m)(r) - a + \hat a = (m_1 - \hat m_1) r^2 + (m_2 - \hat m_2) r - a + \hat a$. Thus of the $2^{256}$ possible values of the key $(r, s)$ each with probability $1/2^{256}$, there are only $2\cdot 2^{128}$ for which $(\hat m, \hat a)$ is a forgery; hence the event of a forgery has probability $2\cdot 2^{128}/2^{256} = 2/2^{128}$. ∎
This is a practical way to authenticate a single message, but not to authenticate many messages. The Carter–Wegman method uses many secrets $r, s_1, s_2, \dots, s_n$ to authenticate the $i^{\mathit{th}}$ message with $a_i = m_i(r) + s_i$; another method is to generate $r_i, s_i$ afresh for each message by a pseudorandom function of the message sequence number $i$.
Example of a theorem about CBC-MAC:
Theorem 2. Let $f$ be a secret uniform random function of 128-bit strings. Let a message $m$ be a 256-bit string $m = m_1 \mathbin\| m_2$.
The probability that a forgery algorithm $A(m, a)$ given a message $m$ and its authenticator $a = f(f(m_1) \oplus m_2)$ succeeds at finding any $(\hat m, \hat a)$ pair with $\hat m \ne m$ and $\hat a = f(f(\hat m_1) \oplus \hat m_2)$ is at most $6/2^{128}$.
Proof: See, e.g., [1], §3.3, or [2]. ∎
This is in contrast to a computational or conditional security theorem which relates the advantage of an algorithm at breaking a composite cryptosystem to the advantage of an algorithm breaking the primitive pieces out of which it is built. Example of a computational theorem about using AES with a polynomial evaluation universal hash to make a Carter–Wegman–Shoup MAC like AES-GMAC:
Theorem 3. Let $k$ be a secret uniform random 128-bit key. Let $r = \operatorname{AES}_k(0)$ and $s = \operatorname{AES}_k(1)$. Let a message $m$ be a polynomial of degree 2 with zero constant term over $\operatorname{GF}(2^{128})$, $m(x) = m_1 x^2 + m_2 x$.
If there is a forgery algorithm $A(m, a)$ which when given a message $m$ and its authenticator $a = m(r) + s = m_1 r^2 + m_2 r + s$ succeeds at finding any $(\hat m, \hat a)$ pair with $\hat m \ne m$ and $\hat a = \hat m(r) + s = \hat m_1 r^2 + \hat m_2 r + s$ with probability $\varepsilon$, then there is a distinguishing algorithm $A'(\mathcal O)$ which with two queries to the oracle $\mathcal O$ can distinguish $\mathcal O := \operatorname{AES}_k$ for uniform random key $k$ from $\mathcal O := f$ for uniform random function $f$ with advantage at least $$|\Pr[A'(\operatorname{AES}_k) = 1] - \Pr[A'(f) = 1]| \geq \varepsilon - 2/2^{128},$$ which costs negligibly more than $A$.
- In other words, if there is way to forge AES-GMAC authenticators with higher probability than Theorem 1 allows, then there's a way to break AES as a pseudorandom function at comparable cost and advantage.
- Consequently, if the best algorithm for distinguishing $\operatorname{AES}_k$ from $f$ has advantage at most $\delta$, then the best algorithm for forging AES-GMAC authenticators has forgery probability at most $\delta + 2/2^{128}$.
Proof: Define $A'(\mathcal O)$ as follows: Compute $r = \mathcal O(0)$ and $s = \mathcal O(1)$; pick a message $m$ and compute $a = m(r) + s$; run the forger $(\hat m, \hat a) := A(m, a)$; check whether $\hat m \ne m$ and $\hat a = \hat m(r) + s$, i.e. check whether the forger succeeded. If the forgery was successful, guess that $\mathcal O = \operatorname{AES}_k$ for some $k$; otherwise guess that $\mathcal O = f$. If $\mathcal O = f$, the forgery probability is at most $2/2^{128}$ by Theorem 1. If $\mathcal O = \operatorname{AES}_k$, the forgery probability may be greater. So $\Pr[A'(f) = 1] \leq 2/2^{128}$ and $\Pr[A'(\operatorname{AES}_k) = 1] = \Pr[\text{$A(m, a)$ forges}] = \varepsilon$. Hence $$\Pr[A'(\operatorname{AES}_k) = 1] - \Pr[A'(f) = 1] \geq \varepsilon - 2/2^{128}. \quad ∎$$
There's a similar theorem about AES-CBC-MAC. (Exercise: Find or figure out the statement of the corresponding AES-CBC-MAC theorem. Exercise: Find an attack on AES-GMAC that has better forgery probability than in Theorem 1 using the fact that $\operatorname{AES}_k$ is a permutation; does this attack violate Theorem 3?)
What about ‘perfect security’ and how it is connected to information-theoretic security? For any type of cryptosystem, like a message with a 128-bit authentication tag which we hope will prevent forgery, perfect security is the best information-theoretic security we could hope for in any cryptosystem of that type.
What's the smallest bound on forgery probability that we could possibly hope to achieve for messages with a 128-bit authentication tag? If the key $k$ is simply a colossal book of every authenticator for every message, and we choose a book uniformly at random from the Library of Babel containing all such books of authenticators, then for any $m, a, \hat m \ne m, \hat a$, the probability that $\hat a$ is the correct authenticator for $\hat m$ is exactly $1/2^{128}$. We can't force the forgery probability any below that because there are only $2^{128}$ possible authenticators.
Of course, it would be unusably unwieldy to choose and agree on such a book. We can still have perfect security for a one-time authenticator if the key is longer than the message, but that's still unwieldy—in practice, people might cook up hare-brained schemes like flipping through real books to choose the key, and thereby ruin the security, which is why we use systems that reliably admit smaller keys at small cost to the forgery probability, like $\ell/2^{128}$ for messages $\ell$ blocks long as in AES-GMAC, or $1/2^{128} + \binom{q \ell}{2}/2^{128}$ after authenticating $q$ messages $\ell$ blocks long as in AES-CBC-MAC.
(Caveat: AES-CBC-MAC is not safe to use in practice for variable-length messages; the above theorems apply only to fixed-length messages. However, variants like AES-CMAC or length-prefixed AES-CBC-MAC provide essentially the same security.)
For different types of cryptosystem there are different notions of advantage and different theorems. For example, for an unauthenticated symmetric-key cipher, the advantage is the probability above 1/2 at an algorithm for distinguishing the ciphertexts of two plaintexts: the adversary chooses two messages $m_0$ and $m_1$, the challenger flips a coin $b$ and sends the adversary the challenge $E_k(m_b)$, and the adversary wins if they can guess what $b$ was. Obviously the adversary can always attain success probability 1/2, e.g. by guessing 0 all the time; what is interesting is when the success probability is above 1/2, and we call $|\Pr[A(E_k(m_b)) = b] - 1/2|$ the ciphertext distinguishing advantage of $A$ against $E$. We then have theorems like:
Theorem 4 (Information-theoretic security for the one-time pad model). Let $E_k(m) := m \oplus k$ be a cipher with secret key $k$ drawn from a distribution $D$. The distinguishing advantage of any algorithm $A$ against $E$ is bounded by the total variation distance $\delta(D, U)$ of the distribution $D$ from the uniform distribution $U$: $$|\Pr[A(E_k(m_b)) = b] - 1/2| \leq \delta(D, U).$$
Theorem 5 (Computational security for a one-time pad with a pseudorandom generator). Let $E'_k(m) := E_{G(k)}(m) = m \oplus G(k)$ be a cipher with secret key $k$ for a pseudorandom generator $G$. If there is a ciphertext distinguisher $A$ with advantage $\varepsilon$ against $E$, then there is a pseudorandom generator distinguisher $A'$ against $G$ with distinguishing advantage $\varepsilon$.
(This method of encryption with a one-time pad generated from a short key by a pseudorandom generator is sometimes called a stream cipher.)
For an unauthenticated cipher, ‘perfect security’ is when the best distinguishing advantage of any algorithm is zero. In one-time pad model, this occurs when the distribution $D$ is identical to the uniform distribution $U$ so that the total variation distance $\delta(D, U) = 0$.
Of course, as with a perfect authenticator, perfect security here requires generating and storing a key as long as the message, so it's not very practical; instead a modern stream cipher uses a short key with a secure pseudorandom generator $G$ like AES-CTR or Salsa20. Theorem 5 guarantees that all the work that has been done to study the security of the primitives carries over to the security of the message cipher $E'$.
What if you're scared about mathematical breakthroughs against AES or Salsa20?
- You could use a pseudorandom generator $G$ for Theorem 5 based on fancy math like number theory, such as Blum–Blum–Shub, on the premise that it has a reduction to a ‘real’ hard problem like factoring. But we only conjecture that factoring is hard just like we only conjecture that breaking AES is hard based on decades of failures of cryptanalysis by smart people—and Blum–Blum–Shub is an astonishingly inefficient generator in contrast to AES or Salsa20, and it has a back door like Dual_EC_DRBG, which is really the only reason to use this kind of fancy math: to support separate public-key and private-key operations.
- You could cook up your own bespoke hare-brained scheme $G$ instead for Theorem 5, like we often see posted on this site, but then you have to study it separately and can't rely on all the work that has gone into studying AES or Salsa20.
- You could skip Theorem 5 and use samples from a physical device for the key in Theorem 4, but then you have to do physics and engineering to study the physical process and the distribution $D$ and can't rely on all the work that has gone into studying AES or Salsa20.
Outside cryptography, the information-theoretic perfect security of the one-time pad with a uniform distribution on the message-length key is sometimes phrased as a statement about the conditional entropy $H[m \mid E_k(m)] = H[m]$, and interpreted to mean that the ciphertext $E_k(m)$ gives no information about the message $m$.
Claude Shannon's observations about entropy of one-time pads in the language of information theory before the advent of modern cryptography are probably why the cryptography literature uses the term ‘information-theoretic’ for theorems about models with idealized components even though they're really just mundane statements in probability theory.
In particular, the phrasing in terms of entropy doesn't lend itself to reasoning about composition in cryptographic systems or about cost-limited adversaries, so it doesn't usually turn up in cryptography literature, except to prove that for ‘perfect security’ the key must take on at least as many distinct values as the message can, so it's not worthwhile to chase ‘perfect security’ for a cipher any more than for an authenticator.
In summary, perfect security of a type of cryptosystem is the best security that can be had even in principle—it is hopeless to aim for better security in any particular cryptosystem of that type. An information-theoretic security theorem of a model of cryptosystems of a particular type tells us what security the model could provide if given ideal components, like the one-time pad or universal hashing authenticator, and a computational security theorem justifies focusing cryptanalytic effort on the components, like AES, and not on the composition, like AES-CTR.
