Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions

arXiv:2412.17003 · cs.IT, cs.CR, math.IT · Submitted 2024-12-22 · 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: Today's paper: "Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions".

Elias: Reed-Solomon codes are studied here in relation to constructing fully anonymous secret-sharing schemes that can tolerate permutations, insertions, and deletions.

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: We've gone through the specifics of "Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions," which focuses on how RS codes can build gap-threshold schemes resistant to permutation, insertion, and deletion attacks.

Elias: I think the key takeaway is that they established concrete algebraic conditions for robustness against this specific adversarial model by proving that certain determinant properties of evaluation points are both necessary and sufficient for the code's resilience.

Priya: For us in privacy research, the implication is that we gain a tool to mathematically verify anonymity when dealing with data that might be subject to insertion or deletion errors, which is a scenario that often comes up in real-world sensor networks or distributed databases.

Nadia: Precisely; this work moves us closer to building systems where the security of sharing a secret isn't just dependent on perfect data integrity, but on its ability to withstand active manipulation from an adversary.

Elias: Looking at the title, "Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions," it clearly signals the scope: linking a foundational secret-sharing concept with error-correcting codes against complex adversarial actions.

Priya: It suggests that future work could explore how these algebraic conditions translate into practical implementations where we can precisely quantify the security trade-offs based on field size and code parameters.

Nadia: That sounds like the natural next step; figuring out exactly how to implement this robust structure in a way that minimizes computational cost while maintaining those strong anonymity properties.

Elias: And from my perspective as a cryptographer, I'd focus on thoroughly analyzing the assumptions made about the field order q and ensuring that those algebraic conditions hold consistently across all relevant parameter choices.

Priya: It’s exciting because it provides a solid theoretical framework for designing more resilient data-sharing mechanisms in environments where data loss or tampering is an expected risk, rather than something we try to prevent entirely.

Nadia: So the takeaway is that Reed–Solomon codes offer a pathway to constructing fully anonymous secret sharing schemes that can handle specific, complex adversarial maneuvers like permutations combined with insertions and deletions.

Conclusion: Nadia: So, to wrap up this discussion, we're looking at how Reed-Solomon codes allow for anonymous secret sharing even when someone messes with the data by rearranging or adding/removing symbols.

Elias: I agree that it’s a sophisticated setup; the authors are showing that this robustness relies on very specific algebraic conditions related to evaluation points.

Priya: From my end, what this means practically is that we have a way to share sensitive information where the reconstruction process doesn't leak who holds which pieces, even if some of those pieces get subtly altered during transmission.

Nadia: It really boils down to creating a system where the security isn't just about keeping data intact; it’s about keeping the identity of the participants hidden while simultaneously handling noise and tampering.

Elias: The authors explicitly define a gap-threshold scheme that achieves perfect anonymity under these adversarial conditions, which is impressive considering how tightly they constrain those algebraic requirements.

Priya: This could have big implications for distributed systems where data integrity is questionable, like in sensor networks or collaborative databases where participants might drop packets or introduce errors.

Nadia: Exactly; we're talking about building trust into sharing mechanisms when you can't even guarantee the accuracy of every single share.

Elias: The paper’s main contribution is establishing those concrete mathematical boundaries, showing exactly what properties an evaluation point set needs to satisfy for the code to be resilient against that specific permutation-insertion-deletion attack.

Priya: It shows how a specific type of coding theory can directly solve a privacy problem involving data manipulation and identity protection simultaneously.

Nadia: The authors' ability to provide explicit constructions, like the deterministic one they presented, makes this research much more than just theoretical; it suggests there’s a path toward building these systems.

Elias: That explicit construction is key because it proves that these complex conditions aren't just abstract math; you can actually construct a working scheme over fields of sufficient size with high probability.

Priya: It pushes the boundary on what we thought was achievable in anonymous sharing schemes—moving beyond simple threshold schemes into environments where data quality is variable.

Nadia: So, the big picture here is that we're getting closer to practical applications where sensitive data can be shared securely even when an attacker actively tries to disrupt the sharing process.

Elias: The authors' work sets a high bar for what’s required algebraically; it suggests we need to look beyond basic error correction when designing truly robust anonymous systems.

Roni Con

Department of Computer Science, Technion–Israel Institute of Technology

