0
$\begingroup$

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”.

$\endgroup$
4
  • $\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 Jan 27 '20 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$ – lyrically wicked Jan 27 '20 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 Jan 27 '20 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$ – lyrically wicked Jan 27 '20 at 9:54
1
$\begingroup$

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].

$\endgroup$
2
  • $\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$ – lyrically wicked Jan 29 '20 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$ – lyrically wicked Jan 31 '20 at 6:02

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.