Paper 2021/470

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

Benny Applebaum and Oded Nir

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\to \{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 $$. Since every monotone function can be cheaply decomposed into $$ downslices, we obtain a similar result for general access structures improving the previously known $$ 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 $$ over monotone DNFs: For each width value $$, uniformly sample $$ monotone terms of size $$, where $$ is an arbitrary vector of non-negative integers. We show that, except with exponentially small probability, $$ can be realized with share size of $$ and can be linearly realized with an exponent strictly smaller than $$. 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.