Why haven't we proven many things computationally secure yet? 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?
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:


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.
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.
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.