On Basing Private Information Retrieval on NP-Hardness

DOI10.1007/978-3-662-49096-9_16zbMath1388.94070MaRDI QIDQ2796134

Tianren Liu, Vinod Vaikuntanathan

Publication date: 23 March 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-662-49096-9_16

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94A60: Cryptography

68P20: Information storage and retrieval of data

Related Items

Structure Versus Hardness Through the Obfuscation Lens, On basing search SIVP on \(\mathbf{NP}\)-hardness, Public-coin statistical zero-knowledge batch verification against malicious verifiers, On the complexity of collision resistant hash functions: new and old black-box separations

Cites Work

• Unnamed Item
• Unnamed Item
• Does co-NP have short interactive proofs ?
• Theory of cryptography. Second theory of cryptography conference, TCC 2005, Cambridge, MA, USA, February 10--12, 2005. Proceedings.
• One-way functions are essential for single-server private information retrieval
• Limits of Provable Security for Homomorphic Encryption
• On basing one-way functions on NP-hardness
• Private information retrieval
• Relativized cryptography
• Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
• Fully homomorphic encryption using ideal lattices
• On Basing Size-Verifiable One-Way Functions on NP-Hardness
• Polar Codes are Optimal for Lossy Source Coding
• Information Security
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Theory of Cryptography
• Theory of Cryptography
• Automata, Languages and Programming
• On Worst‐Case to Average‐Case Reductions for NP Problems