Provable security is a mathematical guarantee that a cryptographic protocol satisfies a precisely defined security property under stated assumptions. A cryptographic security game specifies the adversary's observations, permitted queries and success condition. A security reduction transforms an adversary breaking that property into an algorithm solving another problem, such as one covered by a computational hardness assumption. The reduction accounts for both running time and success probability.[ref]
Practice-Oriented Provable-Security by Mihir Bellare. Sections2.2 and3.2, reductions and concrete security
For an original numerical example, suppose a proved reduction givesAn attack with advantage would yield an algorithm with advantage at leastIf the underlying assumption excludes that advantage at 's running time, the scheme attack is excluded too. A larger multiplicative loss would weaken the inference; ignoring the reduction's resource cost could also make the resulting bound uninformative.
The definition matters as much as the deduction. A message authentication code theorem concerns forgery under the specified access model; it does not thereby establish encryption confidentiality. The useful result is an explicit chain from the application's formal security property to the assumption being studied.[ref]
Practice-Oriented Provable-Security by Mihir Bellare. Section4, assumptions, definitions and limitations
Articles by others on the same topic
Provable security is a concept in cryptography that involves the demonstration of the security of cryptographic algorithms and protocols through mathematical proofs. The main idea is to provide formal evidence that a cryptographic system is secure against specific types of attacks under certain assumptions.