A precise computational approach to knowledge

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). In this thesis, 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.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Pass, Rafael (Rafael Nat Josef)

Advisor dc:contributor.advisor

• Silvio Micali.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/38303

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/38303