偽隨機(jī)序列生成器.ppt

第六章 偽隨機(jī)序列生成器,61 計(jì)算不可區(qū)分性,定義 6.1 一個(gè)概率分布族是由 的一個(gè)無窮子集I，稱為指標(biāo)集，和每個(gè)指標(biāo) 對應(yīng)一個(gè)概率分布 構(gòu)成，其中Di為 的一個(gè)有窮子集。 定義 6.2 兩個(gè)隨機(jī)變量族 和 稱為多項(xiàng)式時(shí)間不可區(qū)分，若對每個(gè)多項(xiàng)式時(shí)間概率算法M，每個(gè)正多項(xiàng)式p(n)和一切充分大的n有 （6.1）,定義 6.3 兩個(gè)隨機(jī)變量序列 和 的變差距離定義為 （6.3） 定義 6.4 稱一個(gè)隨機(jī)變量序列 是偽隨機(jī)的，若它與 上的均勻分布隨機(jī)變量序列是多項(xiàng)式時(shí)間不可區(qū)分的，其中設(shè)Xn取值于 集。,6.2 偽隨機(jī)序列生成器的定義和性質(zhì),定義 6.5 一個(gè)偽隨機(jī)序列生成器是一個(gè)確定性多項(xiàng)式時(shí)間算法G滿足下列兩個(gè)條件： 1)延伸性，存在一個(gè)正整數(shù)函數(shù) 使得對一切 有 ； 2)偽隨機(jī)性，隨機(jī)變量序列 是偽隨機(jī)的，即它與均勻分布隨機(jī)變量序列 是多項(xiàng)式時(shí)間不可區(qū)分的。 生成器G的輸入x稱為它的種子，要求將長n比特的種子延伸為長l(n)比特的序列，且該序列與長l(n)的隨機(jī)比特序列是多項(xiàng)式時(shí)間不可區(qū)分的。l(n)n稱為的延伸因子。,偽隨機(jī)序列生成器的性質(zhì) (1)統(tǒng)計(jì)性質(zhì) 定理 6.1 若是一個(gè)偽隨機(jī)序列生成器，即滿足定義6.5 中的條件，則隨機(jī)變量序列 與 不是統(tǒng)計(jì)接近的。 (2)多項(xiàng)式延伸性 構(gòu)造方法6.1，設(shè)G1為一確定性多項(xiàng)式時(shí)間算法，它將每個(gè)長n比特串延伸為一個(gè)長n+1比特串，p(n)n為任一多項(xiàng)式。我們用G1作p(n)次迭代，即置 為G1的初始輸入，計(jì)算 ，其中 即 為輸入 時(shí)G1輸出的長n+1比特串。定義算法G為 ，它將一個(gè)n長比特串s延伸為一個(gè)p(n)長比特串x。由于G1是確定性多項(xiàng)式時(shí)間算法，故G也是確定性的多項(xiàng)式時(shí)間算法。,(3)不可預(yù)測性。 定義 6.6 隨機(jī)變量序列 稱為多項(xiàng)式時(shí)間不可預(yù)測的若對每個(gè)多項(xiàng)式時(shí)間概率算法M，每個(gè)正多項(xiàng)式p(n)和一切充分大的n有 （6.4） 定理 6.3 一個(gè)隨機(jī)變量序列 是偽隨機(jī)的（參看定義6.4）當(dāng)且僅當(dāng)它是多項(xiàng)式時(shí)間不可預(yù)測的。 (4)單向函數(shù)性。 定理 6.4 設(shè)G為一延伸因子l(n)的偽隨機(jī)序列生成器，若對每對 滿足 ，定義函數(shù) ，則f為一強(qiáng)單向函數(shù)。,63 偽隨機(jī)序列生成器的構(gòu)造,6.3.1 用一般單向置換構(gòu)造偽隨機(jī)序列生成器 定理 6.5 設(shè) 為一11保長強(qiáng)單向函數(shù)， 為函數(shù)f的硬核謂詞（多項(xiàng)式時(shí)間可計(jì)算）。定義 （b(x)和f(x)的連接），則G為一偽隨機(jī)序列生成器。,632 用單向置換族構(gòu)造偽隨機(jī)序列生成器 定理 6.6 設(shè)多項(xiàng)式時(shí)間概率算法A,D,F定義一單向置換族 ， 為該單向置換族的硬核謂詞族，q(n)及 ，G如構(gòu)造方法6.2中所給。再設(shè)對每個(gè) ，D(i)為在Di上均勻分布的隨機(jī)變量，則G為一偽隨機(jī)序列生成器，它將2q(n)長的種子(r,s)延伸為p(n)長的偽隨機(jī)序列。,6.4 用偽隨機(jī)序列生成器構(gòu)造偽隨機(jī)函數(shù),定義 6.7 一個(gè)隨機(jī)函數(shù)序列 是一個(gè)在函數(shù)集 中取值的隨機(jī)變量序列，其概率分布為 ，即 ，特別地，一個(gè)隨機(jī)函數(shù)序列稱為真隨機(jī)函數(shù)序列若其概率分布為 上的均勻分布，即對每個(gè) 有 ，記真隨機(jī)函數(shù)序列為 。 定義 6.8一個(gè)確定性神圖靈機(jī)是一個(gè)確定性圖靈機(jī)（見定義4.4）附加一條磁帶，稱為神帶，和兩個(gè)特殊狀態(tài) ，sinv稱為求神狀態(tài)，sora稱為神現(xiàn)狀態(tài)。當(dāng)一個(gè)神圖靈機(jī)M輸入x，存取函數(shù) 時(shí)，其計(jì)算也是一個(gè)形的有限或無限序列， ，其關(guān)系由讀寫頭所處狀態(tài)的轉(zhuǎn)移函數(shù)和讀寫頭動作的指令函數(shù)確定，若 ，則第j+1個(gè)形如定義4.4所給，若第j個(gè)形中的狀態(tài)sj=sinv，且神帶中的內(nèi)容為 ，則第j+1個(gè)形中的狀態(tài)sj+1=sora，且神帶中的內(nèi)容為f(q)，q稱為M的提問，f(q)稱為神的回答。神圖靈機(jī)的輸出M，記作Mf(x)，以及運(yùn)行（計(jì)算）時(shí)間如定義4.4所定義。,定義 6.9 一個(gè)隨機(jī)函數(shù)序列 稱為偽隨機(jī)函數(shù)序列若對每個(gè)多項(xiàng)式時(shí)間神概率圖靈機(jī)M，每個(gè)正多項(xiàng)式p(n)和一切充分大的n有 （6.5） 構(gòu)造方法6.3 ，設(shè)G為一個(gè)確定性算法，它將n長比特串s延伸為2n長比特串G(s)，定義函數(shù)G0(s)為G(s)的前n個(gè)比特，G1(s)為G(s)的后n個(gè)比特（即G(s)=G0(s)G1(s)）對每個(gè) 和每個(gè) ，定義函數(shù) (6.6) 定義隨機(jī)函數(shù) ，其中Un為 上的均勻分布隨機(jī)變量（即s在 中按均勻分布隨機(jī)抽取）， 即為所構(gòu)造的隨機(jī)函數(shù)序列。,65 偽隨機(jī)置換的構(gòu)造,定義 6.10 一個(gè)隨機(jī)置換序列 是一個(gè)在置換集 中取值的隨機(jī)變量序列，其概率分布為 ，即 ，特別地，一個(gè)隨機(jī)置換序列稱為真隨機(jī)置換序列，若其概率分布為 上的均勻分布，即對每個(gè) 有 ，記真隨機(jī)置換序列為 。 定義 6.11 一個(gè)隨機(jī)置換序列 稱為偽隨機(jī)置換序列，若對每個(gè)多項(xiàng)式時(shí)間神概率圖靈機(jī)M，每個(gè)正多項(xiàng)式p(n)和一切充分大的n有 （6.7）,定理 6.8 設(shè)Fn，t(n)， 如構(gòu)造方法6.4中所給。