cs.IT, cs.CR, math.IT

Submitted: 2024-12-22

Updated: 2026-09-28

Comments: Corrected an error in the proof of Proposition 4.1. This correction does not affect the results of the paper. See Section 1.5

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

Importance score: 90/100

The gist: Reed-Solomon codes are studied here in relation to constructing fully anonymous secret-sharing schemes that can tolerate permutations, insertions, and deletions.

Key concepts

Adversarial Model
This model involves an attacker who first shuffles the order of symbols in a codeword and then modifies it by inserting or deleting symbols. The goal is to see if a secret-sharing scheme can still maintain anonymity even after this complex manipulation.
Gap-Threshold Secret-Sharing Scheme
This is a specific type of secret sharing where any group smaller than the threshold ($k-1$) learns nothing about the secret or the participants. However, any group of size equal to or larger than $2k-1$ can perfectly reconstruct the secret without revealing who holds those shares.
Fully Anonymous Anonymity
This is a very strong security property requiring that the shares held by any unauthorized set of participants are perfectly uniform and independent. This ensures that knowing which specific people hold a set of shares gives no clue about their identities.
Reed-Solomon Codes
These are powerful error-correcting codes used in cryptography. They allow data to be transmitted or stored even if some symbols are lost, corrupted, or rearranged. The paper uses them as the mathematical backbone to ensure the secret-sharing scheme remains secure against adversarial changes.

Terminology

Summary

Reed-Solomon codes are studied here in relation to constructing fully anonymous secret-sharing schemes that can tolerate permutations, insertions, and deletions. The central finding is that there exist Reed–Solomon codes robust against an adversary performing an arbitrary permutation followed by a specific number of insertions and deletions, which implies the existence of a fully anonymous gap-threshold secret-sharing scheme with perfect reconstruction.

The Adversarial Model and Goal

The work investigates the performance of Reed–Solomon codes against an adversary who first permutes the codeword symbols and then performs insertions and deletions. This adversarial model is motivated by recent interest in fully anonymous secret-sharing schemes, which require that the shares of any unauthorized set are uniform and independent. The primary goal is to construct a scheme where any set of unauthorized shares reveal no information about the identity of the participants who hold them, while simultaneously ensuring perfect reconstruction without requiring the identities of the reconstructing parties. This leads to showing that there exist [n, k] Reed–Solomon codes (over sufficiently large fields) that are robust against an adversary that arbitrarily permutes the codeword and then performs n − 2k + 1 insertions and deletions to the permuted codeword.

The Gap-Threshold Secret-Sharing Scheme

The existence of these robust codes implies a specific secret-sharing structure. The paper shows that this robustness yields a (k − 1, 2k − 1, n) gap-threshold secret-sharing scheme that is fully anonymous. This scheme satisfies two key properties:

  1. any k − 1 shares reveal nothing about the secret, and no information on the participants’ identities.

  2. any 2k − 1 suffice to reconstruct the secret without revealing their identities.

The paper formally defines a (t, r, n) ramp threshold scheme where for any set of size at least r, it holds that H(SVA) = 0, and for any set of size at most t, it holds that H(SVA) = H(S). The constructed scheme achieves the strongest notion of anonymity: (1) the shares of unauthorized sets are perfectly uniform and independent, and (2) reconstruction is perfect and does not require the identities of the reconstructing parties.

Algebraic Conditions for Robustness

The core technical challenge involves formulating an algebraic condition on evaluation points that ensures robustness against permutations. This is captured in Proposition 2.5, which states that for an RS code to be robust against the (n − 2k + 1)-permutation-insdel adversary, it must satisfy one of two equivalent conditions:

  1. For every two distinct-element sequences I, J ∈ [n] of size 2k−1 it holds that either det(VI,J (α)) ≠ 0 or any vector in the kernel of VI,J (α) is of the form (0, f1,..., fk−1, −f1,..., −fk−1).

  2. The code RSn,k(α1,..., αn) is robust against the (n − 2k + 1)-permutation-insdel adversary.

These conditions are further refined by Proposition 3.10 and Proposition 3.14, which use the determinant of a specific matrix VI,J (X) to guarantee that for sufficiently large fields, a randomly chosen set of evaluation points α = (α1,..., αn) will satisfy the required algebraic properties with high probability.

