betaFeedback

WorksComputer Science

Equivalent Non-linear Shift Register Transformations and Espresso

Abstract

The stream cipher Espresso was designed by E. Dubrova and M. Hell as a hardware-efficient candidate for 5G security. It has two components - a 256-bit binary non-linear feedback shift register (NFSR), with 14 feedback taps, and a 20-variable non-linear output function. However, the security of Espresso with regard to several standard cryptanalytic attacks are estimated using an alternate NFSR, which has only two feedback taps. The above analysis is based on the claim that this alternate NFSR is obtained using a transformation algorithm which preserves the output sequence of the original NFSR. This issue has become all the more significant in the light of recent results on hardware performance evaluations, which assume that the stated equivalence holds. This article presents the first successful attempt in settling the above question of Espresso NFSR equivalence. We arrive at our main result by a careful analysis of existing transformation methods relevant to the question. In doing so, we first identify and correct a critical flaw in the proof of a foundational result of E. Dubrova. Next, in the context of Espresso equivalence, we analyze and unify the transformation framework of Dubrova and the one proposed by Yao and Parampalli. Based on our analysis, we have succeeded in transforming the LFSR in an Espresso-equivalent design reported by Yao and Parampalli to the Espresso alternate NFSR. Further, we have obtained a corresponding non-linear output function which achieves output-equivalence with the LFSR design, and hence, with Espresso.

Introduction

Linear and non-linear feedback shift registers (LFSRs and NFSRs/NLFSRs) are key design components of several families of stream ciphers. The properties of LFSRs have been well-studied since the seminal work of S. Golomb [9], and a recent work [1] rigorously showcases both new analyses/construction and a survey of key contributions pertaining to LFSR-based designs. In comparison, the analysis of NFSRs is still a work in progress. But recent advances indicate that it may be possible to provide the same level of cryptographic security as LFSR-based designs using NFSRs but with a noticeably reduced hardware footprint. Efforts in this direction have resulted in the design of NFSR-based stream ciphers like LIZARD [10], TRIVIUM [2], Grain [11] and, more recently, Espresso [7]. However, providing security guarantees for NFSR-based stream ciphers is more of a challenge than LFSR-based designs owing to the comparative difficulty in NFSR analysis. A possible way out may be to formulate an equivalent design involving an LFSR, or a simpler NFSR, whose analysis is more tractable.

Another aspect of significance in the design of shift-register based stream ciphers is the choice between Galois and Fibonacci configurations of shift registers. In a Fibonacci NFSR there is only a single feedback update function from the intermediate stages to the terminal stage, all the other stages accept a single input from just the preceding stage. Hence, the Fibonacci configuration is a restricted case of the general Galois configuration, which potentially allows feedback between any pair of stages in the shift register. In [12], it is claimed that a stream cipher based on a Galois-configuration shift register can achieve higher clock frequency on application-specific integrated circuit (ASIC). Again, the security analysis of a stream cipher using the Fibonacci configuration is comparatively easier and well-studied in literature.

The stream cipher Espresso was proposed by E. Dubrova and M. Hell [7] as a hardware-efficient candidate for providing security in 5G communication. This cipher offers an excellent case study for the aforementioned competing design choices - Galois vs. Fibonacci and LFSR vs. NFSR. As a contender for 5G security, Espresso claims better performance than Grain-128 and Trivium in the under-1500 Gate Equivalence (GE) chip-size regime with the stated parameters: 1497 GE area, 2.22 Gbits/sec throughput and 232 nanosecond latency.

Espresso is based on a 256-bit Galois NFSR, having 14 non-linear feedback update functions at different stages, and a non-linear output function, involving the outputs of 20 different stages. However, the security of Espresso against standard cryptanalysis strategies like linear approximation attacks and TMDTO attacks is actually discussed in [7] with respect to an “equivalent” NFSR (cf. p. 277 of [7]), having only two non-linear update functions. Hence, Espresso is clearly an instance of the “analysis-on-equivalent-design” strategy mentioned earlier.

The motivation for the present work arose from an examination of the claimed equivalence of the two NFSRs presented in the Espresso proposal paper in the context of cryptanalysis of Espresso. An immediate issue had already been reported in [16]: no “equivalent” non-linear output function is provided in [7] corresponding to the alternative Galois NFSR. This precludes any comparison between the actual keystreams generated by Espresso and an “equivalent” cipher based on the alternative NFSR. Further unsubstantiated claims made in [7] in this context were reported in [8].

A series of papers by Yao and Parampalli ([16], [15], [17]) culminated in defining the so-termed ‘compensation method’ for transformations of several types of Fibonacci and Galois NFSRs. Their method applied to Espresso is claimed to yield (cf. [16], Section 6.1):

“... a Fibonacci LFSR with a nonlinear output function. Specifically, the output function consists of 2289 monomials. There are 104 variables in the output function and the algebraic degree is 12.”

But the question of whether or not the two NFSRs presented in [7] are actually equivalent was still not resolved. Notwithstanding the existence of this gap, some recent works have already attempted improved implementation of Espresso configurations (e.g. [14]), assuming the validity of the equivalence as claimed in [7].

In this article, we expand on the results reported in [8] and attempt to conclude a proposed resolution to the Espresso equivalence problem reported therein. We begin with a careful analysis of a sequence of transformation techniques which are outlined in E. Dubrova’s works [3], [4],[6], and those of G. Yao and U. Parampalli [16], [17]) in the context of the equivalence problem. We then proceed to define a unified framework of the Dubrova and Yao-Parampalli algorithms, the Dubrova-Yao-Parampalli (D-Y-P) framework, to gain new insights as to the claimed equivalence. Finally, we present experimental results and theoretical analysis to achieve this claimed equivalence using the D-Y-P framework. Specifically, our contributions, collated with those reported in [8], are as follows.

  1. We identify a critical mis-step in the proof of the foundational theorem of Dubrova’s first algorithm (cf. Theorem 1 of [3], Section IV) and provide a correct proof (§ 4).

  2. We show that Dubrova’s first algorithm [3], is essentially subsumed into the framework of the second algorithm [6] (cf. [8]) (Subsection 4.1).

  3. We establish that the Yao-Parampalli algorithm ([16], [17]) is equivalent to Dubrova’s second algorithm in the case of Fibonacci-to-uniform Galois NFSR transformation (cf. [8]) for computing the feedback functions and matching initial states (Subsection 4).

  4. Using the D-Y-P framework, we obtain a NFSR/non-linear function ensemble from the Yao-Parampalli LFSR-based design, featuring the Espresso alternate NFSR FF (cf. Subsection 5.1). Specifically, we have obtained a non-linear output function corresponding to the NFSR FF, thereby closing the gap in the equivalence claims made in [7].

  5. We have supported our experimental results1 using the obtained ‘cipher’ featuring the Espresso alternate NFSR FF, with theoretical analysis (cf. § 6). Our results allow us to conclusively state that:

Using the D-Y-P transformation framework, we have positively settled the Espresso Equivalence Problem by proving the equivalence of the Espresso designs in the sense of matched outputs of the two NFSR/non-linear function ensembles.

Preliminaries and Prior Work

A foundational analysis of non-linear feedback shift registers, in particular, the cycle structure of the state transition graph, is given, like all matters “shift register”, in Golomb’s text [9], Part Three, Chapter VI onwards. We proceed to outline two major algorithms in the works of E. Dubrova, dealing with the transformations between Fibonacci and the so-called uniform Galois NFSRs. This is followed by a brief account of the NFSR transformation framework in the works of G. Yao and U. Parampalli.

The Transformation Framework of E. Dubrova

Our treatment of the transformation framework of E. Dubrova is based on the results in [3], [4], and [6]. In later sections we show that there is an evolutionary thread underlying these works which culminated in the Espresso design in [7]. In the following brief exposition, we segregate Dubrova’s results in the three representative papers under the following heads.

  • Transformation from Fibonacci to uniform Galois NFSR;

  • Matching initial states in Fibonacci-uniform Galois NFSR transformations;

  • Extension to (uniform) Galois-Galois NFSR transformations.

Fibonacci to Uniform Galois NFSR Transformation [3] The first algorithm of E. Dubrova in [3] considers the transformation of a Fibonacci NFSR to a uniform Galois NFSR, which guarantees the following notion of equivalence between the NFSRs (cf. Definition 1, p.5265, [3]): “Two NLFSRs are equivalent if their sets of output sequences are equal.” In [3], the output bit of an NFSR is specified to be the 0-th bit (cf. Section II), and so, the transformation attempts to match the output sequence at the 0-th stage of the original Fibonacci NFSR with that at the 0-th stage of the transformed Galois NFSR. The validity of this transformation is based on the uniform property of a Galois NFSR, which is defined as follows(cf. Definition 7, [3]).

Definition 1. The terminal bit of an nn-bit NFSR is the bit with the minimal index which satisfies the following condition: For all bits ii such that i<τi < \tau, the feedback function fif_i is of type fi=x(i+1)nf_i = x_{(i+1)_n}, where (i+1)n:=(i+1) mod n(i+1)_n := (i+1) \bmod n.

Definition 2. An nn-bit NFSR is uniform if

(a) all its feedback functions are singular functions of the following form:

fi(x0,x1,⋯ ,xn−1)=x(i+1)n⊕gi(x0,x1,⋯ ,xn−1)(1)f_i(x_0,x_1,\cdots,x_{n-1}) = x_{(i+1)_n} \oplus g_i(x_0,x_1,\cdots,x_{n-1}) \tag*{(1)}

gi:{0,1}n−1→{0,1}g_i : \{0,1\}^{n-1} \to\{0,1\} be such that (i+1)n∉dep⁡(gi)(i+1)_n \notin\operatorname{dep}(g_i).

(b) for all its bits ii such that i>τi > \tau, the following condition holds:

max⁡index⁡(gi)≤τ(2)\max\operatorname{index}(g_i) \le\tau \tag*{(2)}

where τ\tau is the terminal bit of the NFSR.

In the above context, the dependence set of a Boolean function ff is denoted by:

dep⁡(f):={i∣f∣xi=0≠f∣xi=1}\operatorname{dep}(f) := \{i \mid f|_{x_i=0} \ne f|_{x_i=1}\}

where f∣xi=j=f(x0,x1,⋯ ,xi−1,j,xi+1,⋯ ,xn−1)f|_{x_i=j}=f(x_0,x_1,\cdots,x_{i-1},j,x_{i+1},\cdots,x_{n-1}), for j∈{0,1}j \in\{0,1\}.

The main algorithm presented in [3] (cf. Section V) is a transformation algorithm from a Fibonacci to a fully shifted, uniform Galois NFSR, which is claimed to preserve the output sequence at the 0-th stage. The term “fully shifted” refers to the fact that this construction guarantees the maximum possible shift from the Fibonacci configuration while maintaining the uniform property.

Matching Initial States in Fibonacci-Galois Transformations [4] In this work dealing with transformations between equivalent NFSRs, in the sense of [3], a formula for the matching initial state of a uniform Galois NFSR is given in terms of the initial state of the Fibonacci NFSR.

Theorem 1 (*Theorem 3, p. 2965, [4]). Let NFN_F be an nn-bit Fibonacci NLFSR and NGN_G be an equivalent to NFN_F uniform Galois NLFSR with the terminal bit τ\tau, 0≤τ<n−10 \le\tau< n-1, and the feedback functions of type

fn−1(x)=x0⊕gn−1(x0,…,xτ)fn−1(x)=x0⊕gn−1(x0,…,xτ)⋯fτ(x)=xτ+1⊕gn−1(x0,…,xτ)fτ−1(x)=xτ⋯f0(x)=x1\begin{aligned} f_{n-1}(x) &= x_0 \oplus g_{n-1}(x_0,\ldots,x_\tau) \\ f_{n-1}(x) &= x_0 \oplus g_{n-1}(x_0,\ldots,x_\tau) \\ &\cdots\\ f_\tau(x) &= x_{\tau+1} \oplus g_{n-1}(x_0,\ldots,x_\tau) \\ f_{\tau-1}(x) &= x_\tau\\ &\cdots\\ f_0(x) &= x_1 \end{aligned}

where gn−1,gn−2,…,gτg_{n-1},g_{n-2},\ldots,g_\tau are Boolean functions. If NFN_F is initialized to a state s=(s0,s1,…,sn−1)s=(s_0,s_1,\ldots,s_{n-1}), and NGN_G is initialized to the state r=(s0,s1,…,sτ,rτ+1,rτ+2,…,rn−1)r=(s_0,s_1,\ldots,s_\tau,r_{\tau+1},r_{\tau+2},\ldots,r_{n-1}) such that

ri=si⊕gi−1(s)⊕gi−2∣+1(s)⊕⋯⊕gτ∣+(i−τ−1)(s)(3)r_i=s_i\oplus g_{i-1}(s)\oplus g_{i-2|+1}(s)\oplus\cdots\oplus g_{\tau|+(i-\tau-1)}(s) \tag*{(3)}

for all i∈{n−1,n−2,…,τ+1}i\in\{n-1,n-2,\ldots,\tau+1\}, then NFN_F and NGN_G generate the same output sequences.

