单向陷门函数

单向陷门函数(One-way Trapdoor Function)定义：

一“可逆”函数F若满足下列二条件，则F称为单向陷门函数：

1.对于所有属于F定义域的任一x，可以很容易算出F(x) = y;

2.对于几乎所有属于F值域的任一y，则在计算上除非获得陷门，否则不可能求出x，使得x = F^(-1)(y)，F^（-1）为F的反函数。但若有一额外数据z（称为陷门），则可以很容易的求出 x = F^(-1)(y)。

单向函数与单向陷门函数的差异在于可逆与不可逆。若单向陷门函数存在，则任何单向陷门函数均可用来设计公开密钥密码系统。同时，若单向函数满足交换性，则单向函数也可能用来设计公开密钥密码系统。