[go: up one dir, main page]

What a lovely hat

Is it made out of tin foil?

Paper 2024/772

Reducing the Share Size of Weighted Threshold Secret Sharing Schemes via Chow Parameters Approximation

Oriol Farràs, Rovira i Virgili University
Miquel Guiot, Rovira i Virgili University
Abstract

A secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets. In a weighted threshold access structure, each party is assigned a weight according to its importance, and the authorized subsets are those in which the sum of their weights is at least the threshold value. For these access structures, the share size of the best known secret sharing schemes is either linear on the weights or quasipolynomial on the number of parties, which leads to long shares, in general. In certain settings, a way to circumvent this efficiency problem is to approximate the access structure by another one that admits more efficient schemes. This work is dedicated to the open problem posed by this strategy: Finding secret sharing schemes with a good tradeoff between the efficiency and the accuracy of the approximation. We present a method to approximate weighted threshold access structures by others that admit schemes with small shares. This method is based on the techniques for the approximation of the Chow parameters developed by De et al. [Journal of the ACM, 2014]. Our method provides secret sharing schemes with share size $n^{1+o(1)}$, where $n$ is the number of parties, and whose access structure is close to the original one. Namely, in this approximation the condition of being authorized or not is preserved for almost all subsets of parties. In addition, we apply the recent results on computational secret sharing schemes by Applebaum et al. [STOC, 2023] to construct computational secret sharing schemes whose share size is polylogarithmic in the number of parties.

Note: A major revision of an IACR publication in TCC 2024.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2024
DOI
10.1007/978-3-031-78023-3_17
Keywords
secret sharing schemeweighted threshold access structurethreshold cryptographyChow parameters
Contact author(s)
oriol farras @ urv cat
miquel guiot @ urv cat
History
2024-12-19: last of 2 revisions
2024-05-20: received
See all versions
Short URL
https://ia.cr/2024/772
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/772,
      author = {Oriol Farràs and Miquel Guiot},
      title = {Reducing the Share Size of Weighted Threshold Secret Sharing Schemes via Chow Parameters Approximation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/772},
      year = {2024},
      doi = {10.1007/978-3-031-78023-3_17},
      url = {https://eprint.iacr.org/2024/772}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.