Cryptography筆記13- 複習一下什麼是PRF和PRP

PRF (pseudo random function)

PRF F(k,x) 是一個function，接受兩個參數k:Key和x:X，map到某一個domain Y，
定義只包含"efficient algorithm"，所以如果不是efficient F，則不能說是一個PRF。

PRF存在的目的就是讓人們分不清一個prf function與truely random function的差別，所以一個PRF看起來要是真的隨機function。

Secure PRF

定義所有從X->Y的functions為set Funs[X,Y]，Funs[X,Y]的size是這樣:
Y中有|Y|個elements，每個element y都可能是某個element x map過來的，所以有|X|種可能，所以X->Y 有 |Y|^|X|種可能的mappinsg

另外定義S_F為某個PRF F(k, x) 形成的set，是Funs[X,Y]的subset，其中k為fixed key，S_F的size是這樣: 事實上，我不理解size會是|K|? 



則我們定義此PRF F是secure如果S_F中隨機挑選出的function無法與Funs[X,Y]中隨機挑選出的function區分 (用advantage) 的話，可以看到advesary A一直送出xi丟進去某個黑箱f，f由challenger決定是一個radom selection from S_F還是一個random selection from Funs[X,Y]，

PRP (pseudo random permutation, Block cipher)

PRP也是一個function，定義域和PRF一樣，但是output domain要跟其中一個input domain X一樣:

定義要求:
1. efficient deterministic Encryptor E(k,x)，如果不是deterministic根本就無法decrypt
2. E(k, _)要一對一，要不然也無法decrypt，意即固定一個key k，只能有unique output
3. decryptor D(k,x) 是 E 的 efficient inversion

Secure PRP

類似secure PRF，adversary可以一直丟xi query給f黑箱，f可能是secure PRP set中的random selection，或是一個1-to-1 且 invertible的permutation function (from X -> X) Perms[X] set中的random selection:















一樣用advantage來判定是否negligible。

Secure PRP範例

舉例來說，input X domain = {0,1}，我們可以簡單知道Perms[X]只有兩種可能的functions:
f(0) = 0
f(1) = 1
------
f(0) = 1
f(1) = 0

如果有一個PRP定義為 E(k,x) = x XOR k，且K = X = {0,1}，則此PRP是否為一個secure PRP?

其實把truth table列出來就可以知道 x XOR k 跟 Perms[X]中兩個functions的distribution一模一樣:
E(0,0) = 0
E(0,1) = 1
------
E(1,0) = 1
E(1,1) = 0

所以這是一個secure PRP。

從secure PRP探討是否為secure PRF?

上例中，secure PRP 定義為 E(k,x) = x XOR k，且K = X = {0,1}，但這是否為一個secure PRF?

這邊Funs[X,X]其實有四種可能:
f(0)=0
f(1)=1
---
f(0) = 1
f(1) = 0
---
f(0)=0
f(1)=0
----
f(0)=1
f(1)=1

但對Funs[X,X]來說，如果隨機選擇f出來，且同時檢驗f(0) f(1)的話，有1/2的機率可以得出f(0) = f(1)的結果，但是對secure PRP來說同時檢驗f(0) f(1)永遠是不一樣的結果。statistical test 可以定義成:

所以答案不是一個secure PRF。

不過如果 |X|夠大，例如AES 128，則secure PRP是一個secure PRF，已經證明出了lemma
。