The Center for Education and Research in Information Assurance and Security (CERIAS)

The Center for Education and Research in
Information Assurance and Security (CERIAS)

Data in the Cloud: Authentication without Leaking


Download PDF Document


Ashish Kundu

Tech report number

CERIAS TR 2010-25

Entry type



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.




2009 – 12 – 6


Data in the Cloud: Authentication without Leaking


Department of Computer Science & CERIAS

Key alpha

Authentication, Graphs, Integrity, Leaking, Trees


Purdue University


Ph.D. Candidate

Publication Date


BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.