SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders

arXiv:2611.16244 · cs.CR, cs.IT, math.IT · Submitted 2026-11-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders".

Elias: Here's the gist of the paper. SEC introduces an expander-code-based ramp secret sharing scheme over Zmodules, specifically designed for lattice-based distributed cryptography.

Nadia: A key feature is its "everywhere-shortness": bounded secret coefficients result in bounded share coefficients, and the integer reconstruction vectors have bounded entries.

Elias: Crucially, each participant receives exactly one share, irrespective of the number of parties (n) or the privacy and reconstruction thresholds.

Nadia: This surpasses prior schemes where the number of sub-shares per participant increased with n, threshold, or security parameter.

Title and authors: Nadia: So, we're looking at a paper called SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders. It’s about this new way to share secrets using expander codes, which is pretty interesting for lattice cryptography.

Elias: Yeah, the authors are Arzaki and Esgin and Sakzad and Steinfeld, and the main point is they're introducing a scheme that has a few really neat properties.

Nadia: One of those properties they highlight is what they call "everywhere-shortness." It means if you start with bounded secret coefficients, then the resulting share coefficients are also bounded, and the integer reconstruction vectors have entries that are also bounded.

Priya: Bounded share coefficients sound promising for practical applications because it keeps things manageable. But I wonder how much control they actually have over those bounds when you scale up to a large number of participants or high security levels.

Elias: That's the big question, Priya, and that's where this paper makes a strong statement. They say that each participant gets exactly one share, no matter how many parties there are or what the privacy and reconstruction thresholds are.

Nadia: That’s significant because most prior schemes had a number of sub-shares per participant that grew with the number of parties or the threshold, which makes things much more complex to manage.

Priya: Having exactly one share is simple for distribution, but it means that if you need a large group to reconstruct the secret, you're relying on just one piece of data from each person. How do we trust that single piece of data isn't somehow hiding too much information?

Elias: That’s where they tackle privacy by incorporating hard-core local leakage resilience. They prove that this scheme is resistant to correlated multi-query local leakage under the MatrixHint MLWE problem, which they connect back to the standard MLWE problem.

Nadia: So, it’s not just about sharing; it’s about making sure that even if someone tries to probe you with multiple queries, a hard-core function of your secret stays pseudorandom given what the other participants share and some noisy leakage.

Priya: That sounds robust for lattice-based crypto, but I need to see how this translates into real-world noise. Does this resilience hold up when the number of queries gets really high?

Title and authors: Elias: They do, and they derive a result called Theorem four <ref:2611.16244#pg2>. It shows that for any coalition of at most k p parties and admissible noisy linear leakage queries, a hard-core function of the secret remains pseudorandom under MLWE with secret width sigma, provided the widths of the sharing randomness and leakage masks exceed sigma by factors proportional to p k p and the square root of Q.

Nadia: That reduction to Matrix Hint MLWE is a powerful way to analyze it, because it lets them use existing hardness assumptions from that area. But what about the reconstruction part? How do we actually get the secret back?

Priya: I’m interested in how they handle the reconstruction vector. If you have a set of parties authorized to reconstruct, they need to recover the secret exactly as an integer linear combination of their shares.

Elias: They establish that this works perfectly with bounded entries for the reconstruction vector, and those entries satisfy a publicly computable bound. This is tied to Theorem one which states that each participant holds exactly one share whose coefficients are bounded if the secret and sharing randomness coefficients are bounded <ref:2611.16244#pg1>.

Nadia: That means even though the scheme is efficient in terms of share size per person, it doesn't sacrifice the ability to reconstruct the secret accurately using a set of participants.

Priya: I’ve seen some work on finding reconstruction vectors that are small, but what they're doing here seems to be more direct—they use LLL reduction and Babai decoding to find a small reconstruction vector.

Elias: Exactly, they use that method to ensure the resulting coefficient size is bounded by a publicly computable bound. That’s part of the theorem that guarantees correctness and everywhere-shortness for SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders >

