A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval

DOI10.1007/978-3-540-78524-8_25zbMath1162.94363MaRDI QIDQ5445520

Iftach Haitner, Gil Segev, Jonathan Hoch

Publication date: 5 March 2008

Published in: Theory of Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78524-8_25

Mathematics Subject Classification ID

94A60: Cryptography

Related Items

A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval, Private Coins versus Public Coins in Zero-Knowledge Proof Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Perfect zero-knowledge arguments for NP using any one-way permutation
• Encryption against storage-bounded adversaries from on-line strong extractors
• Randomness is linear in space
• One-way functions are essential for single-server private information retrieval
• Lower bounds on the efficiency of encryption and digital signature schemes
• One-Way Permutations, Interactive Hashing and Statistically Hiding Commitments
• Computing with Very Weak Random Sources
• Foundations of Cryptography
• Foundations of Cryptography
• Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
• Advances in Cryptology - EUROCRYPT 2004
• Information Security and Privacy
• A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval
• Information Security
• Bounds on the Efficiency of Generic Cryptographic Constructions
• Theory of Cryptography
• Automata, Languages and Programming
• Automata, Languages and Programming
• Theory of Cryptography
• Theory of Cryptography