文档介绍：第5章单向函数
一般单向函数
单向函数的定义
定义 函数称为正则的,若存在正多项式p(n)使对任一,有。正则函数的含意是f(x)的长不比x的长缩短太多。正则函数的一个重要的特殊情形是保长函数,即对任一,有。
定义 一个函数称为强单向函数,若下列两个条件成立:
(1)计算f(x)是容易的,即f(x)是多项式时间可计算的();
(2)计算f(x)的逆是困难的,即对每一多项式时间概率算法() ,每一正多项式p(n)和一切充分大的有
(一)随机猜测算法
无论输入那个, , 总是输出n次扔硬币结果r,作为对x的猜测。将代入()。因与r统计独立,故得()
其中()
当f(x)为1-1映射时,()式中最后得不等式变为等式。这是因为中仅有x一个原像。由()和()可见:
1)若f(x)为任一函数,则的成功概率是一个正数(大小可从到1),因此不能要求任一多项式时间概率算法都不可计算函数f(x)的逆;
2)若f(x)为任一1-1映射,则的成功概率是可忽略的,当然这并不表示f(x)为单向函数,因为只是一个最简单的算法;
3)若f(x)为一单向函数(不要求为1-1映射),则由于为多项式时间概率算法,故()要求的成功概率是可忽略的。
(二)固定输出算法
无论输入那个y=f(x), , 总是输出一个固定的,将代入()式得
()
其中由()给出,()中第二个等式是由于, 表示集中的元素个数。当是的唯一原像时,()中最后一个不等式变为等式。由()可见, 的成功概率与有类似的结论。
定义 一个函数称为弱单向函数,若下列两个条件成立:
(1)计算f(x)是容易的,)相同;
(2)计算f(x)的逆是稍难的,即存在一个正多项式p(n),使对每一多项式时间概率算法和一切充分大的有
候选单向函数
整数因子分解()
()
其中分别表示整数x,y和它们乘积的二进数表示(参看()式
线性编码函数
设常数满足
()
其中,C为F上距阵,m为长消息,e为一个的错误。
单向函数族
一个函数族是由{0,1} 的一个无穷子集I(称为指标集)和每个指标对应一个函数构成,其中为{0,1} 的一个有穷子集。
一个函数族称为强单向函数族。若存在三个多项式时间概率算法A,D,F满足下列两个条件:
1)i和x的抽取和的计算是容易的,即若算法A的输入为(n个1的比特串),则其输出为{0,1} 上的一个随机变量,若算法D的输入为{0,1},则其输出为上的一个随机变量,若算法F的输入为和,则其输出为;
2)计算的逆是困难的,即对每一多项式时间概率算法,每一正多项式p(n)和一切充分大n的有
()
其中和X 由条件1)给出。
定理 任一单向函数可表示为一个单向函数族,反之任一单向函数族也可表示为一单向函数,其中E为{0,1} 的一个无穷子集。
候选单向函数族
例 RSA函数族
例 Rabin函数族
例 Rabin-Blum函数族
例 离散对数函数族
单向函数族的其它性质
单向陷门置换族
设为一单向置换族。 及其后的说明知,)和2)()。
单向置换族称为单向陷门置换族,若存在一个多项式时间概率算法和一个多项式时间确定性算法满足如下条件,其中。
3) ,其中和分别表示算法A和输入时的输出,为上的随机变量,且对每对和 每个有,即陷门作为求逆算法的辅助输入。