Thesis Defense: Itay Berman: Information Theoretic Advances in Zero-Knowledge
Speaker
Itay Berman, MIT
Host
Vinod Vaikuntanathan (Advisor), Yael Kalai and Ronitt Rubinfeld
Abstract:
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, 2003]) and entropy difference�(Goldreich and Vadhan [CCC, 1999]) 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. 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.�
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, 2003]) and entropy difference�(Goldreich and Vadhan [CCC, 1999]) 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. 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.