This paper applies Explainable Artificial Intelligence (XAI) to improve the interpretability of neural differential cryptanalysis on the SPECK cipher. We use Local Interpretable Model-agnostic Explanations (LIME) to analyse and visualise feature importance in neural distinguishers, giving signed contributions and absolute rankings. Signed contributions show whether, and how strongly, specific bit positions influence the model's decision, while absolute rankings reflect their importance regardless of sign. To study interactions beyond single bits, we introduce a Systematic Masking Approach to reveal relations among bits by testing if chosen combinations of masked bits alter classification accuracy. On Gohr's 8-round SPECK32/64 distinguisher, masking up to four-bit combinations shows that decisions involve multi-bit interactions rather than isolated single-bit effects. Although LIME highlights strong single-bit signals, masking reveals interaction patterns consistent with differential cryptanalysis. These findings clarify model behaviour in neural cryptanalysis and show XAI's value for exposing and visualising interaction structure in ciphertext features and decisions.

Abstract We study the n -variable Boolean functions which keep their algebraic degree unchanged when they are restricted to any (affine) hyperplane, or more generally to any affine space of a given co-dimension k . For cryptographic applications it is of interest to determine functions f which have a relatively high algebraic degree and also maintain this degree when restricted to all affine spaces of co-dimension k for k ranging from 1 to as high a value as possible. This highest value will be called the restriction degree stabilityof f , denoted by $$\mathrm{deg\_stab}(f)$$ deg _ stab ( f ) . We give several necessary and/or sufficient conditions for f to maintain its degree on spaces of co-dimension k ; we show that this property is related to the property of having “fast points” as well as to other properties and parameters. The value of $$\mathrm{deg\_stab}(f)$$ deg _ stab ( f ) is determined for functions which are direct sums of monomials, as well as for functions of algebraic degrees $$1,2,n-2,n-1$$ 1 , 2 , n - 2 , n - 1 and n ; we also determine the symmetric functions which maintain their degree on any hyperplane. Furthermore, we give an explicit formula for the number of functions which maintain their degree on all hyperplanes. Finally, using our previous results and some computer assistance, we determine the behaviour of all the functions in up to 8 variables, therefore determining the optimal ones (i.e. with highest value of $$\mathrm{deg\_stab}(f)$$ deg _ stab ( f ) ) for each degree.

At CRYPTO'19, Gohr[1] presented ResNet-based neural distinguishers (ND) for the round-reduced SPECK32/64 cipher. However, due to the black-box use of such deep learning models, it is hard for humans to understand why these distinguishers work, impeding advancements in cryptanalytic knowledge. In this work, we aim to effectively adapt eXplainable Artificial Intelligence (XAI) techniques, notably Local Interpretable Model-Agnostic Explanations (LIME) and Shapley Additive Explanations (SHAP), to gain a detailed understanding of the important features useful in Gohr's neural distinguishers.

Abstract In the design of cryptographic functions, the properties of their discrete derivatives have to be carefully considered, as many cryptographic attacks exploit these properties. One can therefore attempt to first construct derivatives with the desired properties and then recover the function itself. Recently Suder developed an algorithm for reconstructing a function (also called antiderivative) over the finite field $$\mathop {{\mathbb {F}}}_{2^n}$$ F2n given its discrete derivatives in up to n linearly independent directions. Pasalic et al. also presented an algorithm for determining a function over $$\mathop {{\mathbb {F}}}_{p^n}$$ Fpn given one of its derivatives. Both algorithms involve solving a $$p^n \times p^n$$ pn×pn system of linear equations; the functions are represented as univariate polynomials over $$\mathop {{\mathbb {F}}}_{p^n}$$ Fpn . We show that this apparently high computational complexity is not intrinsic to the problem, but rather a consequence of the representation used. We describe a simpler algorithm, with quasilinear complexity, provided we work with a different representation of the functions. Namely they are polynomials in n variables over $$\mathop {{\mathbb {F}}}_{p}$$ Fp in algebraic normal form (for $$p>2$$ p>2 , additionally, we need to use the falling factorial polynomial basis) and the directions of the derivatives are the canonical basis of $$\mathop {{\mathbb {F}}}_{p}^n$$ Fpn . Algorithms for other representations (the directions of the derivatives not being the canonical basis vectors or the univariate polynomials over $$\mathop {{\mathbb {F}}}_{p^n}$$ Fpn mentioned above) can be obtained by combining our algorithm with converting between representations. However, the complexity of these conversions is, in the worst case, exponential. As an application, we develop a method for constructing new quadratic PN (Perfect Nonlinear) functions. We use an approach similar to the one of Suder, who used antiderivatives to give an alternative formulation of the methods of Weng et al. and Yu et al. for searching for new quadratic APN (Almost Perfect Nonlinear) functions.

Abstract Duan and Lai introduced the notion of “fast point” for a Boolean function f as being a direction a so that the algebraic degree of the derivative of f in direction a is strictly lower than the expected $$\deg (f)-1$$ deg ( f ) - 1 . Their study was motivated by the fact that the existence of fast points makes many cryptographic differential attacks (such as the cube and AIDA attack) more efficient. The number of functions with fast points was determined by Duan et al. in some special cases and by Sălăgean and Mandache-Sălăgean in the general case. We generalise the notion of fast point, defining a fast point of order $$\ell $$ ℓ as being a fast point a so that the degree of the derivative of f in direction a is lower by at least $$\ell $$ ℓ than the expected degree. We determine an explicit formula for the number of functions of degree d in n variables which have fast points of order $$\ell $$ ℓ . Furthermore, we determine the number of functions of degree d in n variables which have a given number of fast points of order $$\ell $$ ℓ , and also the number of functions which have a given profile in terms of the number of fast points of each order. We apply our results to compute the probability of a function to have fast points of order $$\ell $$ ℓ . We also compute the number of functions which admit linear structures (i.e. their derivative in a certain direction is constant); such functions have a long history of being used in the analysis of symmetric ciphers.

Higher order differentiation was introduced in a cryptographic context by Lai. Several attacks can be viewed in the context of higher order differentiations, amongst them the cube attack of Dinur and Shamir and the AIDA attack of Vielhaber. All of the above have been developed for the binary case. We examine differentiation in larger fields, starting with the field $$\mathrm {GF}(p)$$ of integers modulo a prime p, and apply these techniques to generalising the cube attack to $$\mathrm {GF}(p)$$ . The crucial difference is that now the degree in each variable can be higher than one, and our proposed attack will differentiate several times with respect to each variable (unlike the classical cube attack and its larger field version described by Dinur and Shamir, both of which differentiate at most once with respect to each variable). Connections to the Moebius/Reed Muller Transform over $$\mathrm {GF}(p)$$ are also examined. Finally we describe differentiation over finite fields $$\mathrm {GF}(p^s)$$ with $$p^s$$ elements and show that it can be reduced to differentiation over $$\mathrm {GF}(p)$$ , so a cube attack over $$\mathrm {GF}(p^s)$$ would be equivalent to cube attacks over $$\mathrm {GF}(p)$$ .

We present several generalisations of the Games-Chan algorithm. For a fixed monic irreducible polynomial f we consider the sequences s that have as characteristic polynomial a power of f. We propose an algorithm for computing the linear complexity of s given a full (not necessarily minimal) period of s. We give versions of the algorithm for fields of characteristic 2 and for arbitrary finite characteristic p, the latter generalising an algorithm of Kaida et al. We also propose an algorithm which computes the linear complexity given only a finite portion of s (of length greater than or equal to the linear complexity), generalising an algorithm of Meidl. All our algorithms have linear computational complexity. The algorithms for computing the linear complexity when a full period is known can be further generalised to sequences for which it is known a priori that the irreducible factors of the minimal polynomial belong to a given small set of polynomials.

The author of the above titled paper (ibid., vol. 55, no. 10, pp. 4695-4700, Oct. 09), apologizes for a citation omission.

We consider the problem of computing a linear recurrence relation (or equivalently a Linear Feedback Shift Register) of minimum order for a finite sequence over a field, with the additional requirement that not only the highest but also the lowest coefficient of the recurrence is nonzero. Such a recurrence relation can then be used to generate the sequence in both directions (increasing or decreasing order of indices), so we call it bidirectional. If the field is finite, a sequence is periodic if and only if it admits a bidirectional linear recurrence relation. For solving the above problem we propose an algorithm similar to the Berlekamp–Massey algorithm and prove its correctness. We describe the set of all solutions to this problem and show that if a sequence admits more than one linear recurrence relation then it admits a bidirectional one. We also prove some properties regarding the bidirectionality of the recurrences of the prefixes of the sequence.

