A ring-like cascade connection and a class of NFSRs with the same cycle structures

Abstract

Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher designs. In this paper, we propose a variant of cascade connections of NFSRs, called ring-like cascade connections. It is shown that given an initial state of a ring-like cascade connection, each register outputs the sequence of the same period. Based on this configuration, a class of NFSRs with the same cycle structure can be derived. Moreover, inspired by this result, two more general types of NFSRs with the same cycle structures are also studied.

Appendices

Appendix

The proof for Lemma 3

Lemma 3

Let h be a Boolean function and $\underline{a}$ an ultimately periodic sequence. Then $\underline{b}=h\underline{a}$ is also ultimately periodic with $\mathrm {per}(\underline{b})\mid \mathrm {per}(\underline{a})$ and $k_2\le k_1$, where $k_1$ and $k_2$ denote the preperiods of $\underline{a}$ and $\underline{b}$, respectively.

Proof

Let $\underline{a}'=L^{k_1}\underline{a}$ and $\underline{b}'=L^{k_1}\underline{b}$. It is clear that $\underline{a}'$ is periodic, and

$$\begin{aligned}\mathrm {per}(\underline{a}')=\mathrm {per}(\underline{a}), \mathrm {per}(\underline{b}')=\mathrm {per}(\underline{b}).\end{aligned}$$

Since $\underline{b}'=h\underline{a}'$, it follows from

$$\begin{aligned}L^{\mathrm {per}(\underline{a}')}\underline{b}'=h(L^{\mathrm {per}(\underline{a}')}\underline{a}')=h\underline{a}'\end{aligned}$$

that

$$\begin{aligned}L^{\mathrm {per}(\underline{a}')}\underline{b}'=\underline{b}',\end{aligned}$$

which implies $\underline{b}'$ is periodic, and $\mathrm {per}(\underline{b}')\mid \mathrm {per}(\underline{a}')$, i.e.,

$$\begin{aligned}\mathrm {per}(\underline{b})\mid \mathrm {per}(\underline{a}).\end{aligned}$$

Moreover, since $\underline{b}'=L^{k_1}\underline{b}$ is periodic, it is clear from the definition of preperiod that $k_2\le k_1$. $\square$