Assurance of authenticity as well as confidentiality of data is an important problem, in cloud computing and in third-party data distribution environments. Existing data authentication schemes for structured and semi-structured data such as trees and graphs leak information, leading to privacy and confidentiality breaches. We have developed schemes for leakage-free authentication of trees and graphs. Our schemes are provably secure and efficient. In this talk, I would present these schemes as well as describe how to address the problem for disconnected trees/graphs (forests) (e.g., a set of databases). Time permitting, we would discuss some of the applications of these schemes. Our solutions have several applications in the cloud-based service offerings such as in the database and e-mail as services, storage and distribution of healthcare and biological data, and in security of social networks.