Structural signatures for tree data structures

ABSTRACT

Data sharing with multiple parties over a third-party distribution framework requires that both data integrity and confidentiality be assured. One of the most widely used data organization structures is the tree structure. When such structures encode sensitive information (such as in XML documents), it is crucial that integrity and confidentiality be assured not only for the content, but also for the structure. Digital signature schemes are commonly used to authenticate the integrity of the data. The most widely used such technique for tree structures is the Merkle hash technique, which however is known to be "not hiding", thus leading to unauthorized leakage of information. Most techniques in the literature are based on the Merkle hash technique and thus suffer from the problem of unauthorized information leakages. Assurance of integrity and confidentiality (no leakages) of tree-structured data is an important problem in the context of secure data publishing and content distribution systems.

In this paper, we propose a signature scheme for tree structures, which assures both confidentiality and integrity and is also efficient, especially in third-party distribution environments. Our integrity assurance technique, which we refer to as the "Structural signature scheme", is based on the structure of the tree as defined by tree traversals (pre-order, post-order, in-order) and is defined using a randomized notion of such traversal numbers. In addition to formally defining the technique, we prove that it protects against violations of content and structural integrity and information leakages. We also show through complexity and performance analysis that the structural signature scheme is efficient; with respect to the Merkle hash technique, it incurs comparable cost for signing the trees and incurs lower cost for user-side integrity verification.

REFERENCES

• 1: IBM XL C/C++. http://www-306.ibm.com/software/awdtools/xlcpp/.
• 2: Java cryptographic architecture. http://java.sun.com/javase/6/docs/technotes/guides/ security/crypto/CryptoSpec.html.
• 3: Rakesh Agrawal , Jerry Kiernan , Ramakrishnan Srikant , Yirong Xu, Order preserving encryption for numeric data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007632]
• 4: Elisa Bertino , Barbara Carminati , Elena Ferrari , Bhavani Thuraisingham , Amar Gupta, Selective and Authentic Third-Party Distribution of XML Documents, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1263-1278, October 2004 [doi>10.1109/TKDE.2004.63]
• 5: A. Buldas and S. Laur. Knowledge-binding commitments with applications in time-stamping. In Public Key Cryptography, pages 150--165, 2007.
• 6: S. Chatvichienchai and M. Iwaihara. Detecting information leakage in updating XML documents of fine-grained access control. In Database and Expert Systems Applications, 2006.
• 7: Sajal K. Das , Kwang Bae Min , Ranette H. Halverson, Efficient Parallel Algorithms for Tree-Related Problems Using the Parentheses Matching Strategy, Proceedings of the 8th International Symposium on Parallel Processing, p.362-367, April 01, 1994
• 8: P. Devanbu , M. Gertz , A. Kwong , C. Martel , G. Nuckolls , S. G. Stubblebine, Flexible authentication of XML documents, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502003]
• 9: Yevgeniy Dodis , Adam Smith, Correcting errors without leaking partial information, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060688]
• 10: Siddhartha K. Goel , Chris Clifton , Arnon Rosenthal, Derived access control specification for XML, Proceedings of the 2003 ACM workshop on XML security, October 31-31, 2003, Fairfax, Virginia [doi>10.1145/968559.968561]
• 11: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 12: M. Goodrich and R. Tamassia. Efficient authenticated dictionaries with skip lists and commutative hashing, 2000.
• 13: Michael T. Goodrich , Roberto Tamassia , Jasminka Hasic, An Efficient Dynamic and Distributed Cryptographic Accumulator, Proceedings of the 5th International Conference on Information Security, p.372-388, September 30-October 02, 2002
• 14: M. T. Goodrich, R. Tamassia, N. Triandopoulos, and R. Cohen. Authenticated data structures for graph and geometric searching. In Lecture Notes in Computer Science, pages 295--313, Berlin / Heidelberg, 2003. Springer.
• 15: Keith Irwin , Ting Yu, Preventing attribute information leakage in automated trust negotiation, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102128]
• 16: V. Kamakoti , C. Pandu Rangan, An optimal algorithm for reconstructing a binary tree, Information Processing Letters, v.42 n.2, p.113-115, May 11, 1992 [doi>10.1016/0020-0190(92)90099-H]
• 17: D. E. Knuth. The Art of Computer Programming, volume 1. Pearson Education Asia, third edition, 2002.
• 18: Paul C. Kocher, On Certificate Revocation and Validation, Proceedings of the Second International Conference on Financial Cryptography, p.172-177, February 23-25, 1998
• 19: Ashish Kundu , Bertino Elisa, Secure Dissemination of XML Content Using Structure-based Routing, Proceedings of the 10th IEEE International Enterprise Distributed Object Computing Conference, p.153-164, October 16-20, 2006 [doi>10.1109/EDOC.2006.46]
• 20: Charles Martel , Glen Nuckolls , Premkumar Devanbu , Michael Gertz , April Kwong , Stuart G. Stubblebine, A General Model for Authenticated Data Structures, Algorithmica, v.39 n.1, p.21-41, January 2004 [doi>10.1007/s00453-003-1076-8]
• 21: Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
• 22: Matthew Morgenstern, Security and inference in multilevel database and knowledge-base systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.357-373, May 27-29, 1987, San Francisco, California, United States
• 23: Adrian Perrig, The BiBa one-time signature and broadcast authentication protocol, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.501988]
• 24: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 25: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 26: Hui Wang , Laks V. S. Lakshmanan, Efficient secure query evaluation over encrypted XML databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 27: Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Ke Wang , Jian Pei, Minimality attack in privacy preserving data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 28: P. Zezula, G. Amato, F. Debole, and F. Rabitti. Tree signatures for XML querying and navigation. In Database and XML Technologies, pages 149--163, 2003.
• 29: Nan Zhang , Wei Zhao, Distributed privacy preserving information sharing, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness); Distributed systems

General Terms:
Design, Management, Performance, Security