Cryptology ePrint Archive: Report 2000/041

On Symmetrically Private Information Retrieval

Sanjeev Kumar Mishra

Abstract: In this paper we give single-round single-server symmetrically private information retrieval (SPIR) scheme, in which privacy of user follows from intractability of quadratic residuosity problem and and privacy of database follows from the number theoretic XOR assumption introduced in this paper. Proposed scheme achieves the communication complexity $O(n^{\e})$, for any $\e > 0$, where $n$ is the number of bits in the database. We also present an efficient block retrieval SPIR scheme. Intrestingly, we show that an $( K \log{n})$ SPIR scheme is possible if there exists an probabilistic bit encryption scheme on which certain operators can be defined with desired properties. Finally we go on to generalize SPIR scheme to private retrieval of secrets and sharing by a group of users. It can also be viewed as an extended secret sharing scheme. We also discover and prove certain properties related to quadratic residuosity in particular and probabilistic bit encryption in general.

Category / Keywords: cryptographic protocols / oblivious transfer, symmetrically private information retrieval, quadratic residuosity, probabilistic encryption, secret sharing scheme.

Date: received 7 Aug 2000

Contact author: s_k_mishra1 at hotmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20000808:172723 (All versions of this report)

Short URL: ia.cr/2000/041

Discussion forum: Show discussion | Start new discussion