[FOM] Provable security and foundations of mathematics
Timothy Y. Chow
tchow at math.princeton.edu
Thu Jun 13 14:44:43 EDT 2019
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
More information about the FOM
mailing list