Search

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta $ -uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta $ -uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m < n$ , and a second upper bound, which is much stronger in the case (happening in practice) where $m$ is near $n$ ; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper. [ABSTRACT FROM AUTHOR]

ChaCha has been one of the most prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack that exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3rd round. At Crypto 2020, Beierle et al. introduced for the first time the single bit distinguishers for 3.5th round, which contributed significantly to regaining the flow of the research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher at 3.5th round helped to produce a 7th round distinguisher of ChaCha and a further improvement in the key recovery. In this paper, first, we provide the theoretical framework for the distinguisher given by Beierle et al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at 3.5th round. Also, Beierle et al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next, we revisit the work of Coutinho et al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218 and $2^{228.51}$ respectively. We show that the differential correlation for the 3.5th round is much smaller than the claim of Coutinho et al. This makes the attack complexities much higher than their claim. [ABSTRACT FROM AUTHOR]

The goal of this paper is to investigate linear approximations of random functions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional models have been based on the average behaviour and simplified using other assumptions such as independence of the linear approximations. Multidimensional cryptanalysis was introduced to avoid making artificial assumptions about statistical independence of linear approximations. On the other hand, it has the drawback of including many trivial approximations that do not contribute to the attack but just cause a waste of time and memory. We show for the first time in this paper that the trivial approximations reduce the degree of freedom of the related $\chi ^{2}$ distribution. Previously, the affine linear cryptanalysis was proposed to allow removing trivial approximations and, at the same time, admitting a solid statistical model. In this paper, we identify another type of multidimensional linear approximation, called Davies-Meyer approximation, which has similar advantages, and present full statistical models for both the affine and the Davies-Meyer type of multidimensional linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson’s $\chi ^{2}$ test and finite population correction and demonstrated to work accurately using practical examples. [ABSTRACT FROM AUTHOR]

