# SPI security of FE1 scheme

I have a question about security of FE1(Page 16-18) in paper "format preserving encryption". Can anyone explain me, why we are allowed to replace PRF with random function in security proof? And also, why is game $G_0$ the same as game $SPI_1$ (explained in page 6) and is game $G_1$ the same as game $SPI_0$?

• Write in your question what all that notation means - you can't expect everybody to read the entire paper. – pg1989 Jul 8 '15 at 18:57

## 1 Answer

why we are allowed to replace PRF with random function in security proof?

That's just how security proofs for these kinds of Feistel schemes work - you say something about the cipher when the round function is a truly random function, then you argue that because a PRF is indistinguishable from a random function for a computational adversary, the security proof still holds when your round function is a PRF. I think they use this technique in the original Luby-Rackoff paper, too.

• This is not specific to Feistel. This is true ANYWHERE where pseudorandom functions are used. The security proof has to show that if you can "break" the scheme (according to whatever definition etc.) then you can distinguish the PRF from a truly random function. Then, you show that with a truly random function the scheme IS secure. Combining the above, you have a full proof of security. – Yehuda Lindell Jul 8 '15 at 20:58
• Yes, of course. You and I both know that, but I thought the more generic statement would confuse the OP. – pg1989 Jul 9 '15 at 1:11
• Thank you. I got that point. I want to make my second question more clear. Maybe you could help me. The procedure Test in game $Spi$ returns whether random value or real value regard to the value of b. but in games in security proof, procedure Test always returns random point and instead procedure Enc returns random point or real value. Why can we say that these are equivalent? – user25463 Jul 9 '15 at 6:48
• In addition, in page 6, we see $Adv^{spi}_E(\mathcal{A})= Pr[SPI1 ^\mathcal{A}_E\Rightarrow true] - Pr[SPI0 ^\mathcal{A}_E\Rightarrow FALSE]$. But in security proof in page 16 $Adv^{spi}_{FE1}(\mathcal{A})\le Pr[SPI1 ^\mathcal{A}_{FE1}\Rightarrow true] - Pr[SPI1 ^\mathcal{A}_{FE1}\Rightarrow FALSE]$. why? – user25463 Jul 9 '15 at 6:49