HMACs for Graph Data

Speaker:  Ashish Kundu – San Jose, CA, United States
Topic(s):  Information Systems, Search, Information Retrieval, Database Systems, Data Mining, Data Science


Graphs are widely used in the representation and processing of data in several domains. Assurance of integrity of graph data is essential. Related work has shown that the digital signatures for graphs are expensive operations. While digital signatures are designed to support security requirements such as non-repudiation, and authentication of the signer, HMACs are used widely for their significant performance benefits over digital signatures as required by certain applications while sacrificing non-repudiation and signer authentication. In thie paper,  we shall discuss the first schemes called message authentication codes (MACs) for integrity assurance of graph databases. We develop two notions of highly efficient integrity verification schemes – HMACs for graphs for two-party data sharing, and redactable HMACs for graphs for third-party data sharing, such as a cloud-based graph database service.  We compute only one HMAC value and two other verification objects for redactable HMACs that are shared with the verifier. Our schemes are provably secure and protect the graphs and redacted graphs from being compromised. Moreover, the proposed schemes can support “fail-stop” and “fail-warn” integrity assurance that reduces the cost of integrity verification and data re-transfer of compromised graphs. Both schemes are efficient not only in terms of processing time, but also in terms of the amount of data received by the client as corroborated by our experimental results. Our experiments show that the graph HMACs and redactable graph HMACs are highly efficient as compared with the digital signatures for graphs.

About this Lecture

Number of Slides:  40
Duration:  60 - 90 minutes
Languages Available:  English
Last Updated: 

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.