6
$\begingroup$

Linear feedback shift registers (LFSR's) work by taking a fixed-length bit-string $b\in\{0,1\}^n$, as well as fixed "taps" (bit positions) and applying XOR to the taps, giving one output bit, which is appended at the $b$ after shifting it.

Now XOR is a linear function. A natural non-linear function that can be used on the fixed set of taps is a kind of "majority vote", which works as follows: if the majority of the taps is $0$, then we output $1$, and vice versa. (For this, it is best to have an odd number of taps.)

A simple implementation of a majority-based feedback shift register can be found here.

Of course, applying this "majority vote" procedure over and over again, this eventually gets periodical.

Question. Given fixed bit-length $n$, what is a lower bound of the maximal length of a period that can be achieved choosing a suitable start string $b\in \{0,1\}^n$ and a suitable set of taps?

Also, I wasn't able to find out if and where this concept has been studied.

$\endgroup$
4
  • 2
    $\begingroup$ While not an answer to your question, ancient CDC mainframes had a "Population Count" instruction, CXi Xk, which would output the number of 1 bits set in register Xk to register Xi. AKA "popcount" or "the NSA instruction", the original primary practical use for this operator was theorized to be cryptanalysis, suggesting this may have been studied or known in the 1960s and 70s. See vaibhavsagar.com/blog/2019/09/08/popcount/…. for more info. $\endgroup$ Mar 23, 2022 at 16:53
  • $\begingroup$ That's really interesting - thanks @JohnDeters for this comment! Also I use a function in my implementation on GitHub that is actually called popcount(). Maybe using the popcount that is built into the CPU would be much faster $\endgroup$ Mar 23, 2022 at 18:55
  • 3
    $\begingroup$ x86 has a popcount instruction too felixcloutier.com/x86/popcnt $\endgroup$
    – qwr
    Mar 23, 2022 at 19:54
  • $\begingroup$ btw, in actual hardware, majority circuits take up a lot of space. The simplicity that you see in C is non-existent gate level. $\endgroup$
    – b degnan
    Mar 30, 2022 at 1:44

3 Answers 3

2
$\begingroup$

I'm reading the question as asking for $b(n)$, the largest possible, such that we can exhibit distinct tap points (in odd number), and $n$-bit state, leading to a periodic sequence of (shortest) period at least $b(n)$ steps.

I have a construction with $b(n)=2n-2$ for $n\ge3$. The taps are the next three bits that will drop out of the MVFSR. The state is all-zeroes, except for the next bit that will drop out of the MVFSR. Here is an illustration with $n=8$: time elapses from left to right, the MVSFR shifts down, the next bit enters on top, the three taps are marked with *.

   0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0
   0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
   0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
   0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0
   0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
*  0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0
*  0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
*  1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1

If we allow a single tap, we get to $b(n)=2n$.

I hope that $b(n)$ can be improved (increased), perhaps to become exponential, but it's already more than $1$ of this answer, and $2$ of this comment.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your answer -> it would be awesome to see $b(n)$ increased to become exponential even with a small number of taps cleverly placed, maybe only $3$ taps? $\endgroup$ Mar 24, 2022 at 2:23
2
$\begingroup$

I would hesitate to claim a better lower bound than 1.

We note that for a majority vote feedback shift register (hereafter MVFSR) if there are $2k+1$ taps and if at any point the fill of the register has at most $k$ zeros (respectively at most $k$ ones) then the register will subsequently fill up with ones (respectively with zeros) and hit a cycle of 1.

Likewise, one feels that there is a lot of substantialism in that MVFSR with sparse fills with lots of zeros are likely to produce zero feedbacks and dense fills with lots of ones are likely to produce one feedbacks. Heuristically this would drive the fill density away from 1/2 and towards the above degeneracy.

It's possible to produce MVFSRs with taps set in arithmetic progression that degenerate into interleavings of smaller registers and so which hit stable cycles of length equal to the number of smaller registers, but this does not feel like a good idea.

One can also note that the map from fill-to-fill for an MVFSR has many two-to-one maps which places a poor upper bound on the final cycle length. In general fills where $k+1$ of the first $2k$ taps are zero or one (i.e. where there are not exactly $k$ zeros and $k$ ones in the first $2k$ tap positions) are fills where the oldest tap bit is irrelevant to the feedback and so we create a two-to-one.

$\endgroup$
2
  • $\begingroup$ Actually, the next bit that is cycled in is the inverse of the majority of the taps - hence, I don't believe a cycle length of 1 is possible (as a string of identical shifted in bits will eventually become the majority and so shift in the opposite bit). Of course, a cycle length of 2 is quite possible, unless care was taken with tap placement... $\endgroup$
    – poncho
    Mar 23, 2022 at 21:21
  • $\begingroup$ Right - and sorry if the question was maybe a bit misleading... I wanted to ask how long a period one could achieve by cleverly place the taps and the starting value of $b$ $\endgroup$ Mar 24, 2022 at 2:21
2
$\begingroup$

I've written some code to just brute force tap configurations and starting values for small register sizes. So I have some values, rather than an analytic result. Of course the results are conditional on there not being any bugs in the code (https://github.com/bmm6o/MVFSR).

for width 4, max cycle length is 8
for width 5, max cycle length is 10
for width 6, max cycle length is 12
for width 7, max cycle length is 14
for width 8, max cycle length is 48
for width 9, max cycle length is 48
for width 10, max cycle length is 80
for width 11, max cycle length is 108
for width 12, max cycle length is 140
for width 13, max cycle length is 270
for width 14, max cycle length is 270
for width 15, max cycle length is 270
for width 16, max cycle length is 480
for width 17, max cycle length is 752
for width 18, max cycle length is 1520

It can be risky to generalize from small values, but it does to seem to approximately double when the width increases by 2. This sequence is not present in the OEIS.

You've probably realized this, but your MVFSR evolves in a way such that most states have exactly 2 pre-images. I'm not sure how to use that to make a probabilistic estimate of the cycle length distribution, but it seems like it would be helpful.

For most cryptographic purposes, putting a lower bound on the maximum cycle length is not the most important question. Much more important is the minimum length, or at least a way to characterize and avoid short cycles. In that way, there is a serious problem with MVFSR. Under optimal tap selection, there are cycles of length just $2n$.

$\endgroup$
6
  • $\begingroup$ you say you want to bound minimum cyclelength but your output says "max cycle length" $\endgroup$
    – kodlu
    Mar 26, 2022 at 16:47
  • 1
    $\begingroup$ Correct. I'm not sure OP is asking the right question, but so far I'm answering the one that was asked. I do plan to get the other answers too. $\endgroup$
    – bmm6o
    Mar 26, 2022 at 21:08
  • 1
    $\begingroup$ I did a completely independent search for max cycle length (I haven't even looked at your code), and came with the same results - your code appears to be correct $\endgroup$
    – poncho
    Mar 29, 2022 at 15:26
  • $\begingroup$ Thanks, @poncho. I guess I'm just really surprised that it's not monotonic. $\endgroup$
    – bmm6o
    Mar 29, 2022 at 15:48
  • $\begingroup$ Not that hugely surprising; there are simpler things (such as 'what is the maximum order of a permutation over k objects') that is also not strictly monotonic... $\endgroup$
    – poncho
    Mar 29, 2022 at 18:06

Your Answer

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

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