Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• Informally, private information retrieval for k≧1 databases (k-PIR) is an interactive scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et.al. proposed 2-PIR with communication complexity 12n^<1/3>+2 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k≧2, there exists k-PIR with communication complexity at most c_k・n^<1/(2k-1)> some constant c_k>0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12n^<1/3>. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k≧4, there exists k-PIR witla communication complexity at most c'_k・n^<1/(2k-1)> for some constant c'_k≪c_k.

• 社団法人電子情報通信学会の論文
• 1999-01-25

著者

• Itoh Toshiya

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

関連論文

• Checkers for Adaptive Programs
• Alternative Necessary and Sufficient Conditions for Collision Intractable Hashing
• A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
• Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
• On the Power of Self-Testers and Self-Correctors (Special Section on Cryptography and Information Security)
• On the Knowledge Tightness of Zero-Knowledge Proofs (Special Section on Cryptography and Information Security)
• Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)
• On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity (Special Section on Cryptography and Information Security)
• On the Knowledge Complexity of Arthur-Merlin Games (Special Section on Cryptography and Information Security)

スポンサーリンク