In § 5, it will be shown that this result can be interpreted in terms of simple compensation in the Yao-Parampalli transformation framework [17] (cf. Subsection 2.2).

General Framework for Galois-to-Galois NFSR Transformations

In [6], a more general algorithm was presented which handles transformations between two NFSRs in the Galois configuration via the operation of valid shifting described as follows.

Definition 3. Given an nn-variate mapping defined by functions of the form in Equation (1), a shifting fi→mfjf_i \xrightarrow{m} f_j, i,j∈{0,1,…,n−1}i,j \in\{0,1,\ldots,n-1\}, i≠ji \ne j, shifts the monomial mm in the algebraic normal form (ANF) of fif_i to the ANF of fjf_j, such that every index a∈dep⁡(m)a \in\operatorname{dep}(m) is changed to b=(a−i+j) mod nb=(a-i+j)\bmod n.

Definition 4. Consider an nn-variate mapping with functions of the form in Equation (1), such that the values computed by fzf_z, z∈{0,1,…,n−1}z \in\{0,1,\ldots,n-1\} form the output sequence. Then a shifting gi→mgjg_i \xrightarrow{m} g_j is valid if, for every index a∈dep⁡(m)a \in\operatorname{dep}(m) and bb as in Definition 3, the following conditions hold.

  1. For each c∈[a,b]∖ic \in[a,b]\setminus i, gc=0g_c=0; if i∈[a,b]i \in[a,b], then gi∗=0g_i^*=0 (gi∗=gi⊕mg_i^*=g_i\oplus m);

  2. For each k∈[i,j]k \in[i,j], k∉dep⁡(gi∗)k \notin\operatorname{dep}(g_i^*). Further, k∉dep⁡(gp)k \notin\operatorname{dep}(g_p) for all p∈{0,1,…,n−1}∖ip \in\{0,1,\ldots,n-1\}\setminus i;

  3. Neither [a,b][a,b] nor [i,j][i,j] contain both zz and z−1z-1.

In the above definition, [i,j][i,j] stands for the set {i,i−1,…,j}\{i,i-1,\ldots,j\} if i>ji>j, and the set {i,i+1,…,j}\{i,i+1,\ldots,j\} if i<ji<j, with similar definitions for [a,b][a,b]. Further, if multiple indices zz constitute the output sequence, the third condition must be fulfilled for all pairs (z,z−1)(z,z-1).

The following result from [6] establishes that when a Galois NFSR is transformed to another through valid shiftings, the output sequences of the two NFSRs may differ only in a specific subset of the stages of the internal state.

Theorem 2 (E. Dubrova [6]). Let FF be a mapping as defined by Equation (1) and F′F' be a mapping obtained from FF by applying a valid shifting gi→mgjg_i \xrightarrow{m} g_j, where i,j∈{0,…,n−1}i,j \in\{0,\ldots,n-1\} and i≠ji \ne j. Denote J={i+1,i+2,…,j}\mathcal{J}=\{i+1,i+2,\ldots,j\} and I={i,i−1,…,j+1}\mathcal{I}=\{i,i-1,\ldots,j+1\}. Let FF be initialized to the state (s0,s1,…,sn−1)(s_0,s_1,\ldots,s_{n-1}) and F′F' to the state (r0,r1,…,rn−1)(r_0,r_1,\ldots,r_{n-1}) such that:

  1. For k∈Ik \in\mathcal{I}, rk=sk⊕m∣k−i−1r_k=s_k\oplus m|_{k-i-1}

  2. For k∈Jk \in\mathcal{J}, rk=sk⊕m∣k−j−1r_k=s_k\oplus m|_{k-j-1}

  3. rk=skr_k=s_k for all k∈{0,1,…,n−1}k \in\{0,1,\ldots,n-1\} not in either I\mathcal{I} or J\mathcal{J}.

Then the sequences of states generated by FF and F′F' may differ only in the bit positions in I\mathcal{I} or J\mathcal{J}, respectively.

Remark 1. The above theorem is a generalization of a result in [4] (Theorem 2, p. 2964), which was proved for the shift of a feedback function from the terminal bit τ\tau to a new terminal bit τ−1\tau-1.

The Yao-Parampalli Framework

In [17], a classification of Galois NFSRs based on the forms of the feedback functions is discussed, where four types of NFSRs are described and four sets of transformation algorithms are presented. Of interest in this article is the Type-II Galois NFSR, which corresponds to Dubrova’s uniform Galois NFSR. Henceforth, we will refer to this configuration as uniform Galois.

The so-called compensation method was defined to satisfy the notion of output equivalence where the output is a function of several stages of the shift register. In this context, we state the following definitions from [17].

Definition 5. A compensation list is a list with nn elements denoted as C=[c0,c1,…,cn−1]C = [c_0, c_1, \ldots, c_{n-1}], where each element ci(x0,…,xn−1)c_i(x_0, \ldots, x_{n-1}), i∈{0,…,n−1}i \in\{0, \ldots, n - 1\} is a combination of variants of shifted monomials.

The combination of two compensation lists Cm1C_{m_1} and Cm2C_{m_2}, for two monomials m1m_1 and m2m_2, is defined as the bitwise XOR C=Cm1⊕Cm2C = C_{m_1} \oplus C_{m_2}.

Given an nn-bit NFSR, the compensation list for shifting a monomial mm from faf_a to fbf_b with a,b∈[0,n−1]a,b \in[0,n - 1] and a>ba > b, is constructed as

C=[c0,c1,…,cn−1]=[0,…,0,m∣−(a−b),…,m∣−1,0,…,0]C = [c_0,c_1,\ldots,c_{n-1}] = [0,\ldots,0,m|_{-(a-b)},\ldots,m|_{-1},0,\ldots,0]

where ci=0c_i = 0 for i∈[0,b]i \in[0,b] or [a+1,n−1][a + 1,n - 1] and ci=m∣−(a−i+1)c_i = m|_{-(a-i+1)} for i∈[b+1,a]i \in[b + 1,a].

Compensation vs. Iterative Compensation In addition to the compensation operation, where the state variables are directly XOR-ed with the corresponding entries in the compensation list, Yao and Parampalli define the operation of iterative compensation in descending (or ascending) order. We discuss this with an illustration, following [17], and henceforth term the direct compensation operation as simple compensation to emphasize the difference.

Let the indices xi,xjx_i,x_j, j=i−1j = i - 1, be compensated by the entries ci,cjc_i,c_j of the compensation list, respectively.

Simple compensation results in xi→xi⊕cix_i \to x_i \oplus c_i and xj→xj⊕cjx_j \to x_j \oplus c_j.

For iterative compensation in the descending order, xix_i is first transformed to xi⊕cix_i \oplus c_i. If ci=ci(…,xj,…)c_i = c_i(\ldots,x_j,\ldots), then, in the next step, xi→xi⊕ci(…,xj⊕cj,…)x_i \to x_i \oplus c_i(\ldots,x_j \oplus c_j,\ldots), i.e. the effect of compensation at the next lower index j=i−1j = i - 1 is applied iteratively on the compensated xix_i.

f(x0,x1,x2)→x2→x2⊕c2(x1)f(x0,x1,x2⊕c2(x1))→x1→x1⊕c1f(x0,x1⊕c1,x2⊕c2(x1⊕c1))f(x_0,x_1,x_2) \xrightarrow{x_2 \to x_2 \oplus c_2(x_1)} f(x_0,x_1,x_2 \oplus c_2(x_1)) \xrightarrow{x_1 \to x_1 \oplus c_1} f(x_0,x_1 \oplus c_1,x_2 \oplus c_2(x_1 \oplus c_1))

Yao-Parampalli Algorithms for Transformations between Fibonacci and Uniform Galois NFSRs [17]

  • Fibonacci-to-Uniform Galois Input: nn-bit Fibonacci NFSR; output function fzf_z; initial state X0X^0.

    Output: nn-bit uniform Galois NFSR; transformed output function f‾z\overline{f}_z; matched initial state X^0\widehat{X}^0.

  1. For each monomial mjm_j, j∈[1,r]j \in[1,r], compute the lowest permissible shifting index pjp_j using Dubrova’s algorithm in [3] and choose a position τj\tau_j, such that pj≤τj≤n−1p_j \le\tau_j \le n-1.

  1. Shift the rr monomials from feedback function fn−1f_{n-1} to fτ1,fτ2,…,fτrf_{\tau_1}, f_{\tau_2}, \ldots, f_{\tau_r}, where 0≤τ1≤τ2≤…≤τr≤n−10 \le\tau_1 \le\tau_2 \le\ldots\le\tau_r \le n-1.

  1. For each monomial mjm_j, j∈[1,r]j \in[1,r], construct compensation list

Cmj=[0,…,0,mj∣−(n−1−τj),…,mj∣−1]C_{m_j} = [0,\ldots,0,m_j|_{-(n-1-\tau_j)},\ldots,m_j|_{-1}]

XOR all such lists to compute a combined compensation list:

C=Cm1⊕Cm2⊕…⊕Cmr.C = C_{m_1} \oplus C_{m_2} \oplus\ldots\oplus C_{m_r}.
  1. Compensate the output function fz‾\overline{f_z} by CC iteratively in the descending order to obtain the output function fz‾\overline{f_z} for the transformed NFSR.

  1. The initial state computed as: x^i0=xi0⊕ci(X0)\hat{x}^{0}_i = x^{0}_i \oplus c_i(X^0), i∈[0,n−1]i \in[0,n-1].

Uniform Galois-to-Fibonacci

Input: nn-bit uniform Galois NFSR; output function fzf_z; initial state X0X^0.

Output: nn-bit Fibonacci NFSR; transformed output function fz‾\overline{f_z}; matched initial state X^0\hat{X}^0.

  1. Shift every monomial gi≠0g_i \ne0, from fif_i, i∈[τ,n−2]i \in[\tau,n-2] to fn−1f_{n-1}.

  1. For each gi≠0g_i \ne0 in the first step, compute the compensation list

Cgi=[0,…,0,gi,gi∣+1,…,gi∣+(n−2−i)]C_{g_i} = [0,\ldots,0,g_i,g_i|_{+1},\ldots,g_i|_{+(n-2-i)}]

XOR all such lists to compute a combined compensation list:

C=Cg0⊕Cg1⊕…⊕Cgn−2.C = C_{g_0} \oplus C_{g_1} \oplus\ldots\oplus C_{g_{n-2}}.
  1. Compensate the output function fz‾\overline{f_z} by CC without iteration to obtain the output function fz‾\overline{f_z} for the transformed Fibonacci NFSR as

fz‾=fz(x0⊕c0,…,xn−1⊕cn−1)\overline{f_z} = f_z(x_0 \oplus c_0,\ldots,x_{n-1} \oplus c_{n-1})
  1. The initial state X^0=[x^00,x^10,…,x^n−10]\hat{X}^0 = [\hat{x}^0_0,\hat{x}^0_1,\ldots,\hat{x}^0_{n-1}] is given by:

x^i0=xi0⊕ci‾(X0),i∈[0,n−1]\hat{x}^0_i = x^0_i \oplus\overline{c_i}(X^0),\quad i \in[0,n-1]

where ci‾\overline{c_i} is obtained from cic_i by iterative compensation in descending order using CC.

Remark 2. The Yao-Parampalli algorithms directly use Dubrova’s formulas in [3] to define the shifted monomials as well as the terminal bits associated with each shift.

We conclude this section with a summary comparison of the relevant features of the Dubrova and Y-P frameworks in the following Table 1. This serves as an overture to the analyses and results in subsequent sections, in particular, § 5, where the connection between the frameworks is analysed further in the context of Fibonacci-to-uniform Galois transformations.

FrameworkTransformation ProfileEquivalenceMatching Initial StatesValidation Status
DubrovaFibonacci to Uniform Galois [3]Output at final stageNoProved
DubrovaFibonacci to Uniform Galois [4]Output at final stageYesProved
DubrovaGalois to Galois [6]Output function on restricted subset of stagesYesProved
Yao-ParampalliFibonacci to Uniform Galois [17]Output function on any subset of stagesYesClaimed
Yao-ParampalliUniform Galois to Fibonacci [17]Output function on any subset of stagesYes—

Table 1. Comparison of Dubrova and Yao-Parampalli Frameworks

“Fixing” Dubrova’s Main Theorem

All the transformation algorithms analysed in the subsequent sections of this article build on Dubrova’s Fibonacci-to-uniform Galois NFSR transformation in [3]. However, we show that there is a non-trivial flaw in the proof of the key result - termed the “main theorem” in [3]. In the remainder of this section we rectify this discrepancy and present a correct proof of this theorem, thereby validating a keystone result in Dubrova’s transformation framework.

We begin by stating the result in question from [3]:

Theorem 3. Given a uniform NLFSR with terminal bit aa, a shifting ga→Pgbg_a \xrightarrow{P} g_b, P⊆AgaP \subseteq A_{g_a}, b<ab<a, results in an equivalent NLFSR if the transformed NLFSR is uniform as well.

The proof uses the feedback graph description of an NFSR as defined below [3].

Definition 6. The feedback graph of an nn-bit NFSR is a directed graph with nn vertices v0,…,vn−1v_0,\ldots,v_{n-1} which represents bits 0,…,n−10,\ldots,n-1 of the NFSR, respectively. There is an edge from viv_i to vjv_j if i∈dep⁡(fj)i \in\operatorname{dep}(f_j).

It is noted that the discrepancies in the proof of this theorem stem from an incorrect application of the ‘substitution’ operation (Definition 3 of Section III in [3]), stated below.

Definition 7. The operation substitution, denoted by sub⁡(vi,vj)\operatorname{sub}(v_i,v_j), is defined for any vertex viv_i, which has a unique predecessor vjv_j. The substitution sub⁡(vi,vj)\operatorname{sub}(v_i,v_j) removes viv_i from the feedback graph and, for each successor vkv_k of viv_i, replaces the edge (vi,vk)(v_i,v_k) by an edge (vj,vk)(v_j,v_k).

Clearly the operation is defined as sub⁡(v(successor),v(predecessor))\operatorname{sub}(v(\textbf{successor}), v(\textbf{predecessor})).

The Discrepancy and Proposed Correction

We first outline the relevant steps of the proof provided in [3]. While we adhere to the original notation in [3] as much as possible, we label the first uniform NFSR as NaN_a and the second as NbN_b, according to the respective terminal bits. The NFSR transformation is effected by the shift of a single product-term xkxax_kx_a, k<ak<a, from gag_a to gbg_b. Express gag_a as ga=ga∗⊕xkxag_a=g_a^* \oplus x_kx_a.

The strategy of Dubrova’s proof may be stated as follows:

If the NFSR NbN_b, with terminal bit bb, is uniform, its feedback graph is reducible to a single vertex vbv_b. Then there exists a non-linear recurrence describing the sequence at vbv_b. The equivalence between Na,NbN_a,N_b is established if this recurrence is shown to be identical with that describing the sequence at vav_a for NaN_a.

Relevant Steps in Dubrova’s Proof: Let τ=a\tau=a and τ=b\tau=b represent the respective terminal bits for NaN_a and NbN_b. As outlined in the steps of the proof to Theorem 1 of [3], the substitution operation is invoked twice in arriving at the non-linear recurrence for each terminal bit τ\tau, τ∈{a,b}\tau\in\{a,b\}. For instance, for τ=a\tau=a, the vertices i<ai<a are first removed via the substitution sequence:

sub⁡(v0,v1),sub⁡(v1,v2),…,sub⁡(va−1,va)\operatorname{sub}(v_0,v_1),\operatorname{sub}(v_1,v_2),\ldots,\operatorname{sub}(v_{a-1},v_a)

Then the vertices viv_i, i>τ=ai>\tau=a are removed as follows in Section IV of [3], page 5268 (we quote in italics):

“After a sequence of n−a−1n-a-1 substitutions sub⁡(vn−1,vn−2),…,sub⁡(va+1,va)\operatorname{sub}(v_{n-1},v_{n-2}),\ldots,\operatorname{sub}(v_{a+1},v_a), we get a non-linear recurrence describing the sequence of values of bit aa

sa(t)=sa(t−n)⊕gn−1(s~a(−n+a+1))⊕gn−2(s~a(−n+a))⊕⋯⊕ga(s~a)⊕sa(t−1−a+k)sa(t−1).”s_a(t)=s_a(t-n)\oplus g_{n-1}(\widetilde{s}_a(-n+a+1))\oplus g_{n-2}(\widetilde{s}_a(-n+a))\oplus\cdots\oplus g_a(\widetilde{s}_a)\oplus s_a(t-1-a+k)s_a(t-1).”

The notation s~a(i)\widetilde{s}_a(i) has been defined (cf. pages 5267, 5268) to mean that each element sa(x)s_a(x) of s~a\widetilde{s}_a has been replaced by sa(x+i)s_a(x+i), where s~a\widetilde{s}_a stands for

s~a:=(sa(t−a−1),sa(t−a),…,sa(t−1−(a−b)))(4)\widetilde{s}_a := (s_a(t-a-1),s_a(t-a),\ldots,s_a(t-1-(a-b))) \tag*{(4)}

A similar step is described in arriving at the non-linear recurrence for the values of the bit bb.

The Discrepancy

We observe that:

  • The vertices i>τi>\tau, for τ=a\tau=a or bb, are removed via the sequence:

sub⁡(vn−1,vn−2),…,sub⁡(vτ+1,vτ)(5)\operatorname{sub}(v_{n-1},v_{n-2}),\ldots,\operatorname{sub}(v_{\tau+1},v_\tau) \tag*{(5)}

It is noted that the arguments of the terms in Equation (5) are not consistent with the definition of the substitution operation (cf. Definition 7) as they have the form

(v(predecessor),v(successor)).(v(\text{predecessor}),v(\text{successor})).
  • Even if the order of the arguments is reversed in each operation, the second substitution sequence fails to achieve the presumed objective of reducing all the remaining vertices to vτv_{\tau}.

However, a simple modification to the strategy of applying the substitution operation suffices to remove this discrepancy in the proof, as discussed below.

The Correction

We aver that the correct strategy to evaluate the non-linear recurrence for the sequence of values of the terminal bit is to apply the following sequence of substitutions, after all the vertices labelled i<τi < \tau have been removed:

sub⁡(vn−1,vτ),sub⁡(vn−2,vτ),…,sub⁡(vτ+1,vτ)\operatorname{sub}(v_{n-1},v_{\tau}),\operatorname{sub}(v_{n-2},v_{\tau}),\ldots,\operatorname{sub}(v_{\tau+1},v_{\tau})

Changing the time-shifts of sτ(t)s_{\tau}(t) appropriately at each stage will result in identical non-linear recurrences for both τ=a\tau= a and τ=b\tau= b, thereby proving the theorem.

Proposed Correct Proof of Dubrova’s Theorem

We now present our proof of Theorem 3 in accordance with the correct formulation proposed in the previous subsection. We have retained Dubrova’s notation from [3] as much as possible and elaborate only those steps where there are significant modifications.

Proof of Theorem 3:

We adhere to Dubrova’s proof in the setting of the theorem as well as the relevant steps in [3] prior to the discrepancy. The transformation of the uniform NFSR NaN_a, with terminal bit aa, into NbN_b, with terminal bit b<ab < a, is effected by the shift of xkxax_kx_a, k<ak < a, from gag_a to gbg_b. As the transformed NbN_b is uniform by hypothesis, and b<ab < a, the feedback components gn−1,gn−2,…,ga∗g_{n-1},g_{n-2},\ldots,g_a^* of NaN_a depend on variables sjs_j with j≤bj \le b. Accordingly, the state-variable values sn−1(t),…,s0(t)s_{n-1}(t),\ldots,s_0(t) of NaN_a are described in terms of the state-variable values si(t−1)s_i(t-1) and the functions gj(s0(t−1),s1(t−1),…,sb(t−1))g_j(s_0(t-1),s_1(t-1),\ldots,s_b(t-1)).

For instance,

sn−1(t)=s0(t−1)⊕gn−1(s0(t−1),s1(t−1),…,sb(t−1))(6)s_{n-1}(t)=s_0(t-1)\oplus g_{n-1}(s_0(t-1),s_1(t-1),\ldots,s_b(t-1)) \tag*{(6)}

and the equation for the terminal bit of NaN_a is:

sa(t)=sa+1(t)⊕ga∗(s0(t−1),s1(t−1),…,sb(t−1))⊕sk(t−1)sa(t−1)(7)s_a(t)=s_{a+1}(t)\oplus g_a^*(s_0(t-1),s_1(t-1),\ldots,s_b(t-1))\oplus s_k(t-1)s_a(t-1) \tag*{(7)}

Successive application of the substitutions sub⁡(vi,vi+1)\operatorname{sub}(v_i,v_{i+1}) from the stage i=0i=0 to the stage i=a−1i=a-1, results in the expression of all the remaining state-variable values as follows ([3]).

sn−1(t)=sa(t−a−1)⊕gn−1(sa(t−a−1),sa(t−a),…,sa(t−1−(a−b)))sn−2(t)=sn−1(t−1)⊕gn−2(sa(t−a−1),sa(t−a),…,sa(t−1−(a−b)))⋯=⋯sa(t)=sa+1(t−1)⊕sa(t−1−a+k)sa(t−1)⊕ga∗(sa(t−a−1),sa(t−a),…,sa(t−1−(a−b)))\begin{aligned} s_{n-1}(t) &= s_a(t-a-1)\oplus g_{n-1}(s_a(t-a-1),s_a(t-a),\ldots,s_a(t-1-(a-b)))\\ s_{n-2}(t) &= s_{n-1}(t-1)\oplus g_{n-2}(s_a(t-a-1),s_a(t-a),\ldots,s_a(t-1-(a-b)))\\ \cdots&= \cdots\\ s_a(t) &= s_{a+1}(t-1)\oplus s_a(t-1-a+k)s_a(t-1)\\ &\quad\oplus g_a^*(s_a(t-a-1),s_a(t-a),\ldots,s_a(t-1-(a-b))) \end{aligned}

The above sequence of substitutions results in replacing all si(t)s_i(t), i<ai < a, with time-shifted sa(t)s_a(t)’s. Our next step involves the proposed second substitution sequence sub⁡(vi,va)\operatorname{sub}(v_i,v_a) from the stage i=n−1i = n - 1 to the stage i=a+1i = a + 1.

The initial substitution in the second sequence, sub⁡(vn−1,va)\operatorname{sub}(v_{n-1},v_a), has already been computed at the end of the first substitution sequence. This is because, at the end of the first sequence, vav_a is the unique predecessor of vn−1v_{n-1} and all the si(t−1)s_i(t-1) have been replaced by sa(t−a−1+i)s_a(t-a-1+i) for i≤b<ai \le b < a. Using the notation s~a\tilde{s}_a from Equation (4), we have:

sn−1(t)=sa(t−a−1)⊕gn−1(s~a)s_{n-1}(t) = s_a(t-a-1) \oplus g_{n-1}(\tilde{s}_a)

Next we arrive at the expression for sn−2(t)s_{n-2}(t) as follows.

sn−2(t)=sn−1(t−1)⊕gn−2(s~a)=sa(t−a−2)⊕gn−1(s~a(−1))⊕gn−2(s~a)\begin{aligned} s_{n-2}(t) &= s_{n-1}(t-1) \oplus g_{n-2}(\tilde{s}_a)\\ &= s_a(t-a-2) \oplus g_{n-1}(\tilde{s}_a(-1)) \oplus g_{n-2}(\tilde{s}_a) \end{aligned}

Claim. At the ii-th stage of the second substitution sequence, i<n−ai < n-a, the state-variable value expression is given by:

sn−i(t)=sa(t−i−a)⊕gn−1(s~a(−i+1))⊕gn−2(s~a(−i+2))⊕…⊕gn−i(s~a)s_{n-i}(t) = s_a(t-i-a) \oplus g_{n-1}(\tilde{s}_a(-i+1)) \oplus g_{n-2}(\tilde{s}_a(-i+2)) \oplus\ldots\oplus g_{n-i}(\tilde{s}_a)

Proof of Claim: Proved by induction on ii, where 1≤i≤n−a−11 \le i \le n-a-1. Assuming Equation (8) holds for some i=m−1i = m-1, we have, for i=mi = m,

sn−m(t)=sn−m+1(t−1)⊕gn−m(s~a)s_{n-m}(t) = s_{n-m+1}(t-1) \oplus g_{n-m}(\tilde{s}_a)

Substituting the formula for sn−m+1(t−1)s_{n-m+1}(t-1) proves the claim.

Applying the above formula for i=n−a−1i = n-a-1, we have

sa+1(t)=sa(t−(n−a−1)−a)⊕gn−1(s~a(−n+a+2))⊕…⊕ga+1(s~a)=sa(t−n+1)⊕gn−1(s~a(−n+a+2))⊕gn−2(s~a(−n+a+3))⊕…⊕ga+1(s~a)\begin{aligned} s_{a+1}(t) &= s_a(t-(n-a-1)-a) \oplus g_{n-1}(\tilde{s}_a(-n+a+2)) \oplus\ldots\oplus g_{a+1}(\tilde{s}_a)\\ &= s_a(t-n+1) \oplus g_{n-1}(\tilde{s}_a(-n+a+2)) \oplus g_{n-2}(\tilde{s}_a(-n+a+3)) \oplus\\ &\quad\ldots\oplus g_{a+1}(\tilde{s}_a) \end{aligned}

Therefore

sa(t)=sa+1(t−1)⊕sa(t−1−a+k)sa(t−1)⊕ga∗(sa(t−a−1),sa(t−a),…,sa(t−1−(a−b)))=sa(t−n)⊕gn−1(s~a(−n+a+1))⊕gn−2(s~a(−n+a+2))⊕…⊕ga+1(s~a(−1))⊕ga∗(s~a)⊕sa(t−1−a+k)sa(t−1)\begin{aligned} s_a(t) &= s_{a+1}(t-1) \oplus s_a(t-1-a+k)s_a(t-1)\\ &\quad\oplus g_a^*(s_a(t-a-1),s_a(t-a),\ldots,s_a(t-1-(a-b)))\\ &= s_a(t-n) \oplus g_{n-1}(\tilde{s}_a(-n+a+1)) \oplus g_{n-2}(\tilde{s}_a(-n+a+2)) \oplus\ldots\\ &\quad\oplus g_{a+1}(\tilde{s}_a(-1)) \oplus g_a^*(\tilde{s}_a) \oplus s_a(t-1-a+k)s_a(t-1) \end{aligned}

