arXiv preprint ·
SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We introduce SEC, an expander-code-based ramp secret sharing scheme over $\mathbb{Z}$-modules, particularly suitable for lattice-based distributed cryptography. It is everywhere-short: bounded secret coefficients yield bounded share coefficients, and the integer reconstruction vectors have bounded entries. Moreover, each participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds. This improves on prior schemes with bounded share coefficients and bounded entries in the integer reconstruction vectors, in which the number of sub-shares or shares per participant grows either with the number of parties and the threshold or with the security parameter. The construction rests on a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix. We prove correctness, everywhere-shortness, and linearity, and give a publicly computable entrywise bound on the reconstruction vector our algorithm returns for each authorized set. For privacy, we introduce hard-core local leakage resilience, which strengthens the leakage-resilience notion of Nielsen and Simkin (EUROCRYPT 2020) to protect a hard-core function of the secret, and we prove that SEC satisfies it against correlated multi-query local leakage under the MatrixHint-MLWE problem, which admits a reduction from the standard MLWE problem. For $n=60$ participants and security parameter $κ=128$, SEC achieves privacy threshold 6 against $2^{64}$ leakage queries and empirical reconstruction threshold 46. The ideal entropy-coded secret and share sizes are about 3.5 KiB and 6.4 KiB, respectively.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Cryptography & Security
Two-Stage Secret Sharing
Nonexistence of a quasi-symmetric $2$-$(33,15,35)$ design
Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes
Toward the Minimal Set of Information Inequalities in Regenerating Codes: An Algebraic Approach
Wireless Node Ranking via Fourier-Driven Maximum-Likelihood Estimation (extended version)
Get the few papers worth your time in Cryptography & Security every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.