Trapdoor permutation

A trapdoor permutation (TDP) is a permutation which is easy to compute but hard to invert (like a OWF), but is in fact easy to invert if given the trapdoor. Trapdoor permutations are associated with Impagliazzo’s “Cryptomania” world. Their existence implies many different public-key cryptography primitives.

Syntax

Properties

A trapdoor permutation with respect to a trapdoor space $\mathcal{T}$ consists of two families of efficiently computable functions $\{f_{\lambda }:\mathcal{D}\to \mathcal{R}{\}}_{\lambda \in \mathbb{N}}$, $\{f_{\lambda }^{-1}:\mathcal{T}\times \mathcal{R}\to \mathcal{D}{\}}_{\lambda \in \mathbb{N}}$, and a distribution $(X,T)$ over $\mathcal{D}\times \mathcal{T}$, such that:

• The function is one-way: there is some negligible function $\nu$, where, for every $\lambda$ and efficient algorithm $\mathcal{A}$: ${\mathrm{Pr}}_{(x,t)\sim (X,T)}[f_{\lambda }(x^{\prime })=f_{\lambda }(x):x^{\prime }\leftarrow \mathcal{A}(1^{\lambda },f_{\lambda }(x))]\le \nu (\lambda ).$
• And the function easy to invert given the trapdoor: there is some negligible function $\nu$, where, for every $\lambda$, ${\mathrm{Pr}}_{(x,t)\sim (X,T)}[f_{\lambda }^{-1}(t,f_{\lambda }(x))=x]\ge 1-\nu (\lambda ).$

Variations

TODO: Enhanced trapdoor permutations

Other results

• PKE can be built from trapdoor permutations
• OT can be built from enhanced trapdoor permutations
• The RSA Assumption implies the existence of a OWP.