Expanding the abbreviated notation for s~a(−i)\tilde{s}_a(-i) in each term we get:

sa(t)=sa(t−n)⊕gn−1(sa(t−n),sa(t−n+1),…,sa(t−n+b))⊕gn−2(sa(t−n+1),sa(t−n+2),…,sa(t−n+b+1))⊕…⊕ga∗(sa(t−a−1),sa(t−a),…,sa(t−1−(a−b)))⊕sa(t−1−a+k)sa(t−1)(8)\begin{aligned} s_a(t) &= s_a(t-n)\\ &\quad\oplus g_{n-1}(s_a(t-n),s_a(t-n+1),\ldots,s_a(t-n+b))\\ &\quad\oplus g_{n-2}(s_a(t-n+1),s_a(t-n+2),\ldots,s_a(t-n+b+1)) \oplus\ldots\\ &\quad\oplus g_a^*(s_a(t-a-1),s_a(t-a),\ldots,s_a(t-1-(a-b)))\\ &\quad\oplus s_a(t-1-a+k)s_a(t-1) \tag*{(8)} \end{aligned}

For the transformed NFSR NbN_b, the state-variable values are given by the following set of equations (cf. [3]):

sn−1(t)=s0(t−1)⊕gn−1(s0(t−1),s1(t−1),…,sb(t−1))…=…sa(t)=sa+(t−1)⊕ga∗(s0(t−1),s1(t−1),…,sb(t−1))…=…sa−1(t)=sa(t−1)…=…sb(t)=sb+1(t−1)⊕sk−a+b(t−1)sb(t−1)…=…s0(t)=s1(t−1)\begin{aligned} s_{n-1}(t) &= s_0(t-1) \mathbin{\oplus} g_{n-1}(s_0(t-1),s_1(t-1),\ldots,s_b(t-1))\\ \ldots&= \ldots\\ s_a(t) &= s_{a+}(t-1) \mathbin{\oplus} g_a^*(s_0(t-1),s_1(t-1),\ldots,s_b(t-1))\\ \ldots&= \ldots\\ s_{a-1}(t) &= s_a(t-1)\\ \ldots&= \ldots\\ s_b(t) &= s_{b+1}(t-1) \mathbin{\oplus} s_{k-a+b}(t-1)s_b(t-1)\\ \ldots&= \ldots\\ s_0(t) &= s_1(t-1) \end{aligned}

It is noted that the product-term xkxax_kx_a has been shifted from sa(t)s_a(t) to sb(t)s_b(t) with the appropriate change in the indices: k→k−a+bk \to k-a+b, a→ba \to b.

Using the notation ([3])

s~b:=(sb(t−b−1),sb(t−b),…,sb(t−1))\widetilde{s}_b := (s_b(t-b-1),s_b(t-b),\ldots,s_b(t-1))

we obtain, as follows (cf. [3]), a similar set of equations after the first sequence of substitutions sub⁡(vi,vi+1)\operatorname{sub}(v_i,v_{i+1}), for i=0,…,b−1i=0,\ldots,b-1.

sn−1(t)=sb(t−b−1)⊕gn−1(s~b)…=…sa(t)=sa+1(t−1)⊕ga∗(s~b)sa−1(t)=sa(t−1)…=…sb(t)=sb+1(t−1)⊕sb(t−1−a+k)sb(t−1)\begin{aligned} s_{n-1}(t) &= s_b(t-b-1) \mathbin{\oplus} g_{n-1}(\widetilde{s}_b)\\ \ldots&= \ldots\\ s_a(t) &= s_{a+1}(t-1) \mathbin{\oplus} g_a^*(\widetilde{s}_b)\\ s_{a-1}(t) &= s_a(t-1)\\ \ldots&= \ldots\\ s_b(t) &= s_{b+1}(t-1) \mathbin{\oplus} s_b(t-1-a+k)s_b(t-1) \end{aligned}

where, in the last line, the argument in the first term of the product-term on the r.h.s. is obtained thus: t−1−(b−(k−a+b))=t−1−a+kt-1-(b-(k-a+b))=t-1-a+k; i.e. it is implicitly assumed that k−a+b≤bk-a+b\leq b.

However, as demonstrated earlier for the NFSR NaN_a, the second sequence of substitutions to compute the recurrence for the bit bb should be

sub⁡(vn−1,vb),sub⁡(vn−2,vb),…,sub⁡(vb+1,vb)\operatorname{sub}(v_{n-1},v_b),\operatorname{sub}(v_{n-2},v_b),\ldots,\operatorname{sub}(v_{b+1},v_b)

With a development similar to Equation (8), we present the corrected form for sb(t)s_b(t) as follows.

sb(t)=sb(t−n)⊕gn−1(s~b(−n+b+1))⊕gn−2(s~b(−n+b+2))⊕…⊕ga∗(s~b(−a+b))⊕sb(t−1−a+k)sb(t−1)\begin{aligned} s_b(t) &= s_b(t-n) \mathbin{\oplus} g_{n-1}(\widetilde{s}_b(-n+b+1)) \mathbin{\oplus} g_{n-2}(\widetilde{s}_b(-n+b+2)) \mathbin{\oplus} \ldots\\ &\quad\mathbin{\oplus} g_a^*(\widetilde{s}_b(-a+b)) \mathbin{\oplus} s_b(t-1-a+k)s_b(t-1) \end{aligned}

In the recurrence for sb(t)s_b(t), the term ga∗g_a^* is contributed from the stage aa, and so, the argument of ga∗g_a^* becomes s~b(−(a−b))\widetilde{s}_b(-(a-b)). This is in contrast with the term ga∗(s~a)g_a^*(\widetilde{s}_a) which appears in the final stage of the recurrence for sa(t)s_a(t). However, substituting the full form of s~b\widetilde{s}_b in the ga∗g_a^* term in sb(t)s_b(t) yields:

ga∗(sb(t−a−1),sb(t−a),…,sb(t−1−(a−b)))g_a^*\left(s_b(t-a-1),s_b(t-a),\ldots,s_b(t-1-(a-b))\right)

Hence, expanding the notation for all the s~b(−i)\widetilde{s}_b(-i)'s in the expression of sb(t)s_b(t) we obtain:

sb(t)=sb(t−n)⊕gn−1(sb(t−n),sb(t−n+1),…,sb(t−n+b))⊕gn−2(sb(t−n+1),sb(t−n+2),…,sb(t−n+b+1))⊕…⊕ga∗(sb(t−a−1),sb(t−a),…,sb(t−1−(a−b)))⊕sb(t−1−a+k)sb(t−1)(9)\begin{aligned} s_b(t)={}&s_b(t-n)\\ &\oplus g_{n-1}\left(s_b(t-n),s_b(t-n+1),\ldots,s_b(t-n+b)\right)\\ &\oplus g_{n-2}\left(s_b(t-n+1),s_b(t-n+2),\ldots,s_b(t-n+b+1)\right)\oplus\ldots\\ &\oplus g_a^*\left(s_b(t-a-1),s_b(t-a),\ldots,s_b(t-1-(a-b))\right)\\ &\oplus s_b(t-1-a+k)s_b(t-1) \tag*{(9)} \end{aligned}

Comparing Equations (8) and (9), it is readily seen that the recurrence for the bit aa in NFSR NaN_a is identical with that for bb in NFSR NbN_b.

This completes the proof. □

Remark 3. It is noted that the final expression of the recurrence for the bit aa in the original NFSR, given as Equation (7) in [3] (p. 5268), and its abbreviated form using the notation s~a\widetilde{s}_a, are both erroneous. The argument of the term gn−2g_{n-2} is shown in Equation (7) to be:

sa(t−n−1),sa(t−n),…,sa(t−n+b−1)s_a(t-n-1),s_a(t-n),\ldots,s_a(t-n+b-1)

when the correct argument is (cf. Equation (8)):

sa(t−n+1),sa(t−n+2),…,sa(t−n+b+1)s_a(t-n+1),s_a(t-n+2),\ldots,s_a(t-n+b+1)

The same error in the argument is present in the corresponding expressions for the bit bb in the transformed NFSR (Equation (9), p. 5268 in [3]) as well, and the correct expression is presented here in Equation (9).

To conclude, we have established that there are serious errors in the proof of E. Dubrova’s theorem in [3] and presented a correct proof. It is important to note that the statement of the theorem, which is a key result in numerous subsequent works by Dubrova and others, has been verified to be true - only the validation was flawed. In fact, the idea of transforming a uniform Galois NFSR via shifts of feedback functions and relating the notion of equivalence of NFSRs with equality of recurrence relations at designated stages have proved to be a powerful toolkit for analysis of shift register-based ciphers.

Unifying Dubrova and Yao-Parampalli Transformation Frameworks

As indicated in the introductory section, there is a strong connection between the transformation algorithms defined in the works of Dubrova [3], [4], [6] and those of Yao and Parampalli [16],[17]. In this section, we attempt to formalize these connections in the context of transformations between Fibonacci and uniform Galois NFSRs. The proofs of most of the results used in this section have been presented earlier in [8].

Unifying Dubrova’s Algorithms

In this subsection we state the evolutionary relation among the transformation algorithms discussed in [3] and [6]. We restrict our discussion to the type of NFSRs featured in the Espresso proposal as captured in the following definition.

Definition 8. A uniform NFSR is termed a strict-terminal uniform NFSR, denoted st-uniform NFSR, if it satisfies the following condition for all stages indexed by i>τi > \tau:

max_index⁡(gi)<τ\operatorname{max\_index}(g_i) < \tau

where τ\tau is the terminal bit.

For instance, the Espresso NFSR GG has terminal bit τ=193\tau= 193 with the largest max_index⁡(gi)=189\operatorname{max\_index}(g_i) = 189, while the Espresso alternate NFSR FF has terminal bit τ=217\tau= 217, with max_index⁡(gi)≤183\operatorname{max\_index}(g_i) \le183. Hence they are both st-uniform NFSRs.

The first algorithm D1 in [3] effects a transformation between a uniform Fibonacci to a uniform, fully shifted Galois NFSR, which shifts all the monomials from the stage n−1n - 1 to a stage with index greater than or equal to the terminal bit τ\tau. The rules of this shifting are given in [3] as follows. Let max_index⁡(m)\operatorname{max\_index}(m) denote the largest index of variables in dep⁡(m)\operatorname{dep}(m); likewise min_index⁡(m)\operatorname{min\_index}(m) denotes the smallest index. For all m∈Sgn−1m \in S_{g_{n-1}}, where Sgn−1S_{g_{n-1}} is the set of monomials of gn−1g_{n-1},

  1. If min_index⁡(m)≤(n−1)−τ\operatorname{min\_index}(m) \le(n - 1) - \tau, then the monomial mm is shifted as

gn−1→mgn−1−min_index⁡(m)g_{n-1} \xrightarrow{m} g_{n-1-\operatorname{min\_index}(m)}
  1. If min_index⁡(m)>(n−1)−τ\operatorname{min\_index}(m) > (n - 1) - \tau, then the monomial is shifted to gτg_\tau.

The following result from [8] shows that the above method in the D1 algorithm for generating a fully shifted st-uniform Galois NFSR from a (uniform) Fibonacci NFSR, which preserves the output sequence at the 0-th stage, is consistent with a valid shifting in the D2 algorithm [6].

Theorem 4. Let FF be a Fibonacci NFSR with feedback functions of the form given in Equation (1), with the set of feedback monomials at the (n−1)(n-1)-th stage denoted by {x0}∪Sgn−1\{x_0\} \cup S_{g_{n-1}}. Then the shift of any monomial m∈Sgn−1m \in S_{g_{n-1}} under the algorithm D1 for st-uniform NFSRs is a valid shifting in the sense of the algorithm D2.

Remark 4. Theorem 4 shows that for Fibonacci to st-uniform Galois transformation, D1 in [3] is subsumed in the framework of D2 in [6]. Hence the post-transformation equivalence conditions (cf. Theorem 2) that are satisfied for D2 will hold for D1 as well.

Dubrova’s Algorithms and the Espresso Equivalence Problem As discussed in the introductory section, an alternate Galois NFSR FF is defined in [7] to discuss the security of Espresso, which is claimed to be “equivalent” to the cipher design. However, we point out that there are two aspects to any meaningful equivalence, in the context of security analysis, of the two NFSR configurations so defined.

  1. Establishing the equivalence of the generated keystreams at designated stages of the 2-tap Galois NFSR FF and the Espresso NFSR GG.

  2. Defining a corresponding non-linear output function for FF, so that both systems generate identical keystreams. No such function is provided in [7].

These unresolved issues constitute the Espresso Equivalence Problem, graphically depicted in Figure 1.

The Espresso Equivalence Problem

Figure 1. The Espresso Equivalence Problem

In [7], the only pointer to establishing the claimed equivalence is a reference, on p. 278, to Dubrova’s algorithm D1 in [3] which we quote below:

“The equivalence of GG and FF can be shown by applying the Fibonacci-to-Galois transformation [6].”

In the light of Theorem 4, we now comment on the applicability of Dubrova’s algorithms to the Espresso equivalence problem using the following Table 2 (cf. [8]), which displays the relevant information culled from Table 1 in place for convenience. It is noted that Dubrova’s first algorithm in [3], while introducing several key notions of the shift formula, uniform NFSR configuration and associated terminal bit, does not provide explicit formulation for matching initial state. Further, it guarantees equivalence across the transformation only for the output at a single stage (e.g. stage 0). Hence, it has been argued in [8] that, contrary to the claim in [7], the algorithm D1 cannot be used to resolve the Espresso equivalence problem, while it may be possible to use the algorithm D2 to gain further insights into the problem. Further analysis in later sections confirms this initial observation.

AlgorithmNFSR TypesMulti-stage EquivalenceMatching Initial States
D1 [3]Fibonacci to Uniform GaloisNoNo
D2 [6]Galois to GaloisYesYes

Table 2. Comparison of Dubrova’s NFSR Transformation Algorithms

Relating Yao-Parampalli and Dubrova’s Algorithms

As discussed in Subsection 2.2, the Yao-Parampalli transformation framework, henceforth denoted as the Y-P framework, analyzes four configurations of Galois NFSRs and back-and-forth transformations with “equivalent” Fibonacci NFSRs, when feasible. However, the only proven technical results in [17] deal with the transformation of a Fibonacci NFSR to a uniform Galois NFSR, which is the precisely the case treated in [3]. Accordingly, we compare the Y-P Fibonacci-to-uniform Galois algorithm with Dubrova’s generalized transformation D2 restricted to this particular case.

The three proven results in [17] are as follows:

  • In Section 2 of [17], Lemma 1 and Lemma 2 relate the internal states of an “original Fibonacci NLFSR” with that of the “transformed Type-II Galois NLFSR”.

  • The third result is Theorem 1 in Section 3 of [17], which states that for “an nn-bit Fibonacci NLFSR transformed to a Type-II Galois NLFSR according to the Fibonacci-to-Type-II algorithm”, the internal states are related by the relations in Lemma 1 and Lemma 2, and, further, the NFSRs are “equivalent”.

It was proved in [8] that matching the initial states before and after the transformation in the Y-P framework yields the same result as outlined in Dubrova’s algorithm D2. In the following, we briefly state the relevant results in [8] and further extend the analysis.

Matching Initial States We begin by stating the two lemmas, proved in [17], and compare them with Dubrova’s Theorem 2. For facilitating this comparison, we use the following

Notation: Denote the kk-th stage at time tt of the transformed uniform Galois NFSR as rktr_k^t, and let skts_k^t denote the corresponding entity for the Fibonacci NFSR. The complete states of the said NFSRs at time tt are denoted with the boldface rt\mathbf{r}^t and st\mathbf{s}^t, respectively.

The lemmas establish that for the shift of a single monomial, using Dubrova’s shift formula in [3], a relation between the initial states of the Fibonacci and the transformed uniform Galois NFSRs is preserved for all subsequent states.

Lemma 1 (Lemma 1, [17]). Given an nn-bit Fibonacci NFSR, a monomial mm is shifted from fn−1f_{n-1} to fbf_b according to the shift operation in Definition 3 and the resulted feedback functions satisfy the conditions for uniform Galois NFSRs. If the initial state of the uniform Galois NFSR is computed according to (10), then the internal state of the uniform Galois NFSR rktr_k^t, k∈{0,…,n−1}k \in\{0,\ldots,n-1\} and the internal state of the Fibonacci NFSR skts_k^t, k∈{0,…,n−1}k \in\{0,\ldots,n-1\} also satisfy this relation for t>0t > 0.

rk=sk⊕m∣−(n−k)(st),for k∈[b+1,n−1]rk=sk,for k∈[0,b](10)\begin{aligned} r_k &= s_k \oplus m|_{-(n-k)}(\mathbf{s}^t), && \text{for } k \in[b+1,n-1] \\ r_k &= s_k, && \text{for } k \in[0,b] \tag*{(10)} \end{aligned}

The second lemma of the Y-P framework, which features iterative compensation, is stated as follows.

Lemma 2 (Lemma 2, [17]). In the setting of Lemma 1,

sk=rk⊕m∣−(n−k)‾(rt),for k∈[b+1,n−1]sk=rk,for k∈[0,b](11)\begin{aligned} s_k &= r_k \oplus\overline{m|_{-(n-k)}}(\mathbf{r}^t), && \text{for } k \in[b+1,n-1] \\ s_k &= r_k, && \text{for } k \in[0,b] \tag*{(11)} \end{aligned}

where m∣−(n−k)‾\overline{m|_{-(n-k)}} is mm compensated by C=[0,…,0,m∣−(a−b),…,m∣−1,0,…,0]C=[0,\ldots,0,m|_{-(a-b)},\ldots,m|_{-1},0,\ldots,0] iteratively in descending order.

:::

The following result in [8] established the equivalence of matching the initial states in Y-P and Dubrova’s formulations by proving the equivalence of Lemma 1 of [17] with Dubrova’s theorem in [6].

Lemma 3. For a Fibonacci-to-uniform Galois transformation, the formulation in [17] for the Galois NFSR stages rktr_k^t in terms of the Fibonacci stages skts_k^t, k∈{0,…,n−1}k \in\{0,\ldots,n-1\}, is simply obtained by a restriction of the formulation in Dubrova’s Theorem in [6] to this particular case.

It is noted that even though the results of matching the initial states are identical, when the transformed initial state is expressed in terms of the original state, there is no obvious counterpart of Lemma 2 in Dubrova’s general framework. Further, the Y-P framework introduces the compensation operation to arrive at the results, which has no apparent equivalent in Dubrova’s works. In the next subsection, we take a closer look at the actual analyses behind these results and reveal a stronger connection between the Dubrova and Y-P frameworks.

De-mystifying Compensation

In this subsection we first examine the two compensation operations defined in the Y-P framework in the context of Fibonacci-uniform Galois transformations, and show that they lead to the evaluation of the same matching initial states, albeit from different directions. Then we prove that the simple compensation operation is a re-formulation of a result from Dubrova’s framework [4], which allows us to relate these two frameworks with greater clarity.

Simple vs. Iterative Compensation It is evident from the statements of Lemma 1 and Lemma 2 (cf. Lemma 1 and Lemma 2 of [17]) that the second lemma includes the first in its premise. We further make the following formal observation, which is obtained from the steps of the proof of the second lemma presented in [17].

Proposition 1. For the Yao-Parampalli Fibonacci-to-uniform Galois transformation, the initial states before and after transformation can be matched in either of two ways, leading to identical results, as follows:

  1. Start with the initial state of the original Fibonacci NFSR and perform simple compensation to obtain the matching initial state of the transformed Galois NFSR;

  2. Start with the initial state of the transformed Galois NFSR and perform iterative compensation to obtain the matching initial state of the original Fibonacci NFSR.

Proof. It follows from Equation (10) and Equation (11) that for indices k∈[0,b]k \in[0,b], where k=b+1k=b+1 is the first possibly non-zero index in the compensation list, both the procedures return identical values by default.

For any k∈[b+1,n−1]k \in[b+1,n-1], consider the expression for the kk-th initial bit of the Fibonacci NFSR in terms of the corresponding bit of the transformed Galois NFSR obtained from Equation (11):

sk0=rk0⊕m∣−(n−k)(r0)‾s_k^0 = r_k^0 \oplus\overline{m|_{-(n-k)}(r^0)}

Here, the overline denotes iterative compensation using the initial state r0r^0 of the Galois NFSR. But, as Lemma 2 pre-supposes Lemma 1, we substitute the value of rk0r_k^0 from Equation (10) in the above to obtain:

sk0=(sk0⊕m∣−(n−k)(s0))⊕m∣−(n−k)(r0)‾s_k^0 = \left(s_k^0 \oplus m|_{-(n-k)}(s^0)\right) \oplus\overline{m|_{-(n-k)}(r^0)}

which readily implies

m∣−(n−k)(s0)=m∣−(n−k)(r0)‾(12)m|_{-(n-k)}(s^0) = \overline{m|_{-(n-k)}(r^0)} \tag*{(12)}

This proves the assertion, as simple compensation using the initial state of the Fibonacci NFSR yields exactly the same values as iterative compensation using the state of the transformed Galois NFSR.

Remark 5. It is noted that the proof of Lemma 2 in [17] essentially consists of proving the relation in Equation (12) (cf. pp. 235–236 [17]).

Simple compensation and Dubrova’s matching formula in [4] As discussed in § 2.1, formulas for matching initial states in transformations between Fibonacci and uniform Galois NFSRs were presented in [4], [6]. Specifically, Theorem 1 in [4], gives the explicit formula for the initial state of a uniform Galois NFSR in terms of the initial state of an “equivalent” Fibonacci NFSR. In the following we show that, in this case, simple compensation in the Y-P framework is a re-formulation of the above formula in [4].

Theorem 5. Let NFN_F and NGN_G be an equivalent pair, in the sense of matched outputs at stage 0, of an nn-bit Fibonacci and a uniform Galois NFSR, respectively. Then matching the initial state s=(s0,…,sn−1)\mathbf{s}=(s_0,\ldots,s_{n-1}) of NFN_F to that of NGN_G, denoted r=(s0,s1,…,sτ,rτ+1,…,rn−1)\mathbf{r}=(s_0,s_1,\ldots,s_\tau,r_{\tau+1},\ldots,r_{n-1}), through the Yao-Parampalli simple compensation operation yields the formula:

rk=sk⊕⨁i=τk−1gi∣+(k−(i+1))(s)r_k=s_k\oplus\bigoplus_{i=\tau}^{k-1}g_i|_{+(k-(i+1))}(\mathbf{s})

which matches exactly with the corresponding formula for rkr_k, τ+1≤k≤n−1\tau+1\leq k\leq n-1, in (Dubrova’s) Theorem 1.

Proof. Consider the case where the uniform Galois NFSR NGN_G has terminal bit τ\tau, where 0≤τ<n−10\leq\tau<n-1, and feedback functions of the form:

fk(x)=x(k+1) mod n⊕gk(x0,…,xτ);k∈[τ,n−1]f_k(\mathbf{x})=x_{(k+1)\bmod n}\oplus g_k(x_0,\ldots,x_\tau); \quad k\in[\tau,n-1]
fk(x)=x(k+1);k∈[0,τ−1]f_k(\mathbf{x})=x_{(k+1)}; \quad k\in[0,\tau-1]

Hence, the transformation entails the shift of all feedback functions, which themselves consist of XORed monomial terms, from the single Fibonacci feedback function at k=n−1k=n-1 of NFN_F. The terminal bit being τ\tau, the first possibly non-zero entry in the compensation list corresponds to the shift from n−1n-1 to τ\tau, with the shifted form being gτg_\tau. We denote the original component of the feedback at the (n−1)(n-1)-th stage of NFN_F as gτ∗g_\tau^*, which is related to the shifted feedback function gτg_\tau of NGN_G as follows:

gτ=gτ∗∣−(n−1−τ)⟹gτ∗=gτ∣+(n−1−τ)g_\tau=g_\tau^*|_{-(n-1-\tau)}\Longrightarrow g_\tau^*=g_\tau|_{+(n-1-\tau)}

The compensation list corresponding to the shift fn−1→gτ∗fτf_{n-1}\xrightarrow{g_\tau^*}f_\tau is given by:

Cτ=[0,…,0,gτ∗∣−(n−1−τ),gτ∗∣−(n−2−τ),…,gτ∗∣−1]C_\tau=[0,\ldots,0,g_\tau^*|_{-(n-1-\tau)},g_\tau^*|_{-(n-2-\tau)},\ldots,g_\tau^*|_{-1}]

Substituting gτg_\tau for gτ∗g_\tau^* in the above, we have:

Cτ=[0,…,0,gτ,gτ∣+1,…,gτ∣+(n−1−(τ+1))]C_\tau=[0,\ldots,0,g_\tau,g_\tau|_{+1},\ldots,g_\tau|_{+(n-1-(\tau+1))}]

which gives the simple compensation contribution involving gτg_\tau in the combined compensation list:

C=Cτ⊕Cτ+1⊕⋯⊕Cn−1C=C_\tau\oplus C_{\tau+1}\oplus\cdots\oplus C_{n-1}

It can be similarly verified that the compensation contribution involving gkg_k, for all τ+1≤k≤n−1\tau+ 1 \le k \le n - 1, is given by:

Ck=[0,…,0,gk,gk∣+1,…,gk∣+(n−1−(k+1))⏟n−1]C_k = [0,\ldots,0,g_k,\underbrace{g_{k|+1},\ldots,g_{k|+(n-1-(k+1))}}_{n-1}]