Nadia: So, to summarize this paper, we have a scheme that gives you exactly one share per participant, keeps those coefficients bounded, and still allows for an integer linear combination reconstruction with a predictable bound.

Priya: What I worry about is the trade-off between the privacy threshold and the reconstruction threshold. If you set k p too low to keep privacy high, then k c, your reconstruction threshold, might be way higher than what's practical for recovery.

Elias: That gap between those thresholds is a limitation they admit in their own work. They note that while they achieve correctness and everywhere-shortness, they can't yet build an everywhere-short scheme with one share per participant that also realizes a perfect threshold access structure.

Nadia: So, for now, we have this very strong construction for lattice cryptography that gives us a good balance between efficiency in terms of shares and the mathematical guarantees of security and reconstruction.

Title and authors: Priya: It’s interesting how they connect it to Matrix Hint MLWE, which really shows how these coding-theoretic ideas can be mapped onto existing cryptographic hardness problems. It suggests that if you can prove a reduction to a known hard problem, you gain a lot of confidence in the scheme's security properties.

Elias: That reduction is key because it lets them use established tools from MLWEpellq dsigma or MLWEpellq dsigma MQ problems against non-uniform PPT adversaries to ensure the hardness holds.

Nadia: It’s a lot of technical stuff, but for someone listening who just wants to know what this means, it means we can potentially build distributed secret sharing systems that are much more lightweight in terms of the number of pieces each person has to hold.

Priya: I think the practical implication is that if you're doing many distributed computations where you need privacy but don't want massive share sizes, SEC offers a concrete path forward using expander codes.

Elias: That’s right, and it builds on prior work in coding theory by using the unique-neighbor peeling observation in bi-adjacency matrices of lossless bipartite expanders to get that square unimodular submatrix.

Nadia: Before we wrap up this SEC paper, I just want to quickly mention how they address verification. They suggest that because their masks are bounded, you can verify partial responses directly against participant-specific public material efficiently.

Priya: That verification capability is important because it means the system isn't just for sending shares; it’s also designed so that if someone sends a share, you can quickly check if it looks plausible without needing everyone to reveal everything.

Elias: So, while the reconstruction part is mathematically sound with bounded vectors, we still have that gap between the privacy threshold and the reconstruction threshold to consider for real-world deployment.

Nadia: Exactly. The paper gives us a solid tool—SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders—that uses expander codes to make sharing more efficient with bounded coefficients per participant.

Priya: It’s a good step forward because it tackles the problem of share size growth that plagued earlier schemes, even if there are still hurdles left to clear on the threshold trade-off.

Elias: We'll keep an eye on how this construction plays out in larger systems and if we can bridge that gap between privacy and reconstruction thresholds for more general access structures.

The paper's summary: Nadia: So, we’re talking about SEC, which is this new way to split secrets using expander codes. This paper shows how they built a scheme where each person gets exactly one share, no matter how many people are in the group or what the security level is supposed to be.

Elias: Right. The big idea here is "everywhere-shortness." They prove that if you start with secret numbers and randomness that are bounded, then the resulting shares and even the reconstruction vectors stay bounded too. That’s a big deal for making this practical for real systems.

Priya: Bounded coefficients sound manageable, but I need to know how much control they really have over those bounds when you're scaling up to a huge number of participants or trying to get super high security levels.

Nadia: That’s the question. The authors show that this construction is built on a specific coding theory observation about bi-adjacency matrices of lossless expanders, which lets them create this square unimodular submatrix for every small set of columns.

Elias: And they use that to distribute the secret through this public integer distribution matrix, and they compute one row for each participant by multiplying that matrix by something where the first row is the secret and the rest are short Gaussian masks.

Priya: So, what does this mean for someone who just wants to know how much data you’re actually dealing with when you use this scheme? What are those numbers?

Nadia: They give us concrete estimates. With sixty participants and a security level of one hundred twenty-eight, they see a privacy threshold of six against two to the sixty-four leakage queries. And for reconstruction, they see an empirical threshold of forty-six.

