CRHF ⇒ accumulator

Fully-black-box reduction · standard model · folklore · security loss: tight: a forged witness exhibits a collision in one of the hash evaluations on its authentication path

Statement

If is a collision-resistant hash function family with , the Merkle tree accumulator over is a collision-free accumulator: ; , on which rejects, and for nonempty , , where and is the root of the depth- binary tree whose leaves are the elements of in sorted order followed by copies of its largest element, each internal node being for its children ; the witness for is the first leaf position holding and the sibling of every node on the path from it to the root; and accepts iff the witness has exactly siblings and recomputing from along yields — folklore.

Sketch

An accepted witness for has exactly siblings, and its leaf position holds some because padding repeats an element of . The path recomputed from and the honest path from therefore have equal length, differ at the leaves () and agree at the root . At the lowest level where they agree, the two hash inputs differ because the child values below them differ, which gives a collision for .

Notes

  • Witnesses have hash values, and the accumulator needs no trapdoor or structured parameters; the construction is the tree of Mer89.