The first possibly non-zero entry of the combined compensation list is the entry in the position τ+1\tau+ 1, given by the single term gτg_\tau.

The entry in the position τ+2\tau+ 2 is accordingly given by: gτ+1⊕gτ∣+1g_{\tau+1} \oplus g_{\tau|+1}.

Collecting the terms in a similar manner, the kk-th entry in the combined compensation list is given by:

gk−1⊕gk−2∣+1⊕⋯⊕gτ∣+(k−(τ+1))=⨁i=τk−1gi∣+(k−(i+1))g_{k-1} \oplus g_{k-2|+1} \oplus\cdots\oplus g_{\tau|+(k-(\tau+1))} = \bigoplus_{i=\tau}^{k-1} g_{i|+(k-(i+1))}

Simple compensation using this combined compensation list yields the kk-th bit of the initial state of NGN_G, say rkr_k, in terms of the initial state ss of NFN_F as:

rk=sk⊕⨁i=τk−1gi∣+(k−(i+1))(s).r_k = s_k \oplus\bigoplus_{i=\tau}^{k-1} g_{i|+(k-(i+1))}(s).

Hence the theorem. □

We summarize our analysis of the transformation frameworks of Dubrova and Yao-Parampalli with the following

Observations:

  1. For Fibonacci-to-uniform Galois NFSR transformation, the simple compensation operation of Yao-Parampalli yields the same result as Dubrova’s formulation for matching initial states to achieve NFSR equivalence.

  1. In the Y-P framework for Fibonacci-uniform Galois transformation, simple compensation and iterative compensation yield identical pairs of matched initial states. However, simple compensation computes the transformed state in terms of the original state while iterative compensation proceeds in the reverse direction.

  1. Therefore, with regard to equivalent transformations between Fibonacci and uniform Galois NFSRs, Dubrova’s general framework ([4], [6]) and the Y-P framework are essentially identical in computing the monomial shifts and matching the initial states.

  1. However, as will be elaborated on in § 6, the real efficacy of iterative/simple compensation is demonstrated in matching the outputs of nonlinear functions, involving several state variables of the NFSRs, before and after the transformations. This contribution in the Y-P framework appears to represent a significant step beyond Dubrova’s framework.

Resolving the Espresso Equivalence Problem

In this section we bring to bear our unifying analysis of Dubrova and Y-P transformation techniques on the Espresso Equivalence Problem (EEP) (cf. Subsection 4.1). As mentioned earlier, Yao and Parampalli have claimed in [16] that the application of uniform Galois-to-Fibonacci NFSR transformation on the Espresso NFSR GG results in a Fibonacci LFSR with feedback function

fL(x):=f255(x)=x0⊕x12⊕x48⊕x115⊕x133⊕x213(13)f_L(\mathbf{x}) := f_{255}(\mathbf{x}) = x_0 \oplus x_{12} \oplus x_{48} \oplus x_{115} \oplus x_{133} \oplus x_{213} \tag*{(13)}

This also generates an output function, which we denote as zYP(x)z_{\mathrm{YP}}(\mathbf{x}), consisting of 2289 monomials and having algebraic degree 12, such that the ensemble comprising LFSR fL(x)f_L(\mathbf{x}) and zYP(x)z_{\mathrm{YP}}(\mathbf{x}), with initial state matched with GG, produces the same keystream as Espresso. This is indeed a fascinating result, and it showcases the power of Dubrova-Yao-Parampalli transformation framework by reducing a Galois NFSR with 14 non-linear taps to a Fibonacci LFSR whose single feedback consists of 6 linear terms. The Y-P LFSR-based Espresso-equivalent design is the springboard for our attempt to resolve EEP.

Thus far, we have shown that the NFSR transformation effected by the Y-P Fibonacci-to-uniform Galois method is essentially the same as Dubrova’s algorithm D2. In [8], the Fibonacci-to-uniform Galois algorithm was applied on the Y-P LFSR (fL(x)f_L(\mathbf{x})) to attempt a transformation to the Espresso alternate NFSR FF. The rationale for this was given in [8] as follows:

If the NFSR FF is recovered, then, given the equivalence claimed in [16], the output function obtained using the Y-P algorithm on the LFSR ensemble would complete the gap in the Espresso NFSR FF design.

A concept schematic of the above strategy is given in Figure 2.

Figure 2. Using Y-P/Dubrova Algorithms to Resolve Espresso Equivalence

Recovery of Espresso NFSR FF from Y-P LFSR

We now present, for the sake of completeness, the steps of the recovery of the Galois NFSR FF by the application of the Fibonacci-to-uniform Galois algorithm on the Fibonacci LFSR fL(x)f_L(\mathbf{x}) as given in [8].

We first note that the NFSR FF has two feedback taps given by:

f255(x)=x0⊕x12⊕x48⊕x115⊕x133⊕x213⊕x41x70⊕x46x87⊕x52x110⊕x55x130⊕x62x157⊕x74x183⊕x87x110x130x157f217(x)=x218⊕x3x32⊕x8x49⊕x14x72⊕x17x92⊕x24x119⊕x36x145⊕x49x72x92x119(14)\begin{aligned} f_{255}(\mathbf{x}) ={}& x_0 \oplus x_{12} \oplus x_{48} \oplus x_{115} \oplus x_{133} \oplus x_{213} \oplus x_{41}x_{70} \oplus x_{46}x_{87} \\ &{}\oplus x_{52}x_{110} \oplus x_{55}x_{130} \oplus x_{62}x_{157} \oplus x_{74}x_{183} \oplus x_{87}x_{110}x_{130}x_{157} \\ f_{217}(\mathbf{x}) ={}& x_{218} \oplus x_3x_{32} \oplus x_8x_{49} \oplus x_{14}x_{72} \oplus x_{17}x_{92} \oplus x_{24}x_{119} \oplus x_{36}x_{145} \\ &{}\oplus x_{49}x_{72}x_{92}x_{119} \tag*{(14)} \end{aligned}

It is remarked in [7] that

f255(x)=fLin(x)⊕fNL(x)(15)f_{255}(\mathbf{x}) = f_{\mathrm{Lin}}(\mathbf{x}) \oplus f_{\mathrm{NL}}(\mathbf{x}) \tag*{(15)}

where fLin(x)f_{\mathrm{Lin}}(\mathbf{x}) is a linear polynomial component and fNL(x)f_{\mathrm{NL}}(\mathbf{x}) is a non-linear component. Further the feedback function at stage 217 is given precisely by

f217(x)=x218⊕fNL(x)(i−38)f_{217}(\mathbf{x}) = x_{218} \oplus f_{\mathrm{NL}}(\mathbf{x})_{(i-38)}

where the second term is given by the non-linear component fNL(x)f_{\mathrm{NL}}(\mathbf{x}) of f255f_{255}, with every variable xix_i changed to xi−38x_{i-38}.

The feedback function of the Y-P Fibonacci LFSR can be re-written as

fL(x)=(fL(x)⊕fNL(x))⊕fNL(x)f_L(\mathbf{x}) = \left(f_L(\mathbf{x}) \oplus f_{\mathrm{NL}}(\mathbf{x})\right) \oplus f_{\mathrm{NL}}(\mathbf{x})

Using Dubrova’s shift formula to transfer all the monomials in fNL(x)f_{\mathrm{NL}}(\mathbf{x}) from stage 255 to stage 217, we obtain the transformed feedback function at stage 217 as:

f217=x218⊕fNL(x)(i−255+217)=x218⊕fNL(x)(i−38)f_{217} = x_{218} \oplus f_{\mathrm{NL}}(\mathbf{x})_{(i-255+217)} = x_{218} \oplus f_{\mathrm{NL}}(\mathbf{x})_{(i-38)}

After the shift, the modified feedback function at stage 255 is

f255(x)=fL(x)⊕fNL(x)f_{255}(\mathbf{x}) = f_L(\mathbf{x}) \oplus f_{\mathrm{NL}}(\mathbf{x})

This is precisely the Galois NFSR FF with exactly two non-linear feedback taps at stages 255 and 217.

Remark 6. A general analysis and application of this ‘trick’ of extracting and shifting an ‘invisible’ feedback term by XORing twice is to be found in [5].

Proposed Resolution of Espresso Equivalence Problem As the NFSR FF is a uniform Galois NFSR, with terminal bit 217, the Y-P Fibonacci-to-uniform Galois algorithm will automatically generate a candidate for the non-linear output function. Hence, we can construct a non-linear filter generator cipher based on the Espresso alternate NFSR FF, which would be equivalent to the Y-P LFSR ensemble in the sense discussed in [16], [17]. Our proposed procedure is formally stated in Algorithm 1. A theoretical validation and experimental results pertaining to this procedure are presented in the following subsections.

Algorithm 1 Generation of Espresso Alternate NFSR Cipher

  1. Input: Y-P nn-bit Fibonacci LFSR LL and Non-linear function zYP(x)z_{\mathrm{YP}}(x); Initial state ss of Fibonacci LFSR. Output: Espresso alternate NFSR FF and Non-linear function zF(x)z_F(x); Matching initial state rr of NFSR FF.

  2. Use Dubrova’s shift formula to generate NFSR FF:

f255→fNL(x)f217f_{255} \xrightarrow{f_{\mathrm{NL}}(x)} f_{217}
  1. Generate combined compensation list CC for the shift.

  2. Obtain matching initial state for FF by simple compensation using CC (Dubrova’s theorem/Y-P lemma).

  3. Obtain output function zF(x)z_F(x) from zYP(x)z_{\mathrm{YP}}(x) by iterative compensation in the descending order using CC.

Validating the Solution to EEP

In this subsection we present theoretical analysis in support of our proposed procedure for resolving the Espresso Equivalence problem.

As stated in Algorithm 1, our procedure is based on using the Dubrova-Yao-Parampalli transformation framework to transform the Yao-Parampalli LFSR-based Espresso-equivalent design into a design based on the Espresso alternate NFSR FF. It is evident from the analysis in Subsection 5.1, that we have achieved the LFSR-NFSR correspondence through appropriate use of Dubrova’s shift formula. The final, more critical, challenge is to ensure that the output of the non-linear function so obtained is identical for both the Y-P LFSR-based design and the NFSR FF-based design derived by us. To that end, we first examine the recipe(s) proposed by Yao-Parampalli in [17], to effect transformations between Fibonacci and uniform Galois NFSRs such that they preserve the output bitstreams of non-linear functions involving several stages of the NFSRs.

Issues with the Yao-Parampalli Algorithms As discussed in § 3.1, there are three proven results in [17], Lemmas 1 and 2 along with the Theorem 6 (cf. p. 238, Section 3, [17]), all of which deal with the transformation of a Fibonacci to a uniform Galois NFSR. We have already discussed the lemmas, and established their equivalence with Dubrova’s works [4], [6], in computing matching initial states for the Fibonacci and Galois NFSRs. We now examine the following theorem of Yao-Parampalli which claims that their algorithm (cf. § 3.1) achieves equivalence in the outputs of the respective non-linear functions.

Theorem 6 (Theorem 1, [17]). Let an nn-bit Fibonacci NLFSR [sic] transformed to a Type-II Galois NLFSR according to the Fibonacci-to-Type-II algorithm, then the internal states of the NLFSR before and after transformation denoted by xitx_i^t and x^it\hat{x}_i^t satisfy

x^it=xit⊕ci(Xt), for k∈[τ1+1,n−1]\hat{x}_i^t = x_i^t \oplus c_i(X^t), \text{ for } k \in[\tau_1+1,n-1]
x^it=xit, for k∈[0,τ1]\hat{x}_i^t = x_i^t, \text{ for } k \in[0,\tau_1]

and

xit=x^it⊕cˉi(X^t), for k∈[τ1+1,n−1]x_i^t = \hat{x}_i^t \oplus\bar{c}_i(\hat{X}^t), \text{ for } k \in[\tau_1+1,n-1]
xit=x^it, for k∈[0,τ1]x_i^t = \hat{x}_i^t, \text{ for } k \in[0,\tau_1]

and the two NLFSRs are equivalent.

A comparison with Lemma 1 and Lemma 2 shows that the formulas in Theorem 6 have the same form with those presented in the lemmas, with single monomials in the former replaced by compensation entries in the latter. The main body of the proof of Theorem 6 consists of validating the stated formulas in simple instances. The crucial assertion in the theorem regarding “equivalence”, which appears to be the real contribution of the Y-P formulation beyond Dubrova’s framework, is handled in the concluding paragraph of the proof in [17] as follows.

“If the output function fzf_z takes xix_i, i∈[τ1+1,n−1]i \in[\tau_1+1,n-1] as input, the corresponding tap in fˉz\bar{f}_z is compensated by CC. Since the compensation is done iteratively, the xix_i in cic_i is also compensated. Therefore, at each clock tt, the bit value of that input in fˉz\bar{f}_z is equal to x^it⊕cˉi(X^t)\hat{x}_i^t \oplus\bar{c}_i(\hat{X}^t) which is equal to xitx_i^t according to (9) (cf. Theorem 6). Hence, the output function fˉz\bar{f}_z generate [sic] same bit as the original function fzf_z does at each clock.”

