What you are saying was true until this February when this paper came out https://eprint.iacr.org/2016/170

It hadn't been implemented yet I'm any practical crypto system that I know of, buy it certainly seems like we are finally going to have actually, provably hard problems to build out security om.

I believe you made an unfortunate typo, substituting "probably" when you meant "provably".

Even auto correct finds it surprising :-)

The scheme in this paper is in the bounded-storage model...

It says you either have to use exponential time or quadratic storage. Schemes based on high memory requirements have actually been sought for a while, since (apparently) memory is considered less scalable than computation.

No, I mean your original comment is inaccurate. The paper presents a time-space lower bound for parity learning, but the encryption scheme based on this result is only 'unconditionally secure' in a model where the adversary is restricted to having at most (n^2)/25 bits of storage. This isn't a general-purpose unconditionally secure encryption scheme, which is what your original comment implied.

All proofs have axioms if you chase them all the way down. Given the axiom that the solving the math in the crypto is intractable, the crypto algorithm is proven secure. But only so long as the axiom holds.

For example, quantum computing may break the axiom, and then the proof will be invalidated.

It might be more correct to say assumption rather than axiom here.

It looks like probably secure is defined in cryptography to mean breaking the algorithm is equivalent to solving the underlying intractable problem [0]. In my mind provably secure meant that the problem was actually intractable (which is not the convention).

0. https://en.wikipedia.org/wiki/Provable_security

That is the conventional meaning of 'provably secure' in every text and research paper on modern cryptography.

You're falling victim to the same misconception. It is not a contradiction to say both that a cryptographic scheme is provably secure and that its security relies on a conjecture about the hardness of a computational problem.

If the conjecture turns out to be false, is the scheme still secure?

If so - interesting, how does that work?

If not - then doesn't that mean it's not probably secure?

Ehhhh.... well, it's complicated. For most cryptosystems, the answer is no, because if you can solve the underlying problem efficiently you can break the security of the scheme as defined. It turns out that this isn't always a 'break' in the sense that most people understand it. For example, a 'break' might just mean the ciphertext is no longer indistinguishable from random noise, but it might be possible to prove meaningful security in a weakened model that doesn't require ciphertexts to look like random noise but, for example, requires that no bits of the plaintext are leaked with high probability. Cryptographers build schemes with very strong, conservative security guarantees for this exact reason.