CryptoDB
On Symmetrically Private Information Retrieval
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2000-11385,
title={On Symmetrically Private Information Retrieval},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / oblivious transfer, symmetrically private information retrieval, quadratic residuosity, probabilistic encryption, secret sharing scheme.},
url={http://eprint.iacr.org/2000/041},
note={ s_k_mishra1@hotmail.com 11177 received 7 Aug 2000},
author={Sanjeev Kumar Mishra},
year=2000
}