Zerber: r-confidential indexing for distributed documents

ABSTRACT

To carry out work assignments, small groups distributed within a larger enterprise often need to share documents among themselves while shielding those documents from others' eyes. In this situation, users need an indexing facility that can quickly locate relevant documents that they are allowed to access, without (1) leaking information about the remaining documents, (2) imposing a large management burden as users, groups, and documents evolve, or (3) requiring users to agree on a central completely trusted authority. To address this problem, we propose the concept of r-confidentiality, which captures the degree of information leakage from an index about the terms contained in inaccessible documents. Then we propose the r-confidential Zerber indexing facility for sensitive documents, which uses secret splitting and term merging to provide tunable limits on information leakage, even under statistical attacks; requires only limited trust in a central indexing authority; and is extremely easy to use and administer. Experiments with real-world data show that Zerber offers excellent performance for index insertions and lookups while requiring only a modest amount of storage space and network bandwidth.

REFERENCES

• 1: Wolf-Tilo Balke , Wolfgang Nejdl , Wolf Siberski , Uwe Thaden, Progressive Distributed Top-k Retrieval in Peer-to-Peer Networks, Proceedings of the 21st International Conference on Data Engineering, p.174-185, April 05-08, 2005 [doi>10.1109/ICDE.2005.115]
• 2: Matthias Bender , Sebastian Michel , Peter Triantafillou , Gerhard Weikum , Christian Zimmer, MINERVA: collaborative P2P search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: 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
• 4: 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]
• 5: 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]
• 6: Elisa Bertino , Sushil Jajodia , Pierangela Samarati, Database security: research and practice, Information Systems, v.20 n.7, p.537-556, Nov. 1995 [doi>10.1016/0306-4379(95)00029-4]
• 7: Elisa Bertino , Ravi Sandhu, Database Security-Concepts, Approaches, and Challenges, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.2-19, January 2005 [doi>10.1109/TDSC.2005.9]
• 8: Matt Blaze, A cryptographic file system for UNIX, Proceedings of the 1st ACM conference on Computer and communications security, p.9-16, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168590]
• 9: Kaouthar Blibech , Alban Gabillon, CHRONOS: an authenticated dictionary based on skip lists for timestamping systems, Proceedings of the 2005 workshop on Secure web services, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103022.1103037]
• 10: Boneh, D., Crescenzo, G. D., Ostrovsky, R., and Persiano, G., Public-key encryption with keyword search, In Proceedings of Eurocrypt 2004.
• 11: Büttcher, S. and Clarke, C. L. A. A Security Model for Full-Text File System Search in Multi-User Environments; In Proceedings of the FAST, 2005, San Francisco, California.
• 12: Chang, Y.-C. and Mitzenmacher, M. Privacy preserving keyword searches on remote encrypted data. Cryptology ePrint Archive, Report 2004/051, Feb 2004. http://eprint.iacr.org/2004/051/
• 13: Taenam Cho , Sang-Ho Lee , Won Kim, A group key recovery mechanism based on logical key hierarchy, Journal of Computer Security, v.12 n.5, p.711-736, September 2004
• 14: Crescenzi, P. and Kann, V. A compendium of NP optimization problems. Available at: http://www.nada.kth.se/~viggo/problemlist/.
• 15: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 16: 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]
• 17: Goh, E., Shacham, H., Modadugu, N. and Boneh, D. Sirius: Securing remote untrusted storage. In NDSS, 2003.
• 18: Goodrich, M., Tamassia, R., and Schwerin, A. Implementation of an authenticated dictionary with skip lists and commutative hashing. In DISCEX II, 2001.
• 19: 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]
• 20: David Hawking, Challenges in enterprise search, Proceedings of the 15th Australasian database conference, p.15-24, January 01, 2004, Dunedin, New Zealand
• 21: Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
• 22: 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]
• 23: 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
• 24: 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.
• 25: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 26: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 27: 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
• 28: 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
• 29: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 30: Singhal, A. Modern Information Retrieval: A Brief Overview. In IEEE, Data Eng. Bull. 24(4), 2001
• 31: 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
• 32: Stud IP LMS. Available at: http://www.studip.de/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing