A new counting method to bound the number of active S-boxes in Rijndael and 3D

Security against differential and linear cryptanalysis is an essential requirement for modern block ciphers. This measure is usually evaluated by finding a lower bound for the minimum number of active S-boxes. The 128-bit block cipher AES which was adopted by National Institute of Standards and Technology (NIST) as a symmetric encryption standard in 2001 is a member of Rijndael family of block ciphers. For Rijndael, the block length and the key length can be independently specified to 128, 192 or 256 bits. It has been proved that for all variants of Rijndael the lower bound of the number of active S-boxes for any 4-round differential or linear trail is 25, and for 4r (\(r \ge 1\)) rounds 25r active S-boxes is a tight bound only for Rijndael with block length 128. In this paper, a new counting method is introduced to find tighter lower bounds for the minimum number of active S-boxes for several consecutive rounds of Rijndael with larger block lengths. The new method shows that 12 and 14 rounds of Rijndael with 192-bit block length have at least 87 and 103 active S-boxes, respectively. Also the corresponding bounds for Rijndael with 256-bit block are 105 and 120, respectively. Additionally, a modified version of Rijndael-192 is proposed for which the minimum number of active S-boxes is more than that of Rijndael-192. Moreover, we extend the method to obtain a better lower bound for the number of active S-boxes for the block cipher 3D. Our counting method shows that, for example, 20 and 22 rounds of 3D have at least 185 and 205 active S-boxes, respectively.     

On unbalanced Feistel networks with contracting MDS diffusion

Though unbalanced Feistel networks (UFN) are widely considered as an alternative to balanced Feistel networks (BFN) and substitution?Cpermutation networks (SPN) in symmetric cryptography, little has been known yet about their resistance against differential and linear cryptanalysis. In this work, we tackle the problem at the example of d-branch SP-type UFNs with contracting MDS diffusion (dCUFN-SP). Under some restrictions on the contracting MDS matrices over multiple rounds, we prove lower bounds on the number of differentially active S-boxes for dCUFN-SP with ${d\in\{3,4\}}$ and on the number of linearly active S-boxes for dCUFN-SP with d ?? 3. As opposed to SPNs and BFNs, the number of differentially active S-boxes for such constructions does not directly translate to an upper bound on the probability of differential trails. So we provide a thorough analysis of single-round differentials that yields an upper bound on the probability of a differential trail. It is also shown that the efficiency level of dCUFN-SP is comparable to that of BFNs and SPNs with respect to differential and linear cryptanalysis.     

Towards the optimality of Feistel ciphers with substitution-permutation functions

We explore the optimality of balanced Feistel ciphers with SP-type F-functions with respect to their resistance against differential and linear cryptanalysis. Instantiations of Feistel ciphers with the wide class of (SP) \(^u\) and (SP) \(^u\) S F-functions are considered: one F-function can contain an arbitrary number of S-box layers interleaved with linear diffusion. For the matrices with maximum diffusion, it is proven that SPS and SPSP F-functions are optimal in terms of the proportion of active S-boxes in all S-boxes—a common efficiency metric for substitution-permutation ciphers. Interestingly, one SP-layer in the F-function is not enough to attain optimality whereas taking more than two S-box layers does not increase the efficiency either.     

Generalized Feistel networks revisited

This work deals with the classification, security and efficiency of generalized Feistel networks (GFNs) with 4 lines. We propose a definition of a GFN, essentially limiting consideration to Feistel-type constructions with domain-preserving F-functions and rotation by one line between rounds. Under this definition, we demonstrate that there are only two non-contracting representatives in the class of 4-line GFNs up to equivalence, namely, the type-I and type-II GFNs that avoid obvious differential effects. We propose to instantiate the GFNs with SPS-functions (two substitution layers separated by a permutation layer) instead of single SP-functions (one substitution-permutation layer only). We prove tight lower bounds on the number of differentially and linearly active functions and S-boxes in such ciphers. We show that the instantiation with SPS-functions using MDS diffusion provides a proportion of differentially and linearly active S-boxes by up to 33 and 50 % higher than that with single SP-functions for type-I and type-II GFNs, respectively, if the same matrix is used in all rounds. Moreover, we present the upper bounds on the differential and the linear hull probability for the type-II GFNs with SPS-functions. This opens up the possibility of designing more efficient block ciphers based on GFN structure.     

The design of composite permutations with applications to DES-like S-boxes

