A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval
From MaRDI portal
Publication:5445520
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
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