There is one public key system that is pretty much that, it's called Merkle Puzzles. It's kind of non-practical though. No one has found a system that is pra

There is one public key system that is pretty much that, it's called Merkle Puzzles. It's kind of non-practical though. No one has found a system that is practical and provably secure. You need the right kind of problem. Pretty much all the problems we have today that can be used for public key cryptography are thought to be hard but can't be proved to be hard. Under the assumption they are hard the system is proved to be secure. Symmetric cryptography (e.g. AES) is in a slightly different boat but again security proofs are based on assumptions about the function used and I don't think anyone has found a function that is provably secure (but there are various constructions that are used that have some provable characteristics). Also under some base security assumption there are further constructions of ciphers that can be proved secure.