Date Added: Jan 2012
Leakage-free authentication of trees and graphs has been studied in the literature. Such schemes have several practical applications especially in the cloud computing area. In this paper, the authors propose an authentication scheme that computes only one signature (optimal). Their scheme is not only super-efficient in the number of signatures it computes and in its run-time, 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, they must also mention that their scheme achieves the desired security - leakage-free authentication of data objects represented as trees, graphs and forests.