Ning Shang
Elisa Bertino
ABSTRACT
Private Information Retrieval (PIR) protocols allow users to learn data items stored at a server which is not fully trusted, without disclosing to the server the particular data element retrieved. Several PIR protocols have been proposed, which provide strong guarantees on user privacy. Nevertheless, in many application scenarios it is important to protect the database as well. In this paper, we investigate the amount of data disclosed by the the most prominent PIR protocols during a single run. We show that a malicious user can stage attacks that allow an excessive amount of data to be retrieved from the server. Furthermore, this vulnerability can be exploited even if the client follows the legitimate steps of the PIR protocol, hence the malicious request can not be detected and rejected by the server. We devise mechanisms that limit the PIR disclosure to a single data item.
- E Bach and J Shallit. Algorithmic Number Theory. MIT Press, Cambridge, MA, USA, 1996. Google Scholar
Digital Library
- A Beimel, Y Ishai, E Kushilevitz, and J-F Reymond. Breaking the O(n
1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. In IEEE Symposium on Foundations of Computer Science, pages 261--270, 2002. Google ScholarDigital Library
- C Cachin, S Micali, and M Stadler. Computationally private information retrieval with polylogarithmic communication. In EUROCRYPT, pages 402--414. Springer, 1999. Google ScholarDigital Library
- B Chor, O Goldreich, E Kushilevitz, and M Sudan. Private information retrieval. In IEEE Symposium on Foundations of Computer Science, pages 41--50, 1995. Google ScholarDigital Library
- G Ghinita, P Kalnis, A Khoshgozaran, C Shahabi, and K-L Tan. Private queries in location based services: anonymizers are not necessary. In Proceedings of ACM SIGMOD, pages 121--132, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- E Kushilevitz and R Ostrovsky. Replication is NOT needed: Single database, computationally-private information retrieval. In IEEE Symposium on Foundations of Computer Science, pages 364--373, 1997. Google ScholarDigital Library
- M Naor and B Pinkas. Oblivious transfer and polynomial evaluation. In STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 245--254, 1999. Google ScholarDigital Library
- K Narayanam and C Rangan. A Novel Scheme for Single Database Symmetric Private Information Retrieval. In Proceedings of Annual Inter Research Institute Student Seminar in Computer Science (IRISS), pages 803--815, 2006.Google Scholar
- N Shang, G Ghinita, Y Zhou, and E Bertino. Controlling data disclosure in computational pir protocols (extended abstract). http://rmal.info/papers/sgzb2009.pdf. The full version of this paper.Google Scholar
Index Terms
- Controlling data disclosure in computational PIR protocols
Recommendations
Lower-Bounds on Public-Key Operations in PIR
Advances in Cryptology – EUROCRYPT 2024AbstractPrivate information retrieval (PIR) is a fundamental cryptographic primitive that allows a user to fetch a database entry without revealing to the server which database entry it learns. PIR becomes non-trivial if the server communication is less ...
Black-Box Constructions of Protocols for Secure Computation
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor ...
An Oblivious Transfer Protocol Based on Elgamal Encryption for Preserving Location Privacy
Location based services (LBS) are applications that require a client's geographical location to provide a service or a piece of information that is related to the client at that location. Although LBSs promise safety and convenience, they threaten the ...
Comments