The Illusion of Absolute Security in Cryptography
There is one intriguing, annoying and painful fact that not many security experts want to see, let alone accept.
Not a single modern cryptographic algorithm is mathematically proved secure.
It sounds flat-out wrong, but it is an undeniable fact. But not as unpleasant as you might think at first glance.
I once dropped this while discussing with a security team and the instant reaction was laughter. Well, I would argue hardly any cryptographer would join them. They would accept that as a simple fact, a fact stated in many books in the area.
Let us dive deeper.
Background
In cryptography there is the, in my opinion unfortunate, concept “provably secure”. I find it unfortunate because I have a mathematical background and I would not use the term “provably” in the sense it is used here.
In mathematics proofs are deduction chains that start from some easy facts we know to be true, then there are deduction rules that we can prove to encapsulate truth in every step. There is an area of mathematics that studies this exact area called logic.
When you prove something, you know for sure it is true. There are texts that use great lengths to provide a definition of a system that we can prove to be truth-preserving. No strings attached.
And then some simple truths can be provided, like 1+1 = 2 (and that proof can be very long).
But in the context of cryptography if something is provably secure, it is provably secure conditionally. The term means that, yes, this method is provably secure IF we assume something. And this difference is a great source of misunderstandings.
Computational intractability
In computer science computation is modelled as a program or machine with an input. A program takes the input, computes, and then returns a value. And as you might guess, some programs run longer that others.
The theory behind this models the phenomenon as formal languages and decision problems. The theory is well-understood and provides us a rich framework studying the computational complexity, i.e. the time needed to solve instances of problems. The area is known as computational complexity theory.
Now, there are problems that we know for-sure are computationally hard, or “intractable”. But, as it happens, these problems are very mathematical and theoretical in nature. They lack some key properties we would need to employ them in cryptography (the key concept here is computational asymmetry).
And therein we face the crux of this post.
There are problems that are used in cryptography.
And these problems are ”usable” in a way that we define later.
But none of these problems is mathematically proved intractable. All we know is that they appear to be intractable. They have been attacked many times and yet no computationally feasible algorithm has been found.
But none is proved intractable.
None.
This does not prove that they are not intractable nor that they are not. We just don’t know. This is the limit of our current understanding.
Reductions and conditional security
I wrote about post-quantum encryption in the Crystals Kyber -series. The algorithm was chosen by NIST as the primary standard to resist quantum computers and it is the spearhead of current post-quantum cryptography.
Kyber applies a variant of the aforementioned LWE-problem (Module LWE) in its encryption scheme. Kyber is in essence built on top of the LWE-problem. The coupling is strong in the sense that Kyber assumes LWE to be intractable and we can prove that if LWE is, indeed, intractable, then Kyber is also. Hence LWE is “usable” in cryptography.
This proof is called a reduction. The core of Kyber reduces to LWE, and now that we can mathematically prove this reduction, Kyber is called provably secure.
Provably secure.
You see it already?
Provably secure shows that breaking the cryptographic scheme is at least as hard as solving the underlying computational problem.
The provably secure is conditionally secure. Fact is, we don’t know if LWE is intractable or not. This is an assumption. A well-founded one, but still an assumption.
The same argument applies to the vast majority of all modern encryption methods. If they are provably secure, it means they are reduced to a problem that we assume intractable.
Assume.
Reduction proofs, hence “provable security”, shows dependency. It does not show proved security. Instead, it makes the underlying assumptions visible and crystal clear.
Empirical evidence
How come we still trust the algorithms even though they are not mathematically proved secure?
This is rather simple. They have been attacked for decades with no success. The empirical evidence is staggering.
The most brilliant minds have worked on these problems for decades with no success. The problems just resist and the evidence slowly piles up. And at some point, the consensus eventually shifts to ”yeah, seems secure, let’s use it”.
The same progress is now ongoing with post-quantum cryptography. We had to come up with new algorithms because we can prove some problems like discrete logarithm become feasible in a quantum computer. Hence the intractability-assumption broke down. This forced the research community to come up with new ideas, and so they did.
Now these ideas are under study and as time goes on, some of them will be picked as the new algorithm for post-quantum-cryptography. It seems unlikely that we could prove them secure in absolute sense, but at some point, the empirical evidence is enough and the trust is gained.
Conclusion
The One-Time Pad is an absolute beast. It is an encryption method that can be proved secure in absolute sense. No assumptions or dependencies. It is secure, period…
..but, unfortunately it is impractical for almost all real-world applications.
The cryptography we can deploy works different. Security is shown partly by reduction proofs, but also with decades of active research.
The key takeaway is that ”provably secure” in cryptography does not prove the algorithm secure. Instead, it surfaces the exact assumption on which the security claim is built on.