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 $$, is equal to the number of $$-additions that are needed to reconstruct the secret. Motivated by this scenario, we initiate the study of $$-party secret-sharing schemes whose reconstruction algorithm makes a minimal number of \emph{additions}. The complexity of existing schemes either scales linearly with $$ (e.g., Shamir, CACM'79) or, at least, quadratically with $$ independently of the size of the domain $$ (e.g., Cramer-Xing, EUROCRYPT '20). This leaves open the existence of a secret sharing whose recovery algorithm can be computed by performing only $$ 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 $$, and correctness for authorized sets of density at least $$, for any given arbitrarily close constants $$. Reconstruction can be computed by making at most $$ additions and, in addition, (1) the share size is constant, (2) the sharing procedure also makes only $$ 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 $$. Prior to our work, no such scheme was known even without features (1)--(3) and even for the ramp setting where $$ and $$ 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.