Elias: That’s about three point five kilobytes for the secret and roughly six point four kilobytes for each share. Those are pretty reasonable sizes compared to older schemes where the number of sub-shares per person just kept growing with security parameters or thresholds.

Priya: But there’s still a gap, right? They admit that there’s a difference between the privacy threshold and the reconstruction threshold they need to hit for this specific setup.

Nadia: That gap is their main limitation, so they can't yet build an everywhere-short scheme with one share per person that also achieves a perfect threshold access structure. It’s not quite there yet for a general case.

Elias: Still, the security analysis is pretty solid because they reduce the privacy problem to Matrix Hint MLWE, which connects it to the standard MLWE problem. This means if you can break SEC, you can break things that are already considered hard in lattice cryptography.

Priya: So we’re looking at a scheme where each person holds one piece of data, those pieces are small enough to be practical, and the reconstruction works with a predictable bound, but we still have to manage the gap between privacy and reconstruction needs.

Nadia: Exactly. It’s a strong tool for distributed secret sharing in lattice cryptography right now because it tackles that share size growth problem head-on. This sets us up to look at how this fits with other distributed systems problems next.

The paper's improvements: Tom: So, we’re talking about how this paper suggests they can actually make SEC better than what they first proposed. They outline a few specific improvements to the original idea of one share per person with bounded coefficients.

Nadia: They focus on enhanced share size control, which means they can configure the system to absolutely guarantee that every single participant receives exactly one share, no matter how many people are involved or what privacy and reconstruction thresholds you set.

Elias: That’s a big win because it directly addresses the weakness in earlier schemes where the number of sub-shares per person kept growing with security parameters or thresholds. So, you get exactly one share for everyone.

Priya: Having exactly one share is simple to distribute, but I still wonder about how they handle verification when someone sends a partial response; can we trust that the bounded masks don't hide big terms?

Nadia: They suggest a way to handle that by using bounded-coefficient masks directly against participant-specific public material. This lets you verify partial responses efficiently because those bounded masks can't hide the large share-dependent term when you use everywhere-short sharing.

Elias: That sounds like it gives us better verification capabilities without needing everyone to reveal everything at once. It means partial signatures could be checked on the fly with less overhead.

Priya: So, for someone who is only focused on the data itself, does this mean the data you see is cleaner or more trustworthy than before? What does this improvement actually show about the underlying noise?

Nadia: They're getting robust privacy guarantees too. They incorporate hard-core local leakage resilience by strengthening Nielsen and Simkin’s idea. This proves that a hard-core function of your secret stays pseudorandom even when there is correlated multi-query local leakage from all the shares.

Elias: That reduction to Matrix Hint MLWE is key there because it shows that this protection holds against non-uniform adversaries, which is exactly what we need for lattice cryptography. It moves the privacy proof into a well-studied area of hardness assumptions.

Priya: So, if someone tries to probe you with multiple queries, they still can't tell anything meaningful about your secret using the shares from other parties, even with that noise? What’s the guarantee here?

Nadia: They show that for any coalition of a certain size and some admissible noisy linear leakage queries, a hard-core function of the secret remains pseudorandom under MLWE. The tail parameter for this is zero in their construction, which means it’s perfectly private in the multi-query local leakage sense they defined.

Elias: That zero tail parameter is strong because it means you don't have to worry about a tiny probability of failure from those query attacks. It solidifies the security proof significantly.

Priya: But I still see that gap between the privacy threshold and the reconstruction threshold they need to hit for this specific setup, so that’s something we gotta keep an eye on.

Nadia: Exactly, that gap between the privacy threshold and reconstruction threshold is still there. It means this is a great construction for efficiency, but it’s not yet a perfect universal access structure for every possible setup.

Elias: Still, it sets a really high bar for what's possible with expander codes in this area of distributed cryptography.

Conclusion: Nadia: So we’re wrapping up on SEC, which is this paper about One-Share Everywhere-Short Secret Sharing from Lossless Expanders. Basically, they showed a way to get exactly one share per participant with very small coefficients and bounded reconstruction vectors for lattice cryptography.

