The theorem, Luby-Rackoff'85, describes that, 3-round Feistel is a secure PRP if f is a secure PRF. I have many questions,
- Why 3-round?
- Is 2-round a secure PRP?
- Is 1-round a secure PRP?
Now, we use the below picture to check if 1-round Feistel a secure PRP?
We specify
Funcs [M, C] as set of all functions from M to C.
We specify
F as the 1-round Feistel.
F: K x M ---> C,
where
K is a key space,
M = {0,1}^(2n), is a message space,
C = {0,1}^(2n), is a cipher text space.
f1 is a secure PRP
f1: K x {0,1}^n ---> {0,1}^n
After we input a message
m = R || L,
,the output cipher text is
c = L1 || R.
When we check the cipher text and the message, we can say that the cipher text is produced by F because the left block of the cipher text is R that comes from the right block of the message. Therefore F is distinguishable from the Funcs. F is not sure PRP.
OK, Let's use the below picture to check if 2-round Feistel is secure PRP.
We specify
F as the 2-round Feistel.
F: K x M ---> C,
where
K is a key space,
M = {0,1}^(2n), is a message space,
C = {0,1}^(2n), is a cipher text space.
f1 and f2 are secure PRP
the output cipher text are ca, cb.
ma = R || La ---> ca = R2a1 || La1
mb = R || Lb ---> cb = R2b1 || Lb1
We observe that.
La1 = La xor f1(R)
Lb1 = Lb xor f1(R)
La1 xor Lb1 = La xor Lb ---- (formula 1)
When we check the two cipher texts and the two messages with this formula 1, we can say that they are produced by F. Therefore F is distinguishable from the Funcs. F is not sure PRP.
-GY
Could you please upload the pictures again? they are not visible now.
ReplyDelete