0
$\begingroup$

Using the format of the "game" to establish if a cipher is IND-CPA secure:

  1. The adversary submits two distinct $M_0$, $M_1$ plain-texts to the challenger.
  2. The challenger selects one of them at random and encrypts it with the symmetric key and gives cipher-text C.
  3. 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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ As always with ciphers it depends on the details. A feistel-cipher can very well be IND-CCA2 (see Twofish for example), but it can also be horribly broken if the round function is crap. $\endgroup$
    – SEJPM
    Sep 19, 2016 at 13:45

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Very elegant! But how do you prove that "Feistel structures can implement any even permutation" ? Is there any constructive proof that shows how to design a Feistel structure that implements any given even permutation? $\endgroup$
    – Kris
    Sep 19, 2016 at 20:38
  • $\begingroup$ @Kristian: I think the proof can be by examination for a $2\times2$-bit Feistel cipher (checking that the $16!/2$ even permutations are reached); then induction from a $2\times n$-bit to a $2\times(n+1)$-bit Feistel cipher. The details are slightly messy. $\endgroup$
    – fgrieu ♦
    Sep 21, 2016 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.