Is a Feistel structure based cipher IND-CPA? Using the format of the "game" to establish if a cipher is IND-CPA secure:


The adversary submits two distinct $M_0$, $M_1$ plain-texts to the challenger.
The challenger selects one of them at random and encrypts it with the symmetric key and gives cipher-text C.
The adversary has to guess which message was encrypted based on C with a probability greater than 1/2 for the cipher-text to be distinguishable.


If the challenger is using an encryption algorithm only based on Feistel structures, would it be possible to always correctly identify, which of the messages the challenger encrypted?
If the challenger is using an encryption algorithm only based on Feistel structures, would it be possible to always correctly identify, which of the messages the challenger encrypted?


No, it will not always be possible to have any such distinguisher, even if we assumed that the attacker had infinite computing resources (!); all we need to assume is that the attacker has a bound on the number queries he is allowed to perform.

We can take advantage of the well-known fact that Feistel structures can implement any even permutation (possibly with a truly huge number of rounds; however the question didn't introduce a bound on the number of rounds); hence it would be possible for a well-chosen set of Feistel structures to produce any even permutation with equal probability.

And, given an attacker that is bounded to no more than $2^N-2$ queries, it is impossible to distinguish a random even permutation from a random permutation.