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: 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 \(\varOmega (\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 a practical application of FASS to stalker detection, we initiate a systematic study of FASS, obtaining the following main results.