## CryptoDB

### Amos Beimel

#### Affiliation: Ben-Gurion University

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

Secret-Sharing Schemes for General and Uniform Access Structures
📺
Abstract

A secret-sharing scheme allows some authorized sets of parties to reconstruct a secret; the collection of authorized sets is called the access structure. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $$2^{n-o(n)}$$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $$O(2^{0.994n})$$. Our first contribution is improving the exponent of secret sharing down to 0.892. For the special case of linear secret-sharing schemes, we get an exponent of 0.942 (compared to 0.999 of Liu and Vaikuntanathan).Motivated by the construction of Liu and Vaikuntanathan, we study secret-sharing schemes for uniform access structures. An access structure is k-uniform if all sets of size larger than k are authorized, all sets of size smaller than k are unauthorized, and each set of size k can be either authorized or unauthorized. The construction of Liu and Vaikuntanathan starts from protocols for conditional disclosure of secrets, constructs secret-sharing schemes for uniform access structures from them, and combines these schemes in order to obtain secret-sharing schemes for general access structures. Our second contribution in this paper is constructions of secret-sharing schemes for uniform access structures. We achieve the following results:A secret-sharing scheme for k-uniform access structures for large secrets in which the share size is $$O(k^2)$$ times the size of the secret.A linear secret-sharing scheme for k-uniform access structures for a binary secret in which the share size is $$\tilde{O}(2^{h(k/n)n/2})$$ (where h is the binary entropy function). By counting arguments, this construction is optimal (up to polynomial factors).A secret-sharing scheme for k-uniform access structures for a binary secret in which the share size is $$2^{\tilde{O}(\sqrt{k \log n})}$$.
Our third contribution is a construction of ad-hoc PSM protocols, i.e., PSM protocols in which only a subset of the parties will compute a function on their inputs. This result is based on ideas we used in the construction of secret-sharing schemes for k-uniform access structures for a binary secret.

2018

ASIACRYPT

Optimal Linear Multiparty Conditional Disclosure of Secrets Protocols
Abstract

In a k-party CDS protocol, each party sends one message to a referee (without seeing the other messages) such that the referee will learn a secret held by the parties if and only if the inputs of the parties satisfy some condition (e.g., if the inputs are all equal). This simple primitive is used to construct attribute based encryption, symmetrically-private information retrieval, priced oblivious transfer, and secret-sharing schemes for any access structure. Motivated by these applications, CDS protocols have been recently studied in many papers.In this work, we study linear CDS protocols, where each of the messages of the parties is a linear function of the secret and random elements taken from some finite field. Linearity is an important property of CDS protocols as many applications of CDS protocols required it.Our main result is a construction of linear k-party CDS protocols for an arbitrary function $$f:[N]^{k}\rightarrow \left\{ 0,1 \right\} $$ with messages of size $$O(N^{(k-1)/2})$$ (a similar result was independently and in parallel proven by Liu et al. [27]). By a lower bound of Beimel et al. [TCC 2017], this message size is optimal. We also consider functions with few inputs that return 1, and design more efficient CDS protocols for them.CDS protocols can be used to construct secret-sharing schemes for uniform access structures, where for some k all sets of size less than k are unauthorized, all sets of size greater than k are authorized, and each set of size k can be either authorized or unauthorized. We show that our results imply that every k-uniform access structure with n parties can be realized by a linear secret-sharing scheme with share size $$\min \left\{ (O(n/k))^{(k-1)/2},O(n \cdot 2^{n/2}) \right\} $$. Furthermore, the linear k-party CDS protocol with messages of size $$O(N^{(k-1)/2})$$ was recently used by Liu and Vaikuntanathan [STOC 2018] to construct a linear secret-sharing scheme with share size $$O(2^{0.999n})$$ for any n-party access structure.

2011

CRYPTO

2004

JOFC

2001

EPRINT

On the Power of Nonlinear Secret-Sharing
Abstract

A secret-sharing scheme enables a dealer to distribute a secret
among n parties such that only some predefined authorized sets of
parties will be able to reconstruct the secret from their shares.
The (monotone) collection of authorized sets is called an access
structure, and is freely identified with its characteristic monotone
function f:{0,1}^n --> {0,1}. A family of secret-sharing schemes is
called efficient if the total length of the n shares is polynomial
in n. Most previously known secret-sharing schemes belonged to a
class of linear schemes, whose complexity coincides with the
monotone span program size of their access structure. Prior to this
work there was no evidence that nonlinear schemes can be
significantly more efficient than linear schemes, and in particular
there were no candidates for schemes efficiently realizing access
structures which do not lie in NC.
The main contribution of this work is the construction of two
efficient nonlinear schemes:
(1) A scheme with perfect privacy whose access structure is
conjectured not to lie in NC;
(2) A scheme with statistical privacy whose access structure is
conjectured not to lie in P/poly.
Another contribution is the study of a class of nonlinear schemes,
termed quasi-linear schemes, obtained by composing linear schemes
over different fields. We show that while these schemes are possibly
(super-polynomially) more powerful than linear schemes, they cannot
efficiently realize access structures outside NC.

2000

CRYPTO

#### Program Committees

- Eurocrypt 2019
- TCC 2018 (Program chair)
- TCC 2018
- TCC 2016
- TCC 2014
- TCC 2012
- TCC 2010
- Crypto 2010
- Crypto 2007
- PKC 2006
- TCC 2005
- Crypto 2005

#### Coauthors

- Benny Applebaum (1)
- Gilad Asharov (1)
- Aner Ben-Efraim (1)
- Benny Chor (3)
- Shlomi Dolev (1)
- Oriol Farràs (4)
- Matthew K. Franklin (1)
- Ariel Gabizon (1)
- Renen Hallak (1)
- Yuval Ishai (6)
- Shiva Prasad Kasiviswanathan (1)
- Ranjit Kumaresan (1)
- Eyal Kushilevitz (4)
- Yehuda Lindell (1)
- Noam Livne (2)
- Nikolaos Makriyannis (1)
- Tal Malkin (6)
- Sigurd Meldgaard (1)
- Silvio Micali (1)
- Yuval Mintz (3)
- Oded Nir (1)
- Pnina Nissim (1)
- Kobbi Nissim (5)
- Eran Omri (5)
- Ilan Orlov (4)
- Carles Padró (2)
- Anat Paskin-Cherniavsky (1)
- Naty Peter (3)
- Yoav Stahl (1)
- Tamir Tassa (1)
- Ilya Tyomkin (1)
- Enav Weinreb (3)