Why haven't we proven many things computationally secure yet?

Question

Brute Force is infeasible for just about every algorithm we use today. Yet, attacks are feasible. This is because weaknesses keep coming up in our algorithms. Why?

We have proven lower bounds for things like sorts, the information security of things like OTP and Shamir's Secret Sharing, proven many problems as hard as any that can be checked in polynomial time (NP-complete), yet we haven't proven anything computationally secure.

Like, we can say that "if this assumption holds, this is secure" but the assumptions are obvious or definitional, like you would expect from axioms, but conjectures that are introduced just so they can be used to prove stuff, and are not in anyway self-evident. Are trust for them goes as far as "a bunch of people have tried to break it, but haven't." As far as I know, we don't even have many cryptographic algorithms for which breaking is NP-Complete.

Why is computational security so hard to prove? Why don't we have any, say, public-private key system that is NP complete to break?

Answer 1

I think @CortAmmon hit the nail on the head: cryptographic structures (hashes, ciphers, etc) are specifically designed to be hard for bad guys to analyse / reverse / find patterns in. It should come as no surprise that this is a double-edged sword: they are also hard for good guys to analyse in the form of mathematical proofs.

As @CortAmmon said: historically, conjectures in geometry and number theory often stood as open problems for hundreds of years before being either proven or disproven. The cannonical example of this is Fermat's Last Theorem which took 358 years, and the development of several new branches of mathematics, to solve.

Due to the nature of cryptography (hiding information inside structure with no discernible pattern), it contains some of the hardest conjectures in all of mathematics. It should not come as a surprise that in the mere 50 years that we have been studying modern cryptography (a spec in the history of mathematics), we still have open problems.

I'll give a few concrete examples:

1. As far as I know, it is an open problem whether hashes in the SHA family are surjective - ie does every possible string in the output space get mapped to? Why do we not know this? Because hash functions are intentionally hard to analyse.

2. Many cryptographic schemes do have formal proofs of security. For example, the 1979 paper by Merkle describing a hash-based signature scheme is full of proofs that the signature scheme is as strong as the underlying hash function. It turns out that despite understanding the security of Merkle-signatures very well, we didn't like the idea of huge, slow signatures, so opted for faster / smaller algorithms that are more mathematically complex and we don't understand as well.

3. As an example: Lattice-based cryptography is one of the leading candidates for quantum-resistant encryption. Steven Galbraith recently gave a talk at the PQCrypto2016 conference where he listed all the branches of mathematics that are involved in understanding lattice-based schemes. He estimated that there are about a dozen people on the planet who are experts in all of those areas of mathematics. How can you hope to find subtle and complex weaknesses when there are so few experts working on the problem?

Bottom line: Math is hard, cryptographic algorithms are specifically designed to be hard to analyse, and modern cryptography is still very young in the history of mathematics.

Answer 2

Why don't we have any, say, public-private key system that is NP complete to break?

$\mathbf{NP}$-completeness is not the appropriate framework to think about the "security" of an encryption scheme, both in theory and in practice. Remember that the complexity classes $\mathbf{P}$, $\mathbf{NP}$, et al. are classes of decision problems, which are basically questions whose answer is "yes" or "no". The problem of "breaking" an encryption scheme certainly does not fall within this category.

In the theory world, the main assumption underlying the whole theoretical cryptography edifice is not $\mathbf{P} \ne \mathbf{NP}$, it is the existence of one-way functions, which is a stronger assumption (i.e., the existence of one-way functions would imply $\mathbf{P} \ne \mathbf{NP}$, but not the other way around). It has been shown that the existence of one-way functions, and not $\mathbf{P} \ne \mathbf{NP}$, is necessary for the most common computationally secure cryptography (including encryption and signatures), and also sufficient for much of it (up to and including CPA-secure symmetric encryption schemes). In the practice world, attempts made to base the security of cryptosystems on $\mathbf{NP}$-complete problems have failed (see for example the 1978 Knapsack cryptosystem of Merkle and Hellman).

In both the theoretical and practical cases, the problem is that the classes $\mathbf{P}$, $\mathbf{NP}$, et al. refer to worst-case hardness. In order for a problem to be $\mathbf{NP}$-hard, it is sufficient for it to have only one $\mathbf{NP}$-hard instance. In cryptographic terms, this would mean that there exists only one key which makes the system hard to break: the system can be easy to break for all the other keys. This is obviously unsatisfactory for cryptography: we require that many hard instances exist, and also that they be easy to generate. Both theoretical and practical cryptography have developed around those ideas, using tools such as one-way functions, trapdoor permutations, etc. (with varying definitions).

Answer 3

The answers and comments so far provide very thorough insight about why concepts in crypto are hard to prove or analyze. However, I think there is still room for tackling another side of your question. Beyond the specific challenge of proving the information theoretical security of a primitive, your question is why does crypto fail?

In my experience, there is a huge gap between theory and practice in information security, and particularly when cryptography gets involved. Sure, there are libraries and products designed thoroughly, with the best intentions and the best knowledge, but the fact remains that bad crypto is implemented around critical systems all the time (to see how bad it can get, http://www.cryptofails.com/ has some terrible cases documented). I have seen people dubbing Base64 encoding as "64 bit encryption", and just some minutes ago a question here asked for a broad comparison between AES and HMAC (whereas they are not equivalent primitives in any sense).

And that's not their fault, as they are likely skilled developers, but an indicator that cryptography has a huge learning curve to be used properly (even if supported by "flawless" implementations of the primitives) and has a lot of nuances that can lead to a buggy implementation (if you see the code that lead to Apple's goto fail, the culprit is a single and apparently harmless line of code).

So, to summarize my main point, information theoretical security proofs are an essential starting point, but a lot can go wrong from there.

As for the "but the assumptions are obvious or definitional", you might want to take a look to the paradigm shift that would be implied by quantum computing. Factoring the product of large primes is hard now, and probably will be then, in the sense that it won't suddenly become trivial, but it might not be hard enough to be used as the base for cryptographic operations. The assumptions are good because they have held so far, and are likely to hold given the status quo, but might not hold at some point, and then the proof crumbles.

Answer 4

The answers are very different for protocols vs. non-interactive algorithms.

Basic Algorithms:

We don't know any way of proving super-quadratic lower bounds for "natural" PSPACE problems.
I'm quite confident that ​ ​ ​ P-uniform TC⁰ ​ =?= ​ almost-PSPACE ​ ​ ​ is open,
and am pretty sure that ​ ​ ​ logspace-uniform TC⁰ ​ =?= ​ PP ​ ​ ​ is also open.
Additionally, there are obstacles to showing that ​ P ≠ NP ​ implies the existence of one-way functions.


Also, most computational cryptography (whether protocols or non-interactive algorithms) requires (at least) one-way functions. ​ (The link I gave 2 sentence ago describes an example that might not.)


"Easy" protocol tasks, like [key agreement in which at most one party provides a password] - these tend to be the ones for which the definition of security will be automatically satisfied when there's only 1 honest party:

We can put together protocols with a proof that breaking them implies breaking their basic algorithms, but [protocols for which it's merely the case that no one has yet publicly worked out how to break them] are entrenched.


"Hard" protocol tasks, like PAKE or [[commitment schemes or multi-party computation protocols] that aim to preserve security when more than one of the protocol is being run concurrently]:

No authentication is available to restrict the adversary's ability to mix messages between different runs of the protocol.