**Author:**
Philippe Camacho,
A.H.,
Marcos Kiwi, and
Roberto Opazo.

**Abstract:**

Accumulator schemes were introduced in order to represent a large
set of values as one short value called the accumulator. These
schemes allow one to generate membership proofs, i.e. short witnesses
that a certain value belongs to the set. In universal accumulator
schemes, efficient proofs of non-membership can also be created.
Li, Li and Xue (Applied Cryptography and Network Security 2007),
building on the work of Camenisch and Lysyanskaya (Crypto 2002),
proposed an efficient accumulator scheme which relies on a trusted
accumulator manager. Specifically, a manager that correctly performs
accumulator updates.
In this work we introduce the notion of *strong universal accumulator
schemes* which are similar in functionality to universal accumulator
schemes, but do not assume the accumulator manager is trusted. We
also formalize the security requirements for such schemes. We then
give a simple construction of a strong universal accumulator scheme
which is provably secure under the assumption that collision-resistant
hash functions exist. The weaker requirement on the accumulator manager
comes at a price; our scheme is less efficient than known universal
accumulator schemes - the size of (non)membership witnesses is
logarithmic in the size of the accumulated set in contrast to constant
in the scheme of Camenisch and Lysyanskaya.
Finally, we show how to use strong universal accumulators to solve a
problem of practical relevance, the so called e-Invoice Factoring Problem.

**Ref:** International Journal of Information Security,
from Online First.

An extended abstract appeared in
Proceedings of the 11th Information Security Conference (ISC 2008),
Taipei, Taiwan, Sept. 15-18, 2008,
Lecture Notes in Computer Science 5222, pages 471-486, Springer-Verlag, 2008.

**Full paper:**
PDF.