Abstract
Third party data distribution frameworks such as the cloud are
increasingly being employed in order to store, process, and publish sensitive
information such as healthcare and finance information, belonging to individuals
and enterprises. Such data objects are often organized as trees, graphs or even forests (e.g.,
XML). In third party frameworks, not only
authentication of data is important but also protection of privacy and assurance
of confidentiality are important. Moreover, data authenticity must be assured
even when the data object that a user has access to consists of subset(s) of the
signed data.
Existing solutions such as Merkle hash technique and the redactable signature
schemes lead to leakages of structural information, which can be used to infer
sensitive information, which in turn would lead to privacy and confidentiality
breaches. So the question is: can we authenticate subset(s) of signed data
objects without leaking, and if so, how efficiently such authentication can be
carried out? We have reported a positive result by presenting efficient and
provably secure solutions not only for trees, but also graphs and forests. We
have presented a scheme that computes only one signature per tree, graph or
forest.
Our schemes support encrypted data to be stored at third-party services. Our
schemes can also be used to automatically recover from structural errors in
tree-structured data, and for leakage-free authentication of paths (e.g.,
XPaths). Further, as the applications of our schemes, we have also developed a
publish/subscribe model for XML --
Structure-based routing, and a scheme for authentication of objects.
Key alpha
Authentication, Graphs, Integrity, Leaking, Trees
