Journal of University of Chinese Academy of Sciences >
Σ-private private information retrieval protocols
Received date: 2010-06-07
Revised date: 2010-08-13
Online published: 2011-05-15
We pose the definition of Σ-private private information retrieval (PIR) protocol,and then construct a Σ-private PIR protocol based on verifiable secret sharing(VSS)scheme on general access structure . We also construct an efficient robust Σ-private PIR protocol based on robust multiplication protocol and the database is also secure. The corresponding communication complexity is dependent on the size of the access structure and is efficient for minority of servers.
ZHANG Zi-Kun , LV Ke-Wei . Σ-private private information retrieval protocols[J]. Journal of University of Chinese Academy of Sciences, 2011 , 28(3) : 389 -397 . DOI: 10.7523/j.issn.2095-6134.2011.3.017
[1] Chor B, Goldreich O, Kushilevitz E, et al. Private information retrieval
[J]. J of the ACM, 1998, 45:965-981.
[2] Kushileviz E, Ostrovsky R. Replication is not needed: single-database computationally private information retrieval //Proc of the 38th Annu IEEE Symp FOCS, 1997:364-373.
[3] Cachin C, Micali S, Stadler M. Computationally private information retrieval with polylogarithmic communication //Proc EUROCRYPT’99. 1999, 1592:402–414.
[4] Beaver D, Feigenbaum J. Hiding instances in multioracle queries //Proc of the 7th Annu Symp on Theoretical Aspects of Computer Science. LNCS 415, Springer-Verlag, 1990:37-48.
[5] Beaver D, Feigenbaum J, Kilian J, et al. Locally Random reductions: improvements and applications
[J]. J of Cryptology, 1997, 10(1):17-36.
[6] Ambainis A. Upper bound on the communication complexity of private information retrieval //Proc of 24th ICALP. LNCS 1256, Springer-Verlag, 1997: 401-407.
[7] Ishai Y, Kushilevitz E. Improved upper bounds on information-theoretic private information retrieval //Proc of the 31st ACM Symp on the Theory of Computing. 1999:79-88.
[8] Beimel A, Ishai Y, Kushilevitz E, et al. Breaking the O(n1/2k-1) barrier for information-theoretic private information retrieval //Proc of 43rd Annu IEEE Symp. FOCS, 2002:261-270.
[9] Yekhanin S. New locally decodable codes and private information retrieval schemes . Electronic Colloquium on Computational Complexity (ECCC), 2006:127.
[10] Beimel A, Ishai Y. Information-theoretic private information retrieval: a unified construction //Proc of the 28th International Colloquium on Automata, Languages and Programming. LNCS 2076, Springer-Verlag, 2001:912-926.
[11] Beimel A, Stahl Y. Robust information-theoretic private information retrieval //Third Conference on Security in Communication Networks. LNCS 2576, Springer-Verlag, 2002:326-341.
[12] Goldberg I. Improving the robustness of private information retrieval //Proc of 2007 IEEE Symposium on Security and Privacy. 2007: 131-145.
[13] Maurer U. Secure multi-party computation made simple //Proc of SCN`02. LNCS 2576, Springer-Verlag, 2003:14-28.
/
| 〈 |
|
〉 |