Paper 2012/036

Efficient Leakage-free Authentication of Trees, Graphs and Forests

Ashish Kundu, Mikhail Atallah, and Elisa Bertino


Leakage-free authentication of trees and graphs have been studied in the literature. Such schemes have several practical applications especially in the cloud computing area. In this paper, we propose an authentication scheme that computes only one signature (optimal). Our scheme is not only super-efficient in the number of signatures it computes and in its runtime, but also is highly versatile -- it can be applied not only to trees, but also to graphs and forests (disconnected trees and graphs). While achieving such efficiency and versatility, we must also mention that our scheme achieves the desired security -- leakage-free authentication of data objects represented as trees, graphs and forests. This is achieved by another novel scheme that we have proposed in this paper -- a secure naming scheme for nodes of such data structures. Such a scheme assigns "secure names" to nodes such that these secure names can be used to verify the order between the nodes efficiently without leaking information about other nodes. As far as we know, our scheme is the first such scheme in literature that is optimal in its efficiency, supports two important security concerns -- authenticity and leakage-free (privacy-preserving/confidentiality), and is versatile in its applicability as it is to trees, graphs as well as forests. We have carried out complexity as well as experimental analysis of this scheme that corroborates its performance.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
digital signatures
Contact author(s)
akundu @ us ibm com
2012-01-29: received
Short URL
Creative Commons Attribution


      author = {Ashish Kundu and Mikhail Atallah and Elisa Bertino},
      title = {Efficient Leakage-free Authentication of Trees, Graphs and Forests},
      howpublished = {Cryptology ePrint Archive, Paper 2012/036},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.