In ICISC-05, and in the ePrint 2010/287, Patarin claimed a lower bound on the number of $2 q$ tuples of $n$ -bit strings $(P_{1}, \ldots, P_{2q}) \in ({\{0,1\}}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda _{i}$ for $1 \leq i \leq q$ such that $P_{1}, P_{2}, \ldots $ , $P_{2q}$ are distinct and $\lambda _{i} \in {\{0,1\}} ^{n} \setminus \{0^{n}\}$. This result is known as Mirror theory and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory. [ABSTRACT FROM AUTHOR]

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest. [ABSTRACT FROM AUTHOR]

Designing Boolean functions whose output can be computed with light means at high speed, and satisfying all the criteria necessary to resist all major attacks on the stream ciphers using them as nonlinear components, has been an open problem since the beginning of this century, when algebraic attacks were invented. Functions allowing a good resistance are known since 2008, but their output is a little too complex to compute. Functions with fast and easy to compute output are known which have good algebraic immunity, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have the same cryptographic weakness: their too small nonlinearity. In the present paper, we introduce a generalization of the HWB functions into a construction of $n$ -variable balanced functions $f$ from $(n-1)$ -variable Boolean functions $g$ having some property held by a large number of functions. Function $f$ is defined by its support, equal to the image set of a vectorial function depending on $g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with $f$ when the initial function $g$ equals constant 1. Other well chosen functions $g$ provide functions $f$ having good cryptographic parameters. We analyze the constructed functions $f$ , we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers. [ABSTRACT FROM AUTHOR]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity 27, i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight. [ABSTRACT FROM AUTHOR]

In this paper, by the Hasse-Weil bound, we determine the necessary and sufficient condition on coefficients $a_{1},a_{2},a_{3}\in {\mathbb F} _{2^{n}}$ with $n=2m$ such that $f(x) = {x}^{3\cdot 2^{m}} + a_{1}x^{2^{m+1}+1} + a_{2} x^{2^{m}+2} + a_{3}x^{3}$ is an APN function over ${\mathbb F}_{2^{n}}$. Our work together with the follow-up work by Chase and Lisoněk indicates that all such APN quadrinomials $f(x)$ are affine equivalent to two instances of Gold functions, which resolves the first half of an open problem by Carlet at the International Workshop on the Arithmetic of Finite Fields, 83-107, 2014. [ABSTRACT FROM AUTHOR]

In this paper, we aim to construct a class of complete permutations $\mathcal F$ over $\mathbb F_{q}^{n}$ from some polynomials $f_{1},f_{2},\ldots,f_{n}$ over $\mathbb F_{q}$. First of all, we determine a necessary and sufficient condition such that $\mathcal F$ is complete. Briefly, we transform the completeness of $\mathcal F$ into showing the permutation properties of two polynomials over $\mathbb F_{q}$ obtained from these $f_{i}$ ’s. Then, following the wide applications, we investigate the constructions of linear complete permutations over $\mathbb F_{2}^{n}$ based on the rotations and XORs. The following two cases are considered: the first one is to use some different circularly left shift transforms $f_{i}$ ’s and the second one is to assume $f_{i}$ ’s are of the form $b_{i}f$ with a fixed $f$ and different $b_{i}$ ’s in $\mathbb F_{q}$. In both cases, we show that the completeness of the permutation is closely related to the ranks of some matrices with particular forms, which can be determined by the cycle decomposition of the permutation over the $n$ branches. Besides, we present several explicit linear complete permutations which might be used in the design as well as the provable security of cryptographic schemes. [ABSTRACT FROM AUTHOR]

In a prior paper (Ellingsen et al., 2020), two of us, along with P. Ellingsen, P. Felke, and A. Tkachenko, defined a new (output) multiplicative differential and the corresponding $c$ -differential uniformity, which has the potential of extending differential cryptanalysis. Here, we continue the work by looking at some APN functions through the mentioned concept and showing that their $c$ -differential uniformity increases significantly in some cases. [ABSTRACT FROM AUTHOR]

In 2016, Chang et al. proposed a Format Preserving Encryption (FPE) scheme over a finite field and used an MDS matrix in the diffusion layer of the scheme for optimal diffusion. Later that year, Gupta et al. defined an algebraic structure named Format Preserving Set (FPS) is the diffusion layer of an FPE scheme. In 2018, Barua et al. showed that it is not possible to construct an FPS over a finite field in the diffusion layer of an FPE scheme if the cardinality of the set is not a power of prime. They extended the search of FPS over a finite commutative ring $\mathcal {R}$ and showed that if an FPS $S \subseteq \mathcal {R}$ is closed under addition then it gets module structure over some subring of $\mathcal {R}$. Moreover, in this case, the only possible cardinalities of FPS are some power of the cardinalities of subrings when the module is free. The purpose of this article is twofold. Firstly, we show that it is possible to construct format preserving sets over a finite commutative ring which are not closed under addition. Secondly, we search for format preserving sets and MDS matrices over torsion modules. We provide examples of format preserving sets of cardinalities 26 and 52 over torsion modules and rings. These cardinalities are interesting because they correspond to the set of English alphabets, without and with capitalization. By considering a finite Abelian group as a torsion module over a PID, we show that a matrix $M$ with entries from the PID is MDS if and only if $M$ is MDS under the projection map on the same Abelian group. [ABSTRACT FROM AUTHOR]

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition $x^{i} \circ x^{1/j}$ of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions $x^{i} \circ L \circ x^{1/j}$ for a linear polynomial $L$ , show how the Kasami functions in odd dimension can be expressed in this way with $i=j$ being a Gold exponent and compute all APN functions of this form for $n \le 9$ and for $L$ with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent $\sum _{i = 1}^{k-1} 2^{2ni} - 1$ which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for $n \le 35$ , and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for $n\leq 21$ show that these points cover about 2/3 of the field. [ABSTRACT FROM AUTHOR]

The Difference Distribution Table (DDT) and the differential uniformity play a major role for the design of substitution boxes in block ciphers, since they indicate the function’s resistance against differential cryptanalysis. This concept was extended recently to $c$ -DDT and $c$ -differential uniformity, which have the potential of extending differential cryptanalysis. Recently, a new theoretical tool, the Boomerang Connectivity Table (BCT) and the corresponding boomerang uniformity were introduced to quantify the resistance of a block cipher against boomerang-style attacks. Here we concentrate on two classes (introduced recently) of permutation polynomials over finite fields of even characteristic. For one of these, which is an involution used to construct a 4-uniform permutation, we explicitly determine the $c$ -DDT entries and BCT entries. For the second type of function, which is a differentially 4-uniform function, we give bounds for its $c$ -differential and boomerang uniformities. [ABSTRACT FROM AUTHOR]

We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the $2^{\text {n}/2}$ birthday bound. [ABSTRACT FROM AUTHOR]

We study the cross-join pairs in the cycles of linear feedback shift registers whose characteristic polynomials are of the form $l(x) = p_{1}(x)p_{2}(x)\cdots p_{k}(x)$ , where $p_{i}(x), 1\leq i\leq k$ are primitive polynomials of coprime degrees. Firstly, we use Coppersmith et al.’s generating function theory to derive the lower and upper bounds for the number of cross-join pairs. Then we design an algorithm to generate these cross-join pairs. The algorithm requires a preparatory phase which costs $O(2^{n'})$ time where $n'$ is the largest degree of $p_{i}(x), 1\leq i\leq k$ , and after that it costs only $O(n^{3})$ time to generate one cross-join pair where $n$ is the degree of $l(x)$. We also consider a special class of cross-join pairs, for which the preparatory phase costs only $O(2^{n''})$ time where $n''$ is the second-largest degree of $p_{i}(x), 1\leq i\leq k$. The number of these special cross-join pairs is about $\frac {1}{12}2^{2n-n'}$. We present some experimental results, which validate our analysis and demonstrate the efficiencies of the algorithms. These cross-join pairs can be used in the cross-joining method to construct de Bruijn sequences. [ABSTRACT FROM AUTHOR]

Permutation polynomials and their compositional inverses have wide applications in cryptography, coding theory, and combinatorial designs. Motivated by several previous results on finding compositional inverses of permutation polynomials of different forms, we propose a general method for finding these inverses of permutation polynomials constructed by the AGW criterion. As a result, we have reduced the problem of finding the compositional inverse of such a permutation polynomial over a finite field to that of finding the inverse of a bijection over a smaller set. We demonstrate our method by interpreting several recent known results, as well as by providing new explicit results on more classes of permutation polynomials in different types. In addition, we give new criteria for these permutation polynomials being involutions. Explicit constructions are also provided for all involutory criteria. [ABSTRACT FROM AUTHOR]