Welcome to the resource topic for 2024/1599
Title:
Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes
Authors: Bar Alon, Amos Beimel, Or Lasri
Abstract:We consider 3 related cryptographic primitives, private information retrieval (PIR) protocols, conditional disclosure of secrets (CDS) protocols, and secret-sharing schemes; these primitives have many applications in cryptography. We study these primitives requiring information-theoretic security. The complexity of these primitives has been dramatically improved in the last few years are they are closely related, i.e., the the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016) was transformed to construct the CDS protocols of Liu, Vaikuntanathan, and Wee (CRYPTO 2017, Eurocrypt 2018) and these CDS protocols are the main ingredient in the construction of the best known secret-sharing schemes.
To date, the messages size required in PIR and CDS protocols and the share size required in secret-sharing schemes is not understood and there are big gaps between their upper bounds and lower bounds. The goal of this paper is to try to better understand the upper bounds by simplifying current constructions and improving their complexity.
We obtain the following two independent results:
- We simplify, abstract, and generalize the 2-server PIR protocol of
Dvir and Gopi (J. ACM 2016) and the 2-server and multi-server
CDS protocols of Liu et al. (CRYPTO 2017, Eurocrypt 2018) and
Beimel, Farr`as, and Lasri (TCC 2023). This is done by considering
a new variant of matching vectors and by using a general share
conversion. In addition to simplifying previous protocols, our
protocols can use matching vectors over any m that is product
of two distinct primes.
Our construction does not improve the communication
complexity of PIR and CDS protocols; however, construction of
better matching vectors over any m that is product of
two distinct primes will improve their communication complexity.
- In many applications of secret-sharing schemes it is important that
the scheme is linear, e.g., by using the fact that parties can locally
add shares of two secrets and obtain shares of the sum of the
secrets. We provide a construction of linear secret-sharing
schemes for $n$-party access structures with improved share size
of $2^{0.7563n}$. Previously, the best share size for linear secret-
sharing schemes was $2^{0.7576n}$ and it is known that for most
$n$-party access structures the shares size is at least $2^{0.5n}$.
This results is achieved by a reduction to unbalanced CDS
protocols (compared to balanced CDS protocols in previous
constructions).
ePrint: https://eprint.iacr.org/2024/1599
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .