International Association
for Cryptologic Research

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}

The world of U.S. equities trading is highly competitive, involves many participants, and has significant global impact. Traders in this arena are responsible for overseeing the movement of billions of dollars, often on behalf of others, and thereby have a responsibility to develop reliable and well-performing trading strategies. “Controlling information leakage” is widely considered fundamental to high-quality, competitive trading strategies. In other words, good trading strategies maintain a level of privacy from an outside market observer. However important and highly valued this information leakage control property may seem, to our knowledge there exists no formal definition for this property in the context of equities trading strategies. Our work addresses this and creates a strong foundation for theoretical and practical work in this domain.

We give a simple and efficient method for obfuscating pattern matching with wildcards. In other words, we construct a way to check an input against a secret pattern, which is described in terms of prescribed values interspersed with unconstrained “wildcard” slots. As long as the support of the pattern is sufficiently sparse and the pattern itself is chosen from an appropriate distribution, we prove that a polynomial-time adversary cannot find a matching input, except with negligible probability. We rely upon the generic group heuristic (in a regular group, with no multilinearity). Previous work [9, 10, 32] provided less efficient constructions based on multilinear maps or LWE.