QR ⇒ Lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)

Fully-black-box reduction · standard model · FGKRS10 · security loss: a factor t = ω(log λ) from the hybrid over the t copies

Statement

If QR is hard for Blum integers, lossy trapdoor functions exist. From modular squaring modulo a Blum integer $N$, FGKRS10 build a collection of $(n,{\log }_2(4/3))$-lossy trapdoor functions on $\{0,1{\}}^n$, inverted in the injective mode with the factorization of $N$; the injective and lossy indices differ only in one element of ${\mathrm{J}}_N$, a non-residue in the injective mode and a quadratic residue in the lossy mode, so QR makes the modes indistinguishable — FGKRS10. The product of $t$ independent copies is $(tn,t{\log }_2(4/3))$-lossy, so for $t=\omega (\log \lambda )$ it is a lossy trapdoor function — standard.

Sketch

In the injective mode the product of injective functions is injective; in the lossy mode each copy has at most $2^{n-{\log }_2(4/3)}$ images, so the product has at most $2^{tn-t{\log }_2(4/3)}$. A hybrid that switches the copies’ indices one at a time reduces mode distinguishing for the product to QR — standard.

Notes

• The underlying squaring-based function on ${\mathbb{Z}}_N^{\ast }$ loses one bit, but its domain depends on $N$; the domain extension to $\{0,1{\}}^n$ costs lossiness, leaving ${\log }_2(4/3)$ bits — FGKRS10.
• Lossy trapdoor permutations from QR with improved lossiness are given by AKPS19.