Cryptology ePrint Archive: Report 2012/352

On Hashing Graphs

Ashish Kundu, Elisa Bertino

Abstract: Collision resistant one-way hashing schemes are the basic building blocks of almost all crypto-systems. Use of graph-structured data models are on the rise -- in graph databases, representation of biological and healthcare data as well as in modeling systems for representing system topologies. Therefore, the problem of hashing graphs with respect to crypto-systems needs to be studied and addressed. The traditional Merkle Hash technique cannot be applied as it is because graphs are more complex data structures than trees. In this paper, we make the following contributions: (1) we define the formal security model of hashing schemes for graphs, (2) we define the formal security model of leakage-free hashing schemes for graphs, (3) we describe a hashing scheme for hashing directed and undirected graphs that uses Merkle hash technique, (4) and a hashing scheme that uses structural information instead of Merkle hash technique, (5) we define leakage-free hashing schemes for graphs. Our constructions use graph traversal techniques and are highly efficient with respect to updates to graphs: they require as little as two (O(1)) hash values to be updated to refresh the hash of the graph, while the Merkle Hash Technique and Search DAG schemes for trees and DAGs respectively require as many as O(|V|) and O(|V|+|E|).

Category / Keywords: cryptographic protocols / Hash, Graphs, Merkle Hash Technique

Publication Info: Manuscript (Preliminary draft)

Date: received 20 Jun 2012

Contact author: akundu at us ibm com

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20120622:200244 (All versions of this report)

Discussion forum: Show discussion | Start new discussion