Trapdoor permutation

A trapdoor permutation (TDP) is a permutation that is easy to compute but hard to invert without a trapdoor: a secret that makes inversion efficient. Trapdoor permutations are one-way functions with an additional invertibility structure, and they are associated with Impagliazzo’s “Cryptomania” world. Their existence implies many public-key cryptographic primitives.

Syntax

A trapdoor permutation family is a tuple of efficient algorithms $\mathsf{TDP}=(\mathsf{Gen},\mathsf{Eval},\mathsf{Invert})$ with respect to a domain $\mathcal{D}$ and trapdoor space $\mathcal{T}$:

• $\mathsf{Gen}(1^{\lambda })\to (f,\mathsf{td}),$ is a randomized key generation algorithm that samples a function index $f$ and a trapdoor $\mathsf{td}\in \mathcal{T},$
• $\mathsf{Eval}(f,x)\to y,$ is a deterministic algorithm that evaluates $f:\mathcal{D}\to \mathcal{D}$ on input $x\in \mathcal{D}$, outputting $y\in \mathcal{D},$
• $\mathsf{Invert}(\mathsf{td},y)\to x,$ is a deterministic algorithm that inverts $f$ on input $y$ given trapdoor $\mathsf{td},$ outputting $x\in \mathcal{D}.$

We require that $f$ defines a bijection (permutation) on $\mathcal{D}$.

Properties

Correctness

For all $\lambda \in \mathbb{N}$ and $x\in \mathcal{D}$, with $(f,\mathsf{td})\leftarrow \mathsf{Gen}(1^{\lambda })$: $\mathrm{Pr}\left[\mathsf{Invert}(\mathsf{td},\mathsf{Eval}(f,x))=x\right]=1.$

One-wayness

A TDP is one-way if for all efficient $\mathcal{A}$, $\mathrm{Pr}\left[\mathsf{Eval}(f,x^{\prime })=\mathsf{Eval}(f,x):(f,\mathsf{td})\leftarrow \mathsf{Gen}(1^{\lambda }),x\stackrel{\$}{\leftarrow }\mathcal{D},x^{\prime }\leftarrow \mathcal{A}(1^{\lambda },f,\mathsf{Eval}(f,x))\right]$ is negligible.

Easy inversion with trapdoor

Inversion with the trapdoor is efficient: $\mathsf{Invert}(\mathsf{td},\mathsf{Eval}(f,x))=x$ with probability 1 in $\mathrm{poly}(\lambda )$ time.

Variations

Enhanced trapdoor permutations

An enhanced TDP comes with a domain sampler and remains hard to invert on a sampled image $y$ even given the sampler’s coins $r$. The EGL85 construction of OT is proved secure under this stronger property, since its receiver samples an image obliviously and holds the sampling coins — Gol04, GR13. No fully black-box construction of an enhanced TDP from a standard TDP exists — Haj18.

Doubly enhanced certified trapdoor permutations

An enhanced TDP is doubly enhanced if, given the index alone, one can efficiently sample a pair $(x,r)$ with $x$ uniform in the domain and $r$ uniform among the domain sampler’s coins that output $f(x)$ — GR13. It is certified if its indices, and the domains they describe, are efficiently recognizable, so that a verifier can check that an index describes a permutation — BY96, CL18. These are the properties the hidden-bits compilation of NIZK proofs uses — GR13, CL18.

Injective trapdoor functions

An injective trapdoor function has the syntax above with $\mathsf{Eval}(f,\cdot ):\mathcal{D}\to \mathcal{R}$ injective rather than a permutation of $\mathcal{D}$, and the same one-wayness and inversion requirements. Every trapdoor permutation is one — folklore.

Claw-free permutations

A claw-free pair is a pair of permutations $f_0,f_1$ of a common domain $\mathcal{D}$, sampled together by $\mathsf{Gen}$, such that no efficient $\mathcal{A}$ given $(f_0,f_1)$ outputs a claw $(x_0,x_1)$ with $f_0(x_0)=f_1(x_1)$, except with negligible probability — GMR88. Each $f_b$ is then one-way, since inverting $f_0$ on $f_1(x_1)$ for uniform $x_1$ yields a claw — standard. GMR88 use claw-free pairs with trapdoors for $f_0^{-1}$ and $f_1^{-1}$.

