A tight lower bound for restricted PIR protocols

DOI10.1007/S00037-006-0208-3zbMATH Open1099.68035OpenAlexW2059123783MaRDI QIDQ2506166FDOQ2506166

Authors: Richard Beigel, William Gasarch, Lance Fortnow 

Publication date: 28 September 2006

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-006-0208-3

Recommendations

• General constructions for information-theoretic private information retrieval
• Some results on query processes and reconstruction functions for unconditionally secure 2-server 1-round binary private information retrieval protocols
• An \(\Omega (n^{1/3})\) lower bound for bilinear group based private information retrieval

zbMATH Keywords

lower boundsprivacyPrivate information retrieval

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (2)

• New Lower Bounds for Privacy in Communication Protocols
• An Efficient PIR Construction Using Trusted Hardware

This page was built for publication: A tight lower bound for restricted PIR protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2506166)