Information-Theoretic Security Bounds

32 concepts18 papers1 proposal

In cryptography, security is often framed as a computational challenge: an attacker is limited by the time and hardware required to solve a hard mathematical problem. However, a more fundamental perspective exists in information-theoretic security. This approach asks not how long an attacker must compute, but how much information they possess. By applying tools from information theory—such as Shannon entropy, Rényi entropy, and mutual information—researchers can establish absolute limits on what an adversary can achieve, regardless of their computational power.

The Entropy Cost of Authentication

At the heart of secure communication is the ability to verify that a message has not been tampered with. Naor et al. established a fundamental lower bound for this task: to ensure a forgery probability of no more than $\epsilon$, the secret key must have a Shannon entropy of at least $2 \log(1/\epsilon)$ bits. This "doubling" of the security parameter shows that authentication is inherently more "expensive" in terms of entropy than simple encryption.

These limits become more complex when the environment is imperfect or hostile. For instance, Zheng et al. demonstrated that the inherent noise in wireless channels can actually be leveraged to enhance security, deriving matching upper and lower bounds for impersonation attacks in noisy models. In multi-party scenarios where participants might collude, Safavi-Naini and Safavi-Naini used entropy-based measures to quantify the minimum uncertainty required to prevent spoofing, even when an arbiter or transmitter is untrusted.

Bounding Side-Channel Success

Side-channel attacks (SCA) exploit physical leakages—such as power consumption or electromagnetic emanations—to recover secret keys. Rather than analyzing every possible attack strategy, researchers use information theory to bound the Success Rate (SR) of any potential attack.

de Chérisey et al. established universal inequalities that link the probability of an attack's success directly to the mutual information between the physical leakage and the secret key. A key intuition here is information saturation: as an attacker collects more measurements, their total knowledge is strictly capped by the total entropy of the secret key. de Chérisey et al. applied Fano’s inequality to identify the critical threshold where a device becomes reliably exploitable, ensuring that mathematical models do not diverge unrealistically as data volume increases.

For modern "masked" implementations (where secrets are split into multiple shares), Ito et al. derived even tighter bounds by looking at the conditional probability distribution of shares given their leakage. They showed that understanding the exact leakage distribution provides a much more precise security margin than mutual information alone, especially against higher-order attacks.

Guesswork and the Limits of Brute Force

When an attacker tries to guess a password or a key, the standard metric is the number of attempts required, known as guesswork. Christiansen et al. proved that in multi-user systems, the complexity of an optimal guessing strategy is fundamentally tied to Rényi entropy, a generalization of Shannon entropy that better captures the behavior of "one-try" or "few-try" attacks.

The difficulty of guessing changes significantly when the attacker has "side information" (e.g., leaked demographic data or reused passwords). Salamatian et al. explored the difference between centralized and decentralized attacks. They found that if multiple independent agents try to crack a secret, the difficulty reaches a fundamental "floor" determined by the conditional entropy of the noise in their observations. However, if those agents pool their information (a centralized attack), they can bypass this floor and drastically reduce the guesswork required.

Entropy Accounting for Storage and Memory

Information-theoretic bounds also serve as a tool for verifying physical resources. In Proofs of Replicated Storage (PoRep), a server must prove it is dedicating unique space for every copy of a file. Damgård et al. developed an entropy accounting framework to prove this. If the server's total stored state is even slightly smaller than the required replicas, the cumulative loss of information across encoding rounds makes it mathematically impossible for the server to pass a verification challenge without performing infeasible computations.

Similarly, memory-limited attackers face bottlenecks in symmetric encryption. Shahaf et al. used KL divergence to provide an unconditional proof of the Streaming Switching Lemma. They showed that the internal state of a streaming algorithm acts as an information bottleneck; the advantage of an attacker is strictly bounded by the ratio of their queries and memory to the total size of the message space.

Finally, these bounds define the limits of "graceful failure." Naor et al. argued that if the joint min-entropy of a message and its encryption randomness is low, security is physically impossible. In such cases, the best a protocol can do is target "indistinguishability under chosen distribution," acknowledging that brute-force verification becomes an inevitable threat when entropy is exhausted.

Key Foundational Work

A3-Codes under Collusion Attacks (1999) — contributed 2 concept elements to this direction.
Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_information_theoretic_security_bounds_14eedfa3,
  title = {information-theoretic security bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-theoretic-security-bounds/rdr_14eedfa3d5ef49779364fdf48955c2a3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_information_theoretic_security_bounds_14eedfa3_v1,
  title = {information-theoretic security bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-theoretic-security-bounds/rdr_14eedfa3d5ef49779364fdf48955c2a3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake