陷门置换定义

  一个陷门置换族是一个PPT算法元组(Gen,Sample,Eval,Invert)(Gen,Sample,Eval,Invert)(Gen,Sample,Eval,Invert)：

1. PPT，运行步数是安全参数的多项式函数。
2. Gen(lK)Gen(l^{\mathcal{K}})Gen(lK)是一个概率性算法，输入为安全参数lKl^{\mathcal{K}}lK，输出为(i,td)(i,td)(i,td)，其中iii是定义域DiD_iDi​上的一个置换fif_ifi​的标号（“公钥”），tdtdtd是允许求fif_ifi​逆的陷门信息（“私钥”）。
3. Sample(lK,i)Sample(l^{\mathcal{K}},i)Sample(lK,i)是一个概率性算法，输入iii有GenGenGen产生，输出为x←RDix\leftarrow _{R}D_ix←R​Di​。
4. Eval(lK,i,x)Eval(l^{\mathcal{K}},i,x)Eval(lK,i,x)是一个确定性算法，输出为y∈Diy \in D_iy∈Di​。即Eval(lK,i,⋅):Di→DiEval(l^{\mathcal{K}},i,\cdot):D_i \rightarrow D_iEval(lK,i,⋅):Di​→Di​是DiD_iDi​上的一个置换。
5. Invert(lK,td,y)Invert(l^{\mathcal{K}},td,y)Invert(lK,td,y)，输出为xxx。

  RSA加密算法就是一个典型的陷门置换：
6. Gen(k)Gen(\mathcal{k})Gen(k)：随机选取两个K\mathcal{K}K比特素数ppp和qqq。计算N=pqN=pqN=pq，φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1)φ(N)=(p−1)(q−1)。选取与φ(N)\varphi(N)φ(N)互素的eee，计算ed=1modφ(N)ed=1 mod \ \varphi(N)ed=1mod φ(N)，输出为((N,e),(N,d))((N,e),(N,d))((N,e),(N,d))。分别对应iii和tdtdtd。定义域DN,eD_{N,e}DN,e​就是ZNZ_{N}ZN​。
7. Sample(K,(N,e))Sample(\mathcal{K},(N,e))Sample(K,(N,e))：从ZNZ_NZN​中选取一个随机元素xxx。
8. Eval(K,(N,e),x)Eval(\mathcal{K},(N,e),x)Eval(K,(N,e),x)：y=xemodNy=x^e mod \ Ny=xemod N。
9. Invert(K,(N,d),y)Invert(\mathcal{K},(N,d),y)Invert(K,(N,d),y)，输出为x=ydmodNx=y^dmod \ Nx=ydmod N 。

单陷门置换定义

  在陷门置换中没有考虑任何“困难性”和安全性的概念（可以为线性置换以及求逆），这在密码学上是没有意义的。所以一般认为密码学中的陷门置换是单陷门置换。单陷门置换是指当陷门信息tdtdtd未知时，一个随机陷门置换的求逆是困难的。具体定义如下：
  一个陷门置换簇(Gen,Sample,Eval,Invert)(Gen,Sample,Eval,Invert)(Gen,Sample,Eval,Invert)是单向的，如果对于任意的PPT敌手A\mathcal{A}A，存在一个可忽略的函数ϵ(K)\epsilon{(\mathcal{K})}ϵ(K)，使得A\mathcal{A}A在下面的对抗中，其优势AdvA(K)≤ϵ(K){Adv}_{\mathcal{A}}(\mathcal{K}) \leq \epsilon{(\mathcal{K})}AdvA​(K)≤ϵ(K)：
FunctionA(K):{Function}_{\mathcal{A}}(\mathcal{K}):FunctionA​(K):
  (i,td)←Gen(K)(i,td)\leftarrow Gen(\mathcal{K})(i,td)←Gen(K)；
  y←Sample(K,i)y \leftarrow Sample(\mathcal{K},i)y←Sample(K,i)；
  x←A(K,i,y)x \leftarrow \mathcal{A}(\mathcal{K},i,y)x←A(K,i,y)
  如果Eval(K,i,x)=yEval(\mathcal{K},i,x)=yEval(K,i,x)=y，返回1；否则返回0。
  A\mathcal{A}A的优势AdvA(K){Adv}_{\mathcal{A}}(\mathcal{K})AdvA​(K)定义为AdvA(K)=Pr[FunctionA(K)=1]{Adv}_{\mathcal{A}}(\mathcal{K})=Pr[{Function}_{\mathcal{A}}(\mathcal{K})=1]AdvA​(K)=Pr[FunctionA​(K)=1]，其中PrPrPr表示概率。
  为了方便理解可以将iii表示为置换fff，tdtdtd表示为逆置换f−1f^{-1}f−1。