Publications - Boolean Functions Team @ UiB

L. Budaghyan, M. Calderini and I. Villa
On equivalence between some families of APN functions
Proceedings WCC 2019
Abstract

We prove that two families among the known APN polynomial functions are equivalent to the hexanomials family introduced by Budaghyan and Carlet in 2008. By that we reduce the list of known families of APN functions to those strictly inequivalent to each other.

L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa
Generalized Isotopic Shift of Gold Functions
Proceedings WCC 2019
Abstract

In the present paper we present several generalizations of the isotopic shift construction when the starting function is a Gold function. In particular we derive a general family of APN functions which produces 15 new APN functions for n = 9.

L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa
On Isotopic Shift Construction for Planar Functions
Proceedings ISIT2019
Abstract

CCZ-equivalence is the most general currently known equivalence relation for functions over finite fields preserving planarity and APN properties. However, for the particular case of quadratic planar functions isotopic equivalence is more general than CCZ-equivalence. A recent construction method for APN functions over fields of even characteristic, so-called isotopic shift construction, was instigated by the notion of isotopic equivalence. In this paper we discuss possible applications of the idea of isotopic shift for the case of planar functions. We show that, surprisingly, some of the known planar functions are actually isotopic shifts of each other. This confirms practically the pertinence of the notion of isotopic shift not only for APN functions but also for planar maps.

L. Budaghyan, M. Calderini, and I. Villa
On relations between CCZ- and EA-equivalences
Cryptography and Communications, 2019. https://doi.org/10.1007/s12095-019-00367-5
Abstract

In the present paper we introduce some sufficient conditions and a procedure for checking whether, for a given function, CCZ-equivalence is more general than EA-equivalence together with taking inverses of permutations. It is known from Budaghyan et al. (IEEE Trans. Inf. Theory 52.3, 1141–1152 2006; Finite Fields Appl. 15(2), 150–159 2009) that for quadratic APN functions (both monomial and polynomial cases) CCZ-equivalence is more general. We prove hereby that for non-quadratic APN functions CCZ-equivalence can be more general (by studying the only known APN function which is CCZ-inequivalent to both power functions and quadratics). On the contrary, we prove that for power non-Gold APN functions, CCZ equivalence coincides with EA-equivalence and inverse transformation for n ≤ 8. We conjecture that this is true for any n.

N. Kaleyski
Changing APN Functions at Two Points
Cryptography and Communications, 2019. https://doi.org/10.1007/s12095-019-00366-6
Abstract

We investigate a construction in which a vectorial Boolean function G is obtained from a given function F over ?2? by changing the values of F at two points of the underlying field. In particular, we examine the possibility of obtaining one APN function from another in this way. We characterize the APN-ness of G in terms of the derivatives and in terms of the Walsh coefficients of F. We establish that changing two points of a function F over ?2? which is plateaued (and, in particular, AB) or of algebraic degree deg(F) < n − 1 can never give a plateaued (and AB, in particular) function for any n ≥ 5. We also examine a particular case in which we swap the values of F at two points of ?2?. This is motivated by the fact that such a construction allows us to obtain one permutation from another. We obtain a necessary and sufficient condition for the APN-ness of G which we then use to show that swapping two points of any power function over a field ?2? with n ≥ 5 can never produce an APN function. We also list some experimental results indicating that the same is true for the switching classes from Edel and Pott (Adv. Math. Commun. 3(1):59–81, 2009), and conjecture that the Hamming distance between two APN functions cannot be equal to two for n ≥ 5.

L. Budaghyan, N. S. Kaleyski, S. Kwon, C. Riera, and P. Stanica
Partially APN Boolean functions and classes of functions that are not APN infinitely often
Cryptography and Communications, 2019. https://doi.org/10.1007/s12095-019-00372-8
Abstract

In this paper we define a notion of partial APNness and find various characterizations and constructions of classes of functions satisfying this condition. We connect this notion to the known conjecture that APN functions modified at a point cannot remain APN. In the second part of the paper, we find conditions for some transformations not to be partially APN, and in the process, we find classes of functions that are never APN for infinitely many extensions of the prime field ?2 , extending some earlier results of Leander and Rodier.

Y. Xu, C. Carlet, S. Mesnager, and C. Wu
Classification of bent monomials, constructions of bent multinomials and upper bounds on the nonlinearity of vectorial functions
IEEE Transactions on Information Theory 64, Issue:1, pp. 367-383, 2018
Abstract

This paper is composed of two main parts related to the nonlinearity of vectorial functions. The first part is devoted to maximally nonlinear (n, m) functions (the so-called bent vectorial functions), which contribute to an optimal resistance to both linear and differential attacks on symmetric cryptosystems. They can be used in block ciphers at the cost of additional diffusion/compression/expansion layers, or as building blocks for the construction of substitution boxes (S-boxes), and they are also useful for constructing robust codes and algebraic manipulation detection codes. A main issue on bent vectorial functions is to characterize bent monomial functions Tr m n (λx d ) from F 2 n to F 2 m (where m is a divisor of n) leading to a classification of those bent monomials. We also treat the case of functions with multiple trace terms involving general results and explicit constructions. Furthermore, we investigate some open problems raised by Pasalic et al. and Muratovic-Ribic et al. in a series of papers on vectorial functions. The second part is devoted to the nonlinearity of (n, m)-functions. No tight upper bound is known when n/2 <; m <; n. The covering radius bound is the only known upper bound in this range (the Sidelnikov- Chabaud-Vaudenay bound coincides with it when m = n – 1 and it has no sense when m <; n – 1). Finding better bounds is an open problem since the 1990s. Moreover, no bound has been found during the last 23 years, which improve upon the covering radius bound for a large part of (n, m)-functions. We derive such upper bounds for functions, which are sufficiently unbalanced or which satisfy some conditions. These upper bounds imply some necessary conditions for vectorial functions to have large nonlinearity.

