On the Cost of Authenticated Data Structures
Roberto Tamassia, Nikos Triandopoulos · 2003
Abstract. Authenticated data structures are a model of computation where untrusted responders answer queries on a data structure on behalf of a trusted source and provide a proof of the validity of the answer to the user. We present a survey of techniques for designing authenticated data structures and overview their computational efficiency. We also discuss implementation issues and practical applications. 1