New Techniques for Private Stream Searching

ABSTRACT

A system for private stream searching, introduced by Ostrovsky and Skeith, allows a client to provide an untrusted server with an encrypted search query. The server uses the query on a stream of documents and returns the matching documents to the client while learning nothing about the nature of the query. We present a new scheme for conducting private keyword search on streaming data which requires O(m) server to client communication complexity to return the content of the matching documents, where m is an upper bound on the size of the documents. The required storage on the server conducting the search is also O(m). The previous best scheme for private stream searching was shown to have O(m logm) communication and storage complexity. Our solution employs a novel construction in which the user reconstructs the matching files by solving a system of linear equations. This allows the matching documents to be stored in a compact buffer rather than relying on redundancies to avoid collisions in the storage buffer as in previous work. This technique requires a small amount of metadata to be returned in addition to the documents; for this the original scheme of Ostrovsky and Skeith may be employed with O(m logm) communication and storage complexity. We also present an alternative method for returning the necessary metadata based on a unique encrypted Bloom filter construction. This method requires O(m log(t/m)) communication and storage complexity, where t is the number of documents in the stream. In this article we describe our scheme, prove it secure, analyze its asymptotic performance, and describe a number of extensions. We also provide an experimental analysis of its scalability in practice. Specifically, we consider its performance in the demanding scenario of providing a privacy preserving version of the Google News Alerts service.

REFERENCES

• 1: Arrington, M. 2006. Aol proudly releases massive amounts of user search data. TechCrunch News.
• 2: John Bethencourt , Dawn Song , Brent Waters, New Constructions and Practical Applications for Private Stream Searching (Extended Abstract), Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.132-139, May 21-24, 2006 [doi>10.1109/SP.2006.27]
• 3: Bethencourt, J., Song, D., and Waters, B. 2006b. New techniques for private stream searching. Tech. rep. CMU-CS-06-106, Carnegie Mellon University.
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: Boneh, D., Crescenzo, G. D., Ostrovsky, R., and Persiano, G. 2004. Public key encryption with keyword search. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04).
• 6: Broder, A. and Mitzenmacher, M. 2005. Network applications of bloom filters: A survey. Internet Math. 1, 4, 485--509.
• 7: Cachin, C., Micali, S., and Stadler, M. 1999. Computationally private information retrieval with polylogarithmic communication. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Texhniques (EUROCRYPT’99).
• 8: Chang, Y.-C. 2004. Single database private information retrieval with logarithmic communication. In Proceedings of the Symposium on Information Security and Privacy (ACISP’04).
• 9: Chor, B., Gilboa, N., and Naor, M. 1997. Private information retrieval by keywords. Tech. rep. CS0917, Department of Computer Science, Technion.
• 10: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.41, October 23-25, 1995
• 11: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 12: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 13: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 14: Freedman, Ishai, Pinkas, and Reingold. 2005. Keyword search and oblivious pseudorandom functions. In Proceedings of the Theory of Cryptography Conference (TCC’05).
• 15: Goh, E.-J. 2003. Secure indexes. Cryptology ePrint Archive, Report 2003/216.
• 16: Kahn, J., Komlós, J., and Szemerédi, E. 1995. On the probability that a random ±1 matrix is singular. J. Amer. Math. Soc. 8, 1, 223--240.
• 17: Komlós, J. 1967. On the determinant of (0,1)-matrices. Studia Math. Hungarica 2, 7--21.
• 18: Wakaha Ogata , Kaoru Kurosawa, Oblivious keyword search, Journal of Complexity, v.20 n.2-3, p.356-371, April/June 2004 [doi>10.1016/j.jco.2003.08.023]
• 19: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.364, October 19-22, 1997
• 20: Lipmaa, H. 2005. An oblivious transfer protocol with log-squared communication. In Proceedings of the Information Security Conference (ISC’05).
• 21: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 22: Ostrovsky, R. and Skeith, W. 2005. Private searching on streaming data. In Proceedings of the Annual International Cryptology Conference (CRYPTO’05).
• 23: Ostrovsky, R. and Skeith, W. 2007. Algebraic lower bounds for computing on encrypted data. Tech. rep. TR07-022, Electronic Colloquium on Computational Complexity.
• 24: Paillier, P. 1999. Public-key cryptosystems based on composite degree residuosity classes. In Proceedings of the International Conference on the Theory and Applications of Cryptograhic Techniques (EUROCRYPT’99).
• 25: Silverman, R. 2001. A cost-based security analysis of symmetric and asymmetric key lengths. Tech. rep. RSA Laboratories. Nov.
• 26: Dawn Xiaodong Song , David Wagner , Adrian Perrig, Practical Techniques for Searches on Encrypted Data, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.44, May 14-17, 2000
• 27: Terence Tao , Van Vu, On random pm 1 matrices: singularity and determinant, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060655]
• 28: Tao, T. and Vu, V. H. 2007. On the singularity probability of random bernoulli matrices. J. Amer. Math. Soc. 20, 3, 603--628.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Performance, Security

Keywords:
Bloom filter, private information retrieval, private stream searching, public key program obfuscation