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.

Lossy trapdoor functions

A lossy trapdoor function has two computationally indistinguishable modes: an injective mode (an injective trapdoor function, not necessarily a permutation) and a lossy mode (where the function is many-to-one and loses information). Lossy TDFs imply injective trapdoor functions and CCA-secure encryption — PW08.

Other results

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

Participates in

Builds on Trapdoor permutation

• Enhanced trapdoor permutations ⇒ OT (via Enhanced trapdoor permutations)
• Lossy trapdoor functions ⇒ IND-CCA PKE (via Lossy trapdoor functions)
• TDP ⇒ OWF
• TDP ⇒ NIZK
• TDP ⇒ PKE

Produces Trapdoor permutation

• RSA ⇒ TDP

Barriers

• No fully-black-box reduction from OT to TDP
• No fully-black-box reduction from PKE to TDP
• No fully-black-box reduction from TDP to enhanced TDP