Paper 2023/838
How to Recover a Secret with O(n) Additions
Abstract
Threshold cryptography is typically based on the idea of secretsharing a privatekey $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 secretsharing 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., CramerXing, 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 nearthreshold 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 secretsharing 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 byproduct, we derive the first blackbox nearthreshold secretsharing scheme with lineartime sharing. We also present several concrete instantiations of our approach that seem practically efficient (e.g., for threshold discretelogbased signatures). Our constructions are combinatorial in nature. We combine graphbased erasure codes that support ``peelingbased'' decoding with a new randomness extraction method that is based on innerproduct with a smallinteger vector. We also introduce a general concatenationlike transform for secretsharing schemes that allows us to arbitrarily shrink the privacycorrectness gap with a minor overhead. Our techniques enrich the secretsharing toolbox and, in the context of blackbox secret sharing, provide a new alternative to existing numbertheoretic 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in CRYPTO 2023
 Keywords
 secret sharingthreshold cryptographyblackbox secret sharing
 Contact author(s)

benny applebaum @ gmail com
odednir123 @ gmail com
benny @ pinkas net  History
 20230823: last of 2 revisions
 20230605: received
 See all versions
 Short URL
 https://ia.cr/2023/838
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/838, author = {Benny Applebaum and Oded Nir and Benny Pinkas}, title = {How to Recover a Secret with O(n) Additions}, howpublished = {Cryptology ePrint Archive, Paper 2023/838}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/838}}, url = {https://eprint.iacr.org/2023/838} }