[Resource Topic] 2000/041: On Symmetrically Private Information Retrieval

Welcome to the resource topic for 2000/041

On Symmetrically Private Information Retrieval

Authors: Sanjeev Kumar Mishra


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.

ePrint: https://eprint.iacr.org/2000/041

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .