Towards Breaking the Exponential Barrier for General Secret Sharing

Speaker: Tianren Liu , MIT CSAIL

Date: Friday, September 29, 2017

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

Public: Yes

Location: 32-G882

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan, MIT CSAIL

Contact: Nardos Abbay, nardos@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Towards Breaking the Exponential Barrier for General Secret Sharing

Abstract: A non-monotone secret-sharing scheme for a Boolean (access) function F: {0,1}^n to {0,1} is a randomized algorithm that on input a secret, output n pairs of shares s_{1,0},s_{1,1},...,s_{n,0},s_{n,1} such that for any x_1,...,x_n, the n shares s_{1,x_1},...,s_{n,x_n} determine the secret if F(x_1,...,x_n)=1 and reveal nothing about the secret otherwise. Standard monotone secret-sharing correspond to the special case where F is monotone and s_{1,0} = ... = s_{n,0} = \bot.

The best secret sharing schemes for general functions (in both the monotone and non-monotone case) have shares of size \Omega(2^n). It has long been conjectured that one cannot do much better, namely, that there are access functions for which any secret sharing scheme necessarily has shares of size 2^{\Omega(n)}.

In this work, we show non-monotone secret sharing schemes for every access function F with shares of size 2^{O(\sqrt(n) log n)}, disproving the conjecture for non-monotone secret sharing schemes. Our technique uses a new notion of decomposable matching vector (DMV) families as well as new constructions of DMV families. Matching vector families are combinatorial objects that have previously been used in circuit complexity, in construction of Ramsey graphs and in private information retrieval (PIR) protocols.

Along the way, we also construct the first two-party and multi-party conditional disclosure of secrets (CDS) protocols for general functions with communication complexity 2^{O(\sqrt(n) log n)}.

Joint works with Vinod Vaikuntanathan and Hoeteck Wee.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Seminar (CIS) 2017.

Created by Nardos Abbay at Wednesday, September 20, 2017 at 5:10 PM.