Thesis Defense: Itay Berman: Information Theoretic Advances in Zero-Knowledge

Speaker: Itay Berman, MIT

Date: Wednesday, April 24, 2019

Time: 3:00 PM to 4:00 PM

Public: Yes

Location: D507

Event Type:

Room Description:

Host: Vinod Vaikuntanathan (Advisor), Yael Kalai and Ronitt Rubinfeld

Contact: Deborah Goodwin, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: 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.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Deborah Goodwin Email at Monday, April 22, 2019 at 7:27 AM.