DDH ⇒ TDH

Standard model · DGI+19

Statement

DDH implies trapdoor hash functions for the index predicates $f_i(x)=x_i$ with one-bit hints: for every index $i$, an encoding key hides $i$, and its trapdoor recovers $x_i$ from the hash $H(x)$ and the hint — DGI+19.

Sketch

The hash key is a matrix $(g_{j,b}{)}_{j\in [n],b\in \{0,1\}}$ of group elements and $H(x)={\prod }_j{g}_{j,x_j}$; the encoding key for index $i$ raises every entry to a secret exponent $s$ and multiplies the $(i,1)$ entry by $g$, so evaluating it on $x$ gives $H(x{)}^s\cdot g^{x_i}$. The trapdoor $s$ recovers $x_i$ from $H(x)$ and this value, a distributed discrete-logarithm step compresses the hint to one bit, and under DDH the encoding key is pseudorandom given the hash key, which hides $i$.

Notes

• The same framework gives one-bit-hint trapdoor hash functions from QR, DCR and LWE (QR ⇒ TDH, DCR ⇒ TDH, LWE with superpolynomial ratio ⇒ TDH) — DGI+19.
• The DDH-based construction carries rate and correctness-error constraints, on which the polylog-communication PIR of TDH ⇒ cPIR depends — DGI+19.