Abstract
Abstract:
The seminal
work of Goldwasser, Micali
and Rackoff put forward a computational approach to
knowledge in interactive systems, providing the foundation of modern
Cryptography. Their notion bounds the knowledge of a player in terms of his
potential computational power (technically defined as polynomial-time
computation).
We put
forward a stronger notion that precisely bounds the knowledge gained by a
player in an interaction in
terms of the actual computation he has performed (which can be considerably
less than any arbitrary polynomial-time computation).
Our
approach not only remains valid even if P= NP, but is most meaningful when
modeling knowledge of computationally easy properties. As such, it broadens the
applicability of Cryptography and weakens the complexity theoretic assumptions
on which Cryptography can be based.
Joint work with Silvio Micali.