Anonymous Shamir’s secret-sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions

Roni Con · 2024

Read Anonymous Shamir’s secret-sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions by Roni Con (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17003.txt.

Introduction

Roni Con wrote a 2024 paper on secret sharing that stays anonymous even under scrambled and edited shares. In Shamir sharing, a secret splits into shares that only set groups can rebuild. A fully anonymous scheme hides who holds each share until rebuild time. Con studies Reed-Solomon codes under an attacker who shuffles the share order, then adds or cuts symbols.

A key finding links code strength to anonymity. Codes that survive shuffling plus deletions can yield fully anonymous ramp schemes. In such schemes, small groups learn nothing, not even member names. The work ties coding theory to privacy for group secrets. It may guide schemes where holders must stay unnamed.

Catalog record

CREATORRoni Con
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17003

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Anonymous Shamir’s secret-sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions Roni Con Abstract In this work, we study 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 [ EBG+24 , BGI+25 ] . A fully anonymous secret-sharing scheme has two key properties: first, the identities of the participants are not revealed before the secret is reconstructed; second, 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. We begin by observing that Reed–Solomon codes, when robust against an adversary who permutes the codeword and then deletes symbols, can be used to construct fully anonymous gap-threshold secret-sharing schemes. We then show that there exist [ n , k ] [n,k] Reed–Solomon codes (over sufficiently large fields) that are robust against an adversary that arbitrarily permutes the codeword and then performs n − 2 ​ k + 1 n-2k+1 insertions and deletions to the permuted codeword. This implies the existence of a ( k − 1 , 2 ​ k − 1 , n ) (k-1,2k-1,n) gap-threshold secret-sharing scheme that is fully anonymous. That is, any k − 1 k-1 shares reveal nothing about the secret, and no information on the participants’ identities. Conversely, any 2 ​ k − 1 2k-1 shares suffice to reconstruct the secret without supplying the participants’ identities to the reconstruction algorithm. We also provide explicit constructions of such schemes based on previous work on Reed–Solomon codes capable of correcting insertions and deletions. The constructions presented here are the first gap-threshold secret-sharing schemes to simultaneously achieve perfect uniform anonymity up to the privacy threshold and perfect anonymous reconstruction. 1 Introduction Reed–Solomon (RS) codes are a crucial family of error-correcting codes that play a significant role in ensuring data integrity across various communication and storage systems. Developed in the 1960s [ RS60 ] , these codes are particularly effective in correcting multiple symbol errors, making them ideal for data transmission and storage. Specific applications include distributed storage systems, QR codes, and data transmission over noisy channels. The ubiquity of these codes is due to their beautiful algebraic structure, which allows us to efficiently encode and decode in the presence of substitutions and erasures. Substitution and erasure errors have been extensively studied, and many ingenious constructions (including Reed–Solomon codes) are known that achieve optimal or near-optimal performance. By contrast, insertion and deletion (insdel) errors—where an insertion adds a symbol between two adjacent ones (or at the word boundaries) and a deletion removes a symbol—have received comparatively less attention. In recent years, however, motivated both by theoretical challenges and by practical applications in DNA-based storage, the design of insdel-correcting codes has become a vibrant research area. Comprehensive surveys on random insdel channels include Mitzenmacher [ Mit09 ] and Cheragchi and Ribeiro [ CR20 ] . For a survey about adversarial insdel errors and more related results, see [ HS21a ] by Haeupler and Shahrasbi. For a detailed account of applications to DNA storage, see the survey by Sabary et al. [ SKSY24 ] . Given the central role of Reed–Solomon codes in coding theory, a natural question is how well they perform against insdel errors, and indeed, this has been studied in a series of works [ SNW02 , TSN07 , DLTX21 , CST23 , LT21 , CST24 , Liu24 , CGLZ25 , BCG+25 ] . In particular, [ CST23 ] established that RS codes over sufficiently large fields achieve the so-called half-Singleton bound , i.e., the optimal rate–error correction trade-off attainable by any linear code. 1 1 1 Nonlinear codes are strictly stronger for insdel errors. Any linear code correcting a \delta -fraction of insdel errors has rate at most \tfrac{1-\delta}{2}+o(1) , whereas nonlinear constructions can approach the Singleton bound; for instance, [ HS21b ] achieves rate close to 1-\delta . Nevertheless, the precise capabilities of RS codes, and more generally of linear insdel-correcting codes, remain far from fully understood; see [ CGLZ25 , Section 1.4] and [ CGHL23 , Section 10] . This paper concerns the Shamir secret-sharing scheme, one of the most notable applications of RS codes in cryptography. We make a novel connection between the anonymity of Shamir’s secret-sharing and RS codes that are robust against an adversary that first permutes the codeword and then deletes symbols from the permuted codeword. The high-level intuition for this connection is as follows. In Shamir’s scheme, the dealer distributes a codeword of an RS code among the players. If an adversary can arbitrarily permute the shares and delete some of them, then robustness against permutations and deletions ensures that the secret can still be reconstructed without supplying the reconstruction algorithm with the identity of the player associated with each share. The anonymity property arises from a the following fact about [n,k]_{q} RS codes (which holds for all MDS codes): A restriction of the code to any k columns is equals the space \mathbb{F}_{q}^{k} . Before describing in further detail the connection, we recall the notion of secret-sharing. Secret-sharing, in general, is a cryptographic method that divides a secret (such as a cryptographic key or sensitive information) into multiple parts, known as shares, which are distributed among a group of participants. The key feature of secret-sharing is that only specific subsets of participants, defined by an access structure , can reconstruct the original secret from their shares. 2 2 2 In this paper we shall focus only on the specific case of threshold access structures. That is, every set of participants of size at least r (for some predetermined r ) can reconstruct the secret). One of the most well-known secret-sharing schemes in the literature is that of Shamir’s [ Sha79 ] . The formal definition of Shamir’s secret-sharing (SSS) is as follows. Given a secret s\in\mathbb{F} to be distributed, a reconstruction threshold k>0 and n parties (identified as n distinct elements \alpha_{i}\in\mathbb{F} ), a dealer randomly selects a polynomial f\in\mathbb{F}[x] of degree less than k such that f(0)=s , and sends to party i the share f(\alpha_{i}). It is easy to see that given k pairs (\alpha_{i},f(\alpha_{i})) , one can reconstruct the polynomial f(x) (using interpolation) and therefore recover the secret f(0) . Moreover, any k-1 such pairs reveal nothing about the secret. In [ EBG+24 , BGI+25 ] , the authors explored a stronger version of secret-sharing, where shares conceal information about the identities of the participants who hold them, and the secret is reconstructed without requiring the algorithm to know the identities of the share holders. Several notions of anonymity are discussed in [ BGI+25 ] , with the strongest one ensuring that any unauthorized set of shares is uniform and independent (such schemes are termed fully anonymous ). In [ EBG+24 ] , the authors presented a variant of Shamir’s secret-sharing scheme in which the shares conceal their identity, though not to the extent of being fully anonymous. One of the main limitations, aside from the lack of full anonymity, is that the reconstruction algorithm may fail (albeit with negligible

Read the complete text