Explicit Constructions

The paper provides explicit constructions based on previous work on RS codes capable of correcting insertions and deletions.

  1. The first scheme is borrowed from [CST24], showing that the two-dimensional RS code is robust against the (n − 3)-permutation-insdel adversary, yielding a fully anonymous ramp secret-sharing scheme.

  2. The second scheme uses evaluation points given in [CST23, Construction 27] and provides a deterministic construction of a fully anonymous (k − 1, 2k − 1, n) ramp secretsharing scheme over a field of order q = n O(k squared ((2k)!) 2).

Comparison with Existing Work

The paper highlights several key differences between its proposed scheme and the work in [EBG+24]:

"Anonymity condition. This paper adopts the strongest notion of anonymity, wherein the shares of any unauthorized set are uniformly random and independent (condition 1 in Definition 1.13). Our scheme achieves this property, while, as discussed above, the scheme of [EBG+24] achieves a weaker notion of anonymity."

**"Perfect vs. non-perfect reconstruction.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this paper, Anonymous Shamir’s secret-sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions, by Roni Con.

The core contribution of this paper is the construction of a specific type of cryptographic secret-sharing scheme—a gap-threshold scheme—that achieves the strongest possible notion of anonymity (perfect uniformity and independence) while ensuring perfect reconstruction, even when an adversary performs arbitrary permutations followed by insertions and deletions.

Here are the specific improvements to AI systems that can be enabled by this research:

The improved AI systems will be characterized by their ability to securely share sensitive information among untrusted nodes while maintaining absolute anonymity, even under active adversarial tampering.

  1. A secure, fully anonymous distributed key generation and secret sharing protocol for decentralized AI model training or critical data storage.

  2. A robust cryptographic mechanism for confidential collaborative computation where participants are malicious and actively trying to infer participant identities from their shares.

Specific capabilities of the improved AI system:

  1. An AI system can securely distribute a high-value secret (e.g., a proprietary model weight set, a master encryption key) among multiple untrusted nodes (participants) such that:

  2. Any unauthorized subset of participants learns absolutely nothing about the identity of the participants holding their shares (perfect anonymity), regardless of the permutation or insertion/deletion errors introduced by an adversary attempting to mislead the reconstruction process.

  3. A designated set of authorized participants can perfectly reconstruct this secret, even if a significant number of shares are lost or corrupted due to adversarial insertions and deletions, provided they possess at least a certain threshold (specifically, any set of size 2k-1 suffices).

In essence, this research provides the mathematical foundation for building AI systems where the trust is not in the participants themselves, but in an information-theoretic guarantee that their collective knowledge is strictly bounded by the secret itself. This moves beyond simple threshold schemes to achieve a state of perfect anonymity under active attack.

Abstract

In this work, we study the performance of Reed-Solomon codes against an adversary that first permutes the symbols of the codeword and then performs insertions and deletions. This adversarial model is motivated by the recent interest in fully anonymous secret-sharing schemes [EBG+24],[BGI+24]. A fully anonymous secret-sharing scheme has two key properties: (1) the identities of the participants are not revealed before the secret is reconstructed, and (2) the shares of any unauthorized set of participants are uniform and independent. In particular, the shares of any unauthorized subset reveal no information about the identity of the participants who hold them. In this work, we first make the following observation: Reed-Solomon codes that are robust against an adversary that permutes the codeword and then deletes symbols from the permuted codeword can be used to construct ramp threshold secret-sharing schemes that are fully anonymous. Then, we show that over large enough fields of size, there are [n,k] Reed-Solomon codes that are robust against an adversary that arbitrary permutes the codeword and then performs n-2k+1 insertions and deletions to the permuted codeword. This implies the existence of a (k-1, 2k-1, n) ramp secret sharing scheme that is fully anonymous. That is, any k-1 shares reveal nothing about the secret, and, moreover, this set of shares reveals no information about the identities of the players who hold them. On the other hand, any 2k-1 shares can reconstruct the secret without revealing their identities. We also provide explicit constructions of such schemes based on previous works on Reed-Solomon codes correcting insertions and deletions. The constructions in this paper give the first gap threshold secret-sharing schemes that satisfy the strongest notion of anonymity together with perfect reconstruction.

Sources

Related papers