Lossy trapdoor functions

An $(n,k)$-lossy trapdoor function samples a function index $s$ in one of two computationally indistinguishable modes: in the injective mode $f_s:\{0,1{\}}^n\to \mathcal{R}$ is injective and inverted by $\mathsf{Invert}$ with the trapdoor, one-wayness not being assumed, and in the lossy mode $f_s$ has at most $2^{n-k}$ images, so it loses at least $k$ bits of its input — PW08. A lossy trapdoor function is an $(n,k)$-lossy one with $k=\omega (\log \lambda )$; without a lower bound on $k$, every injective trapdoor function is an $(n,0)$-lossy one, with the same index in both modes. $r:=n-k$ is the residual leakage. Lossy TDFs imply injective trapdoor functions — PW08 — and IND-CCA-secure encryption — MY10.

Highly lossy trapdoor functions

An $(n,k)$-lossy trapdoor function is highly lossy if its residual leakage is $r\le \rho n$ for a constant $\rho <1/2$, the regime in which it yields collision-resistant hashing — PW08.

Other results

• TDP ⇒ PKE
• Enhanced trapdoor permutations ⇒ OT
• RSA ⇒ TDP

Participates in

Builds on Trapdoor permutation

• Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan) (via Claw-free permutations)
• Claw-free permutations ⇒ CRHF (Damgård) (via Claw-free permutations)
• Doubly enhanced certified TDP ⇒ Enhanced TDP (via Doubly enhanced certified trapdoor permutations)
• Enhanced trapdoor permutations ⇒ OT (via Enhanced trapdoor permutations)
• Highly lossy TDF ⇒ Lossy TDF (via Highly lossy trapdoor functions)
• Highly lossy TDF ⇒ CRHF (via Highly lossy trapdoor functions)
• Lossy TDF ⇒ Injective TDF (via Lossy trapdoor functions)
• Lossy TDF ⇒ OT (via Lossy trapdoor functions)
• Lossy trapdoor functions ⇒ IND-CCA PKE (via Lossy trapdoor functions)
• TDP ⇒ cPIR with total communication below n (Kushilevitz–Ostrovsky)
• TDP ⇒ DS (full-domain hash, random oracle model)
• TDP ⇒ OWF
• TDP ⇒ Injective TDF
• Doubly enhanced certified TDP ⇒ NIZK (via Doubly enhanced certified trapdoor permutations)
• TDP ⇒ PKE

Produces Trapdoor permutation

• DCR ⇒ Highly lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev) (via Highly lossy trapdoor functions)
• DDH ⇒ Highly lossy TDF (Peikert–Waters) (via Highly lossy trapdoor functions)
• Doubly enhanced certified TDP ⇒ Enhanced TDP (via Enhanced trapdoor permutations)
• Factoring ⇒ Claw-free permutations (GMR) (via Claw-free permutations)
• Factoring ⇒ TDP (Rabin)
• Highly lossy TDF ⇒ Lossy TDF (via Lossy trapdoor functions)
• Lossy TDF ⇒ Injective TDF (via Injective trapdoor functions)
• LWE ⇒ Lossy TDF (Peikert–Waters) (via Lossy trapdoor functions)
• Φ-Hiding ⇒ Lossy TDF (Kiltz–O’Neill–Smith) (via Lossy trapdoor functions)
• QR ⇒ Lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev) (via Lossy trapdoor functions)
• RSA ⇒ TDP
• Sub-exponential iO + Sub-exponential OWF ⇒ TDP (Bitansky–Paneth–Wichs)
• TDP ⇒ Injective TDF (via Injective trapdoor functions)

Barriers

• No relativizing reduction from KE to TDP
• No fully-black-box reduction from OT to TDP
• No fully-black-box reduction from PKE to injective TDF (via Injective trapdoor functions)
• No fully-black-box reduction from PKE to TDP
• No fully-black-box reduction from TDP to enhanced TDP