CryptoDB
Fully Anonymous Secret Sharing
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | In a secret sharing scheme for a monotone access structure $\mathcal{A}:\{0,1\}^n\rightarrow \{0,1\}$, a dealer can share a secret $s$ to $n$ parties such that any authorized subset of parties $A\in\mathcal{A}$ can recover $s$ while all other subsets learn nothing about $s$. In this work we study {\em fully anonymous secret sharing} (FASS), which strengthens standard secret sharing by requiring the following properties: \begin{itemize} \item {\bf Share Anonymity.} The shares belonging to any unauthorized set of parties not only hide the secret, but also all identifiable information such as party identities and whether or not the shares were generated together. In particular, it suffices that such shares be uniform and independent. \item {\bf Anonymous Reconstruction.} The reconstruction algorithm does not need to know the reconstructing set of parties. \end{itemize} Efficient FASS schemes are known to exist for threshold access structures. For general access structures, the only known construction relies on a monotone DNF representation of $\mathcal{A}$ and has per-party share size of $\Omega(\ell n)$ where $\ell$ is the number of minterms of $\mathcal{A}$. This leaves an exponential gap between standard secret sharing and FASS even for simple access structures. Moreover, even in the threshold case, known FASS schemes could not achieve optimal robust reconstruction when mixing shares of multiple secrets. Motivated by a recent work of Eldridge et al. [USENIX'24], who demonstrated a practical application of FASS for stalker detection, we initiate a systematic study of FASS, obtaining the following main results. \begin{itemize} \item {\bf Near-Optimal Information-Theoretic FASS.} We obtain strong lower bounds, showing that the dependence on the DNF size is generally inherent. In particular, our lower bounds can be exponential in the number of parties or even in the minimum CNF size. This stands in sharp contrast to standard secret sharing, where no super-polynomial lower bounds are known, and where the share size is linear in the CNF size. For DNF with $\ell$ {\em small} minterms, we improve the previous upper bound to $\tilde O(\ell)$, matching our lower bound up to a polylogarithmic factor. \item {\bf Computational FASS.} We show that the above negative results can be circumvented in the computational setting, obtaining FASS schemes with succinct shares. Under the learning with errors (LWE) assumption, we present a general compiler from standard secret sharing to FASS that preserves the share size of the underlying scheme. For natural graph access structures, we directly construct succinct FASS from either one-way functions or bilinear maps. \item {\bf Robust FASS.} We show that simple modifications of our computational FASS schemes can allow for robust reconstruction of a polynomially unbounded number of secrets from any mixture of their authorized shares. \end{itemize} |
BibTeX
@inproceedings{crypto-2025-35677,
title={Fully Anonymous Secret Sharing},
publisher={Springer-Verlag},
author={Allison Bishop and Matthew Green and Yuval Ishai and Abhishek Jain and Paul Lou},
year=2025
}