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 ?

up vote 6 down vote accepted

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.

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.

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.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.