Φ-Hiding ⇒ Lossy TDF (Kiltz–O’Neill–Smith)

Fully-black-box reduction · standard model · KOS10 · security loss: none for one copy; a factor t from the hybrid over t copies when the exponent is small

Statement

If the Φ-hiding assumption holds, RSA is a lossy trapdoor permutation — KOS10. In the injective mode $\gcd (e,\phi (N))=1$ and $x\mapsto x^e\mathrm{mod}N$ is the RSA permutation with trapdoor $d\equiv e^{-1}(\mathrm{mod}\phi (N))$; in the lossy mode $e\mid \phi (N)$ and the map is at least $e$-to-$1$ on ${\mathbb{Z}}_N^{\ast }$; the two modes are indistinguishable exactly by Φ-hiding. RSA acts on ${\mathbb{Z}}_N$ rather than on bit strings — AKPS19. In the injective mode it permutes all of ${\mathbb{Z}}_N$, so its restriction to the inputs in $[0,2^{|N|-1})$ is an injective function on $\{0,1{\}}^{|N|-1}$ whose lossy mode has lossiness at least $\log e-1-o(1)$ — standard. When $\log e=\omega (\log \lambda )$, for instance for $e$ close to $N^{1/4-\epsilon }$, this is a lossy trapdoor function; for smaller $e$, the product of $t=\omega (\log \lambda )$ independent instances multiplies the lossiness by $t$ and is one — standard.

Sketch

For prime $e\mid p-1$, the map $x\mapsto x^e$ has $(p-1)/e+1$ images on ${\mathbb{Z}}_p$, so at most $(N/e+q)$ images on ${\mathbb{Z}}_N$; the restricted domain has $2^{|N|-1}>N/2$ elements, which gives the lossiness $\log e-1-\log (1+e/p)$ — standard.

Notes

• In the lossy mode $x\mapsto x^e$ is at most $e^2$-to-$1$ on ${\mathbb{Z}}_N$, so for $e\le N^{1/4-\epsilon }$ the lossiness is below $|N|/2$, the residual leakage exceeds half the input length, and the function is not highly lossy — standard.
• A domain-extension technique of FGKRS10 makes RSA a lossy trapdoor permutation on a fixed domain, with considerably reduced lossiness; AKPS19 give Φ-hiding-based lossy trapdoor permutations with improved lossiness and the first all-but-one lossy trapdoor permutation from Φ-hiding — AKPS19.
• KOS10 use the lossiness of RSA to prove RSA-OAEP IND-CPA-secure in the standard model, with the first round’s hash function $t$-wise independent — KOS10.