Let $\omega$ denote the set of non-negative integers. For $n\in\omega\setminus\{0\} $ define the rotation function $$\text{rot}_n:\{0,1\}^n \to \{0,1\}^n$$ by $x \mapsto x'$ where

  • $x'_k = x_{k+1}$ for $k\in\{0,\ldots, n-2\}$, and
  • $x_{n-1} = x_0$.

Let $\bar{0}_n \in \{0,1\}^n$ be the constant $0$-sequence of length $n$. Fix $s_0\in \{0,1\}^n$ and define a function $f_{n,s_0} : \omega\to \{0,1\}^n$ inductively by setting

  • $f_{n,s_0}(0) = \bar{0}_n$, and
  • $f_{n,s_0}(k+1) = f_{n,s_0}(k) \;\oplus \; \text{rot}_n(f_{n,s_0}(k)) \; \oplus \; s_0$.

(By $\oplus$ we denote componentwise addition in $\mathbb{Z}/2\mathbb{Z}$, or equivalently, bitwise XOR.)

Question. For what values of $n\in\omega\setminus\{0\}$ is there $s_0\in \{0,1\}^n$ such that the image of the function $f_{n,s_0} : \omega\to \{0,1\}^n$ is all of $\{0,1\}^n$ (i.e. $f_{n,s_0} : \omega\to \{0,1\}^n$ is surjective)?

  • 3
    $\begingroup$ What does this have to do with cryptography? The above generator is obviously not cryptographically secure. BTW: the standard notation for the set of nonnegative integers is $\mathbb{N}$ $\endgroup$
    – poncho
    Apr 2 at 16:41
  • 1
    $\begingroup$ @poncho: It seems that there is no canonical/universal notation for the set of non-negative integers. Regarding the usage of $\omega$, see, for example, this comment on Mathoverflow. $\endgroup$ Apr 3 at 4:27
  • $\begingroup$ Why is LFSR cryptographically secure, but not the above procedure? But maybe it's better to ask the question on mathoverflow $\endgroup$ Apr 3 at 7:49

I think only for $n=1$.

The map $x\mapsto x\oplus\mathrm{rot}(x)\oplus s_0$ is 2-to-1 since $x$ and $x\oplus 1111\ldots 1$ both map to the same value. It follows that half of the values of $\{0,1\}^n$ do not lie in the image of this map. We can capture at most one missing value with our start point $0$, but the remaining $2^{n-1}-1$ points will never occur in the image.

  • $\begingroup$ Thanks for the beautiful observation that $x$ and $x + 111\ldots111$ map to the same value! $\endgroup$ Apr 3 at 17:18

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.