C. Carlet
On the nonlinearity of monotone Boolean functions
Proceedings of SETA 2016, Chengdu, China, 09-14 October 2016 and Cryptography and Communications, 10(6), pp. 1051-1061, 2018.
Abstract

We prove a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper “Cryptographic properties of monotone Boolean functions”, by Carlet et al. (J. Math. Cryptol. 10(1), 1–14, 2016). We also prove an upper bound on such nonlinearity, which is asymptotically much stronger than the conjectured upper bound and than the upper bound proved for odd dimension in this same paper. Contrary to these two previous bounds, which were not tight enough for allowing to clarify if monotone functions can have good nonlinearity, this new bound shows that the nonlinearity of monotone functions is always very bad, which represents a fatal cryptographic weakness of monotone Boolean functions; they are too closely approximated by affine functions for being usable as nonlinear components in cryptographic applications. We deduce a necessary criterion to be satisfied by a Boolean (resp. vectorial) function for being nonlinear.

L. Budaghyan, C. Carlet, T. Helleseth, N. Li and B. Sun
On upper bounds for algebraic degrees of APN functions
IEEE Transactions on Information Theory 64(6), pp. 4399-4411, 2018.
Abstract

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce several non-existence results which imply, in particular, that for most of the known APN functions F over F2n. the function x2n-1 + F(x) is not APN, and changing a value of F in a single point then results in non-APN functions. This leads us to conjectures that an APN function modified in one point cannot remain APN and that there exists no APN function of algebraic degree n.

C. Carlet
Characterizations of the differential uniformity of vectorial functions by the Walsh transform
IEEE Transactions on Information Theory, Volume: 64, Issue:9, pp. 6443-6453, 2018.
Abstract

For every positive integers n and m and every even positive integer δ, we derive inequalities satisfied by the Walsh transforms of all vectorial (n, m)-functions and prove that the case of equality characterizes differential δ-uniformity. This provides a generalization to all differentially δ-uniform functions of the characterization of Almost Perfect Nonlinear (APN) functions due to Chabaud and Vaudenay, by means of the fourth moment of the Walsh transform. Such generalization has been missing since the introduction of the notion of differential uniformity by Nyberg in 1994 and since Chabaud-Vaudenay’s result in the same year. Moreover, for each even δ ≥ 2, we find several (in fact, an infinity of) such characterizations. In particular, when δ = 2 and δ = 4, we have that, for any (n, n)function [resp. any (n, n – 1)-function)], the arithmetic mean of W F 2 (u 1 , v 1 )W F 2 (u 2 , v 2 )W F 2 (u 1 + u 2 , v 1 + v 2 ) when u 1 , u 2 range independently over F 2 n and v 1 , v 2 are nonzero and distinct and range independently over F 2 m is at least 2 3n , and that F is APN (resp. is differentially 4-uniform) if and only if this arithmetic mean equals 2 3n (which is the value we would get with a bent function if such function could exist). These inequalities give more knowledge on the Walsh spectrum of (n, m)-functions. We deduce in particular a property of the Walsh support of highly nonlinear functions. We also consider the completely open question of knowing if the nonlinearity of APN functions is necessarily non-weak (as it is the case for known APN functions); we prove new lower bounds which cover all power APN functions (and hence a large part of known APN functions), which explain why their nonlinearities are not bad, and we discuss the question of the nonlinearity of APN quadratic functions (since almost all other known APN functions are quadratic).

C. Carlet and X. Chen
Constructing low-weight $d$th-order correlation-immune Boolean functions through the Fourier-Hadamard transform
IEEE Transactions on Information Theory 64(4) (Special Issue in honor of Solomon Golomb), pp. 2969-2978, 2018.
Abstract

The correlation immunity of Boolean functions is a property related to cryptography, to error correcting codes, to orthogonal arrays (in combinatorics), and in a slightly looser way to sequences. Correlation-immune Boolean functions (in short, CI functions) have the property of keeping the same output distribution when some input variables are fixed. They have been widely used as combiners in stream ciphers to allow resistance to the Siegenthaler correlation attack. Very recently, a new use of CI functions has appeared in the framework of side channel attacks (SCA). To reduce the cost overhead of counter-measures to SCA, CI functions need to have low Hamming weights. This actually poses new challenges since the known constructions which are based on properties of the Walsh-Hadamard transform, do not allow to build unbalanced CI functions. In this paper, we propose constructions of low-weight d th-order CI functions based on the Fourier-Hadamard transform, while the known constructions of resilient functions are based on the Walsh-Hadamard transform. These two transforms are closely related but the resulting constructions are very different. We first prove a simple but powerful result, which makes that one only need to consider the case where d is odd in further research. Then, we investigate how constructing low Hamming weight CI functions through the Fourier-Hadamard transform (which behaves well with respect to the multiplication of Boolean functions). We use the characterization of CI functions by the Fourier-Hadamard transform and introduce a related general construction of CI functions by multiplication. By using the Kronecker product of vectors, we obtain more constructions of low-weight d-CI Boolean functions. Furthermore, we present a method to construct low-weight d-CI Boolean functions by making additional restrictions on the supports built from the Kronecker product.

C. Carlet and S. Guilley.
Statistical properties of side-channel and fault injection 1 attacks using coding theory
To appear in Cryptography and Communications 10(5), Special Issue: Statistics in Design and Analysis of Symmetric Ciphers, S. Maitra Editor, pp. 909-933, 2018.
Abstract

