Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes

This chapter delves into the cryptographic primitives of Private Information Retrieval (PIR) protocols, Conditional Disclosure of Secrets (CDS) protocols, and secret-sharing schemes, focusing on their information-theoretic security. The text explores the close relationships between these primitives and their applications in protecting the secrecy of inputs. It highlights the dramatic improvements in the complexity of these protocols over the past few years and the ongoing challenge of determining their optimal complexity. The chapter presents new techniques to address the upper bounds for these primitives, simplifying and generalizing current constructions, and providing new tools for better constructions. It also introduces improved linear secret-sharing schemes, reducing the exponent in the share size. The text discusses the abstraction of the DG and GKS PIR protocols and the LVW and BFL CDS protocols, presenting a simplified 2-server PIR protocol and a simple 3-server PIR protocol. Additionally, it covers the construction of improved linear secret-sharing schemes for arbitrary access structures, using techniques such as covering and bootstrapping. The chapter concludes with a detailed analysis of the share size for downslices with low and high density, providing new upper bounds on the share size of linear secret-sharing schemes for all access structures.