One-way accumulators, introduced by Benaloh and de Mare, can be used to accumulate a large number of values into a single
one, which can then be used to authenticate every input value without the need to transmit the others. However, the one-way
property does is not sufficient for all applications.
In this paper, we generalize the definition of accumulators and define and construct a collision-free subtype. As an application,
we construct a fail-stop signature scheme in which many one-time public keys are accumulated into one short public key. In
contrast to previous constructions with tree authentication, the length of both this public key and the signatures can be
independent of the number of messages that can be signed.
Work done while both authors were at the University of Hildesheim. Supported by the DFG (German Research Foundation). A preliminary
version was available as [Pfit94], more details can be found in [Bari96].