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 there is some negligible function $\nu$ such that for every efficient $\mathcal{A}$: ${\mathrm{Pr}}_{(f,\mathsf{td})\leftarrow \mathsf{Gen}(1^{\lambda }),x\stackrel{\$}{\leftarrow }\mathcal{D}}\left[\mathsf{Eval}(f,x^{\prime })=\mathsf{Eval}(f,x):x^{\prime }\leftarrow \mathcal{A}(1^{\lambda },f,\mathsf{Eval}(f,x))\right]\le \nu (\lambda ).$

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 additionally requires that the TDP remain hard to invert even when given a random coin $r$ and a random element $y=\mathsf{Eval}(f,x)$ sampled using $r$ in a specific way. This stronger property is necessary for constructing OT from TDPs.

Lossy trapdoor functions

A generalization where there are two modes: an injective mode (standard TDP) and a lossy mode (where the function is many-to-one and loses information). Lossy TDFs imply TDPs and are useful for constructing CCA-secure encryption.

Other results

• PKE can be constructed from trapdoor permutations — standard (TDP + hard-core predicate → PKE)
• OT can be constructed from enhanced trapdoor permutations — GKM+00
• The RSA assumption implies the existence of a trapdoor permutation (RSA function) — RSA78
• A OWP cannot be constructed from an injective one-way function in a black-box way — MM11