第六章 伪随机序列生成器
6,1 计算不可区分性
? 定义 6.1 一个概率分布族是由 的一个无穷
子集 I，称为指标集，和每个指标 对应一个
概率分布 构成，其中
Di为 的一个有穷子集。
? 定义 6.2 两个随机变量族 和
称为多项式时间不可区分，若对每个多项
式时间概率算法 M’，每个正多项式 p(n)和一切
充分大的 n有
（ 6.1）
? ?*1,0
Ii?
?? ???
iDx
iiii xpxpDxp 1)(,0)(],1,0[:)(
? ?*1,0
? ?IiDxX iii ??,| ? ?IiEyY iii ??,|
? ? ? ? )(11),(Pr1),(Pr '' ipiYMiXM ii ????
? 定义 6.3 两个随机变量序列 和
的变差距离定义为
（ 6.3）
? 定义 6.4 称一个随机变量序列 是伪随机
的，若它与 上的均匀分布随机变量序列
是多项式时间不可区分的，其中设 Xn取值于
集。
? ?1; ?nX n ? ?1; ?nYn
? ? ? ?
? ???
??????
nx
nn nxYxXn
1,0
1,PrPr21)(
? ?1; ?nX n
? ? )(1,0 nl ? ?1;)( ?nU nl
? ? )(1,0 nl
6.2 伪随机序列生成器的定义和性质
? 定义 6.5 一个伪随机序列生成器是一个确定性多项式
时间算法 G满足下列两个条件,
1)延伸性，存在一个正整数函数 使得对一
切 有 ；
2)伪随机性，随机变量序列 是伪随机的，即
它与均匀分布随机变量序列 是多项式时间不
可区分的。
生成器 G的输入 x称为它的种子，要求将长 n比特的种
子延伸为长 l(n)比特的序列，且该序列与长 l(n)的随机
比特序列是多项式时间不可区分的。 l(n)>n称为的延
伸因子。
),2,1()( ??? nnnl
? ?*1,0?x )()( xlxG ?
? ?1);( ?nUG n
? ?1;)( ?nU nl
? 伪随机序列生成器的性质
(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也是确定性的多项式时间算法。
? ?1);( ?nUG n ? ?1;)( ?nU nl
nsss ??,0
)(,,2,1,)( 11 npisxsG iii ????
? ? nssx iii ??? ?1,1,0 iisx 1?is
)(21)( npxxxxsG ???
(3)不可预测性。
定义 6.6 随机变量序列 称为多项式时间
不可预测的若对每个多项式时间概率算法 M’，
每个正多项式 p(n)和一切充分大的 n有
（ 6.4）
定理 6.3 一个随机变量序列 是伪随机的
（参看定义 6.4）当且仅当它是多项式时间不
可预测的。
(4)单向函数性。
定理 6.4 设 G为一延伸因子 l(n)的伪随机序列生
成器，若对每对 满足,定义函数
,则 f为一强单向函数。
? ?1; ?nX n
? ? )(121)(),1(Pr '' npXn e x tXM nMnX n ???
? ?1; ?nX n
? ?*1,0,?yx yx ?
)(),( xGyxf ?
6,3 伪随机序列生成器的构造
6.3.1 用一般单向置换构造伪随机序列生成器
定理 6.5 设 为一 1－ 1保长强单向函
数,为函数 f的硬核谓词（多项式时
间可计算）。定义 （ b(x)和 f(x)的连
接），则 G为一伪随机序列生成器。
? ? ? ?** 1,01,0,?f
? ? ? ?1,01,0,* ?b
)()()( xbxfxG ?
6,3,2 用单向置换族构造伪随机序列生成器
定理 6.6 设多项式时间概率算法 A,D,F定义一
单向置换族, 为该单向
置换族的硬核谓词族,q(n)及, G如构
造方法 6.2中所给。再设对每个, D(i)为在 Di
上均匀分布的随机变量，则 G为一伪随机序列
生成器，它将 2q(n)长的种子 (r,s)延伸为 p(n)长
的伪随机序列。
? ?IiDDf iii ?? ;,? ?? ?IiDb ii ?? ;1,0:
)(2)( nqnp ?
Ii?
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所定义。
? ?1; ?nFn n?
? ? nnn ffpfF ???? ),(Pr
??? ???
nf
nn nfpfp ?,2,1,1)(,0)(
n? nf ?? nnn fp 221)( ?
? ?1; ?nHn
Sss orainv ?,
? ? ? ?** 1,01,0,?f ?? ),,,(,),,,(),,,( 111000 jjj itsitsits
invj ss ?
? ?*1,0?q
? 定义 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在 中按均匀分布随机抽取）,
即为所构造的随机函数序列。
? ?1; ?nFn
? ? ? ? )(11)1(Pr1)1(Pr npMM nHnF nn ????
? ?ns 1,0? ? ?nnxxxx 1,0),,,( 21 ?? ?
)))(((()( 12 ?? sGGGxf xxxs n?
)(xfF nUn ? ? ?n1,0
? ?n1,0 ? ?1; ?nFn
6,5 伪随机置换的构造
? 定义 6.10 一个随机置换序列 是一个在置
换集 中取值的随机变量序列，其概率分布
为,即,特别地，
一个随机置换序列称为真随机置换序列，若其
概率分布为 上的均匀分布，即对每个 有
,记真随机置换序列为 。
? 定义 6.11 一个随机置换序列 称为伪随
机置换序列，若对每个多项式时间神概率图灵
机 M，每个正多项式 p(n)和一切充分大的 n有
（ 6.7）
? ?1; ?nPn
n?
? ? nnn pP ???? ??? ),(Pr ?
?? ??? n npp nn ? ?? ?,2,1,1)(,0)(
n? n???
!21)( nnp ?? ? ?1; ?nK n
? ?1; ?nPn
? ? ? ? )(11)1(Pr1)1(Pr npMM nKnP nn ????
? 定理 6.8 设 Fn,t(n),如构造方法 6.4中所
给。若随机函数序列 是多项式时间可实
现（计算）的，且 t(n)是多项式时间可计算的，
则随机函数序列 也是多项式时间可实
现的，且为多项式时间可逆的随机置换序列，
更进一步，若 是一个伪随机函数序列，
则 为一伪随机置换序列。
)(ntF
nDES
? ?1; ?nFn
? ?1;)( ?nD E S ntF n
? ?1; ?nFn
? ?1;3 ?nD E S nF
6,1 计算不可区分性
? 定义 6.1 一个概率分布族是由 的一个无穷
子集 I，称为指标集，和每个指标 对应一个
概率分布 构成，其中
Di为 的一个有穷子集。
? 定义 6.2 两个随机变量族 和
称为多项式时间不可区分，若对每个多项
式时间概率算法 M’，每个正多项式 p(n)和一切
充分大的 n有
（ 6.1）
? ?*1,0
Ii?
?? ???
iDx
iiii xpxpDxp 1)(,0)(],1,0[:)(
? ?*1,0
? ?IiDxX iii ??,| ? ?IiEyY iii ??,|
? ? ? ? )(11),(Pr1),(Pr '' ipiYMiXM ii ????
? 定义 6.3 两个随机变量序列 和
的变差距离定义为
（ 6.3）
? 定义 6.4 称一个随机变量序列 是伪随机
的，若它与 上的均匀分布随机变量序列
是多项式时间不可区分的，其中设 Xn取值于
集。
? ?1; ?nX n ? ?1; ?nYn
? ? ? ?
? ???
??????
nx
nn nxYxXn
1,0
1,PrPr21)(
? ?1; ?nX n
? ? )(1,0 nl ? ?1;)( ?nU nl
? ? )(1,0 nl
6.2 伪随机序列生成器的定义和性质
? 定义 6.5 一个伪随机序列生成器是一个确定性多项式
时间算法 G满足下列两个条件,
1)延伸性，存在一个正整数函数 使得对一
切 有 ；
2)伪随机性，随机变量序列 是伪随机的，即
它与均匀分布随机变量序列 是多项式时间不
可区分的。
生成器 G的输入 x称为它的种子，要求将长 n比特的种
子延伸为长 l(n)比特的序列，且该序列与长 l(n)的随机
比特序列是多项式时间不可区分的。 l(n)>n称为的延
伸因子。
),2,1()( ??? nnnl
? ?*1,0?x )()( xlxG ?
? ?1);( ?nUG n
? ?1;)( ?nU nl
? 伪随机序列生成器的性质
(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也是确定性的多项式时间算法。
? ?1);( ?nUG n ? ?1;)( ?nU nl
nsss ??,0
)(,,2,1,)( 11 npisxsG iii ????
? ? nssx iii ??? ?1,1,0 iisx 1?is
)(21)( npxxxxsG ???
(3)不可预测性。
定义 6.6 随机变量序列 称为多项式时间
不可预测的若对每个多项式时间概率算法 M’，
每个正多项式 p(n)和一切充分大的 n有
（ 6.4）
定理 6.3 一个随机变量序列 是伪随机的
（参看定义 6.4）当且仅当它是多项式时间不
可预测的。
(4)单向函数性。
定理 6.4 设 G为一延伸因子 l(n)的伪随机序列生
成器，若对每对 满足,定义函数
,则 f为一强单向函数。
? ?1; ?nX n
? ? )(121)(),1(Pr '' npXn e x tXM nMnX n ???
? ?1; ?nX n
? ?*1,0,?yx yx ?
)(),( xGyxf ?
6,3 伪随机序列生成器的构造
6.3.1 用一般单向置换构造伪随机序列生成器
定理 6.5 设 为一 1－ 1保长强单向函
数,为函数 f的硬核谓词（多项式时
间可计算）。定义 （ b(x)和 f(x)的连
接），则 G为一伪随机序列生成器。
? ? ? ?** 1,01,0,?f
? ? ? ?1,01,0,* ?b
)()()( xbxfxG ?
6,3,2 用单向置换族构造伪随机序列生成器
定理 6.6 设多项式时间概率算法 A,D,F定义一
单向置换族, 为该单向
置换族的硬核谓词族,q(n)及, G如构
造方法 6.2中所给。再设对每个, D(i)为在 Di
上均匀分布的随机变量，则 G为一伪随机序列
生成器，它将 2q(n)长的种子 (r,s)延伸为 p(n)长
的伪随机序列。
? ?IiDDf iii ?? ;,? ?? ?IiDb ii ?? ;1,0:
)(2)( nqnp ?
Ii?
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所定义。
? ?1; ?nFn n?
? ? nnn ffpfF ???? ),(Pr
??? ???
nf
nn nfpfp ?,2,1,1)(,0)(
n? nf ?? nnn fp 221)( ?
? ?1; ?nHn
Sss orainv ?,
? ? ? ?** 1,01,0,?f ?? ),,,(,),,,(),,,( 111000 jjj itsitsits
invj ss ?
? ?*1,0?q
? 定义 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在 中按均匀分布随机抽取）,
即为所构造的随机函数序列。
? ?1; ?nFn
? ? ? ? )(11)1(Pr1)1(Pr npMM nHnF nn ????
? ?ns 1,0? ? ?nnxxxx 1,0),,,( 21 ?? ?
)))(((()( 12 ?? sGGGxf xxxs n?
)(xfF nUn ? ? ?n1,0
? ?n1,0 ? ?1; ?nFn
6,5 伪随机置换的构造
? 定义 6.10 一个随机置换序列 是一个在置
换集 中取值的随机变量序列，其概率分布
为,即,特别地，
一个随机置换序列称为真随机置换序列，若其
概率分布为 上的均匀分布，即对每个 有
,记真随机置换序列为 。
? 定义 6.11 一个随机置换序列 称为伪随
机置换序列，若对每个多项式时间神概率图灵
机 M，每个正多项式 p(n)和一切充分大的 n有
（ 6.7）
? ?1; ?nPn
n?
? ? nnn pP ???? ??? ),(Pr ?
?? ??? n npp nn ? ?? ?,2,1,1)(,0)(
n? n???
!21)( nnp ?? ? ?1; ?nK n
? ?1; ?nPn
? ? ? ? )(11)1(Pr1)1(Pr npMM nKnP nn ????
? 定理 6.8 设 Fn,t(n),如构造方法 6.4中所
给。若随机函数序列 是多项式时间可实
现（计算）的，且 t(n)是多项式时间可计算的，
则随机函数序列 也是多项式时间可实
现的，且为多项式时间可逆的随机置换序列，
更进一步，若 是一个伪随机函数序列，
则 为一伪随机置换序列。
)(ntF
nDES
? ?1; ?nFn
? ?1;)( ?nD E S ntF n
? ?1; ?nFn
? ?1;3 ?nD E S nF
