How well is it understood mathematically why encryption schemes are hard to crack?

Question

I have read some intro material into cryptography. It mainly goes into the current encryption schemes like AES, but not very deeply into the mathematics of why they are secure.

I know that encryption is all based on two principles of "confusion" and "diffusion", but these are very general, handwavey principles. I have not read anything like a formal definition of these two principles, and some kind of proof that if an algorithm satisfies them, it is secure by some formally defined metric.

Moreover, I know that it is currently an open problem whether one-way functions exist or not.

I therefore get the impression that there is not really a very formal mathematical underpinning for our trust in the security of encryption schemes, but that may be taking it too far.

So that's why I'm wondering: what is our current formal mathematical understanding of what makes encryption schemes secure?

• Is there a mathematical theory of "hardness of cracking encryption", with something like a formal definition of hardness and proofs that xertain encryption schemes are hard to crack?

  • Are ther partial theories, that formally capture aspects of encryption security but not others?

Answer 1

...I know that encryption is all based on two principles of "confusion" and "diffusion"

Symmetric algorithms such as block ciphers, hash functions, and stream ciphers are based on these principles. One Time Pads are not. And asymmetric algorithms are not built from these principles, though they may end up possessing them anyways.

... but these are very general, handwavey principles

Actually, diffusion is pretty well defined. There is the avalanche effect, which says that flipping one input bit should result in approximately one-half of the output bits being flipped. There is also the notion of branch number.

"Confusion" is a bit more nebulously defined, although there do exist s-boxes that are known to provide optimal stats against known cryptanalytic techniques.

So that's why I'm wondering: what is our current formal mathematical understanding of what makes encryption schemes secure?

You'll have three different answers, depending on whether or not you're talking about One Time Pads, symmetric ciphers, or public-key encryption.

One Time Pads

One Time Pads are information-theoretically secure, which means that no computational algorithm operating on the ciphertext can help you to learn anything more about the plaintext than what you already know, irrespective of advances in computational power or clever algorithms

Unfortunately, they are too cumbersome to use in practice

Symmetric ciphers

A good symmetric cipher is designed to resist all known attacks, such as linear and differential cryptanalysis.

However, "all known" attacks is certainly not a formal proof that no (publicly) unknown attacks exist that could break a given algorithm.

Proving that an algorithm is computationally secure means a proof that breaking the algorithm implies the ability to break a problem that is known to be hard. No typical block ciphers carry proofs of this sort.

That does not mean they carry no proofs at all. For example, AES has proofs for resistance against known attacks.

Asymmetric algorithms

Asymmetric algorithms are built from problems that are assumed to be hard.

"Assumed to be" might seem unsatisfactory; Unfortunately, that's the best anyone can do until the $\text{P}$ versus $\text{NP}$ debate is proven one way or the other.

This is a major open problem in the world of computer science: If you solve it, you can claim a $1,000,000 prize (and most likely a place as a legend in the history of science and mathematics too).

If $\text{P} \neq \text{NP}$, which is what many people believe to be the case, then cryptosystems built from problems in NP would be secure.

If $\text{P} = \text{NP}$, then it is not necessarily the case that all cryptosystems would be insecure in practice. Such a proof might:

• Only prove the relationship between the problem classes, without actually constructing an algorithm that solves $\text{NP}$ problems in polynomial time.
• Even if such a proof were constructive and included such a polynomial time algorithm, the running time of that algorithm could still be something like $O(n^{1000})$, which would be unhelpful for solving such problems in the real world.

Impagliazzo's Five Worlds

For more on how things would be depending on the $\text{P}$ versus $\text{NP}$ question, you might check out Impagliazzo's Five Worlds. It details what type of world we would live in depending on which relationship is true.