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 Nov 11 '14 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 Nov 12 '14 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 Nov 12 '14 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 Nov 12 '14 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.