A self-shrinking generator is a LFSR sequence processed with an algorithm that is different from von Neumann unbiasing. Does this imply that using von Neumann unbiasing instead would lead to an inferior result of security?


[This incomplete answer is a community wiki; fell free to expand/correct it]

The self-shrinking generator, and von Neumann de-biasing applied to the output of an LFSR, both group bits output by the LFSR in pairs, and for each pair output either nothing or a single bit, according to this table:

Pair    SSG    VN
 00      -     -
 01      -     0
 10      0     1
 11      1     -

We hereafter assume the LFSR has $n$ bits and is maximum-length (that is, uses a primitive polynomial and is not initialized to all-zero).

The LFSR has period $2^n-1$, and within that each of the pairs 01, 10, and 11 appears exactly $2^{n-2}$ times, while the pair 00 appears $2^{n-2}-1$ times. If follows that in $2^{n+1}-2$ steps of the LFSR, both the SSG and VN output exactly $2^{n-2}$ times 0 and as many times 1, and cycle.

Thus both the SSG and VN cycle after (at most) $2^{n-1}$ outputs, and have no bias. For $n>3$, the shortest period conjecturally is $2^{n-1}$ (that conjecture was made for the SSG by Willi Meier and Othmar Staffelbach's The self-shrinking generator, in proceedings of Eurocrypt 1994; they give proof that the shortest period is at least $2^{\left\lfloor n/2\right\rfloor}$).

Illustration with 2 periods of 31 steps of the LFSR based on $x^5+x^2+1$: both SSG and VN have period 16, with 8 zeroes and 8 ones.

LFSR 10101110110001111100110100100001010111011000111110011010010000
SSG   0 0 1 0 1     1 1   1     0         1   0   1 1 0   0 0
VN    1 1   1     0         0   1   0 0 0   0 1       1 0 1 1 0
  • $\begingroup$ I doubt that "Both ..... no bias". My view point is IMHO trivial: If von Neumann is right, then sequences that have lots of 00 and 11 are biased in general. $\endgroup$ – Mok-Kong Shen Jun 10 '17 at 12:13
  • $\begingroup$ @Mok-KongShen: I now prove no bias; that does depend on the hypothesis that the source is a maximal-length LFSR. Indeed, for some other sources, von Neumann debiasing is superior to self-shrinking. $\endgroup$ – fgrieu Jun 11 '17 at 11:44

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.