On the term "provable security" (by Oded Goldreich)


[Revised extract from "a side comment on terminology" in On Post-Modern Cryptography, 2006]

In my opinion, within the domain of the rigorous analysis methodology of Cryptography, the term "provable security" is quite odd and rather inappropriate. Let us elaborate.

Security (according to a specific definition) is a property that some systems may have. In the domain of science, statements are either valid or invalid, and their state of validity can be either known or unknown. Saying that the validity of a statement is known means that the validity can be established based on the accepted methodology of the relevant discipline. Thus, within the domain of a rigorous analysis of cryptography, the term "provable security" (and in general "provable property") makes no sense; that is, the adjective "provable" adds nothing to the claim of security (assuming that the claim is valid, and it cannot be applied if the claim is invalid or unknown to be valid).

Indeed, qualifying a noun by an adjective that adds nothing to it is peculiar, but more importantly it may only cause confusion. Specifically, saying that "X is provable secure" suggests that it is legitimate (within the discipline) to claim that "X is secure" without being able to establish this claim by using the methodology that is acceptable in the discipline. (Needless to say, no scientific discipline allows such a situation. In particular, within the domain of the rigorous analysis methodology of cryptography, if one believes that "X is secure" but cannot establish this fact, then one should state "X is secure" as a conjecture.)


Addendum (2006): My attitude towards this issue is examplified in the following extract from an email correspondence.

[My correspondent was complaining on SICOMP's proof-editors saying:]
Once they changed "provably secure" to "probably secure" :-)

[To this I replied:]
They are right in being confused at such a stupidity. Actually, their guess shows good scientific understanding. What the hell can "provably secure" mean??? If something is secure, what does provability add? By definition, any (non-false) technical claim is either provable or a conjecture. Since the former is default (and thus mentioning it is redundant), they just assumed that the latter was meant....


Back to Oded's list of essays or to Oded's homepage.