Naïve implementation of block ciphers are subject to side-channel and fault injection attacks. To deceive side-channel attacks and to detect fault injection attacks, the designer inserts specially crafted error correcting codes in the implementation. The impact of codes on protection against fault injection attacks is well studied: the number of detected faults relates to their minimum distance. However, regarding side-channel attacks, the link between codes and protection efficiency is blurred. In this paper, we relate statistical properties of code-based countermeasures against side-channel attacks to their efficiency in terms of security, against uni- and multi-variate attacks.

C. Carlet, S. Mesnager, C. Tang, Y. Qi and R. Pellikaan
Linear codes over F_q are equivalent to LCD codes for q>3
IEEE Transactions on Information Theory 64(4) (Special Issue in honor of Solomon Golomb), pp. 3010-3017, 2018.
Abstract

Linear codes with complementary duals (LCD) are linear codes whose intersection with their dual are trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Nonbinary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. In this paper, we introduce a general construction of LCD codes from any linear codes. Further, we show that any linear code over F q (q > 3) is equivalent to a Euclidean LCD code and any linear code over F q 2 (q > 2) is equivalent to a Hermitian LCD code. Consequently an [n, k, d]-linear Euclidean LCD code over F q with q > 3 exists if there is an [n, k, d]-linear code over F q and an [n, k, d]-linear Hermitian LCD code over F q 2 with q > 2 exists if there is an [n, k, d]-linear code over F q 2 . Hence, when q > 3 (resp. q > 2) q-ary Euclidean (resp. q 2 -ary Hermitian) LCD codes possess the same asymptotical bound as q-ary linear codes (resp. q 2 -ary linear codes). This gives a direct proof that every triple of parameters [n, k, d] which is attainable by linear codes over F q with q > 3 (resp. over F q 2 with q > 2) is attainable by Euclidean LCD codes (resp. by Hermitian LCD codes). In particular there exist families of q-ary Euclidean LCD codes (q > 3) and q 2 -ary Hermitian LCD codes (q > 2) exceeding the asymptotical Gilbert-Varshamov bound. Further, we give a second proof of these results using the theory of Gröbner bases. Finally, we present a new approach of constructing LCD codes by extending linear codes.

C. Carlet, C. Guneri, F. Ozbudak, B. Ozkaya and P. Sole
On Linear Complementary Pairs of Codes
IEEE Transactions on Information Theory 64, Issue:10, pp. 6583-6589, 2018.
Abstract

We study linear complementary pairs (LCP) of codes (C, D), where both codes belong to the same algebraic code family. We especially investigate constacyclic and quasicyclic LCP of codes. We obtain characterizations for LCP of constacyclic codes and LCP of quasi-cyclic codes. Our result for the constacyclic complementary pairs extends the characterization of linear complementary dual (LCD) cyclic codes given by Yang and Massey. We observe that when C and D are complementary and constacyclic, the codes C and D ⊥ are equivalent to each other. Hence, the security parameter min(d(C), d(D ⊥ )) for LCP of codes is simply determined by one of the codes in this case. The same holds for a special class of quasi-cyclic codes, namely 2D cyclic codes, but not in general for all quasi-cyclic codes, since we have examples of LCP of double circulant codes not satisfying this conclusion for the security parameter. We present examples of binary LCP of quasi-cyclic codes and obtain several codes with better parameters than known binary LCD codes. Finally, a linear programming bound is obtained for binary LCP of codes and a table of values from this bound is presented in the case d(C) = d(D ⊥ ). This extends the linear programming bound for LCD codes.

C. Carlet, S. Mesnager, C. Tang and Y. Qi
Euclidean and Hermitian LCD MDS codes
Designs, Codes and Cryptography 86(11), pp. 2605-2618, 2018.
Abstract

Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) are of much interest from many viewpoints due to their theoretical and practical properties. However, little work has been done on LCD MDS codes. In particular, determining the existence of q-ary [n, k] LCD MDS codes for various lengths n and dimensions k is a basic and interesting problem. In this paper, we firstly study the problem of the existence of q-ary [n, k] LCD MDS codes and solve it for the Euclidean case. More specifically, we show that for ?>3 there exists a q-ary [n, k] Euclidean LCD MDS code, where 0≤?≤?≤?+1, or, ?=2?, ?=?+2 and ?=3 or ?−1. Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.

C. Carlet, C. Guneri, F. Ozbudak and P. Sole
A new concatenated type construction for LCD codes and isometry codes
Discrete Mathematics 341(3), pp. 830-835, 2018.
Abstract

We give a new concatenated type construction for linear codes with complementary dual (LCD) over small finite fields. In this construction,we need a special class of inner codes that we call isometry codes. Our construction generalizes a recent construction of Carlet et al. (2014–2016) and of Güneri et al. (2016). In particular, it allows us to construct LCD codes with improved parameters directly.

C. Carlet, S. Mesnager, C. Tang and Y. Qi
New characterization and parametrization of LCD Codes
IEEE Transactions on Information Theory 65(1), pp. 39-49, 2019.
Abstract

Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their orthogonal or symplectic basis. Using such a characterization, we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results on the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of q-ary LCD codes have orthonormal basis, where q is a power of an odd prime.

C. Carlet
Componentwise APNness, Walsh uniformity of APN functions, and cyclic-additive difference sets
Finite Fields and Their Applications, Volume 53, pp. 226-253, 2018
Abstract

