文档介绍：第六章伪随机序列生成器
计算不可区分性
定义 一个概率分布族是由的一个无穷子集I,称为指标集,和每个指标对应一个概率分布构成,其中Di为的一个有穷子集。
定义 两个随机变量族和称为多项式时间不可区分,若对每个多项式时间概率算法M’,每个正多项式p(n)和一切充分大的n有
()
定义 两个随机变量序列和的变差距离定义为
()
定义 称一个随机变量序列是伪随机的,若它与上的均匀分布随机变量序列是多项式时间不可区分的,其中设Xn取值于集。
伪随机序列生成器的定义和性质
定义 一个伪随机序列生成器是一个确定性多项式时间算法G满足下列两个条件:
1)延伸性,存在一个正整数函数使得对一切有;
2)伪随机性,随机变量序列是伪随机的,即它与均匀分布随机变量序列是多项式时间不可区分的。
生成器G的输入x称为它的种子,要求将长n比特的种子延伸为长l(n)比特的序列,且该序列与长l(n)的随机比特序列是多项式时间不可区分的。l(n)>n称为的延伸因子。
伪随机序列生成器的性质
(1)统计性质
定理 若是一个伪随机序列生成器, 中的条件,则随机变量序列与不是统计接近的。
(2)多项式延伸性
,设G1为一确定性多项式时间算法,它将每个长n比特串延伸为一个长n+1比特串,p(n)>n为任一多项式。我们用G1作p(n)次迭代,即置为G1的初始输入,计算,其中即为输入时G1输出的长n+1比特串。定义算法G为,它将一个n长比特串s延伸为一个p(n)长比特串x。由于G1是确定性多项式时间算法,故G也是确定性的多项式时间算法。
(3)不可预测性。
定义 随机变量序列称为多项式时间不可预测的若对每个多项式时间概率算法M’,每个正多项式p(n)和一切充分大的n有
()
定理 一个随机变量序列是伪随机的()当且仅当它是多项式时间不可预测的。
(4)单向函数性。
定理 设G为一延伸因子l(n)的伪随机序列生成器,若对每对满足,定义函数,则f为一强单向函数。
伪随机序列生成器的构造
用一般单向置换构造伪随机序列生成器
定理 设为一1-1保长强单向函数, 为函数f的硬核谓词(多项式时间可计算)。定义(b(x)和f(x)的连接),则G为一伪随机序列生成器。
用单向置换族构造伪随机序列生成器
定理 设多项式时间概率算法A,D,F定义一单向置换族, 为该单向置换族的硬核谓词族,q(n)及,。再设对每个,D(i)为在Di上均匀分布的随机变量,则G为一伪随机序列生成器,它将2q(n)长的种子(r,s)延伸为p(n)长的伪随机序列。
用伪随机序列生成器构造伪随机函数
定义 一个随机函数序列是一个在函数集中取值的随机变量序列,其概率分布为,即,特别地,一个随机函数序列称为真随机函数序列若其概率分布为上的均匀分布,即对每个有,记真随机函数序列为。
定义 ()附加一条磁带,称为神带,和两个特殊状态,sinv称为求神状态,sora称为神现状态。当一个神图灵机M输入x,存取函数时,其计算也是一个形的有限或无限序列, ,其关系由读写头所处状态的转移函数和读写头动作的指令函数确定,若 ,则第j+,若第j个形中的状态sj=sinv,且神带中的内容为,则第j+1个形中的状态sj+1=sora,且神带中的内容为f(q),q称为M的提问,f(q)称为神的回答。神图灵机的输出M,记作Mf(x),以及运行(计算)。
定义 一个随机函数序列称为伪随机函数序列若对每个多项式时间神概率图灵机M,每个正多项式p(n)和一切充分大的n有
()
,设G为一个确定性算法,它将n长比特串s延伸为2n长比特串G(s),定义函数G0(s)为G(s)的前n个比特,G1(s)为G(s)的后n个比特(即G(s)=G0(s)G1(s))对每个和每个,定义函数
()
定义随机函数,其中Un为上的均匀分布随机变量(即s在中按均匀分布随机抽取), 即为所构造的随机函数序列。