Black-box non-black-box zero-knowledge via extendable Merkle tree

Speaker: Alessandra Scafuro , UCLA

Date: Friday, January 24, 2014

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan, CIS, TOC, CSAIL, MIT

Contact: Holly A Jones,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: CIS Seminar

Abstract: Can we have a black-box protocol with a non-black-box proof?

We know black-box protocols for many fundamental tasks (zero-knowledge, MPC, etc.) which can be proven by black-box proofs (i.e., the simulator uses the adversary as a black-box). However, there are as many fundamental tasks (const. round concurrent ZK, concurrent MPC, sim-res ZK, etc.) that only admit non-black-box proofs, i.e. the simulator needs to use the code of the adversary. For the majority of such tasks we only know implementation based on the celebrated Barak's technique for non-black-box simulation. Implementing Barak's technique require that even cryptographic primitives (specifically, the hash function) are used in a non-black-box manner.

Is this inherent? Can we implement Barak's technique with a black-box protocol?

The crux of the difficulty is to hide the size of the witness (which cannot be a-priori bounded by any polynomial) without using the code of the hash function. In other words, how to build succinct proofs that are also black-box.

In this work we introduce a novel way of building a Merkle tree -- that we call extendable Merkle tree-- which allows for succinct and black-box proofs of committed values. Succinct black-box proofs along with PCP of Proximity, allow us to provide a black-box implementation of Barak's protocol. Additionally, we show that the extendable Merkle tree is interesting on its own right, as one can construct generalized black-box Zero-Knowledge sets.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security Seminar Seminars Fall 2013 / Spring 2014.

Created by Holly A Jones Email at Wednesday, January 15, 2014 at 4:09 PM.