This paper presents an iterative construction method for building composite permutations. Its efficiency is based on the concepts of pre-computation and equivalence classes. Equivalence class representatives of permutations on four bits are pre-computed. These class representatives can serve as input to the construction method, however, the results are also of independent interest for applications in cryptography. A well-known example of a cryptosystem using composite permutations for its Substitution boxes (S-boxes) is the Data Encryption Standard (DES). Throughout the paper, DES-like S-boxes are defined as mappings satisfying all design criteria as disclosed by one of the designers of DES. All permutations on four bits with DES-like properties are identified. Starting with pre-computed representatives of classes with such permutations, two iterations of a specialized version of the algorithm are applied to obtain bounds on the minimum differential uniformity and minimum non-linear uniformity of DES-like S-boxes. It is established that the two values cannot be less than eight, and that DES-like S-boxes for which the values are both equal to 12 do exist. In addition, if the non-linear uniformity of each of the four permutations in a DES-like S-box is at most six, as in all DES S-boxes, then its non-linear uniformity cannot be less than ten and its minimum differential uniformity equals 12.     

A method for designing dynamical S-boxes based on discretized chaotic map

A method for obtaining dynamically cryptographically strong substitution boxes (S-boxes) based on discretized chaotic map is presented in this paper. The cryptographical properties such as bijection, nonlinearity, strict avalanche, output bits independence and equiprobable input/output XOR distribution of these S-boxes are analyzed in detail. The results of numerical analysis show that all the criteria for designing good S-box can be met approximately. As a result, our approach is suitable for practical application in designing block cryptosystem.     

Upper bound of the length of truncated impossible differentials for AES

On the provable security of a block cipher against impossible differential cryptanalysis, the maximal length of impossible differentials is an essential aspect. Most previous work on finding impossible differentials for AES, omits the non-linear component (S-box), which is important for the security. In EUROCRYPT 2016, Sun et al. showed how to bound the length of impossible differentials of a SPN “structure” using the primitive index of its linear layer. They proved that there do not exist impossible differentials longer than four rounds for the AES “structure”, instead of the AES cipher. Since they do not consider the details of the S-box, their bound is not feasible for a concrete cipher. With their result, the upper bound of the length of impossible differentials for AES, is still unknown. We fill this gap in our paper. By revealing some important properties of the AES S-box, we further prove that even though the details of the S-box are considered, there do not exist truncated impossible differentials covering more than four rounds for AES, under the assumption that round keys are independent and uniformly random. Specially, even though the details of the S-box and key schedule are both considered, there do not exist truncated impossible differentials covering more than four rounds for AES-256.     

An extended method for obtaining S-boxes based on three-dimensional chaotic Baker maps

Tang et al. proposed a novel method for obtaining S-boxes based on the well-known two-dimensional chaotic Baker map. Unfortunately, some mistakes exist in their paper. The faults are corrected first in this paper and then an extended method is put forward for acquiring cryptographically strong S-boxes. The new scheme employs a three-dimensional chaotic Baker map, which has more intensive chaotic characters than the two-dimensional one. In addition, the cryptographic properties such as the bijective property, the nonlinearity, the strict avalanche criterion, the output bits independence criterion and the equiprobable input/output XOR distribution are analyzed in detail for our S-box and revised Tang et al.’s one, respectively. The results of numerical analysis show that both of the two boxes can resist several attacks effectively and the three-dimensional chaotic map, a stronger sense in chaotic characters, can perform more smartly and more efficiently in designing S-boxes.     

A novel method of S-box design based on chaotic map and composition method

An efficient algorithm for obtaining random bijective S-boxes based on chaotic maps and composition method is presented. The proposed method is based on compositions of S-boxes from a fixed starting set. The sequence of the indices of starting S-boxes used is obtained by using chaotic maps. The results of performance test show that the S-box presented in this paper has good cryptographic properties. The advantages of the proposed method are the low complexity and the possibility to achieve large key space.     

Co-variation for sensitivity analysis in Bayesian networks: Properties,consequences and alternatives

Upon varying parameters in a sensitivity analysis of a Bayesian network, the standard approach is to co-vary the parameters from the same conditional distribution such that their proportions remain the same. Alternative co-variation schemes are, however, possible. In this paper we investigate the properties of the standard proportional co-variation and introduce two alternative schemes: uniform and order-preserving co-variation. We theoretically investigate the effects of using alternative co-variation schemes on the so-called sensitivity function, and conclude that its general form remains the same under any linear co-variation scheme. In addition, we generalise the CD-distance for bounding global belief change to explicitly include the co-variation scheme under consideration. We prove a tight lower bound on this distance for parameter changes in single conditional probability tables.     

On complexity of round transformations

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require that the function is a strictly non-linear bijection and that it has a good diffusion. The total number of variables in the normal algebraic form of the component functions of F is taken as its complexity. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F^′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F^′ is useful only from the theoretical point of view.     

Key-Dependent S-Boxes and Differential Cryptanalysis

Key-dependent S-boxes gained some prominence in block cipher design when Twofish became an AES finalist. In this paper we make some observations on how the cryptanalyst might work with key-dependent S-boxes, we begin to develop a framework for the differential cryptanalysis of key-dependent S-boxes, and we introduce some basic techniques that were used in an analysis of reduced-round Twofish.     

