A tight lower bound for restricted PIR protocols

DOI10.1007/S00037-006-0208-3MaRDI QIDQ2506166zbMATH OpenOpenAlexFDO

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

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)

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

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)