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

• URL: http://arxiv.org/abs/2412.17003v1
• Date: Sun, 22 Dec 2024 12:51:16 GMT
• Title: Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions
• Authors: Roni Con,
• Abstract summary: We study the performance of Reed-Solomon codes against an adversary that permutes the symbols of the codeword and then performs insertions and deletions. 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.
• Score: 9.065034043031668
• License:
• 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.

Related papers

• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants. We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• A Construction of Evolving $3$-threshold Secret Sharing Scheme with Perfect Security and Smaller Share Size [11.114225631904004]
  We consider the evolving $k$-threshold secret sharing scheme with $k=3. We then propose a new evolving $3$-threshold scheme with perfect security. Based on this model of the revised scheme and the proposed conventional $3$-threshold scheme, we present a brand-new and more concise $3$-threshold secret sharing scheme.
  arXiv  Detail & Related papers  (2024-10-17T13:17:11Z)
• Secret Sharing with Certified Deletion [4.082216579462796]
  Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. In secret sharing with certified deletion, a (classical) secret is split into quantum shares which can be verifiably destroyed. We show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion.
  arXiv  Detail & Related papers  (2024-05-13T19:01:08Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages [14.150289683819759]
  We introduce the notions of split-state non-malleable codes and secret sharing schemes for quantum messages secure against quantum adversaries with shared entanglement. More precisely, we construct efficiently encodable and decodable split-state non-malleable codes and secret sharing schemes for quantum messages preserving entanglement with external systems.
  arXiv  Detail & Related papers  (2023-08-12T05:15:35Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• RiDDLE: Reversible and Diversified De-identification with Latent Encryptor [57.66174700276893]
  This work presents RiDDLE, short for Reversible and Diversified De-identification with Latent Encryptor. Built upon a pre-learned StyleGAN2 generator, RiDDLE manages to encrypt and decrypt the facial identity within the latent space.
  arXiv  Detail & Related papers  (2023-03-09T11:03:52Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Hiding Images in Deep Probabilistic Models [58.23127414572098]
  We describe a different computational framework to hide images in deep probabilistic models. Specifically, we use a DNN to model the probability density of cover images, and hide a secret image in one particular location of the learned distribution. We demonstrate the feasibility of our SinGAN approach in terms of extraction accuracy and model security.
  arXiv  Detail & Related papers  (2022-10-05T13:33:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.