Paper 2024/1599
Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes
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 the three primitives has been dramatically improved in the last few years and they are closely related, i.e., 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 message size required in PIR and CDS protocols and the share size required in secret-sharing schemes are 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), the recent multi-server PIR protocol
of Ghasemi, Kopparty, and Sudan (STOC 2025), 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). In
particular, we present one PIR protocol generalizing both the 2-
server and multi-server PIR protocols. 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 2-server
protocols can use matching vectors over any
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Secret SharingConditional Disclosure of SecretsPrivate Information Retrieval
- Contact author(s)
-
alonbar08 @ gmail com
amos beimel @ gmail com
orshlomo @ post bgu ac il - History
- 2025-03-24: last of 2 revisions
- 2024-10-08: received
- See all versions
- Short URL
- https://ia.cr/2024/1599
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1599, author = {Bar Alon and Amos Beimel and Or Lasri}, title = {Simplified {PIR} and {CDS} Protocols and Improved Linear Secret-Sharing Schemes}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1599}, year = {2024}, url = {https://eprint.iacr.org/2024/1599} }