Highly lossy TDF ⇒ CRHF

Fully-black-box reduction · standard model · PW08 · security loss: additive: a collision finder with success ε distinguishes the modes with advantage at least about ε − 2^{2r−κn}

Statement

Let $f$ be an $(n,k)$-highly lossy trapdoor function, with residual leakage $r=n-k\le \rho n$ for a constant $\rho <1/2$, and let $\mathcal{H}$ be a universal family of functions to $\{0,1{\}}^{\kappa n}$ for a constant $\kappa$ with $2\rho <\kappa <1$. Then $H_{s,h}(x):=h(f_s(x))$, for a function index $s$ of either mode and $h\stackrel{\$}{\leftarrow }\mathcal{H}$, is a collision-resistant hash function from $\{0,1{\}}^n$ to $\{0,1{\}}^{\kappa n}$ — PW08.

Sketch

A collision $x\ne x^{\prime }$ of $H_{s,h}$ is inner if $f_s(x)=f_s(x^{\prime })$ and outer otherwise. For an injective index every collision is outer. For a lossy index, $f_s$ has at most $2^r$ images, so $h$ collides on two distinct images with probability at most $2^{2r-\kappa n}$, which is negligible since $\kappa >2\rho$; except with that probability every collision is inner. Success of a collision finder is efficiently checkable, so it is about the same in both modes, and reporting whether its collision is inner distinguishes the modes — PW08.

Notes

• The universal hash is what compresses: $f_s$ alone maps $\{0,1{\}}^n$ to a larger range, $n+1$ group elements for the DDH construction, and is injective in the injective mode — PW08.