Fully Anonymous Secret Sharing

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 fully anonymous secret sharing (FASS), which strengthens standard secret sharing by requiring the following properties:

• 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.

• Anonymous Reconstruction. The reconstruction algorithm does not need to know the reconstructing set of parties.

Efficient FASS exists 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 $\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 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 an application of FASS to stalker detection, we initiate a systematic study of FASS, obtaining the following main results.

• Near-Optimal Information-Theoretic FASS. We obtain strong lower bounds, showing that the dependence on the DNF size is generally inherent. In particular, the share size 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 upper bounded by the CNF size. For DNF with $\ell$ small minterms, we improve the previous upper bound to $\tilde O(\ell)$, matching our lower bound up to a polylogarithmic factor.

• 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.

• 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.