We point out the following issues with the above statement and the steps of transformation from “Fibonacci-to-Type II” (uniform Galois) on p. 238 and “Type II-to-Fibonacci” on p. 241 in [17], respectively.

  • It appears from the quoted statement that the equivalence of the outputs of the non-linear functions before and after the transformation is achieved via the following steps:

  1. Perform iterative compensation on the variables constituting the output function fzf_z to obtain fˉz\bar{f}_z.

  2. Perform iterative compensation on the original initial state to obtain x^it⊕cˉi(X^t)\hat{x}_i^t \oplus\bar{c}_i(\hat{X}^t) (following the notation in Lemma 2).

  1. Evaluate the iteratively compensated output function fˉz\bar{f}_z on the iteratively compensated initial state.

Issue: It is simply stated, without proof, that this evaluation is identical with the original output function evaluated on the original initial state.

  • As shown in Subsection 2.2, the steps for “Fibonacci-to-Type II” transformation in [17] consist of the following sequence for producing identical function outputs: iterative compensation of output function followed by simple compensation of the initial state to be used as argument. Issue: This is at variance with the suggested procedure in the “proof” of Theorem 6.

  • The stated procedure for “Type II-to-Fibonacci” in [17] transformation suggests simple compensation of output function followed by iterative compensation of the initial state to be used as argument. Issue: In this case, swapping the sequence of compensation operation that was suggested for the earlier case of “Fibonacci-to-Type II” adds to the ambiguity. More so, as no reason or validation is provided for either.

Remark 7. It is noted in this context that the proof of Theorem 1 as well as that of Lemma 2 in [17] refers to a “Lemma 3” for some sort of validation. Unfortunately, the said result does not exist in the entire paper, even though it is referred to elsewhere as well.

Remark 8. In [17], the authors present an illustration of their algorithm for Fibonacci-to-uniform Galois (Type-II) transformation (cf. Algorithm 2, Section 3, p. 240). They begin with a 4-bit Fibonacci NFSR with initial state X0={x00,x10,x20,x30}={1,1,0,1}X^0 = \{x_0^0,x_1^0,x_2^0,x_3^0\} = \{1,1,0,1\}. However, in the later steps of the algorithm, specifically from Step 5, the initial state is specified as {0,1,1,1}\{0,1,1,1\}. No reason is given for this modification, whatsoever. In the following steps, simple compensation of the modified state {0,1,1,1}\{0,1,1,1\} is used to generate {0,1,0,0}\{0,1,0,0\}, rather than the declared initial state.

Resolving the Issues and Proof of Concept In what follows we resolve the above issues in the Yao-Parampalli algorithms to establish the correct sequence of operations of simple and iterative transformations. Further, we formally prove that our prescribed sequence indeed achieves the following objective of Yao-Parampalli’s algorithms:

The modified non-linear function obtained after transformation, with a modified input state as the argument, will output exactly the same bitstream as the original function with a matched input state as argument.

We begin with a result on the composition of the dependence lists of the compensation entries corresponding to Fibonacci-to-uniform Galois NFSR transformations. This is an ingredient in the proof of the main theorem which will provide theoretical validation to the claimed equivalence.

Lemma 4. For the D-Y-P equivalent transformation from an nn-bit Fibonacci to a uniform Galois NFSR, with terminal bit 0≤τ<n−10 \le\tau< n-1, the entries cic_i of the compensation list CC satisfy the following condition:

max⁡dep⁡(ci)≤i−1, ∀i∈{τ+1,τ+2,…,n−1}\max\operatorname{dep}(c_i) \le i-1,\ \forall i \in\{\tau+1,\tau+2,\ldots,n-1\}

Proof. Consider the following shift from the feedback function at the (n−1)(n-1)-th stage of the Fibonacci NFSR:

fn−1→gτ∗fτf_{n-1} \xrightarrow{g_\tau^*} f_\tau

where we use the notation of Theorem 5, with the resulting shifted function at fτf_\tau denoted by gτg_\tau. As the transformed Galois NFSR, defined using the notation of Theorem 1, is uniform, we have:

dep⁡(gi)⊆[0,τ], ∀i∈{τ+1,τ+2,…,n−1}\operatorname{dep}(g_i) \subseteq[0,\tau],\ \forall i \in\{\tau+1,\tau+2,\ldots,n-1\}

At some such ii, it follows from Theorem 1 and Theorem 5 that the compensation expression is defined by the terms:

gi−1,gi−2∣+1,…,gτ∣+(i−τ−1)g_{i-1},g_{i-2|+1},\ldots,g_{\tau|+(i-\tau-1)}

The first possibly non-zero compensation term is cτ+1c_{\tau+1}, which is simply given by gτg_\tau. Hence, it follows that, for i=τ+1i=\tau+1,

max⁡dep⁡(ci)=max⁡dep⁡(cτ+1)=τ≤i−1\max\operatorname{dep}(c_i)=\max\operatorname{dep}(c_{\tau+1})=\tau\le i-1

For i=τ+2i=\tau+2, we have the contributing terms gτ+1g_{\tau+1} and gτ∣+1g_{\tau|+1} where

dep⁡(gτ+1)⊆[0,τ],whiledep⁡(gτ∣+1)⊆[1,τ+1]\operatorname{dep}(g_{\tau+1}) \subseteq[0,\tau],\quad\text{while}\quad\operatorname{dep}(g_{\tau|+1}) \subseteq[1,\tau+1]

Hence, the assertion holds for i=τ+2i=\tau+2 as well, since max⁡dep⁡(cτ+2)≤τ+1\max\operatorname{dep}(c_{\tau+2}) \le\tau+1. Further, it is readily observed that for any ii, max⁡dep⁡(ci)\max\operatorname{dep}(c_i) is determined by the term involving gτg_\tau, and so, we have:

max⁡dep⁡(ci)≤dep⁡(gτ∣+(i−τ−1))≤(τ+i−τ−1)=i−1.\max\operatorname{dep}(c_i) \le\operatorname{dep}(g_{\tau|+(i-\tau-1)}) \le(\tau+i-\tau-1)=i-1.

This proves the assertion.

We now present the main theorem of this subsection, which explicitly confirms the design of the transformed non-linear output function as well as the choice of input which achieves equivalence of the output bitstreams before and after a Fibonacci-uniform Galois transformation. Some new notation is introduced for this purpose as follows.

Let a function FF in, say, nn Boolean variables x0,…,xn−1x_0,\ldots,x_{n-1}, be denoted as: F(X)=F(x0,…,xn−1)F(X)=F(x_0,\ldots,x_{n-1}). If these variables are iteratively compensated (in descending order of the indices) by some array C=[c0,c1,…,cn−1]C=[c_0,c_1,\ldots,c_{n-1}], where each cic_i is a Boolean function in XX, the form obtained from FF is termed the iteratively compensated FF. We denote the iteratively compensated function with the superscript ι\iota as FιF^{\iota}. Similarly, if the variables are compensated by direct XORing with the entries in CC - what has been termed simple compensation - the compensated function form has the superscript σ\sigma: FσF^{\sigma}.

If the function FF is evaluated at some modified value of XX, where each xix_i component has been iteratively compensated as described above, the evaluation is denoted as F(Xι)F(X^{\iota}), with the analogous form for simple compensation of XX denoted by F(Xσ)F(X^{\sigma}).

A combination of these compensation operations, where both the function and the argument have been compensated, will carry both the superscripts. For instance, an iteratively compensated function FF evaluated on simple compensated argument XX will be denoted by Fι(Xσ)F^{\iota}(X^{\sigma}).

Using the above notation, we now state a result which settles the question of the correct choice of the compensation operations for the output function and initial state to achieve matching output bitstreams for Fibonacci to uniform Galois NFSR transformation.

Theorem 7. For Fibonacci-to-Uniform Galois NFSR transformations according to the D-Y-P framework, any choice of compensation for the output function and the initial state will produce matching output bitstreams before and after transformation. In particular, denoting the Fibonacci output function as ff and the Fibonacci initial state as XX, we have, using the notation defined above, the following equalities:

fι(Xσ)=fσ(Xι)=fι(Xι)=fσ(Xσ)=f(X)f^{\iota}(X^{\sigma}) = f^{\sigma}(X^{\iota}) = f^{\iota}(X^{\iota}) = f^{\sigma}(X^{\sigma}) = f(X)

Proof. We prove the theorem in two parts as follows:

  1. fι(Xσ)=fσ(Xι)=f(X)f^{\iota}(X^{\sigma}) = f^{\sigma}(X^{\iota}) = f(X);

  2. fι(Xι)=f(X)f^{\iota}(X^{\iota}) = f(X) and fσ(Xσ)=f(X)f^{\sigma}(X^{\sigma}) = f(X).

Part 1.: Consider X1=(x0,x1)X_1 = (x_0, x_1), where the subscript corresponds to the maximum index in the list of variables. By Lemma 4, the corresponding entries of the compensation list are specified as follows: c0c_0 is a constant and c1=c1(x0)c_1 = c_1(x_0). Therefore, we have:

fσ(X1)=f(x0⊕c0,x1⊕c1(x0))fσ(X1ι)=f((x0⊕c0)⊕c0,(x1⊕c1(x0⊕c0))⊕c1(x0⊕c0))=f(x0,x1).\begin{aligned} f^{\sigma}(X_1) &= f(x_0 \oplus c_0, x_1 \oplus c_1(x_0)) \\ f^{\sigma}(X_1^{\iota}) &= f((x_0 \oplus c_0) \oplus c_0, (x_1 \oplus c_1(x_0 \oplus c_0)) \oplus c_1(x_0 \oplus c_0)) \\ &= f(x_0, x_1). \end{aligned}

Similarly,

fι(X1)=f(x0⊕c0,x1⊕c1(x0⊕c0))fι(X1σ)=f((x0⊕c0)⊕c0,(x1⊕c1(x0))⊕c1((x0⊕c0)⊕c0))=f(x0,x1⊕c1(x0)⊕c1(x0))=f(x0,x1).\begin{aligned} f^{\iota}(X_1) &= f(x_0 \oplus c_0, x_1 \oplus c_1(x_0 \oplus c_0)) \\ f^{\iota}(X_1^{\sigma}) &= f((x_0 \oplus c_0) \oplus c_0, (x_1 \oplus c_1(x_0)) \oplus c_1((x_0 \oplus c_0) \oplus c_0)) \\ &= f(x_0, x_1 \oplus c_1(x_0) \oplus c_1(x_0)) \\ &= f(x_0, x_1). \end{aligned}

Hence, we have: fσ(X1l)=fl(X1σ)=f(X1)f^\sigma(X_1^l) = f^l(X_1^\sigma) = f(X_1). We prove the result by induction on ii, where Xi=(x0,x1,…,xi)X_i = (x_0, x_1, \ldots, x_i).

Assume, as induction hypothesis, that the result holds for all i≤k−1i \leq k - 1. We will prove the result holds for i=ki = k, i.e.

fσ(Xkl)=fl(Xkσ)=f(Xk).(16)f^\sigma(X_k^l) = f^l(X_k^\sigma) = f(X_k). \tag*{(16)}

The form of the function is compensated first and then the argument is compensated prior to evaluation. Hence, it can be verified that

fl(Xk−1σ)=f((x0l)σ,…,(xk−1l)σ)f^l(X_{k-1}^\sigma) = f((x_0^l)^\sigma, \ldots, (x_{k-1}^l)^\sigma)

with an analogous expansion for fσ(Xk−1l)f^\sigma(X_{k-1}^l). Either way, the result in Equation 17 is proved if the following holds, making use of the induction hypothesis:

(xkσ)l=(xkl)σ=xk given (Xiσ)l=(Xil)σ=Xi, ∀i≤k−1.(x_k^\sigma)^l = (x_k^l)^\sigma= x_k \text{ given } (X_i^\sigma)^l = (X_i^l)^\sigma= X_i,\ \forall i \leq k - 1.

We have:

(xkl)l=(xk⊕ck(Xk−1))l=xkl⊕ck(Xk−1l)=xk⊕ck(Xk−1l)⊕ck(Xk−1l)=xk.\begin{aligned} (x_k^l)^l &= (x_k \oplus c_k(X_{k-1}))^l \\ &= x_k^l \oplus c_k(X_{k-1}^l) \\ &= x_k \oplus c_k(X_{k-1}^l) \oplus c_k(X_{k-1}^l) \\ &= x_k. \end{aligned}

On the other hand,

(xkl)σ=(xk⊕ck(Xk−1l))σ=(xk⊕ck(Xk−1))⊕ck((Xk−1l)σ)=xk⊕ck(Xk−1)⊕ck(Xk−1) (by induction)=xk.\begin{aligned} (x_k^l)^\sigma&= (x_k \oplus c_k(X_{k-1}^l))^\sigma\\ &= (x_k \oplus c_k(X_{k-1})) \oplus c_k((X_{k-1}^l)^\sigma) \\ &= x_k \oplus c_k(X_{k-1}) \oplus c_k(X_{k-1}) \text{ (by induction)} \\ &= x_k. \end{aligned}

Hence the equalities in Equation 17 hold.

