Merkle Tree Traversal Revisited

摘要

We propose a new algorithm for computing authentication paths in the Merkle signature scheme. Compared to the best algorithm for this task, our algorithm reduces the worst case running time considerably.