52单向函数族 ■52.1单向函数族的定义 定义54一个函数族是由{0,1}的一个无穷子集|(称为指 标集)和每个指标∈对应一个函数f(x):D→>@构成 其中为{0,1}的个有穷子集 定义55个函数族D→lk为强单向函数族 若存在三个多项式时间概率算法AD,F满足下列两个条件: 1)i和x的抽取和的计算是容易的,即若算法A的输入 为、(n个1的比特x),则其输出为{0,1}上的一个随 机亵量,若算法D的输入为 0门},则其输出为 的一随机变量,若算法的输入为”和,则 其输出为;X 2)计算逆是困难的,即对每一多项式时间概 率算法()每一多项式p(n)和一切充分大n的有 M (59) 其(种条件4km5.2 单向函数族 ◼ 5.2.1单向函数族的定义 ◼ 定义5.4 一个函数族是由{0,1} 的一个无穷子集I（称为指 标集）和每个指标 对应一个函数 构成， 其 中为{0,1} 的一个有穷子集。 ◼ 定义5.5 一个函数族 称为强单向函数族。 若存在三个多项式时间概率算法A,D,F满足下列两个条件： 1）i和x的抽取和 的计算是容易的，即若算法A的输入 为 （n个1的比特串），则其输出为 {0，1} 上的一个随 机变量 ，若算法D的输入为 {0，1}，则其输出为 上的一个随机变量 ，若算法F的输入为 和 ，则 其输出为 ； 2）计算 的逆 是困难的，即对每一多项式时间概 率算法 ，每一正多项式p(n)和一切充分大n的有 （5.9） 其中 和X 由条件1）给出。 * i I   * f i (x): Di → 0,1 Di * f i : Di →0,1 ;i  I * f (x) i n 1 I  n n I i I  n Di X n i I Di x  f (x) i f (x) i ( ( )) 1 f f x i i − ' M   ( ) Pr ' ( , ( )) 1 ( ( )) 1 p n M I n f I n Xn  f I n f I n Xn  − n I n