Thesis Defense: Itay Berman: Information Theoretic Advances in Zero-Knowledge
Itay Berman, MIT
Date: Wednesday, April 24, 2019
Time: 3:00 PM to 4:00 PM
Host: Vinod Vaikuntanathan (Advisor), Yael Kalai and Ronitt Rubinfeld
Contact: Deborah Goodwin, 617.324.7303, firstname.lastname@example.org
Speaker URL: None
TALK: Thesis Defense: Itay Berman: Information Theoretic Advances in Zero-Knowledge
Zero-knowledge proofs have an intimate relation to notions from informationtheory. In particular, the class of all problems possessing statisticalzero-knowledge proofs (SZK) was shown to have complete problems characterized bythe statistical distance (Sahai and Vadhan [JACM, 2003]) and entropy difference(Goldreich and Vadhan [CCC, 1999]) of a pair of efficiently samplabledistributions. This characterization has been extremely beneficial inunderstanding the computational complexity of languages with zero-knowledgeproofs and deriving new applications from such languages.In this thesis, we further study the relation between zero-knowledge proofs andinformation theory. Our main results are:1. Two additional complete problems for SZK characterized by other information theoretic notions---triangular discrimination and Jensen-Shannon divergence. These new complete problems further expand the regime of parameters for which the Statistical Difference Problem is complete for SZK.2. The hardness of a problem related to the non-interactive variant of the Entropy Difference Problem implies the existence of a useful cryptographic primitive called multi-collision resistant hash functions (MCRH).3. We initiate the study of zero-knowledge in the model of interactive proofs of proximity (IPP). We show efficient zero-knowledge IPPs for several problems. We also show that not every efficient IPP can be made zero-knowledge.
Created by Deborah Goodwin at Monday, April 22, 2019 at 7:27 AM.