Breaking barriers in secret sharing

In this thesis, we study secret sharing schemes for general (non-threshold) access functions. In a secret sharing scheme for n parties associated to a monotone function [mathematical formula], a dealer distributes shares of a secret among n parties. Any subset of parties [mathematical formula] can jointly reconstruct the secret if F(T) = 1, and should have no information about the secret if F(T) = 0. One of the major long-standing questions in information-theoretic cryptography is to determine the minimum size of the shares in a secret-sharing scheme for an access function F. There is an exponential gap between lower and upper bounds for share size: the best known scheme for general monotone functions has shares of size 2[superscript n-o(n)], while the best lower bound is n² / log(n). In this thesis, we improve this more-than-30-year-old upper bound by construct- ing a secret sharing scheme for any access function with shares of size 2[superscript 0.994n] and a linear secret sharing scheme for any access function with shares of size 2[superscript 0.994n]. As a contribution of independent interest, we also construct a secret sharing scheme with shares of size [mathematical formula] for a family of [mathematical formula] monotone access functions, out of a total of [mathematical formula] of them. As an intermediate result, we construct the first conditional disclosure of secrets (CDS) with sub-exponential communication complexity. CDS is a variant of secret sharing, in which a group of parties want to disclose a secret to a referee the parties' respective inputs satisfy some predicate. The key conceptual contribution of this thesis is a novel connection between secret sharing and CDS, and the notion of (2-server, information-theoretic) private information retrieval.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Liu, Tianren,Ph. D.Massachusetts Institute of Technology.

Advisor dc:contributor.advisor

• Vinod Vaikuntanathan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/124114

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/124114