DCR ⇒ Highly lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)

Fully-black-box reduction · standard model · FGKRS10

Statement

If DCR is hard, highly lossy trapdoor functions exist, with essentially any required amount of lossiness — FGKRS10. The function index is $(N,c)$ with $c$ a random Damgård–Jurik encryption modulo $N^{s+1}$ of $1$ in the injective mode and of $0$ in the lossy mode, and the factorization of $N$ is the trapdoor — FGKRS10. The two modes are indistinguishable by semantic security of Damgård–Jurik encryption, which follows from DCR — DJ01.

Sketch

Fix a constant $s\ge 3$ and let $f(x):=c^x\mathrm{mod}{N}^{s+1}$ on $x\in \{0,1{\}}^n$ with $n=s(|N|-1)$, so that $x<N^s$. For $c=(1+N)u^{N^s}$, $f(x)=(1+N{)}^x(u^x{)}^{N^s}$ is a Damgård–Jurik encryption of $x$, which decryption with the factorization recovers. For $c=u^{N^s}$, every image is an $N^s$-th power, and there are $\phi (N)<2^{|N|}$ of them, so the residual leakage is at most $|N|\le (1+o(1))n/s<n/2$ — standard.

Notes

• Efficiency: the index is $N$ and one element of ${\mathbb{Z}}_{N^{s+1}}$, and an evaluation is one exponentiation modulo $N^{s+1}$ with an $n$-bit exponent, against $n^2+n$ group elements for the DDH-based matrix construction — standard; FGKRS10 present their functions as more efficient than that matrix-based approach — FGKRS10.
• Highly lossy trapdoor functions give collision-resistant hashing, and lossy ones IND-CCA2-secure PKE — PW08.
• Lossy trapdoor permutations with improved lossiness from DCR, QR and Φ-hiding are given by AKPS19.