6.4 用伪随机序列生成器构造伪随机函数
定义 6.7 一个随机函数序列Fn ; n 1 是一个在函数集 n中取值的
随机变量序列，其概率分布为 PrFn f pn ( f ), f n，即
pn ( f ) 0, pn ( f ) 1, n 1,2,
，特别地，一个随机函数序列称为真
Pr
M Pn (1n ) 1 Pr
M Kn (1n ) 1
1 p(n)
（6.7）
定理 6.8 设Fn，t(n)，DESFnt(n)如构造方法6.4中所 给。若随机函数序列 Fn;n 1是多项式时间可实
现（计算）的，且t(n)是多项式时间可计算的，
则随机函数序列
DESFn也t(n);是n 1多 项式时间可实
1)延伸性，存在一个正整数函数 l(n) n(n 1,2, ) 使得对一
切 x 0,1*有 G(x) l( x ) ；
2)伪随机性，随机变量序列 G(U
它与均匀分布随机变量序列U
n l(
);
n)
n 1是伪随机的，即
; n 1 是多项式时间不
可区分的。
生成器G的输入x称为它的种子，要求将长n比特的种 子延伸为长l(n)比特的序列，且该序列与长l(n)的随机 比特序列是多项式时间不可区分的。l(n)>n称为的延 伸因子。
随机f函n 数序列若其概率分n布为 上的均匀分布，即对f 每个n
有
，记真随机函数序H n列; n 为 1
。
pn ( f )
1 2n2n
定义 6.8一个确定性神图灵机是一个确定性图灵机（见定义4.4）
附加一条磁带，称为神带，和两个特殊状态sinv , sora S ，sinv称为求 神状态，sora称为神现状态。当一个神图灵机M输入x，存取函数 f : 0,1* 0,1*时，其计算也是一个形的有限或无限序列，(s0 ,t0 ,i0 ), (s1,t1,i1), ,(s j
n
)
1 2
1 p(n)
（6.4）
定理 6.3 一个随机变量序列X n;n 1是伪随机的
（参看定义6.4）当且仅当它是多项式时间不
可预测的。
(4)单向函数性。
定理 6.4 设G为一延伸因子l(n)的伪随机序列生 成器，若对每对 x, y 0,1*满足 x y ，定义函数
f (x, y) G(x)，则f为一强单向函数。
式时间概率算法M’，每个正多项式p(n)和一切 充分大的n有
Pr M ' (X i ,i) 1 Pr M ' (Yi ,i) 1
1 p( i )
（6.1）
定义 6.3 两个随机变量序列X n;n 1和Yn ;n 1 的变差距离定义为
(n)
1 2
PrX n
x0,1n
x PrYn
6．3．2 用单向置换族构造伪随机序列生成器
定理 6.6 设多项式时间概率算法A,D,F定义一 单向置换族fi : Di Di ;i I ， 为该单向 bi : Di 0,1;i I 置换族的硬核谓词族，q(n)及p(n) 2q(n)，G如构 造方法6.2中所给。再设对每个 i I，D(i)为在Di 上均匀分布的随机变量，则G为一伪随机序列 生成器，它将2q(n)长的种子(r,s)延伸为p(n)长 的伪随机序列。
串s延伸为2n长比特串G(s)，定义函数G0(s)为G(s)的
前n个比特，G1(s)为G(s)的后n个比特（即
G(s)=G0(s)G1(s)）对每个s 0,1n 和每个 x (x1, x2, , xn )0，,1n
定义函数
f s (x) Gxn ( (Gx2 (Gx1 (s)) )
(6.6)
定义随机函数Fn fUn (x) ，其中Un为0,1上n 的均匀分布随
6．3 伪随机序列生成器的构造
6.3.1 用一般单向置换构造伪随机序列生成器 定理 6.5 设 f : 0,1* 0,1* 为一1－1保长强单向函 数，b : 0,1* 0,1为函数f的硬核谓词（多项式时 间可计算）。定义G(x) f (x)b(x（) b(x)和f(x)的连 接），则G为一伪随机序列生成器。
x, n
1
（6.3）
定义 6.4 称一个随机变量序列X n;n 1是伪随机
的，若它与 0,1l(n) 上的均匀分布随机变量序列Ul(n);n 1
是多项式时间不可区分的，其中设Xn取值于 集。 0,1l ( n )
6.2 伪随机序列生成器的定义和性质
定义 6.5 一个伪随机序列生成器是一个确定性多项式 时间算法G满足下列两个条件：
，其关系由读写头所处状态的转移函数和读写头动作的指令
函数确定，若 s j sinv ，则第j+1个形如定义4.4所给，若第j个形中
的状态sj=sinv，且神带中的内容为 q 0,1* ，则第j+1个形中的状态 sj+1=sora，且神带中的内容为f(q)，q称为M的提问，f(q)称为神的回 答。神图灵机的输出M，记作Mf(x)，以及运行（计算）时间如定
第六章 伪随机序列生成器
6．1 计算不可区分性
定义 6.1 一个概率分布族是由0,1*的一个无穷 子集I，称为指标集，和每个指标 i I对应一个 概率分布pi (x) : Di [0,1], pi (x) 0, pi (x) 1构成，其中 Di为0,1*的一个有穷子集。xDi
定义 6.2 两个随机变量族 X i 和 | xi Di ,i I Yi | yi Ei ,i I 称为多项式时间不可区分，若对每个多项
伸为一个p(n)长比特串x。由于G1是确定性多项式时
间算法，故G也是确定性的多项式时间算法。
(3)不可预测性。
定义 6.6 随机变量序列X n;n 1称为多项式时间
不可预测的若对每个多项式时间概率算法M’，
每个正多项式p(n)和一切充分大的n有
Pr
M ' (1 Xn
,
X
n
)
next M
'
(
X
任一多项式。我们用G1作p(n)次迭代，即置s0 s, s n 为G1的初始输入，计算G1(si1) xi si ,i 1,2, , p(n) ，其中
即 xi 0,1, si si1 n xi为si 输入 s时i1 G1输出的长n+1比特串。
定义算法G为
G(s) x x1，x2 它x p将(n) 一个n长比特串s延
现的，且为多项式时间可逆的随机置换序列，
更进一步，若 F是n;n一 1个伪随机函数序列，
则
DES为Fn 3;一n 1伪 随机置换序列。
一个随机置换序列称为真随n 机置换序列，若其
概率分布为 上的n 均匀分布，即对每个 有 n pn ( ) 12n!，记真随机置换序列为Kn ;n 1。
定义 6.11 一个随机置换序列 Pn;n 1 称为伪随
机置换序列，若对每个多项式时间神概率图灵
机M，每个正多项式p(n)和一切充分大的n有
机变量（即s在0,1n 中按均匀分布随机抽取），Fn ; n 1
即为所构造的随机函数序列。
6．5 伪随机置换的构造
定义 6.10 一个随机置换序列Pn;n 1是一个在置
换集n 中取值的随机变量序列，其概率分布
为 ，即 ，特别地， PrPn pn ( ), n
pn ( ) 0, pn ( ) 1, n 1,2,
义4.4所定义。
定义 6.9 一个随机函数序列Fn ; n 1称为伪随机函数序
列若对每个多项式时间神概率图灵机M，每个正多项
式p(n)和一切充分大的n有
Pr
M Fn (1n ) 1 Pr
M Hn (1n ) 1
1 p(n)
（6.5）
构造方法6.3 ，设G为一个确定性算法，它将n长比特
ቤተ መጻሕፍቲ ባይዱ
伪随机序列生成器的性质
(1)统计性质
定理 6.1 若是一个伪随机序列生成器，即满足定义
6.5 中的条件，则随机变量序列 G(U n ); n 1与 U l(n) ; n 1
不是统计接近的。
(2)多项式延伸性
构造方法6.1，设G1为一确定性多项式时间算法，它
将每个长n比特串延伸为一个长n+1比特串，p(n)>n为