On Symmetrically Private Information Retrieval

Sanjeev Kumar Mishra

Paper 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.

Metadata

Available format(s): PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: oblivious transfer symmetrically private information retrieval quadratic residuosity probabilistic encryption secret sharing scheme.
Contact author(s): s_k_mishra1 @ hotmail com
History: 2000-08-08: received
Short URL: https://ia.cr/2000/041
License: CC BY

BibTeX

@misc{cryptoeprint:2000/041,
      author = {Sanjeev Kumar Mishra},
      title = {On Symmetrically Private Information Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/041},
      year = {2000},
      url = {https://eprint.iacr.org/2000/041}
}