In [Characterizations of the differential uniformity of vectorial functions by the Walsh transform, IEEE Transactions on Information Theory 2017], the author has characterized differentially δ-uniform functions by equalities satisfied by their Walsh transforms. This generalizes the characterization of APN functions by the fourth moment of the Walsh transform. We study two notions which are related: (1) the componentwise APNness (CAPNness) of -functions, which is a stronger version of APNness, related to the characterization by the fourth moment, in which the arithmetic mean of when u ranges over and v is fixed nonzero in equals (2) the componentwise Walsh uniformity (CWU) of -functions (, resp. ), which is a stronger version of APNness (resp. of differential 4-uniformity) related to one of the new characterizations, in which the arithmetic mean of when range independently over and are fixed nonzero and distinct in , equals . Concerning the first notion, it is known from Berger, Canteaut, Charpin and Laigle-Chapuy that any plateaued function is CAPN if and only if it is AB and that APN power permutations are CAPN. We prove that CAPN functions can exist only if n is odd; this solves an eleven year old open problem by these authors. Concerning the second notion, we show that any crooked function (and in particular any quadratic APN function) is CWU, but we observe also that other APN functions like Kasami functions and the inverse of one of the Gold APN permutations are CWU for . We show that the CWUness of APN power permutations is equivalent to a property of . This new property, that we call cyclic-additive difference set property, is more complex than the cyclic difference set property (proved in the case of Kasami APN functions by Dillon and Dobbertin). We prove it in the case of the inverse of Gold function. In the case of Kasami functions, we observe that the cyclic-additive property is also true for even and we leave the proof of the CWUness and the cyclic-additive property as open problems.

