第六章伪随机序列生成器 ●●●●● ●●●● ●●。●●
第六章 伪随机序列生成器
●●●●● ●●●● 6.1计算不可区分性 ●●0 ●●● ●●●● ●定义6.1一个概率分布族是由)一个无穷 子集l,称为指标集,和每个指标i∈对应一个 概率分布P(∞);D→01p(x)≥0∑P(x)=1构成,其中 x∈D D为)的一个有穷子集 ●定义62两个随机变量族{|x∈D,i∈l和y,ly∈E,iel 称为多项式时间不可区分,若对每个多项 式时间概率算法M,每个正多项式p(η)和一切 充分大的n有 P(x,)=1}-P{(C,)=l) (6.1)
6．1 计算不可区分性 ⚫ 定义 6.1 一个概率分布族是由 的一个无穷 子集I，称为指标集，和每个指标 对应一个 概率分布 构成，其中 Di为 的一个有穷子集。 ⚫ 定义 6.2 两个随机变量族 和 称为多项式时间不可区分，若对每个多项 式时间概率算法M’，每个正多项式p(n)和一切 充分大的n有 （6.1） * 0,1 i I → = Di x i i i i p (x): D [0,1], p (x) 0, p (x) 1 * 0,1 Xi | xi Di ,i I Yi | yi Ei ,i I ( ) Pr ' ( , ) 1 Pr ' ( , ) 1 1 p i M X i M Y i i = − i =
●●●●● ●●●● ●●0 ●●● ●●●● 定义6.3两个随机变量序列{x;n≥和{n;n≥} 的变差距离定义为 △(m)=∑Pr{n=x}-Pr{=xln21 (63) x∈0y ●定义6.4称一个随机变量序列{xn;n≥1是伪随机 的,若它与1}"上的均匀分布随机变量序列mn2l 是多项式时间不可区分的,其中设Xn取值于 0集
⚫ 定义 6.3 两个随机变量序列 和 的变差距离定义为 （6.3） ⚫ 定义 6.4 称一个随机变量序列 是伪随机 的，若它与 上的均匀分布随机变量序列 是多项式时间不可区分的，其中设Xn取值于 集。 Xn ;n 1 Yn ;n 1 = = − = n x n Xn x Yn x n 0,1 Pr Pr , 1 2 1 ( ) Xn ;n 1 ( ) 0,1 l n Ul(n) ;n 1 ( ) 0,1 l n
●●●●● ●●●● 62伪随机序列生成器的定义和性质 ●●0 ●●● ●●●● ●定义6.5一个伪随机序列生成器是一个确定性多项式 时间算法G满足下列两个条件: 1)延伸性,存在一个正整数函数m)>mn=12,…)使得对 切x∈{o}有G(x)=l(x); 2)伪随机性,随机变量序列G(U)n≥1}是伪随机的,即 它与均匀分布随机变量序列m;n21是多项式时间不 可区分的 生成器G的输入ⅹ称为它的种子,要求将长n比特的种 子延伸为长(n)比特的序列,且该序列与长(n)的随机 比特序列是多项式时间不可区分的。()>n称为的延 伸因子
6.2 伪随机序列生成器的定义和性质 ⚫ 定义 6.5 一个伪随机序列生成器是一个确定性多项式 时间算法G满足下列两个条件： 1)延伸性，存在一个正整数函数 使得对一 切 有 ； 2)伪随机性，随机变量序列 是伪随机的，即 它与均匀分布随机变量序列 是多项式时间不 可区分的。 生成器G的输入x称为它的种子，要求将长n比特的种 子延伸为长l(n)比特的序列，且该序列与长l(n)的随机 比特序列是多项式时间不可区分的。l(n)>n称为的延 伸因子。 l(n) n(n = 1,2, ) * x 0,1 G(x) = l( x ) G(Un );n 1 Ul(n) ;n 1
●●●●● 伪随机序列生成器的性质 ●●●● ●●0 (1)统计性质 ●●● ●●●● 定理61若是一个伪随机序列生成器,即满足定义 65中的条件,则随机变量序列{(Un)n≥1与{mn≥ 不是统计接近的。 (2)多项式延伸性 构造方法6.1,设G1为一确定性多项式时间算法,它 将每个长n比特串延伸为一个长n+1比特串,p(n)>n为 任一多项式。我们用G1作p(m)次迭代,即置s。=ss=n 为G1的初始输入,计算G(S)=x$,=1,2…,p(n),其中 x∈=-x为输入时G1输出的长n+1比特串 定义算法G为G()=x=xx2凝一个n长比特串s延 伸为一个p(n)长比特串x。由于G1是确定性多项式时 间算法,故G也是确定性的多项式时间算法
⚫ 伪随机序列生成器的性质 (1)统计性质 定理 6.1 若是一个伪随机序列生成器，即满足定义 6.5 中的条件，则随机变量序列 与 不是统计接近的。 (2)多项式延伸性 构造方法6.1，设G1为一确定性多项式时间算法，它 将每个长n比特串延伸为一个长n+1比特串，p(n)>n为 任一多项式。我们用G1作p(n)次迭代，即置 为G1的初始输入，计算 ，其中 即 为输入 时G1输出的长n+1比特串。 定义算法G为 ，它将一个n长比特串s延 伸为一个p(n)长比特串x。由于G1是确定性多项式时 间算法，故G也是确定性的多项式时间算法。 G(Un );n 1 Ul(n) ;n 1 s0 = s, s = n ( ) , 1,2, , ( ) G1 si−1 = xi si i = p n xi 0,1, si = si−1 = n i i x s i−1 s 1 2 ( ) ( ) p n G s = x = x x x
(3)不可预测性。 ●●●●● 定义66随机变量序列x,m2称为多项式时l 不可预测的若对每个多项式时间概率算法M,。 每个正多项式p(n)和一切充分大的n有 P(,x)=meo(x,)}<2+ 2p(n) (64) 定理63一个随机变量序列xn21是伪随机的 (参看定义64)当且仅当它是多项式时间不 可预测的。 (4)单向函数性 定理64设G为一延伸因子(m)的伪随机序列生 成器,若对每对xy∈满足=川,定义函数 f(x,y)=G(x),则f为一强单向函数
(3)不可预测性。 定义 6.6 随机变量序列 称为多项式时间 不可预测的若对每个多项式时间概率算法M’， 每个正多项式p(n)和一切充分大的n有 （6.4） 定理 6.3 一个随机变量序列 是伪随机的 （参看定义6.4）当且仅当它是多项式时间不 可预测的。 (4)单向函数性。 定理 6.4 设G为一延伸因子l(n)的伪随机序列生 成器，若对每对 满足 ，定义函数 ，则f为一强单向函数。 Xn ;n 1 ( ) 1 2 1 Pr (1 , ) ' ( ) ' p n M Xn nextM Xn Xn = + Xn ;n 1 * x, y 0,1 x = y f (x, y) = G(x)
●●●●● ●●●● 6.3伪随机序列生成器的构造 ●●0 ●●● ●●●● 6.3.1用一般单向置换构造伪随机序列生成器 定理65设∫:{}→@为-1-1保长强单向函 数,b:@}→@为函数f的硬核谓词(多项式时 间可计算)。定义(x)=1xx)(b(x和f(x)的连 接),则G为一伪随机序列生成器
6．3 伪随机序列生成器的构造 6.3.1 用一般单向置换构造伪随机序列生成器 定理 6.5 设 为一1－1保长强单向函 数， 为函数f的硬核谓词（多项式时 间可计算）。定义 （b(x)和f(x)的连 接），则G为一伪随机序列生成器。 * * f : 0,1 → 0,1 :0,1 0,1 * b → G(x) = f (x)b(x)
●●●●● ●●●● ●●0 ●●● ●●●● 6.3.2用单向置换族构造伪随机序列生成器 定理6.6设多项式时间概率算法A,D,F定义 单向置换族:D,→D;∈}:D→∈为该单向 置换族的硬核谓词族,q(η)及以)>24n,G如构 造方法62中所给。再设对每个∈,D(为在Di 上均匀分布的随机变量,则G为一伪随机序列 生成器,它将2q()长的种子〔,s)延伸为p(n)长 的伪随机序列
6．3．2 用单向置换族构造伪随机序列生成器 定理 6.6 设多项式时间概率算法A,D,F定义一 单向置换族 ， 为该单向 置换族的硬核谓词族，q(n)及 ，G如构 造方法6.2中所给。再设对每个 ，D(i)为在Di 上均匀分布的随机变量，则G为一伪随机序列 生成器，它将2q(n)长的种子(r,s)延伸为p(n)长 的伪随机序列。 f i : Di → Di ;i I bi : Di →0,1;i I p(n) 2q(n) i I
●●●●● ●●●● 64用伪随机序列生成器构造伪随机函数 定义6.7一个随机函数序列{Fnn≥1是一个在函数集中取值的 随机变量序列,其概率分布为P{=∫}=p,(,∫∈L,即 Pn()≥0.∑Pn()=1n=12 特别地,一个随机函数序列称为真 随函数序列若其概率分布为上的均匀分布,即对每个P0=2 有 ,记真随机函数庑列为} 定义6.8一个确定性神图灵机是一个确定性图灵机(见定义4.4) 附加一条磁带,称为神带,和两个特殊状态Sm,sm∈S,Sin称为求 神状态,S。a称为神现状态。当一个神图灵机M输入x,存取函数 f:}→@时,其计算也是一个形的有限或无限序列,)(s14)…( ,其关系由读写头所处状态的转移函数和读写头动作的指令 函数确定,若S≠Sm,则第j+1个形如定义4.4所给,若第个形中 的状态S=sm,且神带中的内容为g∈,则第j+1个形中的状态 s+1=So,且神带中的内容为f(q),q称为M的提间,fQ)称为神的回 答。神图灵机的输出M,记作M(x),以及运行(计算)时间如定 义4.4所定义
6.4 用伪随机序列生成器构造伪随机函数 ⚫ 定义 6.7 一个随机函数序列 是一个在函数集 中取值的 随机变量序列，其概率分布为 ，即 ，特别地，一个随机函数序列称为真 随机函数序列若其概率分布为 上的均匀分布，即对每个 有 ，记真随机函数序列为 。 ⚫ 定义 6.8一个确定性神图灵机是一个确定性图灵机（见定义4.4） 附加一条磁带，称为神带，和两个特殊状态 ，sinv称为求 神状态，sora称为神现状态。当一个神图灵机M输入x，存取函数 时，其计算也是一个形的有限或无限序列， ，其关系由读写头所处状态的转移函数和读写头动作的指令 函数确定，若 ，则第j+1个形如定义4.4所给，若第j个形中 的状态sj=sinv，且神带中的内容为 ，则第j+1个形中的状态 sj+1=sora，且神带中的内容为f(q)，q称为M的提问，f(q)称为神的回 答。神图灵机的输出M，记作Mf (x)，以及运行（计算）时间如定 义4.4所定义。 Fn ;n 1 n n n n Pr F = f = p ( f ), f = = n f n n p ( f ) 0, p ( f ) 1,n 1,2, n n f n n n p f 2 2 ( ) = 1 Hn ;n 1 sinv ,sora S * * f : 0,1 → 0,1 (s0 ,t 0 ,i 0 ),(s1 ,t 1 ,i 1 ), ,(sj ,t j ,i j ), j inv s s * q 0,1
●●●●● 定义69一个随机函数序列F;n≥称为伪随机函孱。 列若对每个多项式时间神概率图灵机M,每个正多项 式p(n)和一切充分大的n有 Pr(")=1}P()=< p(n) (65) ●构造方法6、3,设G为一个确定性算法,它将n长比特 串s延伸为2n长比特串G(s),定义函数G0(s)为G(s)的 前n个比特,G1(s)为G(s)的后n个比特(即 G(s)=G0(s)G1(s)对每个∈和每个x=(xx2x)∈ 定义函数 f(x)=G.(…(G2(Gx2(s)…) (66) 定义随机函数f=f(x),其中Un为上的均匀分布随 机变量(即s柚}中按均匀分布随机抽取),{nn≥1 即为所构造的随机函数序列
⚫ 定义 6.9 一个随机函数序列 称为伪随机函数序 列若对每个多项式时间神概率图灵机M，每个正多项 式p(n)和一切充分大的n有 （6.5） ⚫ 构造方法6.3 ，设G为一个确定性算法，它将n长比特 串s延伸为2n长比特串G(s)，定义函数G0(s)为G(s)的 前n个比特，G1(s)为G(s)的后n个比特（即 G(s)=G0(s)G1(s)）对每个 和每个 ， 定义函数 (6.6) 定义随机函数 ，其中Un为 上的均匀分布随 机变量（即s在 中按均匀分布随机抽取）， 即为所构造的随机函数序列。 Fn ;n 1 ( ) Pr (1 ) 1 Pr (1 ) 1 1 p n M M Fn n Hn n = − = n s 0,1 n n x = (x1 , x2 , , x ) 0,1 ( ) ( ( ( ( )) ) f s x = Gxn Gx2 Gx1 s F f (x) n Un = n 0,1 n 0,1 Fn ;n 1