Precise Zero Knowledge
Silvio Micali, Rafael Pass · 2011
We put forward the notion of Precise Zero Knowledge and provide its first implementations in a variety of settings under standard complexity assumptions. Whereas the classical notion of Zero Knowledge bounds the knowledge of a player in terms of his potential computational power (technically defined as polynomial-time computation), Precise Zero Knowledge bounds the knowledge gained by a player in terms of its actual computation (which can be considerably less than any arbitrary polynomial-time computation). Consequently, our approach not only remains valid even if P = NP, but is most meaningful when modeling knowledge of computationally easy properties.