Elias: Right. It's a construction that uses expander codes to make sharing more efficient by controlling the size of those coefficients across the board. The main result is that you get a scheme where each person holds one piece of data, and all those pieces are small enough to be practical for real systems.

Priya: So if we take what you just said, does this mean that in practice, we can handle distributed computations where we don't have to deal with massive share sizes? What does this change for someone who is building a system?

Nadia: It means yes. It tackles the problem of share size growth that plagued earlier schemes by making sure those coefficients stay bounded if the secret and randomness you start with are bounded. This opens up possibilities for more lightweight distributed systems.

Elias: And from a cryptographic standpoint, they’ve tied the security analysis to Matrix Hint MLWE, which is a known hard problem in lattice cryptography. That connection gives us confidence that this scheme holds up against those non-uniform adversaries we worry about in this field.

Priya: I still see that gap between the privacy threshold and the reconstruction threshold they need to hit for this specific setup, so that’s something we gotta keep an eye on when we look at deploying these things.

Nadia: True. That gap between those thresholds is still there, so it’s not a perfect universal access structure yet, but it's a very solid construction for what it can do right now in lattice cryptography.

Elias: It’s a good step forward because they tackle the share size problem head-on using coding theory ideas from expander codes. That foundation is going to be important for future research into distributed protocols.

Priya: I just want to make sure we remember that while it's efficient, we still have to be careful about how much noise or leakage might affect those bounded reconstruction vectors in a real-world scenario.

Nadia: Definitely. So that’s SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders for now. It’s a strong tool for getting more efficient, bounded sharing in lattice cryptography, and we'll keep watching how this construction plays out when we look at other distributed systems problems next.

Muhammad Arzaki, Muhammed F. Esgin, Amin Sakzad, Ron Steinfeld

Faculty of Information Technology, Monash University

cs.CR, cs.IT, math.IT

Submitted: 2026-11-12

Updated: 2026-11-12

Comments: 84 pages, 3 figures. Also available as Cryptology ePrint Archive, Paper 2026/2841: https://eprint.iacr.org/2026/2841

Code: https://github.com/arzaki-cstheory/SEC-LaTSEC

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 86/100

The gist: SEC introduces an expander-code-based ramp secret sharing scheme over Zmodules, specifically designed for lattice-based distributed cryptography.

Key concepts

Everywhere-Shortness
This property ensures that if the secret and sharing randomness are small, every resulting share coefficient is also bounded in size. Furthermore, the integer vectors needed for reconstruction have entries that are also bounded by a publicly known limit. This makes the scheme robust against large coefficients.
Lossless Bipartite Expander
The construction uses a matrix derived from a lossless bipartite expander graph. A key property of these expanders is that peeling off unique neighbors from the bi-adjacency matrix yields a square unimodular submatrix for small sets of columns. This mathematical structure underpins the scheme's ability to distribute secrets efficiently.
Matrix Hint-MLWE
This is the specific hard problem used to prove the privacy guarantees of SEC. By reducing the complex leakage scenario to this problem, researchers can show that a hard-core function of the secret remains pseudorandom even when subjected to noisy linear leakage from a private coalition.
One-Share Guarantee
Unlike previous schemes where share counts depend on security parameters or thresholds, SEC ensures every single participant receives precisely one share. This simplifies distribution and improves efficiency while maintaining strong cryptographic properties for lattice-based cryptography.

Terminology

Summary

SEC introduces an expander-code-based ramp secret sharing scheme over Zmodules, specifically designed for lattice-based distributed cryptography. p. 0

Where the paper says it

arzaki@monash. edu; Abstract We introduce SEC, an expander-code-based ramp secret sharing scheme over Zmodules, particularly suitable for lattice-based distributed cryptography.

A key feature is its everywhere-shortness: bounded secret coefficients result in bounded share coefficients, and the integer reconstruction vectors have bounded entries. Crucially, each participant receives exactly one share, irrespective of the number of parties (n) or the privacy and reconstruction thresholds. p. 0
Where the paper says it

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 surpasses prior schemes where the number of sub-shares per participant increased with n, threshold, or security parameter. p. 0
Where the paper says it

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 leverages a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling yields a square unimodular submatrix for every sufficiently small set of columns. p. 0
Where the paper says it

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.

