2004 | OriginalPaper | Buchkapitel
Single Database Private Information Retrieval with Logarithmic Communication
verfasst von : Yan-Cheng Chang
Erschienen in: Information Security and Privacy
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8].In fact, our schemes directly yield implementations for 1-out-of-N ℓ-bit string oblivious transfer with O(ℓ) sender-side communication (against semi-honest receivers and malicious senders). Note the sender-side communication complexity is independent of N, the constant hidden in the big-O notation is quite small, and ℓ is unrestricted. Moreover, we show a way to do communication balancing between the sender-side and the receiver-side, and show how to handle malicious receivers with small communication overheads.