Cryptography筆記6 - Secure PRG

PRG定義

用機率觀點來看，就是如果某個PRG將seed space map (s bits)到key space (n bits, n >> s)，雖然PRG map出來的 key space是真正所有n-bits key space (欄圈)的極小subset(紅圈)而已:

但是透過uniformly chosen key的話，如果無法分辨兩者的不同的話，則說此generator為一個PRG。

Statistical Test Algorithm

統計演算法就是一個黑箱，用來看我們透過某個PRG candidate產生的bit string是否"looks random"，例如下面兩個檢驗標準:

第一個是看某個n-bit input string x中，0的數目和1的數目的差距要小於某個值
第一個是看某個n-bit input string x中，consecutive 00 出現的次數應該要約等於n/4

類似像這樣的檢驗。

不過注意statistical test不一定正確，所以我們需要一個標準來評斷一個statistical test的好壞。

用Advantage檢驗statistical tests

定義

一個PRG的advantage也是以機率觀點來定義，是兩個項目的差。
第一個項目是 如果從key space中以uniform distribution來選擇一個key k的話，此PRG的test A輸出1的機率。第二項和第一項相同，只是key space是所有bit string，而且是truely random。

當然兩個機率相減的絕對值一定也是在[0,1]區間內，如果Adv靠近1，則代表兩項的test產出1的機率差別很大，亦即PRG不"看似random"，反之則PRG看似random。當然如果Adv靠近1，代表此statitstical test A是很好的檢驗此PRG的方法，稱為"break the PRG"。

舉例來說:

某個generator G 產出的k不是uniformly distributed，而是有2/3的機率會把第一個bit設為1。
如果一個test A定義如上，那試問此generator的advantage?

按照定義Adv第一項為 2/3，第二項為1/2，則advantage  = |2/3 - 1/2| = 1/6
1/6不算是可忽略數字，所以我們稱此test A breaks G with advantage 1/6。

Computationally Indistinguishable

上面advantage的定義可以寫成更通式，如果有兩個bit string來自不同的distribution P1, P2，如果不存在任何efficient statistical test能使來自此兩distribution的generator的advantage小於某個可忽略的值的話，則說P1 ~p P2，意即P1和P2是無法在polynomial time區別出來。

Secure PRG

有了advantage的定義，我們定義secure PRG:

對所有efficient statistical test A來說，Advantage(A, G)如果output是可忽略的，則此PRG是secure!

不過目前尚無符合此定義的PRG。不過符合此定義的PRG一定會有以下的特徵:
unpredictable:這個之前有講過，就是沒有任何predictor可以拿到前i個 bits之後，可以預測出i+1 bits。