The scheme operates by distributing the secret through a public integer distribution matrix G:= g G in Z n times k, where G is a signed and permuted transpose of the bi-adjacency matrix of a lossless bipartite expander, and g is a secret-bearing column. p. 4

Where the paper says it

The main coding-theoretic ingredient may be of independent interest: in the biadjacency matrix of a lossless bipartite expander whose expansion exceeds half the left degree, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix (Lemma 4); we are not aware of a previous formulation of this unimodularity conclusion. 3 Technical Overview Following the coding-theoretic approach of McEliece and Sarwate [5], SEC shares a secret through a public integer distribution matrix G := g Gˆ ∈ Z n×k , where Gˆ is a signed and permuted transpose of the bi-adjacency matrix of a lossless bipartite expander and g is a secret-bearing column.

The dealer computes one row of the product G for each participant by multiplying G by a matrix whose first row is the secret and whose remaining rows are short Gaussian masks. p. 4
Where the paper says it

3 Technical Overview Following the coding-theoretic approach of McEliece and Sarwate [5], SEC shares a secret through a public integer distribution matrix G := g Gˆ ∈ Z n×k , where Gˆ is a signed and permuted transpose of the bi-adjacency matrix of a lossless bipartite expander and g is a secret-bearing column. The dealer multiplies G by a matrix whose first row is the secret and whose remaining rows are short Gaussian masks, giving one row of the product to each participant.

A set T [n] is certified and reconstructs exactly when an element lambda T in Z T exists such that lambda T T G = e 1. p. 4
Where the paper says it

The dealer multiplies G by a matrix whose first row is the secret and whose remaining rows are short Gaussian masks, giving one row of the product to each participant. A set T ⊆ [n] is certified, and reconstructs exactly, when e ⊤ 1 ∈ RowZ(GT ), that is, when some λT ∈ Z |T| satisfies λ ⊤ T GT = e ⊤ 1 .

The scheme achieves correctness, everywhere-shortness, and linearity. p. 0

Where the paper says it

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, SEC incorporates hard-core local leakage resilience by strengthening Nielsen and Simkin's notion to protect a hard-core function of the secret. It proves that SEC satisfies this against correlated multi-query local leakage under the MatrixHint-MLWE problem, which is reducible from the standard MLWE problem. p. 0
Where the paper says it

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.

With n=60 participants and security parameter kappa=128, SEC achieves a privacy threshold of 6 against 2 64 leakage queries and an empirical reconstruction threshold of 46. p. 0
Where the paper says it

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.

Ideal entropy-coded secret and share sizes are approximately 3. p. 0
Where the paper says it

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. p. 0
Where the paper says it

The ideal entropy-coded secret and share sizes are about 3. 5 KiB and 6.

4 KiB, respectively. p. 0
Where the paper says it

5 KiB and 6. 4 KiB, respectively.

The main result (Theorem 1) establishes that:

  1. Each participant holds exactly one share, whose coefficients are bounded if the secret and sharing randomness coefficients are bounded. p. 4

    Where the paper says it

    Then the following hold. Each participant holds exactly one share, whose coefficients are bounded whenever the coefficients of the secret and of the sharing randomness are bounded.

  2. A certified set recovers the secret exactly as an integer linear combination of its shares, with reconstruction vector entries satisfying a publicly computable bound. p. 4

    Where the paper says it

    Every set for which the public reconstruction algorithm finds an integer reconstruction vector, called a certified set, recovers the secret exactly as an integer linear combination of its shares. The entries of the reconstruction vector satisfy a publicly computable bound.

  3. For any coalition of at most k p parties and admissible noisy linear leakage queries, a hard-core function of the secret remains pseudorandom under MLWE with secret width sigma, provided the widths of the sharing randomness and leakage masks exceed sigma by factors proportional to p k p and sqrt Q, respectively. p. 4

    Where the paper says it

    In particular, every coalition of at least k det c = n − b + 1 parties is certified, where b ≥ ⌊n/k⌋ is the number of pairwise disjoint certified supports planted by the construction and k is the dimension of the underlying code. For every coalition of at most kp parties and every admissible choice of at most Q prescribed noisy linear leakage queries on all shares, a hard-core function of the secret remains pseudorandom under MLWE with secret width σ, provided that the widths of the sharing randomness and the leakage masks exceed σ by factors proportional to p kp and √ Q, respectively, up to factors depending on n and the expander.

