- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
64用伪随机序列生成器构造伪随机函数-Read.ppt
第六章 伪随机序列生成器 6.1 计算不可区分性 定义 6.1 一个概率分布族是由 的一个无穷子集I,称为指标集,和每个指标 对应一个概率分布 构成,其中Di为 的一个有穷子集。 定义 6.2 两个随机变量族 和 称为多项式时间不可区分,若对每个多项式时间概率算法M’,每个正多项式p(n)和一切充分大的n有 (6.1) 定义 6.3 两个随机变量序列 和 的变差距离定义为 (6.3) 定义 6.4 称一个随机变量序列 是伪随机的,若它与 上的均匀分布随机变量序列是多项式时间不可区分的,其中设Xn取值于 集。 6.2 伪随机序列生成器的定义和性质 定义 6.5 一个伪随机序列生成器是一个确定性多项式时间算法G满足下列两个条件: 1)延伸性,存在一个正整数函数 使得对一切 有 ; 2)伪随机性,随机变量序列 是伪随机的,即它与均匀分布随机变量序列 是多项式时间不可区分的。 生成器G的输入x称为它的种子,要求将长n比特的种子延伸为长l(n)比特的序列,且该序列与长l(n)的随机比特序列是多项式时间不可区分的。l(n)n称为的延伸因子。 伪随机序列生成器的性质 (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也是确定性的多项式时间算法。 (3)不可预测性。 定义 6.6 随机变量序列 称为多项式时间不可预测的若对每个多项式时间概率算法M’,每个正多项式p(n)和一切充分大的n有 (6.4) 定理 6.3 一个随机变量序列 是伪随机的(参看定义6.4)当且仅当它是多项式时间不可预测的。 (4)单向函数性。 定理 6.4 设G为一延伸因子l(n)的伪随机序列生成器,若对每对 满足 ,定义函数 ,则f为一强单向函数。 6.3 伪随机序列生成器的构造 6.3.1 用一般单向置换构造伪随机序列生成器 定理 6.5 设 为一1-1保长强单向函数, 为函数f的硬核谓词(多项式时间可计算)。定义 (b(x)和f(x)的连接),则G为一伪随机序列生成器。 6.3.2 用单向置换族构造伪随机序列生成器 定理 6.6 设多项式时间概率算法A,D,F定义一单向置换族 , 为该单向置换族的硬核谓词族,q(n)及 ,G如构造方法6.2中所给。再设对每个 ,D(i)为在Di上均匀分布的随机变量,则G为一伪随机序列生成器,它将2q(n)长的种子(r,s)延伸为p(n)长的伪随机序列。 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所定义。 定义 6.9 一个随机函数序列 称为伪随机函数序列若对每个多项式时间神概率图灵机M,每个正多项式
文档评论(0)