On the number of zeros of Abelian integrals for a polynomial Hamiltonian irregular at infinity

Up to now, most of the results on the tangential Hilbert 16th problem have been concerned with the Hamiltonian regular at infinity, i.e., its principal homogeneous part is a product of the pairwise different linear forms. In this paper, we study a polynomial Hamiltonian which is not regular at infinity. It is shown that the space of Abelian integral for this Hamiltonian is finitely generated as a R[h] module by several basic integrals which satisfy the Picard-Fuchs system of linear differential equations. Applying the bound meandering principle, an upper bound for the number of complex isolated zeros of Abelian integrals is obtained on a positive distance from critical locus. This result is a partial solution of tangential Hilbert 16th problem for this Hamiltonian. As a consequence, we get an upper bound of the number of limit cycles produced by the period annulus of the non-Hamiltonian integrable quadratic systems whose almost all orbits are algebraic curves of degree k+n, under polynomial perturbation of arbitrary degree.     

Cryptanalysis of Rijndael S-box and improvement

By the discovered correlation between linear functions over GF(qⁿ) and matrices over GF(q), a new scheme is presented to resolve the algebraic expression of Rijndael S-box in this paper. This new scheme has the advantage of predetermining in the case of a given random basis over GF(qⁿ). The reason why only nine terms are involved in the algebraic expression of Rijndael S-box is presented, which corrects the available inaccurate illustration. An improved AES S-box is presented to improve the complexity of AES S-box algebraic expression with terms increasing from 9 to 255 and algebraic degree invariable. The improved AES S-box also has good properties of Boolean functions in SAC and balance, and is capable of attacking against differential cryptanalysis with high reliable security. We finally summarize all the available methods to determine the algebraic expression of Rijndael S-box.     

The size of 3-uniform hypergraphs with given matching number and codegree

To determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvátal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear 3-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of 3-graphs with bounded codegree and matching number.     

On bounds for the mode and median of the generalized hyperbolic and related distributions

Except for certain parameter values, a closed form formula for the mode of the generalized hyperbolic (GH) distribution is not available. In this paper, we exploit results from the literature on modified Bessel functions and their ratios to obtain simple but tight two-sided inequalities for the mode of the GH distribution for general parameter values. As a special case, we deduce tight two-sided inequalities for the mode of the variance-gamma (VG) distribution, and through a similar approach we also obtain tight two-sided inequalities for the mode of the McKay Type I distribution. The analogous problem for the median is more challenging, but we conjecture some monotonicity results for the median of the VG and McKay Type I distributions, from we which we conjecture some tight two-sided inequalities for their medians. Numerical experiments support these conjectures and also lead us to a conjectured tight lower bound for the median of the GH distribution.     

Exact relations between nonlinearity and algebraic immunity

We sharpen some lower bounds on the higher order nonlinearity of a Boolean function in terms of the value of its algebraic immunity and obtain new tight bounds. We prove a universal tight lower bound, which enables us to reduce the problem of estimating higher order nonlinearity to finding the dimension of certain linear subspaces in the space of Boolean functions. As a simple corollary of this result, we obtain all previously known estimates in this area. For polynomials with disjoint terms, finding the dimension of those linear subspaces reduces to a simple combinatorial inspection. We prove a tight lower bound on the second order nonlinearity of a Boolean function in terms of the value of its algebraic immunity.     

On the distance between non-isomorphic groups

A result of Ben-Or, Coppersmith, Luby and Rubinfeld on testing whether a map between two groups is close to a homomorphism implies a tight lower bound on the distance between the multiplication tables of two non-isomorphic groups.     

Separation between second price auctions with personalized reserves and the revenue optimal auction

When buyer valuations are drawn IID from a known regular distribution, a second price auction with a symmetric reserve price is the revenue-optimal single-item auction. When this distribution is irregular, we provide the first separation result showing that a second price auction with reserves earns at most 0.778 times the revenue of Myerson’s optimal auction, even when the reserves can be asymmetric. Since the lower bound is 0.745 for i.i.d. buyers, our result is nearly tight.     

Nonlinearities of S-boxes

We introduce an indicator of the non-balancedness of functions defined over Abelian groups, and deduce a new indicator, denoted by NB, of the nonlinearity of such functions. We prove an inequality relating NB and the classical indicator NL, introduced by Nyberg and studied by Chabaud and Vaudenay, of the nonlinearity of S-boxes. This inequality results in an upper bound on NL which unifies Sidelnikov–Chabaud–Vaudenay's bound and the covering radius bound. We also deduce from bounds on linear codes three new bounds on NL that improve upon Sidelnikov–Chabaud–Vaudenay's bound and the covering radius bound in many cases.