# What is the difference between information-theoretic and perfect types of security?

I'm having a hard time pinning down an exact definition of the difference between information-theoretic and perfect types of security. A rigorous definition seems elusive...

A. Wikipedia puts the difference down to the perfect type being a (poorly) defined special case of the information-theoretic type. "...a cryptosystem to leak some information" - yet I thought that these two particular security definitions only applied to breaking the encryption, rather than peripheral things like leaking the time the message was sent, it's length, etc.

B. An e-voting manufacturer uses entropy to quantify the difference as:-

1. $$H(K | C) = H(K)$$ – Perfect secrecy
2. $$H(K | C) < H(K)$$ – Information-theoretic security

Yet #2 can be rewritten as $$H(K | C) = H(K) - \delta$$, and that leads to #2 equalling #1 if $$\delta \to 0$$.

C. And finally a link from What's the difference between perfect security and unconditional security? is suggesting that "perfect security is the same as information-theoretic security".

Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional security: it does not rely on any computational assumption, and is not limited to probabilistic polytime adversaries.

A perfectly secure protocol is such that any (possibly unbounded) adversary has probability $$0$$ of breaking the security property. It is a special case of information-theoretic security: every perfectly secure protocol is information-theoretically secure, but the converse is not true.

To take a simple example, the distinction often appears when some secret value is masked with a random value, and we ask how hard it is to distinguish the masked value from a uniformly random value. Consider the following protocol: $$x$$ is an integer, say, between $$0$$ and $$n - 1$$. The game is as follows: we first sample a random bit $$b$$. If $$b = 0$$, we send a random value $$r \gets X$$ to the (unbounded) adversary, sampled from some set $$R$$, while if $$b=1$$, we sample a random value $$r \gets R$$ and send $$x + r$$ to the adversary. Fix a security parameter $$k$$. We say that the protocol has perfect security if the adversary has probability exactly $$1/2$$ of guessing the value of $$b$$ given the input, and that the protocol has information-theoretic security if the adversary has probability $$1/2 + \mu(k)$$ of guessing the value of $$b$$, where $$\mu$$ is a negligible function.

Suppose we identify $$[0, n-1]$$ with $$\mathbb{Z}_n$$ and define $$R$$ to be $$\mathbb{Z}_{n}$$ as well. The computation of $$x + r$$ is done over $$\mathbb{Z}_n$$. In this case, the protocol is clearly perfectly secure, as sampling $$r$$ from $$\mathbb{Z}_{n}$$ and returning $$x+r$$ gives exactly the uniform distribution over $$\mathbb{Z}_{n}$$, for any $$x$$.

On the other hand, suppose we set $$R = [0, 2^{k} \cdot n]$$ and compute $$x + r$$ over the integers. Then, it is easy to show that any (possibly unbounded) adversary has probability at most $$1/2^{k}$$ of distinguishing a sample from $$R$$ from a sample from $$x + R$$ (the statistical distance between these sets is $$1/2^{k}$$). Since this is a negligible function in $$k$$, this variant satisfies information theoretic security, but not perfect security.

• Thanks, but is it possible to precis this down to a lowly engineer's level of understanding :-) Is $+r$ the superset of $\oplus r$? – Paul Uszak Apr 5 '19 at 12:36
• You mean, what is the set $x + R$? I meant is as a shortcut for the set of all elements of the form $x + r$ for some $r \in R$ (which correspond exactly to the set from which the input of the adversary is randomly sampled in the case $b = 1$). – Geoffroy Couteau Apr 5 '19 at 12:49
• @GeoffroyCouteau I think in cryptography, Information-theoretic security is the same as perfect security. The Information-theoretic security notion in your answer is called statistical security in cryptography. But things may differ in other, e.g. information theory community. – Changyu Dong Apr 5 '19 at 14:02
• But you're right in that there is no official definition which would be universally the same across all fields of science - I only gave the most common use of the term in theoretical cryptography. – Geoffroy Couteau Apr 5 '19 at 14:07
• I agree with Geoffroy. In general, I believe Information-Theoretic Security encompasses both statistical and perfect security. This is essentially the "complement" of Computational Security. – Daniel Apr 8 '19 at 11:56
• 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.

• Okay, so let's dump perfect security as wishful thinking. Inf.theo. = OTP. Comp.sec. = AES. But AES has nothing mathematically 'hard' in it. It's just a bucket load of bits stirred with some polynomials and xors (I'm being flippant). Where does stuff like those algos based on 'hard' maths, eg. prime factorisation, discrete logs and quadratic residuosity fit in? Do they fall into comp.sec too? It feels they should be elsewhere, or at least a sub category. – Paul Uszak Apr 8 '19 at 2:35
• Breaking AES is hard as far as we know, just like factoring products of two uniform-random 1024-bit primes is hard as far as we know. You can write modular exponentiation as a circuit on a bucket load of bits with xors. There's standard computational theorems that if there's a good algorithm to decrypt Rabin ciphertexts, then there's a good algorithm to factor integers. There's a standard computational theorem that if there's a good algorithm to forge Schnorr signatures, then there's a good algorithm to compute discrete logs in the group. – Squeamish Ossifrage Apr 8 '19 at 3:05
• You should read ‘one-time pad’ as a model. The model itself has an information-theoretic theorem, and any short-key instantiation of it like AES-CTR has a computational theorem. The point of the computational theorems is to focus cryptanalytic effort: Cryptanalysts only need fail to break AES or compute discrete logs, in order for us to have confidence that AES-CTR is a secure unauthenticated cipher, or that Schnorr is a secure signature scheme—cryptanalysts need not spend effort studying AES and AES-CTR, or spend effort studying discrete logs and Schnorr signatures. – Squeamish Ossifrage Apr 8 '19 at 3:11
• Skipping the computational theorem doesn't improve security—just pushes the effort around: If, instead of using AES-CTR for your one-time pad, you draw the one-time pad key from some physical process with distribution $D$, then instead of relying on cryptanalysts to have studied AES you're relying on physicists and engineers to have studied the physical process and distribution $D$. Key derivation functions are amazingly resilient to small deviations from uniform in their inputs, so we can use modern cryptography with merely mostly-uniform short keys from hardware RNGs with high confidence. – Squeamish Ossifrage Apr 8 '19 at 3:15