[FOM] Provable security and foundations of mathematics

[Timothy Y. Chow]

On Thu, 13 Jun 2019, José Manuel Rodríguez Caballero wrote:
>       For mathematicians who study the provable security literature,
>       as Menezes and I did, there are several reasons to be uneasy.
>       Most obviously, a provable security theorem applies only to
>       attacks of a specified sort and says nothing about clever
>       attacks that might not be included in the theorem. 
>  
> So, my descriptive question:
>
>       whether or not provable security can be reduced to foundations
>       of mathematics. 
> 
> can be reformulated in a constructive way as follows:
> 
> Could be possible to find a security definition in ZFC which includes 
> all possible security definitions?

There are two very general reasons why I don't think this is a very 
productive question to think about.

1. One type of "clever attack" is to bribe or blackmail someone who knows 
the secret information into divulging the secret.  You might think that 
this is silly, but it illustrates the point that any purely mathematical 
approach will necessarily exclude some kinds of attacks that are very 
important in the real world.  For another example of a type of attack that 
is very difficult to completely mathematize, consider attacks that exploit 
the physical characteristics (power usage, timing, etc.) of an 
implementation of the algorithm.  "All possible attacks" would presumably 
include attacks that exploit physical theories of the future that 
are currently unknown.  What if parapsychology turns out to be true and it 
is possible to manipulate cryptologics telekinetically?

2. Supposing you did find a security definition which "includes all 
possible security definitions."  Given the woeful current state of our 
ability to prove unconditional lower bounds on computational complexity, 
we would clearly be unable to prove any interesting unconditional results 
about such a definition.

Tim