What conditions does a provable secure cryptosystem satisfy? A cryptosystem can be entirely dependent on its underlying problem or it can have a reduction to other known problems. Solvability can be affordable if there exists a reduction of the base problem to another problem, and the last is feasible.

I understand that a cryptosystem is provable secure if it has been well studied during years giving rigorous proofs on:


Cryptanalysis. By analyzing the base problem with existing techniques, measuring complexity (computational hardness), attempting to reduce to an affordable/easier problem.
Implementation. There is an efficient way to describe the cryptosystem in a resource bounded device, where security must be achieved.
Future expectation. Security facts based on theoretical cryptanalytic techniques, where the application of these methods is not feasible nowadays but theorized in the future.


Q: Is there any other condition for a cryptosystem to be stated as provable secure?

Q: Provable secure is not the same as probable secure. Does this last term has a broader definition in Cryptography?

Example, in maths a probable prime it's a pseudoprime (prime with probability threshold). And a provable prime is a prime that has been proved to be prime (i.e satisfies Fermat test and is not a Carmichael Number).
Provably secure doesn't actually mean secure. Plenty of provably secure cryptosystems were broken and not because the proof had a flaw. When something is provably secure, it just meant some statement regarding it's security has been proven. There are any number of such statements.

A proof always starts off with some assumptions, such as the hardness of some underlying problem, or security property of some building block. A statement about something else can then be build on top of those assumptions. But when that statement is formalized, it is never as broad as: "$X$ is secure".  Instead the statement would be a more specific statement such as: "If you can invert $F$ you can also invert $G$, but $G$ is believed to be hard to invert. In this protocol under such and such assumption an attacker learns nothing more then he knew initially."



WPA is provably secure. They went all out on this proof. It was not just proven that the specification was secure in that no key material could leak. The implementation was proven to match the specification and the compiler was proven to work correctly.

And yet WPA was horribly broken. The proof didn't say anything about an attacker being able to coerce an all zero key. The attacker learned nothing, the security proof was not violated.



Provably secure does not imply Secure. It implies only whichever claims were actually proven.