Cascade connection architectures of nonlinear feedback shift registers (NFSRs) have been widely used as the main components in the design of cryptographic algorithms, such as the Grain family of stream ciphers. It is known that the cascade connection of ann-stage NFSR into anm-stage NFSR is equivalent to an (n+m)-stage NFSR. However, the converse problem on decomposing an NFSR into the cascade connection of two smaller NFSRs has not been well addressed, which can be transformed to decomposing the characteristic functionhof the NFSR into the formh=f*gfor some nonlinearf,g, where “*” is a special composition of Boolean functions. In this paper, we present a complete and efficient method for such decomposition problem based on previous works. The framework of the decomposition consists of two steps. The first is to construct a candidate set forgas precise as possible, and the second is to verify each candidategand recover the correspondingf. We propose the notion of *-multiples of Boolean functions, and present three ways to take derivatives ofhto extract the low-degree *-multiples ofg, which are useful to determinegefficiently. Compared to existing methods, the new approach can provide a very small candidate set forgin most cases, with the size beingO(deg(h)), thereby achieving lower and more stable time costs in determining whetherhis *-reducible and enumerating all pairs (f,g) such thath=f*g(if it is *-reducible). Moreover, we show that the decomposition method also applies to shift-invariant maps, by establishing a connection between the *-product of Boolean functions and the composition of shift-invariant maps.

Nonlinear feedback shift registers (NFSRs) are an important building blocks in the design of stream ciphers over the past years. An NFSR is vulnerable to cryptanalysis if there are output sequences with low linear complexities. In this paper, we present a method to find output sequences of an NFSR with low linear complexities from a new perspective. Let f be the characteristic function of an NFSR, and let$f_{L}$be the linear part of f. First, we present some theoretical results in order to find sequences$\underline {a}\in G(f_{L})$such that$\underline {a}\in G(f)$. In particular, it is shown that if$f_{L}$has divisors of the form$g(x^{d})$, then$G(f)$is more likely to have linear sequences. Then, we introduce two kinds of isomorphisms of NFSRs which could be used to find more potential linear sequences in$G(f)$. Such isomorphisms induce a close relationship among the linear structures of NFSRs, whose realization relies on a type of decomposition of Boolean functions. As a generalization, we propose a framework to analyze the linear structure of a Galois NFSR. The idea is to focus on the Galois LFSR derived from the Galois NFSR by removing the nonlinear part, which can be transformed into an equivalent Fibonacci LFSR. Finally, we apply the results to some lightweight algorithms designed based on the cascade connections of NFSRs, and find several families of sequences generated by the main register of Lizard with linear complexities no more than 30.

Reflection structure has a significant advantage that realizing decryption and encryption results in minimum additional costs, and many block ciphers tend to adopt such structure to achieve the requirement of low overhead. PRINCE, MANTIS, QARMA, and PRINCEv2 are lightweight block ciphers with reflection feature proposed in recent years. In this paper, we consider the automatic differential cryptanalysis of reflection block ciphers based on Boolean satisfiability (SAT) method. Since reflection block ciphers have different round functions, we extend forward and backward from the middle structure and achieve to accelerate the search of the optimal differential characteristics for such block ciphers with the Matsui’s bounding conditions. As a result, we present the optimal differential characteristics for PRINCE up to 12 rounds (full round), and they are also the optimal characteristics for PRINCEv2. We also find the optimal differential characteristics for MANTIS, QARMA‐64, and QARMA‐128 up to 10, 12, and 8 rounds, respectively. To mount an efficient differential attack on such block ciphers, we present a uniform SAT model by combining the differential characteristic searching process and the key recovery process. With this model, we find two sets of 7‐round differential characteristics for PRINCE with less guessed key bits and use them to present a multiple differential attack against 11‐round PRINCE, which improves the known single‐key attack on PRINCE by one round to our knowledge.

LBlock is a lightweight block cipher with Feistel‐SP structure proposed by Wu and Zhang in Applied Cryptography and Network Security 2011, and a modified version LBlock‐s is used later in the design of the lightweight authenticated encryption cipher LAC, one of the CAESAR candidates. The best known integral attack on LBlock is presented by Zhang and Wu which can attack 23‐round LBlock based on a 16‐round integral distinguisher found with division property. In Selected Areas in Cryptography 2018, Eskandari et al . further presented a 17‐round integral distinguisher of LBlock with bit‐based division property using SAT solver. Using their method, the authors further find some new 17‐round integral distinguishers of LBlock and use one of them to present a 24‐round integral attack on LBlock. Similarly, they also find some 17‐round integral distinguishers of LBlock‐s and select one to present a 24‐round integral attack on LBlock‐s. In this way, they have improved known single‐key attacks on LBlock and LBlock‐s by one round.

