Let $S$ denote a keyless permutation that operates on $4$-bit inputs and returns $4$-bit outputs (that is, $S$ is a $4$-bit S-Box).

In this question, $x_0$ denotes an arbitrary bitstring that ends with 0000 (four zero bits) such that the length $L$ of $x_0$ is a multiple of $4$ and there is no upper bound for $L$. Then $x_0 + i$ denotes a bitstring that represents the sum of $x_0$ and $i$, assuming that $x_0$ is interpreted as a single natural number and all ($L - 4$) leading bits of $x_0$ are not affected. For example,

000001010000 + 1 =  000001010001,
000001010000 + 14 = 000001011110,
000001010000 + 15 = 000001011111

Does there exist an efficient iterative construction $F(x)$ based on $S$ so that the length of $F(x)$ is $4$ and a tuple $$\{F(x_0), F(x_0 + 1), \ldots, F(x_0 + 14), F(x_0 + 15)\}$$ is a sequence of $16$ different $4$-bit elements for any $x_0$ (that is, each $x_0$ generates a permutation of $4$-bit values), and all of the $2^4! = 20922789888000$ possible permutations are equiprobable if $x_0$ is a sequence of random bits followed by four zero bits (assuming that the length of $x_0$ is $4n$, where $n$ is an arbitrarily large natural number greater than $1$)? If it is not possible for all permutations to be absolutely equiprobable in the mathematical sense, then at least the distribution of permutations must be as uniform as possible and look “pseudo-random”.

  • $\begingroup$ You mean tupple where there is "set", since sets are not ordered. For fixed length $l$ of $x_0$, there are $2^{l-4}$ possible $x_0$, that's not divisible by $2^4!$, thus distribution is not exactly equiprobable. Same for fixed maximum length $l$ of $x_0$ since $(2^l-1)/15$ is not divisible by $2^4!$. Thus the "equiprobable " requirement can only be met for some unnatural finite distribution of $x_0$, or asymptotically for some missing definition of the distribution of (at least: the length) of $x_0$. Also, I fear that the procedure will require unbounded memory. $\endgroup$
    – fgrieu
    Commented Jan 27, 2020 at 8:59
  • $\begingroup$ @fgrieu: The term "equiprobable" in this situation implies that if one does not know the length of the next $x_0$ beforehand, then it is not possible to predict anything about the next sixteen values in the tuple $\{F(x_0), \ldots, F(x_0 + 15)\}$. $\endgroup$ Commented Jan 27, 2020 at 9:22
  • $\begingroup$ Even if we define that all $2^{l-4}$ values of $x_0$ of a certain length $l$ are equiprobable, "does not know the length of the next $x_0$" does not define a distribution of $x_0$. Even if we stick to the natural $P(l=m)/P(l=m+4)=k$ with $k>1$ and independent of $m$, different $k$ define different distributions for $x_0$, thus different definitions of "equiprobable". There's the same problem with integers: we can't just define a random arbitrarily large integer; that's under-specified. $\endgroup$
    – fgrieu
    Commented Jan 27, 2020 at 9:46
  • $\begingroup$ @fgrieu: > "different $k$ define different distributions for $x_0$" — yes, but all I want is that these different distributions look "pseudo-random enough" and "independent" of each other. $\endgroup$ Commented Jan 27, 2020 at 9:54

1 Answer 1


In Haskell the recursive function

f s x = s (g 16 (x `div` 16) (x `mod` 16))
  where g 1 _ = id
        g n x = t (n-1) (x `mod` n) . g (n-1) (x `div` n)
        t x y z = if x == z then y
                            else if y == z then x else z

runs for any function s that is a permutation on [0..15] through all permutations on [0..15] if you let x run through all numbers 0...20922789888000*16-1.

Of course, s doesn't matter much, so I'd set s = id, and look at the definition of g using t: t x y is simply exchanging the values x and y, keeping all other values the same.

Now g n x is a(n arbitrary!) permutation on [0..n-1] depending on x: x mod n determines which element to exchange with n-1 (all other elements are untouched) and x divided by n is used as parameter to for defining recursively g (n-1).

If you pick n uniformly from 0..20922789887999, the permutation g n will be a uniform random element of the symmetric group on [0..15].

  • $\begingroup$ This algorithm is not iterative. An iterative construction (in the cryptographic sense) implies that the input is processed one block at a time. In this case, the length of one block is 4 bits and the processing function is the 4-bit S-Box. Examples of iterative constructions include a sponge function, Pearson hash etc. And furthermore, $x$ is an arbitrary bitstring. It cannot be bounded by a fixed number. $\endgroup$ Commented Jan 29, 2020 at 4:52
  • $\begingroup$ For example, interpreting $x$ as a single natural number and performing the modulo operation on $x$ (when the divisor is not a power of two) very significantly reduces the efficiency of the algorithm. $\endgroup$ Commented Jan 31, 2020 at 6:02

Your Answer

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

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