4
$\begingroup$

There was this one time I came up with a small permutation that had a block size of 16 bits. This was small enough to compute every mapping. I then iterated the mapping starting with zero to see how many iterations it would take to return to zero. The number was less than half of $2^{16}$.

For whatever reason, let's say a person needs a pseudorandom permutation that has only one cycle. Perhaps they need to make a single-cycle S-box or they want to use the permutation to create a non-linear tweak to the plaintext input of a block cipher (each block's tweak is the result of successive iterations instead of increments of one). First thing that comes to my mind is a full-period LCG, but when I tried this for making an S-box ($f(x) = (37 \cdot x + 11) \mbox{ mod } 256$), the results seemed rather orderly. This wouldn't matter for a tweak for plaintext blocks, but it seems desirable to simply not have that property of orderliness. So, what are some way of generating/constructing single-cycle permutations?

$\endgroup$
5
$\begingroup$

The obvious way to construct such a pseudorandom single-cycle permutation is to take a pseudorandom permutation $P$ (which need not be single-cycle), a simple fixed single-cycle permutation $Inc$ (e.g. just increment the value by 1), and construct:

$$S = P^{-1} \ \circ Inc \ \circ P $$

That is, to evaluate $S(x)$, you first apply the permutation $P$ to $x$, then the permutation $Inc$, and then the permutation $P^{-1}$, which is the inverse of the permutation $P$.

Things that should be obvious:

  • $S$ is a single cycle permutation

  • Every single cycle permutation can be expressed this way with an appropriate choice of $P$

  • (Less obvious) if $P$ is selected uniformly over all permutations, then $S$ is selected uniformly over all single-cycle permutations.

$\endgroup$
  • $\begingroup$ $(f\circ g)(x)$ usually means $f(g(x))$, i.e., $g$ is applied first. ;) $\endgroup$ – fkraiem Sep 25 '17 at 13:01
  • $\begingroup$ @fkraiem: ordering really doesn't matter here, but ok, I fixed it... $\endgroup$ – poncho Sep 25 '17 at 13:02
  • 1
    $\begingroup$ Reference. $\endgroup$ – Occams_Trimmer Sep 25 '17 at 14:15
1
$\begingroup$

If you want to build a single cycle s box and want to construct it by drawing a uniformly random single cycle permutation this can be done directly:

  1. Create a set P of numbers 2..N

  2. Set Idx=1

  3. Draw a random member M from P assign it to the index Idx

  4. Remove the member from P

  5. Set Idx=M

  6. If P is nonempty repeat from step 3.

  7. Assign 1 to the last spot at Idx.

You can represent P with an Array and a size counter, in order to remove an element you copy the last element to it's position and reduce size. This allows all steps to be $O(1)$ and the total runtime $O(n)$

If you want a large single cycle permutation (too big to keep materialized in full) poncho gave a fair solution which relies on a pseudo random permutation.

$\endgroup$

Your Answer

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

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