C. Carlet, S. Mesanger, C. Tang and Y. Qi
On sigma-LCD codes
IEEE Transactions on Information Theory 65(3), pp. 1694-1704, 2019
Abstract

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against sidechannel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with o complementary dual (σ-LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, σ-LCD codes can also be used to construct LCP of codes. We show that for q 2, all q-ary linear codes are σ-LCD, and for every binary linear code C, the code {0} × C is σ-LCD. Furthermore, we study deeply σ-LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of σ-LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good σ-LCD GQC codes. Finally, we focus on σ-LCD abelian codes and prove that all abelian codes in a semisimple group algebra are σ-LCD. The results derived in this paper extend those on the classical LCD codes and show that σ-LCD codes allow the construction of LCP of codes more easily and with more flexibility.

C. Carlet, A. Daif, S. Guilley and C. Tavernier
Polynomial direct sum masking to protect against both SCA and FIA
To appear in the Journal of Cryptographic Engineering (JCEN)
Abstract

Side-channel attacks (SCAs) and fault injection attacks (FIAs) allow an opponent to have partial access to the internal behavior of the hardware. Since the end of the 1990s, many works have shown that this type of attacks constitutes a serious threat to cryptosystems implemented in embedded devices. In the state of the art, there exist several countermeasures to protect symmetric encryption (especially AES-128). Most of them protect only against one of these two attacks (SCA or FIA). A method called ODSM has been proposed to withstand SCA and FIA, but its implementation in the whole algorithm is a big open problem when no particular hardware protection is possible. In the present paper, we propose a practical masking scheme specifying ODSM which makes it possible to protect the symmetric encryption against these two attacks.

C. Carlet, X. Chen and L. Qu
Constructing Infinite Families of Low Differential Uniformity $(n,m)$-Functions with $m>n/2$
Designs, Codes and Cryptography 87(7), pp.1577-1599, 2019.
Abstract

Little theoretical work has been done on (n, m)-functions when ?2<??2. In this paper, we first characterize the differential uniformity of those (n, m)-functions of the form ?(?,?)=?(?)?(?), where I(x) is the (m, m)-inverse function and ?(?) is an (?−?,?)-function. Using this characterization, we construct an infinite family of differentially Δ-uniform (2?−1,?)-functions with ?≥3 achieving Nyberg’s bound with equality, which also have high nonlinearity and not too low algebraic degree. We then discuss an infinite family of differentially 4-uniform (?+1,?)-functions in this form, which leads to many differentially 4-uniform permutations. We also present a method to construct infinite families of (?+?,?)-functions with low differential uniformity and construct an infinite family of (2?−2,?)-functions with Δ≤2?−1−2?−6+2 for any ?≥8. The constructed functions in this paper may provide more choices for the design of Feistel ciphers.

C. Carlet, C. Guneri, S. Mesnager and F. Ozbudak
Construction of Some Codes Suitable for Both Side Channel and Fault Injection Attacks
Proceedings of WAIFI 2017, Lecture Notes in Computer Science 11321, pp.95-107, 2018
Abstract

Using algebraic curves over finite fields, we construct some codes suitable for being used in the countermeasure called Direct Sum Masking which allows, when properly implemented, to protect the whole cryptographic block cipher algorithm against side channel attacks and fault injection attacks, simultaneously. These codes address a problem which has its own interest in coding theory.

S. Picek, K. Knezevic, D. Jakobovic and C. Carlet
A Search for Differentially-6 Uniform (n, n-2) Functions
Proceedings of IEEE CEC 2018, pp. 1-7, 2018.
Abstract

Finding cryptographic primitives satisfying certain properties is a difficult problem. In this domain, besides the algebraic constructions, researchers often use heuristics. There exists a set of interesting problems related to the notion of differential uniformity for a function F: F_2^n -> F_2^m. When n = m, then the best obtainable differential uniformity equals 2, since it is necessarily positive and even, and since examples of differentially 2-uniform functions are known. Heuristics are able to reach such functions ; there is then some intuition that heuristics can be used for other open problems related to differential uniformity. When n > m>n/2, differential uniformity is bounded by 2^{;n-m};+2 from below (when m = n – 2, by 6). Unfortunately, we know such functions only for dimensions equal to n = 4, 5. In this paper, we explore several evolutionary algorithms and problem sizes in order to find functions having differential uniformity equal to 6. Our results show that several solution encodings are able to find such functions but only in dimensions $(4, 2)$ and $(5, 3)$. Since differentially 6-uniform functions were known for those sizes before, our results can be used as a source of new functions in those dimensions and as an indicator that for (6, 4) such functions either do not exist or that it is extremely difficult to find them.

W. Cheng, S. Guilley, C. Carlet, J.-L. Danger and A. Schaub
Optimal Codes for Inner Product Masking
Cryptographic architectures embedded in logic devices 2019
Abstract

Direct Sum Masking (DSM) and Inner Product (IP) masking are two types of countermeasures that have been introduced as alternatives to simpler (e.g., additive) masking schemes to protect cryptographic implementations against side-channel analysis. In this paper, we first show that IP masking can be written as a particular case of DSM. We then analyze the improved security properties that these (more complex) encodings can provide over Boolean masking. For this purpose, we introduce a slight variation of the probing model, which allows us to provide a simple explanation to the “security order amplification” for such masking schemes that was put forward at CARDIS 2016. We then use our model to search for new instances of masking schemes that optimize this security order amplification. We finally discuss the relevance of this security order amplification (and its underlying assumption of linear leakages) based on an experimental case study.

W. Cheng, C. Carlet, K. Goli, S. Guilley and J.-L. Danger
Detecting Faults in Inner Product Masking Scheme
IACR Cryptology ePrint Archive (http://eprint.iacr.org/) 2019/919. Presented at PROOFS 2019, 8th International Workshop on Security Proofs for Embedded Systems, Atlanta, USA, 2019. https://easychair.org/publications/paper/HTzP
Abstract

Side-channel analysis and fault injection attacks are two typical threats to cryptographic implementations, especially in modern embedded devices. Thus there is an insistent demand for dual side-channel and fault injection protections. As it is known, masking scheme is a kind of provable countermeasures against side-channel attacks. Recently, inner product masking (IPM) was proposed as a promising higher-order masking scheme against side-channel analysis, but not for fault injection attacks. In this paper, we devise a new masking scheme named IPM-FD. It is built on IPM, which enables fault detection. This novel masking scheme has three properties: the security orders in the word-level probing model, bit-level probing model, and the number of detected faults. IPM-FD is proven secure both in the word-level and in the bit-level probing models, and allows for end-to-end fault detection against fault injection attacks. Furthermore, we illustrate its security order by linking it to one defining parameters of linear code, and show its implementation cost by applying IPM-FD to AES-128.

L.Budaghyan, T.Helleseth, N.Li, B.Sun
Some Results on the Known Classes of Quadratic APN Functions
C2SI 2017, LNCS, pp.3-16, 2017
Abstract

In this paper, we determine the Walsh spectra of three classes of quadratic APN functions and we prove that the class of quadratic trinomial APN functions constructed by Göloğlu is affine equivalent to Gold functions.

N. Bruneau, C. Carlet, S. Guilley, A. Heuser, E. Prouff and O. Rioul
Stochastic Collision Attack
Transactions on Information Forensics \& Security Vol. 12, Issue: 9, pp. 2090-2104, 2017
Abstract

On the one hand, collision attacks have been introduced in the context of side-channel analysis for attackers who exploit repeated code with the same data without having any knowledge of the leakage model. On the other hand, stochastic attacks have been introduced to recover leakage models of internally processed intermediate secret variables. Both techniques have shown advantages and intrinsic limitations. Most collision attacks, for instance, fail in exploiting all the leakages (e.g., only a subset of matching samples are analyzed), whereas stochastic attacks cannot involve linear regression with the full basis (while the latter basis is the most informative one). In this paper, we present an innovative attacking approach, which combines the flavors of stochastic and collision attacks. Importantly, our attack is derived from the optimal distinguisher, which maximizes the success rate when the model is known. Notably, we develop an original closed-form expression, which shows many benefits by using the full algebraic description of the leakage model. Using simulated data, we show in the unprotected case that, for low noise, the stochastic collision attack is superior to the state of the art, whereas asymptotically and thus, for higher noise, it becomes equivalent to the correlation-enhanced collision attack. Our so-called stochastic collision attack is extended to the scenario where the implementation is protected by masking. In this case, our new stochastic collision attack is more efficient in all scenarios and, remarkably, tends to the optimal distinguisher. We confirm the practicability of the stochastic collision attack thanks to experiments against a public data set (DPA contest v4). Furthermore, we derive the stochastic collision attack in case of zero-offset leakage that occurs in protected hardware implementations and use simulated data for comparison. Eventually, we underline the capability of the new distinguisher to improve its efficiency when the attack multiplicity increases.

C. Carlet, S. Mesnager, F. Ozbudak and A. Sinak
<a href="https://link.springer.com/chapter/10.1007/978-3-319-55589-8_22"Explicit Characterizations for Plateaued-ness of p-ary (Vectorial) Functions
Proceedings of C2SI 2017, LNCS volume 10194, pp. 328-345, 2017
Abstract

Plateaued (vectorial) functions have an important role in the sequence and cryptography frameworks. Given their importance, they have not been studied in detail in general framework. Several researchers found recently results on their characterizations and introduced new tools to understand their structure and to design such functions. In this work, we mainly extend some of the observations made in characteristic 2 and given in (Carlet, IEEE Trans. Inf. Theor. 61(11), 6272–6289, 2015) to arbitrary characteristic. We first extend to arbitrary characteristic the characterizations of plateaued (vectorial) Boolean functions by the autocorrelation functions, next their characterizations in terms of the second-order derivatives, and finally their characterizations via the moments of the Walsh transform.

C. Carlet, A. Heuser and S. Picek
Trade-offs for S-boxes: Cryptographic Properties and Side-channel Resilience
Proceedings of ACNS 2017, Lecture Notes in Computer Science 10355, pp. 393-414, 2017
Abstract

When discussing how to improve side-channel resilience of a cipher, an obvious direction is to use various masking or hiding countermeasures. However, such schemes come with a cost, e.g. an increase in the area and/or reduction of the speed. When considering lightweight cryptography and various constrained environments, the situation becomes even more difficult due to numerous implementation restrictions. However, some options are possible like using S-boxes that are easier to mask or (more on a fundamental level), using S-boxes that possess higher inherent side-channel resilience. In this paper we investigate what properties should an S-box possess in order to be more resilient against side-channel attacks. Moreover, we find certain connections between those properties and cryptographic properties like nonlinearity and differential uniformity. Finally, to strengthen our theoretical findings, we give an extensive experimental validation of our results.

R. Poussier, Q. Guo, F.-X. Standaert, C. Carlet and S. Guilley
Connecting and Improving Direct Sum Masking and Inner Product Masking
Proceedings of CARDIS 2017, Lecture Notes in Computer Science 10728, pp. 123-141, 2017
Abstract

D. Tang, C. Carlet and Z. Zhou
Binary Linear Codes From Vectorial Boolean Functions and Their Weight Distribution
Discrete Mathematics 340, no 12, pp. 3055-3072, 2017
Abstract

Binary linear codes with good parameters have important applications in secret sharing schemes, authentication codes, association schemes, and consumer electronics and communications. In this paper, we construct several classes of binary linear codes from vectorial Boolean functions and determine their parameters, by further studying a generic construction developed by Ding et al. recently. First, by employing perfect nonlinear functions and almost bent functions, we obtain several classes of six-weight linear codes which contain the all-one codeword, and determine their weight distribution. Second, we investigate a subcode of any linear code mentioned above and consider its parameters. When the vectorial Boolean function is a perfect nonlinear function or a Gold function in odd dimension, we can completely determine the weight distribution of this subcode. Besides, our linear codes have larger dimensions than the ones by Ding et al.’s generic construction.

C. Carlet, P. Méaux and Yann Rotella
Boolean functions with restricted input and their robustness; application to the FLIP cipher
FSE 2018. IACR Trans. Symmetric Cryptol 2017, no 3, pp. 192-227, 2017
Abstract

We study the main cryptographic features of Boolean functions (balanced-ness, nonlinearity, algebraic immunity) when, for a given number n of variables, the input to these functions is restricted to some subset E of F n 2. We study in particular the case when E equals the set of vectors of fixed Hamming weight, which plays a role in the FLIP stream cipher and we study the robustness of the Boolean function in this cipher.

D. Tang, C. Carlet, X. Tang and Z. Zhou
Construction of Highly Nonlinear 1-Resilient Boolean Functions with Optimal Algebraic Immunity and Provably High Fast Algebraic Immunity
IEEE Trans. Information Theory 63(9), pp. 6113-6125, 2017
Abstract

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.

C. Carlet and S. Feukoua
Three basic questions on Boolean functions
Advances in Mathematics of Communications Vol. 11, no. 4, pp. 837-855, 2017
Abstract

In a first part of this paper, we investigate those Boolean functions satisfying two apparently related, but in fact distinct conditions concerning the algebraic degree: 1. we study those Boolean functions f whose restrictions to all affine hyperplanes have the same algebraic degree (equal to deg(f), the algebraic degree of f), 2. we study those functions whose derivatives Daf(x) = f(x) + f(x + a), a 6= 0, have all the same (optimal) algebraic degree deg(f) − 1. For determining to which extent these two questions are related, we find three classes of Boolean functions: the first class satisfies both conditions, the second class satisfies the first condition but not the second and the third class satisfies the second condition but not the first. We also give for any fixed positive integer k and for all integers n, p, s such that p ≥ k + 1, s ≥ k + 1 and n ≥ ps, a class (denoted by Cn,p,s) of functions whose restrictions to all k-codimensional affine subspaces of F n 2 have the same algebraic degree as the function. In a second part of the paper, we introduce the notion of second-orderbent function, whose second order derivatives DaDbf(x) = f(x) + f(x + a) + f(x + b) + f(x + a + b), a 6= 0, b 6= 0, a 6= b, are all balanced. We exhibit an example in 3 variables and we prove that second-order-bent functions cannot exist if n is not congruent with 3 mod 4. We characterize second-order-bent functions by the Walsh transform, state some of their properties and prove the non existence of such functions for algebraic degree 3 when n > 3. We leave open the question whether second-order-bent functions can exist for n larger than 3.

C. Carlet
On the nonlinearity of monotone Boolean functions
Proceedings of SETA 2016, Chengdu, China, 09-14 October 2016 and Cryptography and Communications, 10(6), pp. 1051-1061, 2018
Abstract

C. Carlet and S. Guilley
Statistical properties of side-channel and fault injection 1 attacks using coding theory
To appear in Cryptography and Communications 10(5), Special Issue: Statistics in Design and Analysis of Symmetric Ciphers, S. Maitra Editor, pp. 909-933, 2018
Abstract

L. Budaghyan, M. Calderini, C. Carlet, R. Coulter, I. Villa
Constructing APN functions through isotopic shifts
Proceedings of the Int. Conference on Sequences and Their Applications – SETA 2018, Hong Kong, Oct. 2018
Abstract

In our work we suggest a new approach for construction of APN functions over the fields of even characteristic which are of interest for many areas of mathemat- ics and information theory and, in particular, for cryptography. This approach is based on the notion of isotopic equivalence, which is defined only for quadratic planar functions. It is proven that CCZ-equivalence (the most general equivalence relation known of functions which preserves APN property) is a particular case of this isotopic equivalence in case of quadratic planar functions. It is an open problem whether isotopic equivalence of quadratic planar functions can induce an equivalence relation for APN functions more general than CCZ-equivalence.The present work is dedicated to that problem.

M. Calderini
A note on some algebraic trapdoors for block ciphers
Advances in Mathematics of Communications 2018, 12(3): 515-524.
Abstract

We provide sufficient conditions to guarantee that a translation based cipher is not vulnerable with respect to the partition-based trapdoor. This trapdoor has been introduced, recently, by Bannier et al. (2016) and it generalizes that introduced by Paterson in 1999. Moreover, we discuss the fact that studying the group generated by the round functions of a block cipher may not be sufficient to guarantee security against these trapdoors for the cipher.

L. Budaghyan, C. Carlet, T. Helleseth, N. Kaleyski
Changing points in APN functions
Submitted to IEEE Trans. on Inform. Theory, presented at BFA 2018
Abstract

We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of G via the derivatives of F , and deduce an algorithm for searching for APN functions whose values differ from those of F only on a given U ⊆ F2n . We introduce a value ΠF associated with any F , which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function F and the closest APN function in terms of ΠF . We show how ΠF can be computed efficiently for F quadratic. We compute ΠF for all known APN functions over F2n up to n ≤ 8. This is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function F (x) = x3 , and observe that it tends to infinity with n. We describe how to efficiently find all sets U such that taking G(x) = F (x) + v for x ∈ U and G(x) = F (x) for x ∈ / U is APN.

L. Budaghyan, N. Kaleyski, S. Kwon, C. Riera, P. Stanica
Partially APN Boolean Functions
Proceedings of the Int. Conference on Sequences and Their Applications – SETA 2018, Hong Kong, Oct. 2018
Abstract

In this paper we define a notion of partial APNness and find various charac- terizations and constructions of classes of functions satisfying this condition. We connect this notion to the known conjecture that APN functions modified at a point cannot remain APN.

N. Kaleyski
Changing two points in an APN functions
Proceedings of the Int. Conference on Sequences and Their Applications – SETA 2018, Hong Kong, Oct. 2018
Abstract

We investigate a construction in which a vectorial Boolean function G is obtained from a given function F over F 2 n by changing the values of F at two points of the underlying field. In particular, we examine the possibility of obtaining one APN function from another in this way. We characterize the APN-ness of G in terms of the derivatives and in terms of the Walsh coefficients of F . We establish that changing two points of a function F over F 2 n which is plateaued (and, in particular, AB) or of algebraic degree deg ( F) < n − 1 can never give a plateaued (and AB, in particular) function for any n ≥ 5. We also examine a particular case in which we swap the values of F at two points of F 2 n . This is motivated by the fact that such a construction allows us to obtain one permutation from another. We obtain a necessary and sufficient condition for the APN-ness of G which we then use to show that swapping the values at 0 and 1 of any power function over a field F 2 n with n ≥ 5 can never produce an APN function. We also describe some experimental results indicating that the same is true for the switching classes from [9], and conjecture that the Hamming distance between two APN functions cannot be equal to two for n ≥ 5.

Movsisyan Yu.
On functional equations and distributive second order formulae with specialized quantifiers
Algebra and Discrete Mathematics, 45(2),2018, pp. 269-285.
Abstract

The structure of invertible algebras with distributive second order formulae with specialized quantifiers is given. As a consequence, the applications for solutions of the some functional equations of distributivity on quasigroups are provided.

Movsisyan Yu., Davidov S., Krapez A.
Functional equations with division and regular operations
Asian-European Journal of Mathematics, Vol.11,No.3, 2018
Abstract

Functional equations are equations in which the unknown (or unknowns) are functions. We consider equations of generalized associativity, mediality (bisymmetry, entropy), paramediality, transitivity as well as the generalized Kolmogoroff equation. Their usefulness was proved in applications both in mathematics and in other disciplines, particularly in economics and social sciences (see J. Aczél, On mean values, Bull. Amer. Math. Soc.54 (1948) 392–400; J. Aczél, Remarques algebriques sur la solution donner par M. Frechet a l’equation de Kolmogoroff, Pupl. Math. Debrecen4 (1955) 33–42; J. Aczél, A Short Course on Functional Equations Based Upon Recent Applications to the Social and Behavioral Sciences, Theory and decision library, Series B: Mathematical and statistical methods (D. Reidel Publishing Company, Dordrecht, Boston, Lancaster, Tokyo, 1987); J. Aczél, Lectures on Functional Equations and Their Applications (Supplemented by the author, ed. H. Oser) (Dover Publications, Mineola, New York, 2006); J. Aczél, V. D. Belousov and M. Hosszu, Generalized associativity and bisymmetry on quasigroups, Acta Math. Acad. Sci. Hungar.11 (1960) 127–136; J. Aczél and J. Dhombres, Functional Equations in Several Variables (Cambridge University Press, New York, 1991); J. Aczél and T. L. Saaty, Procedures for synthesizing ratio judgements, J. Math. Psych.27(1) (1983) 93–102). We use unifying approach to solve these equations for division and regular operations generalizing the classical quasigroup case.

Movsisyan Yu.
Representations of Free Algebras of Varieties and Hypervarieties
IX International Conference of the Georgian Mathematical Union, Dedicated to 100-th Anniversary of Ivane Javakhishvili Tbilisi State University, Abstracts, p55
Abstract

–

Movsisyan Yu., Gevorgyan A.
Schauffler Type Theorems for New Second Order Formulas
IX International Conference of the Georgian Mathematical Union, Dedicated to 100-th Anniversary of Ivane Javakhishvili Tbilisi State University, Abstracts, p.119
Abstract

–

L. Budaghyan, P. Stanica.
What is a cryptographic Boolean function
Notices of American Mathematical Society, 2019
Abstract

–

A. De Trano, N. Karimi, R. Karri, X. Guo, C. Carlet and S. Guilley
Exploiting Small Leakages in Masks to Turn a Second-Order Attack into a First-Order Attack
To appear in The Scientific World Journal. Hindawi Publishing Corporation. Doi: 10.1155/2015/743618
Abstract

Masking countermeasures, used to thwart side-channel attacks, have been shown to be vulnerable to mask-extraction attacks. State-of-the-art mask-extraction attacks on the Advanced Encryption Standard (AES) algorithm target S-Box re-computation schemes, but have not been applied to scenarios where S-Boxes are precomputed offline. We propose an attack targeting precomputed S-Boxes stored in nonvolatile memory. Our attack targets AES implemented in software protected by a low entropy masking scheme and recovers the masks with 91% success rate. Recovering the secret key requires fewer power traces (in fact, by at least two orders of magnitude) compared to a classical second order attack. Moreover, we show that this attack remains viable in a noisy environment, or with a reduced number of leakage points.

C. Carlet
On APN exponents, characterizations of differentially uniform functions by the Walsh transform, and related cyclic-difference-set-like structures
Proceedings of WCC 2017. To appear in Designs, Codes and Cryptography, 2019
Abstract

In this paper, we summarize the results obtained recently in three papers on differentially uniform functions in characteristic 2, and presented at the workshop WCC 2017 in Saint-Petersburg, and we give new results on these functions. Firstly, we recall the recent connection between almost perfect nonlinear (APN) power functions and the two notions in additive combinatorics of Sidon sets and sum-free sets; we also recall a characterization of APN exponents which leads to a property of Dickson polynomials in characteristic 2 previously unobserved, which is generalizable to all finite fields. We also give a new characterization of APN exponents in odd dimension by Singer sets. Secondly, after recalling the recent multiple generalization to differentially ?-uniform functions of the Chabaud–Vaudenay characterization of APN functions by their Walsh transforms, we generalize the method to all criteria on vectorial functions dealing with the numbers of solutions of equations of the form ∑?∈??(?+??,?)+??(?)+??=0, with ?? linear; we give the examples of injective functions and of o-polynomials; we also deduce a generalization to differentially ?-uniform functions of the Nyberg characterization of APN functions by means of the Walsh transforms of their derivatives. Thirdly, we recall the two notions of componentwise APNness (CAPNness) and componentwise Walsh uniformity (CWU). We recall why CAPN functions can exist only if n is odd and why crooked functions (in particular, quadratic APN functions) are CWU. We also recall that the inverse of one of the Gold permutations is CWU and not the others. Another potential class of CWU functions is that of Kasami functions. We consider the difference sets with Singer parameters equal to the complement of ??={?(?)+?(?+1)+1;?∈?2?} where F is a Kasami function. These sets have another potential property, called the cyclic-additive difference set property, which is related to the CWU property in the case of power permutations (n odd). We study cyclic-additive difference sets among Singer sets. We recall the main properties of Kasami functions and of the related set ?? shown by Dillon and Dobbertin and we observe and prove new expressions for ??.

R. Aragona, M. Calderini, R. Civino, M. Sala and I. Zappatore
Wave-Shaped Round Functions and Primitive Groups
To be published in Advances in Mathematics of Communications
Abstract

Round functions used as building blocks for iterated block ciphers, both in the case of Substitution-Permutation Networks and Feistel Networks, are often obtained as the composition of different layers which provide confusion and diffusion, and key additions. The bijectivity of any encryption function, crucial in order to make the decryption possible, is guaranteed by the use of invertible layers or by the Feistel structure. In this work a new family of ciphers, called wave ciphers, is introduced. In wave ciphers, round functions feature wave functions, which are vectorial Boolean functions obtained as the composition of non-invertible layers, where the confusion layer enlarges the message which returns to its original size after the diffusion layer is applied. This is motivated by the fact that relaxing the requirement that all the layers are invertible allows to consider more functions which are optimal with regard to non-linearity. In particular it allows to consider injective APN S-boxes. In order to guarantee efficient decryption we propose to use wave functions in Feistel Networks. With regard to security, the immunity from some group-theoretical attacks is investigated. In particular, it is shown how to avoid that the group generated by the round functions acts imprimitively, which represent a serious flaw for the cipher.

C. Brunetta, M. Calderini and M. Sala
On Hidden Sums Compatible with A Given Block Cipher Diffusion Layer
To be published in Discrete Mathematics
Abstract

Sometimes it is possible to embed an algebraic trapdoor into a block cipher. Building on previous research, in this paper we investigate an especially dangerous algebraic structure, which is called a hidden sum and which is related to some regular subgroups of the affine group. Mixing group theory arguments and cryptographic tools, we pass from characterizing our hidden sums to designing an efficient algorithm to perform the necessary preprocessing for the exploitation of the trapdoor.

Sidebar