Paper 2023/838

How to Recover a Secret with O(n) Additions

Abstract

Threshold cryptography is typically based on the idea of secret-sharing a private-key $s\in F$ ``in the exponent'' of some cryptographic group $G$, or more generally, encoding $s$ in some linearly homomorphic domain. In each invocation of the threshold system (e.g., for signing or decrypting) an ``encoding'' of the secret is being recovered and so the complexity, measured as the number of group multiplications over $G$, is equal to the number of $F$-additions that are needed to reconstruct the secret. Motivated by this scenario, we initiate the study of $n$-party secret-sharing schemes whose reconstruction algorithm makes a minimal number of \emph{additions}. The complexity of existing schemes either scales linearly with $n\log |F|$ (e.g., Shamir, CACM'79) or, at least, quadratically with $n$ independently of the size of the domain $F$ (e.g., Cramer-Xing, EUROCRYPT '20). This leaves open the existence of a secret sharing whose recovery algorithm can be computed by performing only $O(n)$ additions. We resolve the question in the affirmative and present such a near-threshold secret sharing scheme that provides privacy against unauthorized sets of density at most $\tau_p$, and correctness for authorized sets of density at least $\tau_c$, for any given arbitrarily close constants $\tau_p<\tau_c$. Reconstruction can be computed by making at most $O(n)$ additions and, in addition, (1) the share size is constant, (2) the sharing procedure also makes only $O(n)$ additions, and (3) the scheme is a blackbox secret-sharing scheme, i.e., the sharing and reconstruction algorithms work universally for all finite abelian groups $F$. Prior to our work, no such scheme was known even without features (1)--(3) and even for the ramp setting where $\tau_p$ and $\tau_c$ are far apart. As a by-product, we derive the first blackbox near-threshold secret-sharing scheme with linear-time sharing. We also present several concrete instantiations of our approach that seem practically efficient (e.g., for threshold discrete-log-based signatures). Our constructions are combinatorial in nature. We combine graph-based erasure codes that support ``peeling-based'' decoding with a new randomness extraction method that is based on inner-product with a small-integer vector. We also introduce a general concatenation-like transform for secret-sharing schemes that allows us to arbitrarily shrink the privacy-correctness gap with a minor overhead. Our techniques enrich the secret-sharing toolbox and, in the context of blackbox secret sharing, provide a new alternative to existing number-theoretic approaches.

Note: Added a few references and a proof for the impossibility of pairwise hashing over a large field with a linear number of additions.