Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?

Question

One of the problems of one-time Lamport signatures is that public keys are disposed after use, so you must generate many keys and store them in a Merkle tree. The root is the "real" public key and each signature is supplied with a Merkle branch from the root public-key to the one-time public key.

I was thinking of using a cryptographic accumulator to store efficiently the one-time public keys. The root public-key would be the the digest of accumulated one-time public-keys. A signature would only include the proof that the one-time public key belongs to the accumulator. This proof may be shorter than a Merkle branch if the number of public keys is over 256, for comparable security thresholds.

The only drawback I see is that known cryptographic accumulators (e.g. Benaloh and M. de Mare) are based on number-theoretic assumptions (such as factoring), and using Lamport signatures one is usually trying to avoid those assumptions, probably to get quantum computing resistant schemes.

Nevertheless, I suspect there are cryptographic accumulators which are quantum computing resistant, so the argument may not be strong enough.

To summarize, may cryptographic accumulators serve as a more efficient method to distribute Lamport public keys ?

Answer 1

Yes, they can be used for that purpose. The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures. Nonetheless, they can be used in this way.

Answer 2

As D.W. notes, this works for the purpose in question. Actually, relying on number theoretic assumptions for the accumulators will give you no benefit as you have observed.

However, here is a construction of accumulators from Nyberg in FSE'96, which does not rely on number theoretic or any computational assumptions. This is the paper of Nyberg and you may take a look at it.

Answer 3

It seems they can be used for that purpose.

I found this paper: "Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees" Niko Baric and Birgit Pfitzmann Eurocrypt '97, LNCS, Springer-Verlag, Berlin 1997.