One-Way Accumulators:
A Decentralized Alternative to Digital Signatures
(Extended Abstract)
Josh Benaloh
Clarkson University
Michael de Mare
Giordano Automation
Abstract
This paper describes a simple candidate one-way hash function which satis es a quasi-commutative property that allows it to be used as an accumulator. This property allows protocols to be developed in which the need for a trusted central authority can be eliminated. Space-e cient distributed protocols are given for document time stamping and for membership testing, and many other applications are possible.
1 Introduction
One-way hash functions are generally de ned as functions of a single argument which (in a \di cult to invert" fashion) reduce their arguments to a pre-determined size. We view hash functions, somewhat di erently here, as functions which take two arguments from comparably sized domains and produce a result of similar size. In other words, a hash function is a function h with the property that h: A B ! C where jAj jB j jC j. There is, of course, no substantial di erence between this view and the traditional view except that this view allows us to de ne a special quasi-commutative property which, as it turns out,
has several applications.
The desired property is obtained by considering functions h: X Y ! X and asserting that for all x 2 X and for all y ; y 2 Y ,
h(h(x; y ); y ) = h(h(x; y ); y ):
This property is not at all unusual. Addition and multiplication modulo n both have this property as does exponentiation modulo n when written as en(x; y) = xy mod n. Of these,
only exponentiation modulo n has the additional property that (under suitable conditions),
the function is believed to be di cult to invert.
This paper will describe how to use the combination of these two properties (quasicommutativity and one-wayness) to develop a one-way accumulator which (among other applications) can be used to provide space-e cient cryptographic protocols for time stamping and membership testing.
1
2
1
2
2
1
1
2 De nitions
