Redactable Graph Hashing, Revisited

We revisit the previous work of Arshad et al. (CODASPY 2014) about the security of redactable graph hashing schemes. Such schemes, introduced in a series of works by Devanbu et al. (DBSec 2000, CCS 2001, Algorithmica 2004), allow to hash graphs and to release sub graphs which can be verified against the original hash value. Arshad et al. introduce security notions for collision resistance and privacy of graphs, where the latter should capture the infeasibility to reconstruct the full graph from the hash value of a redacted one.