Veriable Data Streaming

In a veriable data streaming protocol, the client streams a long string to the server who stores it in its database. The stream is veriable in the sense that the server can neither change the order of the elements nor manipulate them. The client may also retrieve data from the database and update them. The content of the database is publicly veriable such that any party in possession of some value s and a proof can check that s is indeed in the database. We introduce the notion of veriable data streaming and present an ecient 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 xed in advanced such that the user, knowing some trapdoor, can authenticate a new element on demand without pre- or re-computing all other leaves. We call this data structure 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 ecient verication algorithm. As a second application of CATs, we present a new transformation from any one-time to many-time signature scheme that is more ecient than previously known solutions.