In this paper, a new and efficient method for solving affine sub-families included in a family of nonlinear feedback shift register (NFSR) sequences is proposed. The linear case is focused on since the affine case is an analogy. Let f(x0,x1,...,xn) = x0⊕f1(x1,...,xn-1)⊕xnbe a characteristic function of an n-stage NFSR, where n is a positive integer. Let deg(f) = d > 1 and f[d]be the summation of all terms in the algebraic normal form of f whose degrees attain the maximum d. First, it is proved that every linear sub-family of G(f) is a sub-family of linear feedback shift register sequences generated by a characteristic polynomial of the form Σi∈Scixi, where ci∈ F2and S consists of all subscripts of variables appearing in f[d]. That is to say, every linear sub-family of G( f ) is a factor of some polynomial Σi∈Scixiover the finite field F2. This result is a well generalization of linear recurring sequences theory since it also holds if d = 1. Based on this result, a candidate set of linear sub-families could be obtained by polynomial factorizations over F2. Second, we propose a new method to verify a linear sub-family whose memory requirement and time complexity are clearer than the previous method. For instance, all affine sub-families of the 160-bit main register used in Grain v1 could be determined within two seconds by a PC using the new method in this paper, which is unobtainable for previous algorithms.

Truncated differential attack (TDA) proposed by Knudsen in Fast Software Encryption 1995 (FSE'95) has been widely used in the analysis of block ciphers. In this study, the authors specifically study the security of SP block ciphers against TDA. In FSE'15, Li et al . introduced a meet‐in‐the‐middle technique to construct truncated differential for Feistel ciphers. They first apply Li's technique to SP block ciphers and get some further results. Second, they introduce the concept of generalised truncated difference to control the diffusion of active S‐boxes in the truncated differential. On the basis of these, two 5‐round truncated differential distinguishers for mCrypton and CRYPTON V1.0 have been constructed. Using these two 5‐round distinguishers, they present the first 8‐round DA on mCrypton‐64 and improve the former best TDA on CRYPTON V1.0 by one round.

Grain-128 is a hardware oriented stream cipher based on the cascade connection of a 128-bit linear feedback shift register into a 128-bit quadratic nonlinear feedback shift register (NFSR). Its main register is in essence a quadratic NFSR, however its affine sub-families could not be solved by the previous methods. In this paper, it is shown that the family of sequences generated by the main register of Grain-128 includes no affine sub-families except a small one of order three. To achieve this goal, a new method is proposed for solving affine sub-families of general quadratic NFSRs. Let NFSR(f) be an NFSR with a quadratic characteristic function f . It is proved that the characteristic function of a linear sub-family of the NFSR(f) divides a linear combination of variables appearing in the quadratic terms of f , where the division can be seen as the univariate polynomial division over the finite field F2. This facilitates picking up a candidate set of linear sub-families through univariate polynomial factorization over F2. The affine case is an analogy. Besides, a useful new upper bound on the orders of affine sub-families of a quadratic NFSR is given.

Conditional differential cryptanalysis on NFSR‐based cryptosystems was first proposed by Knellwolf et al . in Asiacrypt 2010 and has been successfully used to attack reduced variants of Grain v1. In this paper, we greatly improve conditional differential attacks on Grain v1 in the following four aspects. First, a new differential engine is derived to correctly track the differential trails of Grain v1. Second, we propose a new difference‐searching strategy which serves to find suitable differences for the conditional differential attack on a given reduced variant of Grain v1. Third, a highly IV‐saving condition‐imposing strategy is presented. Last, we propose a further bias‐increasing strategy. In particular, the improvements on the difference‐searching strategy and the condition‐imposing strategy are crucial to mount conditional differential attacks on the variants of Grain v1 with more than 106 rounds. It is shown that the improved conditional differential attacks could retrieve 31 distinct secret key expressions for 107‐round Grain v1 and could retrieve 15 distinct secret key expressions for 110‐round Grain v1. Both the attacks succeed with constant probabilities. Thus far, our results are the best known for the reduced variants of Grain v1 as far as the number of rounds attacked is concerned.

The well‐known stream cipher Grain‐128a is the new version of Grain‐128. While Grain‐128 is vulnerable against several introduced attacks, Grain‐128a is claimed to be secure against all known attacks and observations on Grain‐128. So far the only published single‐key attack on Grain‐128a is the conditional differential cryptanalysis proposed by Michael Lehmann et al . at CANS 2012. In their analysis, a distinguishing attack on 189‐round Grain‐128a in a weak‐key setting was proposed. In this study, the authors present two new conditional differential attacks on Grain‐128a, i.e. attack A and attack B. In attack A, the authors successfully retrieve 18 secret key expressions for 169‐round Grain‐128a. To the best of our knowledge, attack A is the first attack to retrieve secret key expressions for reduced Grain‐128a. In attack B, the authors extend the distinguishing attack against Grain‐128a up to 195 rounds in a weak‐key setting. Thus far, attack B is the best known attack for reduced Grain‐128a as far as the number of rounds attacked is concerned. Hopefully, the authors’ reflections on the design of Grain‐128a provide insights on such compact stream ciphers.

The well‐known stream cipher Grain v1 is one of the finalists of European eSTREAM project. In this study, a novel guess‐and‐determine attack on Grain v1 is introduced. The attack primarily employs a new conditional BSW sampling technique and the main creative idea is that the conditions are set not only on state bits but also on the updates of the registers for the BSW sampling technique. It is shown that using this technique we can further reduce the sampling resistance of Grain v1 to which is the best result so far. The attack leads to an efficient internal state recovery of Grain v1 with only online time employing a memory of , requiring keystreams each of length and preprocessing time. It is shown that these figures are obviously better compared with the previous results. This is also the first attempt to control the updates of the registers of Grain v1 in the guess‐and‐determine attack and hopefully this provides new insights for cryptanalysis on such compact stream ciphers.

SKINNY is a family of lightweight block ciphers proposed at CRYPTO 2016, which follows the TWEAKEY framework and takes a tweakey input. It is shown that SKINNY family not only has good hardware/software performances, but also provides strong security guarantees against differential/linear cryptanalysis. In this study, the authors study the security of SKINNY against the impossible differential attack. First, they get some properties of the subkeys of SKINNY by analysing its key schedule. Then, combining with the early‐abort technique and the greedy strategy, they present impossible differential attacks on SKINNY based on an 11‐round impossible differential. Let SKINNY‐ n ‐ k be the SKINNY cipher with n ‐bit block size and k ‐bit tweakey size. On the basis of their method, 17‐round SKINNY‐64‐64 (resp. SKINNY‐128‐128) can be broken in (resp. ) 17‐round encryptions, 19‐round SKINNY‐64‐128 (resp. SKINNY‐128‐256) can be broken in (resp. ) 19‐round encryptions and 21‐round SKINNY‐64‐192 (resp. SKINNY‐128‐384) can be broken in (resp. ) 21‐round encryptions. To the best of their knowledge, these results are currently the best results with respect to the attacked rounds.

The Feistel‐2 cipher is a type of Feistel ciphers proposed by Isobe and Shibutani at Asiacrypt 2013. Its round functions consist of a public F ‐function and a subkey XORed before the F ‐function. Recently, a variation of the Feistel‐2 cipher, in which the subkey is XORed after the F ‐function, has been widely used in proposals such as SIMON and Simeck. The authors denote this type of Feistel ciphers as Feistel‐2. In this study, they study the security of Feistel‐2* ciphers. First, they propose the differential function reduction technique. Then, they present all‐subkeys‐recovery attacks against Feistel‐2* ciphers based on this technique. Let z be the key size to block size ratio of block ciphers. It is shown that their attacks can break up 6, 8 and 10 rounds of the Feistel‐2* cipher for z = 1, 3/2 and 2, respectively. Thanks to the meet‐in‐the‐middle approach, their attacks only need a few chosen plaintexts. Moreover, with higher‐data complexity, all attacks can be improved by one round. This implies that a secure Feistel‐2* cipher should at least iterate 8, 10 and 12 rounds for z = 1, 3/2 and 2, respectively.

Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher design as building blocks. In this paper, we study the problem of decomposing an NFSR into the cascade connection of an NFSR into a linear feedback shift register (LFSR), which is a kind of concatenation of an NFSR and LFSR. A necessary and sufficient condition for such decomposition is provided and other algebraic properties about such decomposition are also studied. Based on these theoretical results, a binary decision diagram (BDD)-based algorithm for such decomposition is proposed. Compared with the previous algorithm proposed by Ma et al., our algorithm can find more accurate candidate LFSR and the algebraic properties presented in this paper guarantee that the memory requirement during our verification is linear in the size of the BDD of the NFSRs characteristic function.

Letnbe a positive integer. An NFSR ofnstages is called irreducible if the family of output sequences of any NFSR of stages less thannis not included in that of the NFSR. In this paper, we prove that the density of the irreducible NFSRs ofnstages is larger than 0.39. This implies that it is expected to find an irreducible NFSR ofnstages among three randomly chosen NFSRs ofnstages.

This paper studies the distinctness of primitive sequences overZ/(M) modulo 2, whereMis an odd integer that is composite and square-free, andZ/(M) is the integer residue ring moduloM. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomialf(x) overZ/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper, and consequently, the set of primitive sequences overZ/(M) that can be proven to be distinct modulo 2 is greatly enlarged.

LetMbe a square-free odd integer andZ/(M) the integer residue ring moduloM. This paper studies the distinctness of primitive sequences overZ/(M) modulo 2. Recently, for the case ofM=pq, a product of two distinct prime numberspandq, the problem has been almost completely solved. As for the case thatMis a product of more prime numbers, the problem has been quite resistant to proof. In this paper, a partial proof is given by showing that a class of primitive sequences of order 2n'+1 overZ/(M) is distinct modulo 2, wheren'is a positive integer. Besides as an independent interest, this paper also involves two distribution properties of primitive sequences overZ/(M), which are related closely to our main results.

Let p be an odd prime number, e an integer greater than 1, and Z/(pe) the integer residue ring modulo pe. In this paper, we obtain an improved result of the previous paper (IEEE Trans. Inf. Theory, 56(1) (2010) 555-563) on distribution properties of compressing sequences derived from primitive sequences over Z/(pe). It is shown that two primitive sequences α and b generated by a strongly primitive polynomial f(x) over Z/(pe) are the same, if there exist s∈ Z/(p) and k∈ Z(p)* such that the distribution of in their compressing sequences ae-1+η(a0,⋯.ae-2) and be-1+η(b0,⋯,be-2) is coincident at the positions t with α(t)=k, where η(x0,⋯,xe-2) is an (e-)-variable polynomial over Z/(p) with the coefficient of xe-2p-1⋯x1p-1x0p-1not equal to (-1)e· (p+1)/2 and α is an m-sequence over Z/(p)determined by f(x) and a. Compared with the previous result, this gives a more precise characterization on the positions of a compressing sequence, i.e., of the form ae-1+η(a0,⋯,ae-2), derived from a primitive sequence a over Z/(pe) that completely determines a. In particular, the result is also true for the highest level sequence ae-1by taking η(x0,⋯,xe-2)=0.

Although 2 -adic complexity was proposed more than ten years ago, even form-sequences which are thought of as the most important linear recurring sequences, no theoretical results about their 2-adic complexity has been presented. In this paper, it is shown that for a binarym-sequence, its 2-adic complexity attains the maximum, which implies that no feedback with carry shift registers (FCSRs) with connection integer less than22n-1- 1 can generatem-sequences of ordern.

Let Z/(pe) be the integer residue ring with odd prime p and integer e ¿ 2. Any sequence a over Z/(pe) has a unique p-adic expansion a = a0+ a1· p + ··· + ae-1· pe-1, where aican be regarded as a sequence over Z/(p) for 0 ¿ i ¿ e - 1. Let f(x) be a strongly primitive polynomial over Z/(pe) and a, b be two primitive sequences generated by f(x) over Z/(pe). Assume ¿(x0,..., xe-1) = xe-1+ ¿(x0,..., xe-2) is an e-variable function over Z/(p) with the monomial (p+1)/2 xe-2p-1...x1p-1not pearing in the expression of ¿(x0,x1,..., xe-2). It is shown that if there exists an s ¿ Z/(p) such that ¿(a0(t),..., ae-1(t)) = s if and only if ¿(b0(t),..., be-1(t)) = s for all nonnegative t with ¿(i) ¿ 0, where ¿ is an m-sequence determined by f(x) and a0, then a = b. This implies that for compressing sequences derived from primitive sequences generated by f(x) over Z/(pe), single element distribution is unique on all positions t with ¿(t) ¿ 0. In particular, when ¿(x0,x1,..., xe-2) = 0, it is a completion of the former result on the uniqueness of distribution of element 0 in highest level sequences.

It has long been open whether all pairs of proper decimations of l-sequences based on primes are cyclically distinct. By determining the nontrivial maximal autocorrelation of l-sequences, this paper presents a partial proof of the distinctness problem. Since the proof idea is completely different from former ones, the set of decimations that are known to be cyclically distinct is further enlarged. On the basis of convincing experimental data, the proof seems to ensure that more than 79% of l-sequences based on different primes satisfy the fact that every pair of proper decimations is cyclically distinct. In particular, a complete proof is provided for l-sequences based on primes of the form $2\cdot r+1$, where r is an odd prime number.

In this correspondence, we introduce a method to construct Boolean functions in any number of variables, with optimal algebraic immunity. Remarkably, all functions of this type with an odd number of variables can be obtained in this way. We study some cryptographic properties, such as balancedness, algebraic degree of the constructed functions. Moreover, a lower bound of the number of Boolean functions with optimal algebraic immunity is given.

Let Zopf/(pe) be the integer residue ring with odd prime p and integer eges2. For a sequence a_ over Zopf/(pe), one has a unique p-adic expansion a_=a_0+a_1.p+...+a_(e-1).pe-1, where a_ican be regarded as a sequence over Zopf/(p) for 0lesilese-1. Let f(x) be a strongly primitive polynomial over Zopf/(pe) and G'(f(x), pe) be the set of all primitive sequences generated f(x) by over Zopf/(pe). Recently, the authors, Xuan-Yong Zhu and Wen-Feng Qi, have proved that for a function phi(x0,...,xe-1)=g(xe-1)+eta(x0,...,xe-2)over Zopf/(p) and a_,b_isinG'f(x),pe), where 2lesdeg glesp-1, phi(a_0,a_1...,a_e-1)=phi(b_0,b_1...,b_e-1) if and only if a_=b_. To further complete their work, we show that such injectivity also holds for deg g=1. That is for a function phi(x0,...,xe-1)=xe-1+eta(x0,...,xe-2)over Zopf/(p) and a_,b_isinG'f(x),pe), phi(a_0,a_1...,a_e-1)=phi(b_0,b_1...,b_e-1) if and only if a_=b_.

