We introduce the notion of verifiable data streaming and present an efficient instantiation that supports an exponential number of values based on general assumptions. Our main technique is an authentication tree in which the leaves are not fixed in advanced such that the user, knowing some trapdoor, can authenticate a new element on demand \emph{without} pre- or re-computing all other leaves. We call this data structure \emph{chameleon authentication tree} (CAT). We instantiate our scheme with primitives that are secure under the discrete logarithm assumption. The algebraic properties of this assumption allow us to obtain a very efficient verification algorithm. As a second application of CATs, we present a new transformation from any one-time to many-time signature scheme that is more efficient than previously known solutions.
Category / Keywords: cryptographic protocols / Publication Info: ACM CCS 2012 Date: received 25 Jan 2013 Contact author: schroeder at me com Available format(s): PDF | BibTeX Citation Version: 20130129:224034 (All versions of this report) Short URL: ia.cr/2013/038