Authentication of elements (e.g. digital certificates 140) as possessing a
pre-specified property (e.g. being valid) or not possessing the property
is performed by (1) assigning a distinct integer p.sub.i to each element,
and (2) accumulating the elements possessing the property or the elements
not possessing the property using a P-th root u.sup.1/P (mod n) of an
integer u modulo a predefined composite integer n, where P is the product
of the integers associated with the accumulated elements. Alternatively,
authentication is performed without such accumulators but using witnesses
associated with such accumulators. The witnesses are used to derive
encryption and/or decryption keys for encrypting the data evidencing
possession of the property for multiple periods of time. The encrypted
data are distributed in advance. For each period of time, decryption keys
are released which are associated with that period and with the elements
to be authenticated in that period of time. Authentication can be
performed by accumulating elements into data which are a function of each
element but whose size does not depend on the number of elements, and
transmitting the accumulator data over a network to a computer system
which de-accumulates some elements as needed to re-transmit only data
associated with elements needed by other computer systems. This technique
is suitable to facilitate distribution of accumulator data in networks
such as ad hoc networks.