CryptoDB
Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| 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 supplying tools for improving their complexity. We obtain the following 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 using general share conversions. For $k\geq 3$ servers, our main contribution is a simpler proof the correctness of the protocol, avoiding the partial derivatives and interpolation polynomials used by Ghasemi et al. - In addition to simplifying previous protocols, our 2-server protocols can use a relaxed variant of matching vectors over any $m$ that is the product of two distinct primes. Our constructions do not improve the communication complexity of PIR and CDS protocols; however, construction of better relaxed matching vectors over \emph{any} $m$ that is the product of two distinct primes will improve the communication complexity of $2$-server PIR and $2$- server CDS protocols. - 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. In an independent result, 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 result is achieved by a reduction to unbalanced CDS protocols (compared to balanced CDS protocols in previous constructions). |
BibTeX
@inproceedings{tcc-2025-36254,
title={Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes},
publisher={Springer-Verlag},
author={Or Lasri and Amos Beimel and Bar Alon},
year=2025
}