Zerber+R: top-k retrieval from a confidential index

ABSTRACT

Privacy-preserving document exchange among collaboration groups in an enterprise as well as across enterprises requires techniques for sharing and search of access-controlled information through largely untrusted servers. In these settings search systems need to provide confidentiality guarantees for shared information while offering IR properties comparable to the ordinary search engines. Top-k is a standard IR technique which enables fast query execution on very large indexes and makes systems highly scalable. However, indexing access-controlled information for top-k retrieval is a challenging task due to the sensitivity of the term statistics used for ranking.

In this paper we present Zerber^+R -- a ranking model which allows for privacy-preserving top-k retrieval from an outsourced inverted index. We propose a relevance score transformation function which makes relevance scores of different terms indistinguishable, such that even if stored on an untrusted server they do not reveal information about the indexed data. Experiments on two real-world data sets show that Zerber^+R makes economical usage of bandwidth and offers retrieval properties comparable with an ordinary inverted index.

REFERENCES

• 1: Alspach, D. and Sorenson, H. Nonlinear Bayesian Estimation Using Gaussian Sum Approximations. IEEE Transactions on Automatic Control, Vol. 17, No. 4, p. 439--448, Aug., 1972.
• 2: Mayank Bawa , Roberto J. Bayardo, Jr. , Rakesh Agrawal, Privacy-preserving indexing of documents on the network, Proceedings of the 29th international conference on Very large data bases, p.922-933, September 09-12, 2003, Berlin, Germany
• 3: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering, p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 4: Elisa Bertino , Silvana Castano , Elena Ferrari, Securing XML Documents with Author-X, IEEE Internet Computing, v.5 n.3, p.21-31, May 2001 [doi>10.1109/4236.935172]
• 5: Boneh, D., Crescenzo, G. D., Ostrovsky, R., and Persiano, G., Public-key encryption with keyword search. In Proceedings of Eurocrypt 2004.
• 6: Stefan Büttcher , Charles L. A. Clarke, A security model for full-text file system search in multi-user environments, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.13-13, December 13-16, 2005, San Francisco, CA
• 7: Chang, Y.-C. and Mitzenmacher, M. Privacy preserving keyword searches on remote encrypted data. Cryptology ePrint Archive, Report 2004/051, Feb 2004.
• 8: Benjamin C. M. Fung , Ke Wang , Philip S. Yu, Top-Down Specialization for Information and Privacy Preservation, Proceedings of the 21st International Conference on Data Engineering, p.205-216, April 05-08, 2005 [doi>10.1109/ICDE.2005.143]
• 9: Goh, E., Shacham, H., Modadugu, N. and Boneh, D. Sirius: Securing remote untrusted storage. In NDSS, 2003.
• 10: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 11: Vijay S. Iyengar, Transforming data to satisfy privacy constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775089]
• 12: Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 13: Kohlschütter, C., Chirita, P.-A. and Nejdl W. Using Link Analysis to Identify Aspects in Faceted Web Search. SIGIR'2006 Faceted Search Workshop, 2006, Seattle, WA.
• 14: Gerome Miklau , Dan Suciu, Controlling access to published data using cryptography, Proceedings of the 29th international conference on Very large data bases, p.898-909, September 09-12, 2003, Berlin, Germany
• 15: Soumyadeb Mitra , Windsor W. Hsu , Marianne Winslett, Trustworthy keyword search for regulatory-compliant records retention, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 16: Open Directory Project: http://www.dmoz.org/
• 17: Rice, J. Mathematical Statistics and Data Analysis II Edition 1995. ISBN 0-534-20934-3
• 18: Singhal, A. Modern Information Retrieval: A Brief Overview. In IEEE, Data Eng. Bull. 24(4), 2001
• 19: 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
• 20: Stud IP LMS. Available at: http://www.studip.de/.
• 21: Ashwin Swaminathan , Yinian Mao , Guan-Ming Su , Hongmei Gou , Avinash L. Varna , Shan He , Min Wu , Douglas W. Oard, Confidentiality-preserving rank-ordered search, Proceedings of the 2007 ACM workshop on Storage security and survivability, October 29-29, 2007, Alexandria, Virginia, USA [doi>10.1145/1314313.1314316]
• 22: Sergej Zerr , Elena Demidova , Daniel Olmedilla , Wolfgang Nejdl , Marianne Winslett , Soumyadeb Mitra, Zerber: r-confidential indexing for distributed documents, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353380]