Provable security
= Provable security
\b[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.<Practice-Oriented Provable-Security by Mihir Bellare>[Sections2.2 and3.2, reductions and concrete security]{ref}
For an original numerical example, suppose a proved reduction gives
$$
\operatorname{Adv}_{\mathrm{scheme}}(A)
\leq 2\operatorname{Adv}_{\mathrm{primitive}}(B)+10^{-4}.
$$
An attack with advantage $0.01$ would yield an algorithm $B$ with advantage at least
$$
\frac{0.01-0.0001}{2}=0.00495.
$$
If the underlying assumption excludes that advantage at $B$'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.<Practice-Oriented Provable-Security by Mihir Bellare>[Section4, assumptions, definitions and limitations]{ref}