The privacy analysis reduces the problem to Matrix Hint-MLWE, deriving Theorem 4: Pr[pp from Setup(1 kappa) h PPT A, U in U k p,Q: Adv(pp,U) A,HC-Leak(kappa) at most epsilon MQ(kappa, A, U) i at least 1 - delta MQ. p. 5

Where the paper says it

We instead express the complete adversarial view as one stacked linear hint with a jointly distributed perturbation and bound it uniformly over admissible coalitions and leakage patterns. The integral image and kernel properties supplied by the unimodular submatrices allow us to apply the linear-transformation theorem of [40], showing that the joint perturbation is statistically close to the elliptic discrete Gaussian required by MatrixHint-MLWE.

For the certified expander-based construction, the tail parameter is delta MQ = 0, meaning FMQ is (delta MQ, epsilon MQ) -private in the multi-query HC-LLR sense of Definition 10. p. 0
Where the paper says it

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.

Empirically, reconstruction thresholds are k c=31 for n=50 and k c=46 for n=60, with observed maximum reconstruction coefficient bounds beta hat lambda = 8. p. 3

Where the paper says it

cThe privacy and reconstruction thresholds hold with overwhelming probability over a public seed [32]. dThe privacy threshold kp holds for every coalition of at most kp parties, given a lossless expander, while the reconstruction threshold kc is selected empirically.

The construction's security relies on the hardness of MLWEp 'q d sigma or MLWEp 'q d sigma MQ problems against non-uniform PPT adversaries. The principal trade-off is the gap between the privacy threshold k p and reconstruction threshold k c. p. 1
Where the paper says it

In a t-out-of-n threshold scheme, every set of at least t parties is authorized and every smaller set is unauthorized. Ramp schemes permit a gap between a privacy threshold and a larger reconstruction threshold, enabling a better information rate than perfect threshold sharing [3, 4].

The construction's limitations include the gap between these thresholds, and an open problem remains in constructing an everywhere-short scheme with one share per participant that realizes a perfect (non-ramp) threshold access structure.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Enhanced share size control: The system can be configured to ensure that every participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds, improving on prior schemes where share counts grow with security parameters or thresholds.

  2. Bounded output verification: The system can verify partial responses directly against participant-specific public material because bounded-coefficient masks cannot hide the large share-dependent term when using everywhere-short sharing, allowing for efficient verification of partial signatures.

  3. Robust privacy guarantees: The AI system provides hard-core local leakage resilience, proving that a hard-core function of the secret remains computationally indistinguishable from uniform given the shares of a private coalition and prescribed noisy linear leakage from all shares, which is suitable for lattice-based cryptography.

  4. Multi-query security: The system supports multi-query privacy by reducing the experiment to Matrix Hint-MLWE, where the joint perturbation is statistically close to the elliptic discrete Gaussian required by MatrixHint-MLWE, allowing it to handle noise from multiple queries effectively.

  5. Deterministic reconstruction vector finding: The system employs an algorithm that finds a small reconstruction vector using LLL reduction and Babai decoding, which ensures the resulting coefficient size is bounded by a publicly computable bound, satisfying Item 2 of Theorem 1.

  6. Adaptable security settings: The system can operate under different query budgets, supporting both standalone sharing schemes (Q=0) and lattice-based threshold signatures (Q=264), allowing users to choose the appropriate security model.

Abstract

We introduce SEC, an expander-code-based ramp secret sharing scheme over 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.

Related papers