Information-Theoretic Security

Open Table of contents

What it is
Goal
Attack Model
Example: One-Time Pad
References

What it is

Information-Theoretic Security is a branch of security in Cryptography that focuses on analyzing cryptographic constructions from a theoretical point of view.

Goal

The main objective of Information-Theoretic Security is to prove (or disprove) that an attacker learns absolutely nothing about a plaintext given its corresponding ciphertext.

This goal results in a binary notion of security as a construction is either secure or not. There’s no “middle ground” or range in which security is measured.

Attack Model

To analyze a construction, one assumes that the attacker has unlimited resources to deploy.

This means that when a secret key is involved, every single key can be tested to see if the ciphertext can be decrypted to the correct plaintext. If even in such an extreme case the attacker doesn’t learn anything about the plaintext given the ciphertext, we can consider the scheme “theoretically impossible” to break.

Example: One-Time Pad

One might think that there can’t be any way that a cryptographic construction provides Information-Theoretic Security due to the unlimited resources an attacker has access to.

How can a scheme be impossible to break if every key can be tested?

As it turns out, there’s one cipher that provides such perfect secrecy: The One-Time Pad.

The One-Time Pad encrypts and decrypts messages by XORing the given message $m$ with a key $k$ that has the same length as $m$ , should be sampled from a uniform distribution and must never be re-used.

Thanks to the properties of the key $k$ , given any ciphertext of length $l$ that is the result of encrypting a plaintext under such key $k$ we can see that the corresponding decryption maps to a plaintext space with all plaintexts of length $l$ being equally likely to be the plaintext that was encrypted under $k$ .

Because of this, even if we can try any possible key to decrypt the ciphertext we won’t be able to know which plaintext the correct one is.

You can read more about the One-Time Pad and why it ensures Information-Theoretic Security in its dedicated article.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.