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 transfersymmetrically private information retrievalquadratic residuosityprobabilistic encryptionsecret sharing scheme.
Contact author(s)
s_k_mishra1 @ hotmail com
History
2000-08-08: received
Short URL
https://ia.cr/2000/041
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2000/041}},
      url = {https://eprint.iacr.org/2000/041}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.