第5章单向函数
第5章 单向函数
51一般单向函数 51.1单向函数的定义 定义51函数f:{}→{}*称为正则的,若存在正多项式 p(n)使对任一x∈901),有p((x)2。正则函数的含意是 f()的长不比x的长缩短太多。正则函数的一个重要的特殊 情形是保长函数,即对任一x∈{01}有f(x) 定义52一个函数f:{0,}→⑨0,}为强单向函数,若下列 两个条件成立: (1)计算f(x)是容易的,即fx)是多项式时间可计算的 参看定义4.10) (2)计算f(x)的逆f((x)是困难的,即对每一多项式时间 概率算法(参看定义4.13)M,每一正多项式p(η)和一切充 分大的m(mn≥n有 Pr{(f(n)∈f(U)}< p(n
5.1 一般单向函数 ◼ 5.1.1 单向函数的定义 ◼ 定义 5.1 函数 称为正则的，若存在正多项式 p(n)使对任一 ，有 。正则函数的含意是 f(x)的长不比x的长缩短太多。正则函数的一个重要的特殊 情形是保长函数，即对任一 ，有 。 ◼ 定义 5.2 一个函数 称为强单向函数，若下列 两个条件成立： （1）计算f(x)是容易的，即f(x)是多项式时间可计算的 （参看定义4.10）； （2）计算f(x)的逆 是困难的，即对每一多项式时间 概率算法（参看定义4.13） ，每一正多项式p(n)和一切充 分大的 有 :0,1 0,1* * f → * x 0,1 p( f (x)) x * x 0,1 f (x) = x :0,1 0,1* * f → ( ( )) 1 f f x − ' M ( ) n n n0 ( ) Pr ' ( ( )) 1 ( ( )) 1 p n M f Un f f Un −
一)随机猜测算法M 无论输入那个y=f(x),x∈Ql,M总是输出n次扔硬币结 果r,作为对x的猜测。将M代入(5.1)。因Un与r统计 独立,故得P{()∈f((n)=∑2∑250x)2(52) 其中 1若r∈f-(f(x) (53) δ(r,x) 其它r 当fx)为1-1映射时,(52)式中最后得不等式变为 这是因为∫((x)仅有x一个原像。由(52)和 (53)可见 1)若f(x)为任一函数,则M的成功概率是一个正数 (大小可从2到1),因此不能要求任一多项式时间概 率算法都不可计算函数f(x)的逆; 2)若f(×)为任一1-1映射,则M的成功概率是可忽略 的,当然送并不表示(.单向函数,因为M只是一个 最简单的算法; 3)若f(x)为一单向函数(不要求为1-1映射),则由 于M为多项式时间概率算法,故(51)要求M的成功 概率是可忽略的
◼ （一）随机猜测算法 无论输入那个 ， ， 总是输出n次扔硬币结 果r，作为对x的猜测。将 代入（5.1）。因 与r统计 独立，故得 （5.2） 其中 （5.3） 当f(x)为1－1映射时，（5.2）式中最后得不等式变为 等式。这是因为 中仅有x一个原像。由（5.2）和 (5.3)可见： 1）若f(x)为任一函数，则 的成功概率是一个正数 （大小可从 到1），因此不能要求任一多项式时间概 率算法都不可计算函数f(x)的逆； 2）若f(x)为任一1－1映射，则 的成功概率是可忽略 的，当然这并不表示f(x)为单向函数，因为 只是一个 最简单的算法； 3）若f(x)为一单向函数（不要求为1－1映射），则由 于 为多项式时间概率算法，故（5.1）要求 的成功 概率是可忽略的。 y = f (x) n x 0,1 M1 M1 U n − − − − = x r n n n n n Pr M ( f (U )) f ( f (U )) 2 2 (r, x) 2 1 1 = − r r f f x r x 其它 若 0 1 ( ( )) ( , ) 1 ( ( )) 1 f f x − M1 −n 2 M1 M1 M1 M1 M1
■(二)固定输出算法M, 无论输入那个y=f(x),x∈J,M2总是输出一个 固定的x∈{0},将M2代入(51)式得 PM2()∈f(()=Pr{x∈f(n ∑2"(x,x)=f'(f(x)2≥2 (54) 其中8(x)由(53)给出,(54)中第二个 等式是由于x∈f((x)→x∈f((x),f((x) 表示集((x)的元素个数。当x是/(x)的唯 原像时,(54)中最后一个不等式变为 等式。由(54)可见,M的成功概率与4有 类似的结论
◼ （二）固定输出算法 无论输入那个y=f(x)， ， 总是输出一个 固定的 ，将 代入（5.1）式得 （5.4） 其中 由（5.3）给出，（5.4）中第二个 等式是由于 ， 表示集 中的元素个数。当 是 的唯 一原像时，（5.4）中最后一个不等式变为 等式。由（5.4）可见， 的成功概率与 有 类似的结论。 n x 0,1 M2 M2 n x 0,1 ' M2 Pr ( ( )) ( ( )) Pr ( ( )) 1 ' 1 2 n n Un M f U f f U x f f − − = n n x n x x f f x − − − − = 2 ( , ) = ( ( )) 2 2 ' 1 ' ( , ) ' x x ( ( )) ( ( )) ' 1 1 ' x f f x x f f x − − ( ( )) 1 ' f f x − ( ( )) 1 ' f f x − ' x ( ) ' f x M2 M1
■定义5.3一个函数称为弱单向函数,若下列 两个条件成立: (1)计算f(x)是容易的,它与定义52的1) 相同 (2)计算f(x)的逆f((x湜是稍难的,即存在 个正多项式p(n),使对每一多项式时间概 率算法M和一切充分大的mn2n) PrM((Un)∫(f(Un
◼ 定义 5.3 一个函数称为弱单向函数，若下列 两个条件成立： （1）计算f(x)是容易的，它与定义5.2的1） 相同； （2）计算f(x)的逆 是稍难的，即存在 一个正多项式p(n)，使对每一多项式时间概 率算法 和一切充分大的 有 ( ( )) 1 f f x − ' M ( ) n n n0 ( ) Pr ' ( ( )) 1 ( ( )) 1 p n M f Un f f Un −
51.2候选单向函数 ■例5.1整数因子分解(参看例4.1) fmu (x,y)=x y, x=y (56) 其中x,yxy分别表示整数xy和它们乘积的二进数 表示(参看(4.1)式 ■例53线性编码函数 设常数k,s>0满足k<1-H2(1+) fcode g, m,e)=G, mG+)=G,r) (58) 其中,C为FLn小×n距阵,m为如长消息,e为 v(e)≤m/2的错误
5.1.2 候选单向函数 ◼ 例5.1 整数因子分解（参看例4.1） （5.6） 其中 分别表示整数x,y和它们乘积的二进数 表示（参看（4.1）式 ◼ 例5.3 线性编码函数 设常数 满足 （5.8） 其中，C为F上 距阵，m为 长消息，e为一 个 的错误。 f x y x y x y mult( , ) = , = x, y, x y k,, 0 1 ((1 ) ) k − H2 + f (G,m,e) (G,mG e) (G,r) code = + = kn n 2 kn w(e) n / 2
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) 其(种条件4km
5.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
■定理51任一单向函数f:{0→Q*可表示 为一个单向函数族,反之任一单向函数族 G:D→0l};∈小}也可表示为一单向函数 f:E→⑨}其中E为0,1}的一个无穷子集
◼ 定理 5.1 任一单向函数 可表示 为一个单向函数族，反之任一单向函数族 也可表示为一单向函数 ，其中E为{0,1} 的一个无穷子集。 :0,1 0,1* * f → f i : Di →0,1 ;i I * f : E →0,1* *
522候选单向函数族 ■例54RSA函数族 ■例55Rabn函数族 ■例56Rabn一Bum涵数族 ■例57离散对数函数族
5.2.2 候选单向函数族 ◼ 例 5.4 RSA函数族 ◼ 例 5.5 Rabin函数族 ◼ 例 5.6 Rabin－Blum函数族 ◼ 例 5.7 离散对数函数族
5.3单向函数族的其它性质 ■53.1单向陷门置换族 定义56设:D→D;∈为一单向置换族。由定义 5.5及其后的说明知,存在多项式时间概率算法A 和D及多项式时间确定性算法F满足定义5.5中的 条件1)和2)(参看定义55) 单向置换族:D→D;∈称为单向陷门置换族,若 存在一个多项式时间概率算法A1→0×}和 个多项式时间确定性算法F满足如下条件,其中 n=1,2,… ■3)4(1)=(4(1"),z(A()=(n,(n),其中A"和A(")分别 表示算法A和A输入1时的输出,1为1⌒上的随机 变量,且对每对(,(),i∈l 和x∈D每个有F(xo()=x 即陷门作为求逆算法的辅助输入
5．3 单向函数族的其它性质 ◼ 5.3.1 单向陷门置换族 ◼ 定义5.6 设 为一单向置换族。由定义 5.5 及其后的说明知，存在多项式时间概率算法 和D及多项式时间确定性算法F满足定义5.5中的 条件1）和2）（参看定义5.5）。 ◼ 单向置换族 称为单向陷门置换族，若 存在一个多项式时间概率算法 和一 个多项式时间确定性算法 满足如下条件，其中 。 ◼ 3） ，其中 和 分别 表示算法A和 输入 时的输出，为 上的随机 变量，且对每对 和 每个有 ， 即陷门 作为求逆算法 的辅助输入。 f i : Di → Di ;i I A1 f i : Di → Di ;i I * * * A:1 → 0,1 0,1 −1 F 1 1 ; 1,2, * = n = n (1 ) ( (1 ), ( (1 )) ( , ( )) 1 1 n n n n n A = A A = I I (1 ) n A (1 ) 1 n A A1 n 1 n I n I 0,1 (i, (i)),i I Di x F i f x x i = − ( ( ), ( )) 1 (i) −1 F