Lower-Bounds on Public-Key Operations in PIR

on YouTube ↗35m

" summary

Proves a concrete barrier: any PIR without preprocessing that treats group/HomEnc-style primitives as a simulatable oracle forces the server to do a nearly linear amount of public-key work (query-size × query-count ≈ n), independent of symmetric-key effort. Shows a compilation that replaces S-oracle calls by having the receiver lazily simulate them, paying sender communication proportional to S-queries; derives communication lower-bounds for OT extension (IKNP optimal) and for general asymmetric 2PC. Notes LWE-style non-simulatable assumptions and preprocessing are outside the impossibility.

AI-written summary · about

" chapters (10)

1. 0:00Lower-bounds in PIR
2. 1:04Simplest lower-bound consequences
3. 4:55Sublinear public-key in PIR?
4. 11:25Asymmetric PSI overhead
5. 14:19OT extension fails for PIR
6. 20:08Main result public-key PIR
7. 23:24Simulatable oracles
8. 27:35PIR protocol compilation
9. 29:48PIR consequences open problems
10. 32:39Q&A

" related talks

• 01h 04mDoubly Efficient Private Information RetrievalElette Boyle · Quantum and Lattices Joint Reunion Workshop
• 43mSingle-Server Private Information Retrieval with Sublinear Amortized TimeAlexandra Henzinger · Quantum and Lattices Joint Reunion Workshop
• 59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWEDaniel Wichs · Minimal Complexity Assumptions for Cryptography 2023
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 14mPrivate Information Retrieval and Oblivious RAMElaine Shi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 01h 01mCircularity Based IO, Part 1Rafael Pass, Romain Gay · Simons Institute Workshop: New Developments in Obfuscation