Let $E$ be a random even permutation of the set $\{0\dots n-1\}$. We construct a permutation $P$ of the set $\{0\dots m-1\}$, for some $m\le n$, using cycle-walking; that is, computing $P(x)$ is as follows:

  • repeat
    • $x\gets E(x)$
  • until $x<m$
  • output $x$

What is the probability that the parity of $P$ is $n-m\bmod 2$, as a function of $m$ and $n$? How low should be $m$ so that this is withing $\pm\epsilon$ of $1/2$?

The motivation was to decide if cycle-walking is enough to transform a small Feistel Cipher into a pseudo-random permutation of a smaller domain, in the cipher of this question. Poncho rightly pointed out that in a Feistel cipher, using modular addition rather than XOR also achieves this goal.

I observe that when $n-m\ll\sqrt n$, probability that $P$ has parity $n-m\bmod 2$ is high, because for most $E$, there are $2m-n$ values of $x<m$ such that the repeat loop is executed once, and $n-m$ values such that the repeat loop is executed twice.

  • 2
    $\begingroup$ The standard trick for small block Feistel ciphers is to use modular addition, rather than xor, in each round; that way, the round, and hence the permutation, has a 0.5 probability of being odd. $\endgroup$
    – poncho
    Commented Nov 11, 2014 at 23:32
  • $\begingroup$ @poncho: I think you mean addition of a key as wide as the state, which does give balanced parity. Replacing XOR with modular addition in the combination of the round function output and half state does not. $\endgroup$
    – fgrieu
    Commented Nov 12, 2014 at 6:44
  • 1
    $\begingroup$ On the contrary, if the two halves of the Feistel state are $a, b$, then the update 'a += F(k, b)' can be odd; in fact, it will be if an odd number of the $F(k, b)$ values are odd (fixed $k$, over all possible values of $b$). $\endgroup$
    – poncho
    Commented Nov 12, 2014 at 13:34
  • $\begingroup$ @poncho: You are absolutely right! I misinterpreted the argument given in that answer into the (incorrect): any reversible transformation leaving at least 1 bit of the state unchanged is even. What's correct is: any transformation leaving at least 1 bit of the state unchanged and without influence on the other bits is even. $\endgroup$
    – fgrieu
    Commented Nov 12, 2014 at 14:22


Your Answer

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

Browse other questions tagged or ask your own question.