【基本思想】
考虑一个函数族 $\{f_i\}$，其中每个索引 $i$ 对应一个具体函数 $f_i$。如果这些函数不仅是单向的，而且每个 $f_i$ 还是定义域上的置换，那么它们就构成一族单向置换（One-Way Permutations）。
与索引 $i$ 对应的一段辅助信息 $t(i)$，称为陷门（Trapdoor）。仅凭 $i$，无法高效计算出这个陷门，但是可以高效生成相互匹配的一对 $(i,t(i))$。
因此，陷门单向置换的核心思想是：对于不知道陷门的人来说，$f_i$ 是难以反演的，但对于知道陷门 $t(i)$ 的人来说，$f_i$ 可以被高效反演。
也就是说，陷门单向置换同时具有两种看似相反的性质：一方面，它作为单向置换，对一般高效算法来说难以反演；另一方面，只要掌握了对应的陷门信息，就可以高效恢复原像。
【陷门单向置换族的严格定义】
设 $I:1^{*} \to \{0,1\}^{*} \times \{0,1\}^{*}$ 是一个概率算法，输入安全参数 $1^n$ 后输出一对字符串。记 $I_1(1^n)$ 为算法 $I(1^n)$ 输出对中的第一个元素，也就是函数索引。
若一个三元算法组 $(I,D,F)$ 满足以下两个条件，则被称为强陷门置换族（Collection of Strong Trapdoor Permutations）或弱陷门置换族（Collection of Weak Trapdoor Permutations）：
（1）能诱导出单向置换族
三元组 $(I_1,D,F)$ 本身构成强单向置换或弱单向置换，$I_1$ 用于生成函数索引，$D$ 用于从对应定义域中采样，$F$ 用于计算函数值。特别地，有：
也就是说，算法 $F$ 在输入索引 $i$ 和元素 $x$ 后，计算的是第 $i$ 个函数 $f_i$ 在 $x$ 上的取值。
（2）给定陷门后容易反演
存在一个确定性的多项式时间算法 $F^{-1}$，使得对于算法 $I$ 输出范围中的任意 $(i,t)$，以及任意 $x\in D_i$，都有：
这说明，只要给定陷门 $t$，就可以从 $f_i(x)$ 高效恢复出原像 $x$。
因此，陷门单向置换的基本定义可以概括为：在没有陷门时，函数族保持单向性；在拥有陷门时，函数族可以被高效反演。
【陷门单向置换族的高概率定义】
高概率的动机
上述定义要求每个条件严格成立，但在实际构造中，可以允许这些条件以压倒性高概率（Overwhelmingly High Probability）成立。
也就是说，生成索引和陷门的算法 $I$ 可以以可忽略概率输出不好的 $(i,t)$，例如对应的 $f_i$ 不是置换，或者陷门反演算法无法对所有 $x\in D_i$ 正确恢复原像。另一方面，通常还要求定义域采样算法 $D$ 在对应定义域上产生近似均匀的分布。
将这些修改合并后，可以得到一个重新表述的陷门置换定义。
形式化定义
设 $\bar I\subseteq \{0,1\}^{*}$ 是索引集合，并记：
设一族以 $\bar I$ 为索引集合的函数为：
其中，每个 $f_i$ 都是在对应定义域 $D_i$ 上的单射。由于 $f_i$ 是从 $D_i$ 到自身的单射，因此它也可以视为 $D_i$ 上的置换。
若存在四个概率多项式时间算法 $I,D,F,F^{-1}$，并满足以下五个条件，则称这样的一族置换为陷门置换（Trapdoor Permutation）
五个条件
索引与陷门的选择
对于每个安全参数 $n$，算法 $I(1^n)$ 输出合法索引和陷门的概率至少为：
这表示，算法 $I$ 以压倒性高概率输出一个长度为 $n$ 的合法索引 $i\in \bar I_n$，以及与之对应的陷门信息。
定义域中的采样
对于每个 $n\in \mathbb{N}$ 和每个 $i\in \bar I_n$，定义域采样算法 $D$ 需要满足：
（1）$D(i)$ 落在对应定义域 $D_i$ 中的概率至少为：
（2）在条件 $D(i)\in D_i$ 成立的前提下，$D(i)$ 在 $D_i$ 上是均匀分布的，即对任意 $x\in D_i$，都有：
这说明，算法 $D$ 的作用是从第 $i$ 个函数的定义域中近似均匀地采样元素。
由此可知，$D_i$ 中元素的长度至多为 $|i|$ 的多项式。因此可以认为：
并且不失一般性地，可以写作：
高效计算函数值
对于每个 $n\in \mathbb{N}$、每个 $i\in \bar I_n$ 和每个 $x\in D_i$，算法 $F$ 正确计算 $f_i(x)$ 的概率至少为：
这说明，虽然函数族是抽象定义的，但必须存在一个高效算法 $F$ 来实际计算这些函数。
难以反演
令 $I_n$ 表示算法 $I(1^n)$ 输出对中第一个元素的分布，也就是随机生成的索引分布。再令：
也就是说，先随机生成索引 $I_n$，再从对应定义域中采样 $X_n$。
反演困难性有两个版本。
（1）标准/均匀复杂度版本：对任意概率多项式时间算法 $A’$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：
这表示，任何均匀的概率多项式时间算法，在给定索引 $I_n$ 和函数值 $f_{I_n}(X_n)$ 后，成功恢复原像 $X_n$ 的概率都是可忽略的。
（2）非均匀复杂度版本：对任意多项式大小电路族 $\{C_n\}_{n\in \mathbb{N}}$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：
这表示，即使允许每个输入长度 $n$ 使用一个专门设计的多项式大小电路，仍然无法以非可忽略概率反演该函数族。
这两个版本的区别在于：均匀版本抵抗的是均匀的概率多项式时间算法，而非均匀版本抵抗的是多项式大小电路族，后者通常是更强的攻击模型。
给定陷门后可反演
对于每个 $n\in \mathbb{N}$，算法 $I(1^n)$ 输出范围中的任意 $(i,t)$，只要 $i\in \bar I_n$，则对任意 $x\in D_i$，都有：
这说明，陷门反演算法 $F^{-1}$ 在给定陷门 $t$ 后，可以以压倒性高概率从 $f_i(x)$ 中恢复出 $x$。
对高概率定义的说明
如果某些索引只占指数级小的比例，并且对于这些索引，条件 2、条件 3 或条件 5 不成立，那么可以直接将这些索引从 $\bar I$ 中删除，并将这部分错误计入条件 1 中允许的错误概率。
此外，条件 3 和条件 5 还可以进一步放宽：不仅可以对算法内部随机性取概率，也可以对均匀分布的 $x\in D_i$ 一起取概率。也就是说，不必要求对每个固定的 $x$ 都以高概率正确，只要求在随机选择 $x$ 时整体上以高概率正确。
【实例】
在常见的单向函数族中介绍的 RSA 函数族 和 Rabin 函数族可以很容易地修改为具有陷门性质的函数族。
修改的关键是：生成算法不仅输出公开索引，还要输出对应的秘密陷门。
RSA 陷门
在 RSA 中，算法 $I_{\mathrm{RSA}}$ 可以修改为同时输出：
其中，$(N,e)$ 是函数索引，$(N,d)$ 是陷门。
这里 $d$ 是 $e$ 关于 $(P-1)(Q-1)$ 的乘法逆元，即：
由于 $e$ 被选择为与 $(P-1)(Q-1)$ 互质，所以这样的逆元 $d$ 存在。
RSA 的反演算法 $F_{\mathrm{RSA}}^{-1}$ 与 RSA 的正向计算形式相同，只是指数从 $e$ 换成 $d$，即：
如果正向函数为：
那么给定陷门 $(N,d)$ 后，有：
对于模 $N$ 的乘法群中的每个 $x$，上式等于 $x$。此外，对于任意 $x$，即使 $x$ 与 $N$ 不互质，也有：
因此，RSA 的陷门是私有指数 $d$，或者说是能够支持计算 $d$ 的秘密信息，给定该陷门后，可以高效反演 RSA 映射。
Rabin 陷门
对于 Rabin 构造而言，陷门是 $N$ 的质因子分解。
给定模 $N$ 下的一个二次剩余，如果知道 $N$ 的质因子分解，就可以高效计算出它的四个平方根。具体做法是：先分别在 $N$ 的每个质因子模下提取平方根，然后使用中国剩余定理将这些结果合并起来。
特别地，如果质数 $P$ 满足：
那么 $x$ 在模 $P$ 下的平方根可以通过计算：
得到它的一个平方根，其中中间计算结果都要对 $P$ 取模。另一个平方根则是该结果在模 $P$ 下的相反数。
需要注意的是，普通的 Rabin 平方映射在模 $N$ 下通常不是置换，因为一个二次剩余一般对应四个平方根。因此，若要得到陷门置换，需要对定义域和值域进行适当限制。特别地，当 $N$ 是 Blum 整数时，前面介绍的 SQR 函数族在因子分解困难的假设下，可以构成一族陷门置换。
