# Self-shrinking generator

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

• 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. – Mok-Kong Shen Jun 10 '17 at 12:13
• @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. – fgrieu Jun 11 '17 at 11:44