This paper investigates well-known conjectures in Boolean function analysis, specifically focusing on the Fourier Min-Entropy/Influence (FMEI) conjecture, a natural relaxation of the more established Fourier Entropy/Influence (FEI) conjecture. While the FEI conjecture proposes that the Fourier entropy of a Boolean function is bounded by a constant multiple of its total influence, the FMEI conjecture substitutes entropy with min-entropy. We present a construction of Boolean functions that establishes a new lower bound on the universal constant of the FMEI conjecture. By employing the Generalized Maiorana-McFarland construction with suitably chosen injective mappings, we construct Boolean functions whose FMEI value surpasses the previous bound 2.8444. Specifically, our construction can yield functions demonstrating an FMEI value strictly less than 4 but arbitrarily close to 4, and we provide the conditions for the FMEI value to exceed 3. Furthermore, we investigate other classes of plateaued functions, such as partially bent functions and the Address functions, and prove that relaxing the injective constraint in the Generalized Maiorana-McFarland construction cannot increase the FMEI value. Thereby, it provides new insights toward understanding of the FMEI conjecture.

In this paper, we propose the Differential Fault Attack (DFA) on three Homomorphic Encryption (HE) friendly stream ciphers Masta, Pasta, and Elisabeth. Both Masta and Pasta are Rasta-like ciphers with publicly derived and pseudo-random affine layers. The design of Elisabeth is an extension of FLIP and FiLIP, following the group filter permutator paradigm. All these three ciphers operate on elements over ℤpor ℤ2n, rather than ℤ2. We can recover the secret keys of all the targeted ciphers through DFA. In particular, for Elisabeth, we present a new method to determine the filtering path, which is vital to make the attack practical. Our attacks on various instances of Masta are practical and require only one block of keystream and a single word-based fault. By injecting three word-based faults, we can theoretically mount DFA on two instances of Pasta, Pasta-3 and Pasta-4. For Elisabeth-4, the only instance of the Elisabeth family, we present two DFAs in which we inject four bit-based faults or a single word-based fault. With 15000 normal and faulty keystream words, the DFA on Elisabeth-4 can be completed in just a few minutes.

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.

Let$n=2m$. In 2020, Budaghyan, Helleseth and Kaleyski [IEEE TIT 66(11): 7081-7087, 2020] considered a family of quadrinomials over$\mathbb {F}_{2^{n}}$of the form$x^{3}+a(x^{2^{s}+1})^{2^{k}}+bx^{3\cdot 2^{m}}+c(x^{2^{s+m}+2^{m}})^{2^{k}}$. They showed that two infinite classes of almost perfect nonlinear (APN) functions belong to this family when$\gcd (6,m)=1$. We observe that these two infinite classes of APN quadrinomials and the infinite class of APN polynomials from the Budaghyan-Carlet family belong to a more general family of polynomials over$\mathbb {F}_{2^{n}} $with the form$f(x)=a{\mathrm{ Tr}}^{n}_{m}(F(x))+a^{2^{m}}{\mathrm{ Tr}}^{n}_{m}(G(x))$, where$a \in \mathbb {F}_{2^{n}}\backslash \mathbb {F}_{2^{m}} $, and both$F$and$G$are quadratic functions over$\mathbb {F}_{2^{n}}$. We characterize when$f(x) $is APN. With the help of our characterization, letting$F(x)=bx^{2^{i}+1} $and$G(x)=cx^{2^{s}+1}$with$b, c\in \mathbb {F}_{2^{n}} $, we obtain an infinite family of APN functions of the form$f(x) $when${\mathrm{ gcd}}(2,m)=1 $and verify that for$n=10 $two APN instances from this infinite family are CCZ-inequivalent to each other, and to any APN function over$\mathbb {F}_{2^{10}} $from the previously known infinite families.