Part 2.: Consider evaluation of fl(X1l)f^l(X_1^l) in two stages as follows. First we compute the form of the iteratively compensated function (in descending order):

fl(X1)=f(x0l,x1l)=f(x0⊕c0,x1⊕c1(x0⊕c0))f^l(X_1) = f(x_0^l, x_1^l) = f(x_0 \oplus c_0, x_1 \oplus c_1(x_0 \oplus c_0))

Next we evaluate the above compensated function on an iteratively compensated argument, i.e. replacing all the variables in the above expression with iteratively compensated variable forms in descending order. Therefore, we have:

fl(X1)→x1→x1lf(x0⊕c0,(x1⊕c1(x0⊕c0))⊕c1(x0⊕c0))=f(x0⊕c0,x1)→x0→x0lf((x0⊕c0)⊕c0,x1)=f(x0,x1)=fl(X1).\begin{aligned} f^l(X_1) \xrightarrow{x_1 \to x_1^l}{}& f(x_0 \oplus c_0, (x_1 \oplus c_1(x_0 \oplus c_0)) \oplus c_1(x_0 \oplus c_0)) = f(x_0 \oplus c_0, x_1) \\ \xrightarrow{x_0 \to x_0^l}{}& f((x_0 \oplus c_0) \oplus c_0, x_1) = f(x_0, x_1) \\ &= f^l(X_1). \end{aligned}

In the same manner as computed above for k=1k = 1, the first pass involving the iterative compensation of the argument in fl(Xk)f^{l}(X_k), for any positive integer k≤n−1k \le n - 1, will be:

fl(Xk)→xk→xklf(Xk−1l,(xk⊕ck(Xk−1l))⊕ck(Xk−1l))=f(Xk−1l,xk).f^{l}(X_k) \xrightarrow{x_k \to x_k^{l}} f\left(X_{k-1}^{l},(x_k \oplus c_k(X_{k-1}^{l})) \oplus c_k(X_{k-1}^{l})\right) = f(X_{k-1}^{l},x_k).

Therefore, the successive passes for the iterative compensation of the argument will clearly return

fl(Xkl)=f(Xk).f^{l}(X_k^{l}) = f(X_k).

Finally, we have:

fσ(X1σ)=f(x0σ⊕c0,x1σ⊕c1)=f((x0⊕c0)⊕c0,(x1⊕c1)⊕c1)=f(x0,x1)\begin{aligned} f^{\sigma}(X_1^{\sigma}) &= f(x_0^{\sigma} \oplus c_0,x_1^{\sigma} \oplus c_1) \\ &= f((x_0 \oplus c_0) \oplus c_0,(x_1 \oplus c_1) \oplus c_1) \\ &= f(x_0,x_1) \end{aligned}

which is readily extended from k=1k = 1 to any positive integer k≤n−1k \le n - 1:

fσ(Xkσ)=f(Xk).f^{\sigma}(X_k^{\sigma}) = f(X_k).

Hence the theorem.

In view of the results in Theorem 7, we now have sufficient clarity as regards the D-Y-P Fibonacci-to-uniform Galois NFSR transformation for choosing either iterative or simple compensation for the original output function as well as the original initial state to produce matched output bitstreams post transformation.

Our experimental results in the next subsection further corroborate the statement of Theorem 7, which removes all ambiguity regarding the steps of this particular NFSR transformation.

Experimental Results

In [16], a 256-bit Fibonacci LFSR was derived from the Espresso design NFSR GG using (Dubrova-Yao-Parampalli) uniform Galois-to-Fibonacci transformation. The transformation generated a counterpart to the non-linear output function defined for Espresso which had 2289 monomials in 104 variables and degree 12. It was claimed that this LFSR/non-linear function ensemble, following the recipe of simple compensation of the output function and iterative compensation of the initial state ([16], [17]), generated identical bitstreams with Espresso. We have experimentally verified this claim, which is depicted in the left halves of the schematics in Figure 2 and Figure 3.

Figure 3. Resolving the Espresso Equivalence Problem

Building on the verified claim in [16], we have successfully used the D-Y-P Fibonacci-to-uniform Galois transformation on the LFSR-based ensemble to generate a non-linear output function corresponding to the Espresso alternate Galois NFSR FF (cf. Algorithm 1). Our non-linear function consists of 3656 monomials in 88 variables and has algebraic degree 18. This NFSR FF/non-linear function ensemble generates identical output bitstream, using iterative compensation of the output function and simple compensation of the initial state (cf. [17]), with the Fibonacci LFSR/non-linear function ensemble in [16].

Further, in accordance with the results in Theorem 7, we have verified that the output bitstream of our NFSR FF -based ensemble matches the Yao-Parampalli LFSR-based ensemble using both simple and iterative compensation separately on their output function and the LFSR initial state.

We have, therefore, positively resolved the Espresso Equivalence Problem as stated in § 5 (cf. Figure 1), by generating a non-linear output function corresponding to the Espresso alternate NFSR FF which ‘inherits’ the equivalence with the original Espresso design through the following steps:

  1. Espresso Galois NFSR GG ensemble is output-equivalent to Yao-Parampalli Fibonacci LFSR ensemble

  2. Yao-Parampalli Fibonacci LFSR ensemble is output-equivalent to Espresso NFSR FF ensemble (this paper).

  3. Therefore, Espresso Galois NFSR GG ensemble is output-equivalent to Espresso NFSR FF ensemble.

This is graphically depicted in Figure 3.

Conclusion and Future Work

The design methodology of the stream cipher Espresso is theoretically significant as well as of practical interest as it attempts to harness the benefits of a Galois NFSR-based implementation while promising simpler analysis through an equivalent design. But the validity of its security claims against several standard cryptanalytic techniques rested on the equivalence of two designs discussed in [7]. We have termed this the Espresso Equivalence Problem and have demonstrated the first instance for its positive resolution.

In order to demonstrate the said equivalence, we have attempted a partial unification of E. Dubrova and Yao-Parampalli’s transformation techniques. The insights obtained from the above analysis led us to recover the Espresso alternate NFSR FF from the Y-P LFSR, and, finally, a matching non-linear function for FF. This has opened up the possibility of revisiting the security of Espresso through a proper analysis of the now truly output-equivalent alternate NFSR FF and non-linear function ensemble. However, it remains an open question whether the two output-equivalent versions will provide any significant advantage in analysis, as evident from the following list of properties:

  • Espresso: [7] Galois NFSR GG with 14 non-linear taps; Output function: 14 monomials, 20 variables, algebraic degree 6.

  • Y-P Design: [16] Fibonacci LFSR; Output function: 2289 monomials, 104 variables, algebraic degree 12.

  • Espresso Equivalent: (this paper) Galois NFSR FF with 2 non-linear taps; Output function: 3656 monomials, 88 variables, algebraic degree 18.

In course of establishing the Espresso equivalence, we have demonstrated that (cf. Theorem 7), for the Fibonacci-to-uniform Galois transformation, either compensation procedure applied to the output function-initial state would suffice to match the output. This assertion has also been verified by our experiments. However, this begs the obvious question:

Why is the sequence of compensation operations applied in [17], with respect to Fibonacci-to-uniform Galois transformation, to the output function and the initial state, interchanged for the uniform Galois-to-Fibonacci case?

The answer to the above question may lie in formulating and proving analogous results of Lemma 1, Lemma 2, and Theorem 6 for the case of uniform Galois-to-Fibonacci case. Further, in addition to the Fibonacci-uniform Galois transformation, three other NFSR designs have been discussed in [17]. However, as stated earlier, rigorous proof of concept has only been provided for Fibonacci-to-uniform Galois case. Proving (or disproving) the (output) equivalence in all these cases would be a worthwhile research direction.

Recently, there is a growing body of research on NFSR equivalence, for instance, [18], [19] and [13]. In [19], the authors claim to establish that the 288-stage Galois NFSR of Trivium cannot be shown to be equivalent to a 288-stage Fibonacci NFSR. We hope that further investigation would lead to the creation of a general template for equivalence-preserving shift register transformations. Such a template, if rigorously formulated, would open up the exciting possibility of obtaining equivalent circuits for existing designs of proven security like Grain and Trivium, and possibly identify variants with optimized implementation.

Acknowledgement The assistance of Debendranath Das with initial experimental verifications and the inputs from Subhamoy Maitra, Mridul Nandi and Sabyasachi Karati are gratefully acknowledged. The work of Anirban Ghatak is supported by SAG, DRDO, Delhi, and R. C. Bose Centre for Cryptology and Security, ISI, Kolkata.

References

  1. [1]Carlet, C., Sarkar, P.: The nonlinear filter model of stream cipher redivivus. Cryptology ePrint Archive, Paper 2025/160 (2025), https://eprint.iacr.org/2025/160arxiv.org/abs/2502.01110
  2. [2]De Cannière, C.: Trivium: A stream cipher construction inspired by block cipher design principles. In: Katsikas, S.K., López, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) Information Security. pp. 171–186. Springer Berlin Heidelberg, Berlin, Heidelberg (2006). https://doi.org/10.1007/11836810_13
  3. [3]Dubrova, E.: A Transformation From the Fibonacci to the Galois NLFSRs. IEEE Transactions on Information Theory 55(11), 5263–5271 (2009). https://doi.org/10.1109/TIT.2009.2030467
  4. [4]Dubrova, E.: Finding matching initial states for equivalent NLFSRs in the Fibonacci and the Galois configurations. IEEE transactions on information theory 56(6), 2961–2966 (2010). https://doi.org/10.1109/TIT.2010.2046250
  5. [5]Dubrova, E.: A Scalable Method for Constructing Galois NLFSRs With Period 2^{n−1} Using Cross-Join Pairs. IEEE Transactions on Information Theory 59(1), 703–709 (2012). https://doi.org/10.1109/TIT.2012.2214204
  6. [6]Dubrova, E.: An equivalence-preserving transformation of shift registers. In: International Conference on Sequences and Their Applications. pp. 187–199. Springer (2014). https://doi.org/10.1007/978-3-319-12325-7_16
  7. [7]Dubrova, E., Hell, M.: Espresso: A stream cipher for 5G wireless communication systems. Cryptography and Communications 9, 273–289 (2017). https://doi.org/10.1007/s12095-015-0173-2
  8. [8]Ghatak, A., Chattopadhyay, A., Awasthi, A., Gupta, I.: Analyzing non-linear shift register transformations in the design and cryptanalysis of espresso. In: Karfa, C., Asadi, N., Chattopadhyay, A. (eds.) Security, Privacy, and Applied Cryptography Engineering. pp. 171–190. Springer Nature Switzerland, Cham (2026). https://doi.org/10.1007/978-3-032-16342-4_10
  9. [9]Golomb, S.W.: Shift register sequences: secure and limited-access code generators, efficiency code generators, prescribed property generators, mathematical models. World Scientific (2017). https://doi.org/10.1142/9361
  10. [10]Hamann, M., Krause, M., Meier, W.: LIZARD - A Lightweight Stream Cipher for Power-Constrained Devices. IACR Transactions on Symmetric Cryptology 2017(1), 45–79 (Mar 2017). https://doi.org/10.13154/tosc.v2017.i1.45-79
  11. [11]Hell, M., Johansson, T., Maximov, A., Meier, W.: The Grain family of stream ciphers, pp. 179–190. Springer, Germany (2008). https://doi.org/10.1007/978-3-540-68351-3_14
  12. [12]Mansouri, S.S., Dubrova, E.: An Improved Hardware Implementation of the Grain Stream Cipher. In: 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools. pp. 433–440 (2010). https://doi.org/10.1109/DSD.2010.49
  13. [13]Pan, Y., Zhong, J., Lin, D.: The equivalence between Galois and Fibonacci NF-SRs. Theoretical Computer Science 1003 (2024). https://doi.org/10.1016/j.-tcs.2024.114620
  14. [14]Shi, Z., Chen, C., Yang, G., Xiong, H., Li, F., Hu, H., Wan, Z.: Design Space Exploration of Galois and Fibonacci Configuration Based on Espresso Stream Cipher. ACM Trans. Reconfigurable Technol. Syst. 16(3) (Jun 2023). https://-doi.org/10.1145/3567428DOI
  15. [16]Yao, G., Parampalli, U.: Cryptanalysis of the class of maximum period Galois NLFSR-based stream ciphers. Cryptography and Communications 13, 847–864 (2021). https://doi.org/10.1007/s12095-021-00511-0
  16. [17]Yao, G., Parampalli, U.: Improved transformation algorithms for generalized Galois NLFSRs. Cryptography and Communications 14(2), 229–258 (2022). https://-doi.org/10.1007/s12095-021-00500-3DOI
  17. [18]Zhao, X.X., Qi, W.F., Zhang, J.M.: Further results on the equivalence between Galois NFSRs and Fibonacci NFSRs. Designs, Codes and Cryptography 88, 153–171 (2020). https://doi.org/10.1007/s10623-019-00677-y
  18. [19]Zhong, J., Pan, Y., Kong, W., Lin, D.: Necessary and Sufficient Conditions for Galois NFSRs Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium. Cryptology ePrint Archive (2021), https://eprint.iacr.org/2021/928

Paper details

vlnc:W_ucqjbhh9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents