DDH ⇒ Highly lossy TDF (Peikert–Waters)

Fully-black-box reduction · standard model · PW08 · security loss: a factor polynomial in n, from a hybrid over the entries of the encrypted matrix

Statement

If DDH holds in a group $\mathbb{G}=⟨g⟩$ of prime order $p$, then lossy trapdoor functions on $\{0,1{\}}^n$ exist whose lossy mode has at most $p$ images, so the residual leakage is at most $\log p$; for $n\ge c\log p$ with a constant $c>2$ it is at most $n/c$, so the functions are highly lossy — PW08.

Sketch

The index is an entrywise ElGamal encryption of a matrix $M\in \{0,1{\}}^{n\times n}$ with randomness $r_i$ per row and secret key $s_j$ per column: $(g^{r_i}{)}_i$ and $(g^{r_i{s}_j+M_{ij}}{)}_{i,j}$. For $x\in \{0,1{\}}^n$, $f(x):=(g^{⟨r,x⟩},(g^{⟨r,x⟩s_j+(x^{\top }M{)}_j}{)}_j)$ is computed from the index by multiplying entries. With $M=I$ the trapdoor $(s_j{)}_j$ recovers each $g^{x_j}$, hence $x$; with $M=0$ the output depends on $x$ only through $⟨r,x⟩\in {\mathbb{Z}}_p$. The two indices are indistinguishable under DDH by a hybrid over the matrix entries — PW08.

Notes

• Efficiency: the index has $n^2+n$ group elements, an output has $n+1$, and an evaluation costs about $n^2$ group multiplications — standard.
• Lossy trapdoor functions give IND-CCA2-secure PKE, injective trapdoor functions and OT, and highly lossy ones give collision-resistant hashing — PW08.