Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-052 | 12th April 2021 13:03

Upslices, Downslices, and Secret-Sharing with Complexity of 1.5^n

RSS-Feed




TR21-052
Authors: Benny Applebaum, Oded Nir
Publication: 12th April 2021 20:17
Downloads: 740
Keywords: 


Abstract:

A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about s.
The collection of authorized/unauthorized sets can be captured by a monotone function f:\{0,1\}^n\rightarrow \{0,1\}.
In this paper, we focus on monotone functions that all their min-terms are sets of size a, and on their duals -- monotone functions whose max-terms are of size b. We refer to these classes as (a,n)-upslices and (b,n)-downslices, and note that these natural families correspond to monotone a-regular DNFs and monotone (n-b)-regular CNFs. We derive the following results.

1. (General downslices) Every downslice can be realized with total share size of 1.5^{n+o(n)}<2^{0.585 n}. Since every monotone function can be cheaply decomposed into n downslices, we obtain a similar result for general access structures improving the previously known 2^{0.637n+o(n)} complexity of Applebaum, Beimel, Nir and Peter (STOC 2020). We also achieve a minor improvement in the exponent of linear secrets sharing schemes.

2. (Random mixture of upslices) Following Beimel and Farras (TCC 2020) who studied the complexity of random DNFs with constant-size terms, we consider the following general distribution F over monotone DNFs: For each width value a\in [n], uniformly sample k_a monotone terms of size a, where k=(k_1,\ldots,k_n) is an arbitrary vector of non-negative integers. We show that, except with exponentially small probability, F can be realized with share size of 2^{0.5 n+o(n)} and
can be linearly realized with an exponent strictly smaller than 2/3. Our proof also provides a candidate distribution for ``exponentially-hard'' access structure.

We use our results to explore connections between several seemingly unrelated questions about the complexity of secret-sharing schemes such as worst-case vs. average-case, linear vs. non-linear and primal vs. dual access structures. We prove that, in at least one of these settings, there is a significant gap in secret-sharing complexity.



ISSN 1433-8092 | Imprint