- Towards Breaking the Expone...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in September 2017

## 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

**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:**

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