In this correspondence, we investigate feedback with carry shift register (FCSR) memory sequences. For an -sequence generated by an FCSR with connection integer and initial memory , we prove that for , where and is the memory sequence. Generally speaking, the period of a memory sequence is a factor of that of the FCSR output binary sequence. We show there are a large number of connection integers, with which an FCSR can generate sequences that have the same period as their memory sequences, especially including all connection integers for -sequences.

Let $\underline{a}$ be a maximum period feedback with carry shift register sequence (l‐sequence) with connection integer $q=p^e$ and period $T=p^{e-1}(p-1)$. It is shown that the expected value of its autocorrelations is 0, and its variance is $O(q\ln^{4}q)$. Thus when q is sufficiently large, with high probability, the autocorrelations are low. Furthermore, it is shown that when $e\geq2$, for any integer i, $1\leq i\leq e/2$, when the shift is a multiple of $T/2p^i$, the absolute value of the autocorrelations of $\underline{a}$ is $T/p^{2i-1}$, and the sign relies on the parity of the multiple.

To resist algebraic attacks, Boolean functions should possess high algebraic immunity. In 2003, Courtois and Meier showed that the algebraic immunity of an n-variable Boolean function is upper bounded by /spl lceil/n/2/spl rceil/. And then several papers studied how to find symmetric Boolean functions with maximum algebraic immunity. In this correspondence, we prove that for each odd n, there is exactly one trivially balanced n-variable symmetric Boolean function achieving the maximum algebraic immunity.

Let$underlinea$be an l-sequence generated by a feedback-with-carry shift register with connection integer$p^e$, where$p$is an odd prime and$egeq 1$. Goresky and Klapper conjectured that when$p^enotin 5,9,11,13$, all decimations of$underlinea$are cyclically distinct. When$e=1$and$p ≫ 13$, they showed that the set of distinct decimations is large and, in some cases, all decimations are distinct. In this article, we further show that when$egeq 2$and$p^eneq 9$, all decimations of$underlinea$are also cyclically distinct.

Klapper and Goresky (1995) introduced feedback with carry shift register (FCSR) and presented a significant kind of FCSR sequences, that is, l-sequences. They showed that the number of 0s and 1s occurring in one of their periods are equal. We discuss the partial period distribution of l-sequences, and show that when the periods become large, the proportion of 1s (resp., 0s) occurring in any of their partial periods approximates 50%.