Paper 2023/955

Succinct Computational Secret Sharing

Benny Applebaum, Tel Aviv University
Amos Beimel, Ben-Gurion University of the Negev
Yuval Ishai, Technion – Israel Institute of Technology
Eyal Kushilevitz, Technion – Israel Institute of Technology
Tianren Liu, Peking University
Vinod Vaikuntanathan, Massachusetts Institute of Technology

A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$. The question of minimizing the (largest) share size for a given $f$ has been the subject of a large body of work. However, in most existing constructions for general access structures $f$, the share size is not much smaller than the size of some natural computational representation of $f$, a fact that has often been referred to as the ``representation size barrier'' in secret sharing. In this work, we initiate a systematic study of succinct computational secret sharing (SCSS), where the secrecy requirement is computational and the goal is to substantially beat the representation size barrier. We obtain the following main results. (1) SCSS via Projective PRGs. We introduce the notion of a *projective PRG*, a pseudorandom generator for which any subset of the output bits can be revealed while keeping the other output bits hidden, using a *short* projective seed. We construct projective PRGs with different levels of succinctness under a variety of computational assumptions, and apply them towards constructing SCSS for graph access structures, monotone CNF formulas, and (less succinctly) useful subclasses of monotone circuits and branching programs. Most notably, under the sub-exponential RSA assumption, we obtain a SCSS scheme that, given an arbitrary access structure $f$, represented by a truth table of size $N=2^n$, produces shares of size polylog(N)=\poly(n) in time $\tilde O(N)$. For comparison, the share size of the best known information-theoretic schemes is $O(N^{0.58})$. (2) SCSS via One-way Functions. Under the (minimal) assumption that one-way functions exist, we obtain a near-quadratic separation between the total share size of computational and information-theoretic secret sharing. This is the strongest separation one can hope for, given the state of the art in secret sharing lower bounds. We also construct SCSS schemes from one-way functions for useful classes of access structures, including forbidden graphs and monotone DNF formulas. This leads to constructions of fully-decomposable conditional disclosure of secrets (also known as privacy-free garbled circuits) for general functions, represented by a truth table of size $N=2^n$, with share size polylog(N) and computation time $\tilde O(N)$, assuming sub-exponentially secure one-way functions.

Note: This is the full version of a STOC'23 paper.

Available format(s)
Publication info
secret sharingprojective pseudorandom generators
Contact author(s)
benny applebaum @ gmail com
amos beimel @ gmail com
yuval ishai @ gmail com
eyalk @ cs technion ac il
liutianren @ gmail com
vinod nathan @ gmail com
2023-06-19: approved
2023-06-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan},
      title = {Succinct Computational Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/955},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.