The k-error linear complexity of a periodic sequence s over a field K and with period N is the minimum linear complexity that s can have after changing at most k of its terms in each period. This concept can be used as a measure of cryptographic strength for sequences. We introduce a generalisation of the notion of k-error linear complexity, which we call the extension field k-error linear complexity, defined as being the k-error linear complexity of s when working in the smallest extension field of K which contains an N-th root of unity, assuming N is not divisible by the characteristic of K. The optimisation problem of finding the extension field k- error linear complexity is firstly transformed to an optimisation problem in the DFT (discrete Fourier transform) domain, using Blahut's theorem. We then give an approximation algorithm of polynomial complexity for the problem (O(N2) operations in the extension field), by restricting the search space to error sequences whose DFT have period up to k. The algorithm was implemented in GAP and the results on a series of sequences are discussed.

We consider the problem of computing a linear recurrence relation (or equivalently a Linear Feedback Shift Register) of minimum order for a finite sequence over a field, with the additional requirement that not only the highest but also the lowest coefficient of the recurrence is non-zero. Such a recurrence relation can then be used to generate the sequence in both directions (increasing or decreasing order of indices), so we will call it bidirectional. If the field is finite, a sequence is periodic if and only if it admits a bidirectional linear recurrence relation. For solving the above problem we propose an algorithm similar to the Berlekamp-Massey algorithm and prove its correctness. We also describe the set of all solutions to this problem and prove some properties of the minimal polynomials of initial segments of the sequence.

Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear complexity and also a large k-error linear complexity. Efficient algorithms for computing the k-error linear complexity of a sequence over a finite field only exist for sequences of period equal to a power of the characteristic of the field. It is therefore useful to find a general and efficient algorithm to compute a good approximation of the k-error linear complexity. In this paper we investigate the design of a genetic algorithm to approximate the k-error linear complexity of a sequence. Our preliminary experiments show that the genetic algorithm approach is suitable to the problem and that a good scheme would use a medium sized population, an elitist type of selection, a special design of the two point random crossover and a standard random mutation. The algorithm outputs an approximative value of the k-error linear complexity which is on average only 19.5% higher than the exact value. This paper intends to be a proof of concept that the genetic algorithm technique is suitable for the problem in hand and future research will further refine the choice of parameters.

The linear Games-Chan algorithm for computing the linear complexity c(s) of a binary sequence s of period /spl lscr/=2/sup n/ requires the knowledge of the full sequence, while the quadratic Berlekamp-Massey algorithm requires knowledge of only 2c(s) terms. We show that we can modify the Games-Chan algorithm so that it computes the complexity in linear time knowing only 2c(s) terms. The algorithms of Stamp-Martin and Lauder-Paterson can also be modified, without loss of efficiency, to compute analogs of the k-error linear complexity for finite binary sequences viewed as initial segments of infinite sequences with period a power of two. We also develop an algorithm which, given a constant c and an infinite binary sequence s with period /spl lscr/=2/sup n/, computes the minimum number k of errors (and an associated error sequence) needed over a period of s for bringing the linear complexity of s below c. The algorithm has a time and space bit complexity of O(/spl lscr/). We apply our algorithm to decoding and encoding binary repeated-root cyclic codes of length /spl lscr/ in linear, O(/spl lscr/), time and space. A previous decoding algorithm proposed by Lauder and Paterson has O(/spl lscr/(log/spl lscr/)/sup 2/) complexity.

Let R be a finite chain ring (e.g., a Galois ring), K its residue field, and C a linear code over R. We prove that d(C), the Hamming distance of C, is d((~C~:~/spl alpha/~)~), where (C:/spl alpha/) is a submodule quotient, /spl alpha/ is a certain element of R, and denotes the canonical projection to K. These two codes also have the same set of minimal codeword supports. We explicitly construct a generator matrix/polynomial of (~C~:~/spl alpha/~)~ from the generator matrix/polynomials of C. We show that in general d(C)/spl les/d(C~) with equality for free codes (i.e., for free R-submodules of R/sup n/) and in particular for Hensel lifts of cyclic codes over K. Most of the codes over rings described in the literature fall into this class. We characterize minimum distance separable (MDS) codes over R and prove several analogs of properties of MDS codes over finite fields. We compute the Hamming weight enumerator of a free MDS code over R.

We prove that, except for the well-known case p=k=2, it is not possible to construct a weight function on Z(p/sup k/) for which Z(p/sup k/) is isometric to Z/sub p//sup k/ with the Hamming metric.