Information theoretic advances in zero-knowledge

Zero-knowledge proofs have an intimate relation to notions from information theory. In particular, the class of all problems possessing statistical zero-knowledge proofs (SZK) was shown to have complete problems characterized by the statistical distance (Sahai and Vadhan [JACM, 20031) and entropy difference (Goldreich and Vadhan [CCC, 19991) of a pair of efficiently samplable distributions. This characterization has been extremely beneficial in understanding the computational complexity of languages with zero-knowledge proofs and deriving new applications from such languages. In this thesis, we further study the relation between zero-knowledge proofs and information theory. We show the following results: 1. Two additional complete problems for SZK characterized by other information theoretic notions-triangular discrimination and Jensen-Shannon divergence.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

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

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Berman, Itay.

Advisor dc:contributor.advisor

• Vinod Vaikuntanathan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

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

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/122725

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/122725