Constructing S-boxes that are inherently resistant against side-channel attacks is an important problem in cryptography. By using an optimal distinguisher under an additive Gaussian noise assumption, we clarify how a defender (resp., an attacker) can make side-channel attacks as difficult (resp., easy) as possible, in relation with the auto-correlation spectrum of Boolean functions. We then construct balanced Boolean functions that are optimal for each of these two scenarios. Generalizing the objectives for an S-box, we analyze the auto-correlation spectra of some well-known S-box constructions in dimensions at most 8 and compare their intrinsic resiliency against side-channel attacks. Finally, we perform several simulations of side-channel attacks against the aforementioned constructions, which confirm our theoretical approach.

Very recently, a class of cryptographically significant Boolean functions were constructed by Tang and Maitra [ IEEE Trans. Inform. Theory, 64 (2018), pp. 393--402] by modifying the $\mathcal{PS}_{ap}$ class of bent functions. The basic ideas used in Tang--Maitra construction were derived from a modification of a subclass of bent functions which is defined over the finite field, and a concern was raised in the same paper whether the implementation of such functions will be as efficient as that of Maiorana--McFarland type bent functions. In this paper, we look at the concrete realization of such functions over a vector space and answer the question positively. The first part of this paper investigates how the finite field implementation of the functions can be viewed as simple truth tables. Next, we present a completely new construction that itself starts from Maiorana--McFarland bent functions which are straightforward concatenations of linear functions.

In this paper, we consider the maximum absolute value Δfin the autocorrelation spectrum (not considering the zero point) of a function f. In an even number of variables n, bent functions possess the highest nonlinearity with Δf= 0. The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with Δfn/2. So far, there are only a few examples of such functions for n = 10, 14, but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on n variables having absolute indicator strictly lesser than δn= 2n/2- 2((n+6)/4), nonlinearity strictly greater than ρn= 2n-1-2n/2+2n/2-3-5·2((n-2)/4)and algebraic degree n - 1, where n ≡ 2 (mod 4) and n ≥ 46. While the bound n ≥ 46 is required for proving the generic result, our construction starts from n = 18, and we could obtain balanced functions with Δfn/2and nonlinearity > 2n-1- 2n/2for n = 18, 22, and 26.

In 2013, Tang, Carlet, and Tang [IEEE TIT 59(1): 653-664, 2013] presented two classes of Boolean functions. The functions in the first class are unbalanced and the functions in the second one are balanced. Both of those two classes of functions have high nonlinearity, high algebraic degree, optimal algebraic immunity, and high fast algebraic immunity. However, they are not 1-resilient which represents a drawback for their use as filter functions in stream ciphers. In this paper, we first propose a large family of 1-resilient Boolean functions having high lower bound on nonlinearity, optimal algebraic immunity, and optimal algebraic degree, that is, meeting the Siegenthaler bound. Most notably, we can mathematically prove that every function in n variables belonging to this family has fast algebraic immunity no less than n - 6, which is the first time that an infinite family of 1-resilient functions with provably high fast algebraic immunity has been invented. Furthermore, we exhibit a subclass of the family which has higher lower bound on nonlinearity than all the known 1-resilient functions with (potentially) optimal algebraic immunity and potentially high fast algebraic immunity.

Inspired by the previous work of Tu and Deng, we propose two infinite classes of Boolean functions of 2kvariables wherek≥ 2. The first class contains unbalanced functions having high algebraic degree and nonlinearity. The functions in the second one are balanced and have maximal algebraic degree and high nonlinearity (as shown by a lower bound that we prove; as a byproduct we also prove a better lower bound on the nonlinearity of the Carlet-Feng function). Thanks to a combinatorial fact, first conjectured by the authors and later proved by Cohen and Flori, we are able to show that they both possess optimal algebraic immunity. It is also checked that, at least for numbers of variablesn≤ 16, functions in both classes have a good behavior against fast algebraic attacks. Compared with the known Boolean functions resisting algebraic attacks and fast algebraic attacks, both of them possess the highest lower bounds on nonlinearity. These bounds are however not enough for ensuring a sufficient nonlinearity for allowing resistance to fast correlation attack. Nevertheless, as for previously found functions with the same features, there is a gap between the bound that we can prove and the actual values computed for bounded numbers of variables (n≤ 38). Moreover, these values are very good. The infinite class of functions we propose in Construction 2 presents, among all currently known constructions, the best provable tradeoff between all the important cryptographic criteria.