偽隨機序列生成器.ppt

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