Claw-free permutations ⇒ CRHF (Damgård)

Fully-black-box reduction · standard model · Dam87 · security loss: none: every collision yields a claw

Statement

Let $(f_0,f_1)$ be a claw-free pair of permutations of $\mathcal{D}$, let $x_0\in \mathcal{D}$ be fixed, and let $⟨m⟩=b_1\cdots b_t$ be a prefix-free encoding of messages. Then

$${\mathsf{H}}_{f_0,f_1,x_0}(m):=f_{b_1}(f_{b_2}(\cdots f_{b_t}(x_0)\cdots ))$$

is collision resistant — Dam87. Every fixed-length encoding is prefix-free, so on messages of a fixed length $n(\lambda )$ exceeding the bit length of elements of $\mathcal{D}$, encoded as themselves, ${\mathsf{H}}_{f_0,f_1,x_0}:\{0,1{\}}^n\to \mathcal{D}$ is a compressing collision-resistant hash function family.

Sketch

Let $m\ne m^{\prime }$ collide, with encodings $b_1\cdots b_t$ and $b_1^{\prime }\cdots b_{t^{\prime }}^{\prime }$. Each $f_b$ is injective, so the two evaluations still agree after the longest common prefix of the encodings. Prefix-freeness leaves two non-empty remainders whose first bits differ, and the reduction computes the corresponding inner values $u,v$ forward from $x_0$, obtaining a claw $f_0(u)=f_1(v)$ — Dam87.

Notes

• Efficiency: one evaluation of a permutation per encoded message bit; with GMR88’s factoring-based pair, one modular squaring, and for $f_1$ a multiplication by $4$, per bit — standard.