Secret Sharing: Linear vs. Nonlinear Schemes

Amos Beimel
Ben Gurion University of the Negev

A secret sharing scheme enables a dealer to share a secret among a set of parties such that only some predefined authorized subsets will be able to reconstruct the secret from their shares. Such schemes enables the storage
of sensitive data in environments where not all participants are fully trusted. Originally motivated by the problem of secure information storage, secret-sharing schemes have found numerous other applications in cryptography and distributed computing. Most of the known secret sharing schemes are linear. Furthermore, linearity is a desirable property for many
applications such as secure computation. Interestingly, the power of linear secret sharing schemes is captured by a computational model called monotone span programs.

In this talk I will describe basic results and constructions of secret sharing schemes, discuss the properties of linear secret sharing
schemes and their limitations, and present examples of non-linear schemes.

Audio (MP3 File, Podcast Ready) Presentation (PowerPoint File)

Back to Workshop II: Locally decodable codes, private information retrieval, privacy-preserving data-mining, and public key encryption with special properties