Lower-Bounds on Public-Key Operations in PIR

Explore fundamental limitations in Private Information Retrieval (PIR) protocols through this 35-minute conference talk that establishes crucial lower bounds on computational requirements. Learn how any PIR protocol without pre-processing forces servers to perform a nearly linear number of public-key operations relative to database size, independent of symmetric-key operation counts. Discover the broader implications of these theoretical findings for oblivious transfer (OT) extension protocols and their communication complexity constraints. Gain insights into the mathematical foundations that govern secure computation protocols and understand why certain efficiency limitations are inherent to PIR systems, providing essential knowledge for researchers and practitioners working in cryptography and privacy-preserving technologies.