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$?
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.