Welcome to the resource topic for 2023/838
Title:
How to Recover a Secret with O(n) Additions
Authors: Benny Applebaum, Oded Nir, Benny Pinkas
Abstract:Motivated by applications in threshold cryptography, we initiate the study of secret-sharing schemes that distribute a secret from a large field F_p among n parties such that the recovery algorithm makes a minimal number of \emph{additions}. Existing schemes achieve either O(n\log p) additions (e.g., Shamir, Comm. of ACM, 1979) or at least \Omega(n^2) operations independently of the field size (e.g., Cramer-Xing, EUROCRYPT, 2020). 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 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 \mathbb{G}. 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 seems 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 for low dimensional sub-space that is based on inner-product with a small-integer vector. By combining these tools with the blueprint of Cramer et al. (EUROCRYPT 2015), we derive efficient secret-sharing scheme with far-apart thresholds. We then 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.
ePrint: https://eprint.iacr.org/2023/838
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .