Papers on Boolean Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
No edit summary
 
(One intermediate revision by the same user not shown)
Line 21: Line 21:
* [https://eprint.iacr.org/2017/516.pdf Characterizations of the differential uniformity of vectorial functions by the Walsh transform]
* [https://eprint.iacr.org/2017/516.pdf Characterizations of the differential uniformity of vectorial functions by the Walsh transform]
** C. Carlet
** C. Carlet
** TODO
** For every positive integers <math>n, m</math> and every even positive integer <math>\delta</math>, we derive inequalities satisfied by the Walsh transforms of all vectorial <math>(n, m)</math>-functions and prove that the case of equality characterizes differential <math>\delta</math>-uniformity. This provides a generalization to all differentially <math>\delta</math>-uniform functions of the characterization of APN <math>(n, n)</math>-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 the same year. For each even <math>\delta \ge 2</math>, we find several such characterizations. In particular, when <math>\delta = 2</math> and <math>\delta = 4</math>, we have that, for any <math>(n, n)</math>-function (resp. any <math>(n, n - 1)</math>-function), the arithmetic mean of <math> W^2_F (u_1, v_1) W^2)F (u_2, v_2) W^2_F (u_1 + u_2, v_1 + v_2)</math> when <math>u_1, u_2</math> range independently over <math>\mathbb{F}^2_n</math> and <math>v_1, v_2</math> are nonzero and distinct and range independently over <math>\mathbb{F}_2^m</math>, is at least <math>2^{3n}</math>, and that <math>F</math> is APN (resp. is differentially 4-uniform) if and only if this arithmetic mean equals <math>2^{3n}</math> (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 <math>(n, m)</math>-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 rather good, and we discuss the question of the nonlinearity of APN quadratic functions (since almost all other known APN functions are quadratic).




Line 46: Line 46:
* [https://www.researchgate.net/publication/265815787_An_APN_permutation_in_dimension_six An APN permutation in dimension six]
* [https://www.researchgate.net/publication/265815787_An_APN_permutation_in_dimension_six An APN permutation in dimension six]
** KA Browning, JF Dillon, MT McQuistan, AJ Wolfe
** KA Browning, JF Dillon, MT McQuistan, AJ Wolfe
** TODO
** A map <math>f : GF(2^m) \rightarrow GF(2^m)</math> is almost perfect nonlinear, abbreviated APN, if <math>x \mapsto f(x+a) - f(x)</math> is 2-to-1 for all nonzero <math>a</math> in <math>GF(2^m)</math>. If <math>f(0) = 0</math>, then this condition is equivalent to the condition that the binary code <math>C_f</math> of length <math>2^m - 1</math> with parity-check matrix <math>H_f = \left[ \begin{array}{ccc} \ldots & \omega^j & \ldots \\ \ldots & f(\omega^j) & \ldots \end{array} \right]</math> is double-error-correcting, where $\omega$ is primitive in $GF(2^m)$. A commonly held belief is that, if the dimension <math>m</math> is even, then an APN map on <math>GF(2^m)</math> cannot be a permutation. We give a counterexample in dimension <math>m = 6</math>.




Line 108: Line 108:




* [Y. Edel, A. Pott https://pdfs.semanticscholar.org/0d6c/71fac2ec96cfe437a02e558fd26a33ea5bed.pdf]
* [https://pdfs.semanticscholar.org/0d6c/71fac2ec96cfe437a02e558fd26a33ea5bed.pdf A new almost perfect nonlinear function which is not quadratic ]
** A new almost perfect nonlinear function which is not quadratic
** Y. Edel, A. Pott
** Following an example in [13], we show how to change one coordinate function of an almost perfect nonlinear (APN) function in order to obtain new examples. It turns out that this is a very powerful method to construct new APN functions. In particular, we show that the approach can be used to construct “non-quadratic” APN functions. This new example is in remarkable contrast to all recently constructed functions which have all been quadratic.
** Following an example in [13], we show how to change one coordinate function of an almost perfect nonlinear (APN) function in order to obtain new examples. It turns out that this is a very powerful method to construct new APN functions. In particular, we show that the approach can be used to construct “non-quadratic” APN functions. This new example is in remarkable contrast to all recently constructed functions which have all been quadratic.



Latest revision as of 16:25, 14 January 2019

  • On Almost Perfect Nonlinear Functions Over [math]\displaystyle{ \mathbb{F}_2^n }[/math]
    • T.P. Berger , A. Canteaut , P. Charpin , Y. Laigle-Chapuy
    • We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic 2. We provide new characterizations of APN functions and of APN permutations by means of their component functions. We generalize some results of Nyberg (1994) and strengthen a conjecture on the upper bound of nonlinearity of APN functions. We also focus on the case of quadratic functions. We contribute to the current works on APN quadratic functions by proving that a large class of quadratic functions cannot be APN


  • New Links between Differential and Linear Cryptanalysis
    • C. Blondeau, K. Nyberg
    • Recently, a number of relations have been established among previously known statistical attacks on block ciphers. Leander showed in 2011 that statistical saturation distinguishers are on average equivalent to multidimensional linear distinguishers. Further relations between these two types of distinguishers and the integral and zero-correlation distinguishers were established by Bogdanov et al. [6]. Knowledge about such relations is useful for classification of statistical attacks in order to determine those that give essentially complementary information about the security of block ciphers. The purpose of the work presented in this paper is to explore relations between differential and linear attacks. The mathematical link between linear and differential attacks was discovered by Chabaud and Vaudenay already in 1994, but it has never been used in practice. We will show how to use it for computing accurate estimates of truncated differential probabilities from accurate estimates of correlations of linear approximations. We demonstrate this method in practice and give the first instantiation of multiple differential cryptanalysis using the LLR statistical test on PRESENT. On a more theoretical side, we establish equivalence between a multidimensional linear distinguisher and a truncated differential distinguisher, and show that certain zero-correlation linear distinguishers exist if and only if certain impossible differentials exist.



  • Open Questions on Nonlinearity and on APN Functions
    • C. Carlet
    • In a first part of the paper, we recall some known open questions on the nonlinearity of Boolean and vectorial functions and on the APN-ness of vectorial functions. All of them have been extensively searched and seem quite difficult. We also indicate related less well-known open questions. In the second part of the paper, we introduce four new open problems (leading to several related sub-problems) and the results which lead to them. Addressing these problems may be less difficult since they have not been much worked on.


  • Characterizations of the differential uniformity of vectorial functions by the Walsh transform
    • C. Carlet
    • For every positive integers [math]\displaystyle{ n, m }[/math] and every even positive integer [math]\displaystyle{ \delta }[/math], we derive inequalities satisfied by the Walsh transforms of all vectorial [math]\displaystyle{ (n, m) }[/math]-functions and prove that the case of equality characterizes differential [math]\displaystyle{ \delta }[/math]-uniformity. This provides a generalization to all differentially [math]\displaystyle{ \delta }[/math]-uniform functions of the characterization of APN [math]\displaystyle{ (n, n) }[/math]-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 the same year. For each even [math]\displaystyle{ \delta \ge 2 }[/math], we find several such characterizations. In particular, when [math]\displaystyle{ \delta = 2 }[/math] and [math]\displaystyle{ \delta = 4 }[/math], we have that, for any [math]\displaystyle{ (n, n) }[/math]-function (resp. any [math]\displaystyle{ (n, n - 1) }[/math]-function), the arithmetic mean of [math]\displaystyle{ W^2_F (u_1, v_1) W^2)F (u_2, v_2) W^2_F (u_1 + u_2, v_1 + v_2) }[/math] when [math]\displaystyle{ u_1, u_2 }[/math] range independently over [math]\displaystyle{ \mathbb{F}^2_n }[/math] and [math]\displaystyle{ v_1, v_2 }[/math] are nonzero and distinct and range independently over [math]\displaystyle{ \mathbb{F}_2^m }[/math], is at least [math]\displaystyle{ 2^{3n} }[/math], and that [math]\displaystyle{ F }[/math] is APN (resp. is differentially 4-uniform) if and only if this arithmetic mean equals [math]\displaystyle{ 2^{3n} }[/math] (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 [math]\displaystyle{ (n, m) }[/math]-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 rather good, and we discuss the question of the nonlinearity of APN quadratic functions (since almost all other known APN functions are quadratic).


  • Highly nonlinear mappings
    • C. Carlet, C. Ding
    • Functions with high nonlinearity have important applications in cryptography, sequences and coding theory. The purpose of this paper is to give a well-rounded treatment of non-Boolean functions with optimal nonlinearity. We summarize and generalize known results, and prove a number of new results. We also present open problems about functions with high nonlinearity.


  • Links between differential and linear cryptanalysis
    • F. Chabaud, S. Vaudenay
    • Linear cryptanalysis, introduced last year by Matsui, will most certainly open-up the way to new attack methods which may be made more efficient when compared or combined with differential cryptanalysis.


  • On the classification of APN functions up to dimension five
    • M. Brinkmann, G. Leander
    • We classify the almost perfect nonlinear (APN) functions in dimensions 4 and 5 up to affine and CCZ equivalence using backtrack programming and give a partial model for the complexity of such a search. In particular, we demonstrate that up to dimension 5 any APN function is CCZ equivalent to a power function, while it is well known that in dimensions 4 and 5 there exist APN functions which are not extended affine (EA) equivalent to any power function. We further calculate the total number of APN functions up to dimension 5 and present a new CCZ equivalence class of APN functions in dimension 6.


  • New families of quadratic almost perfect nonlinear trinomials and multinomials
    • C. Bracken, E. Byrne, N. Markin, G. McGuire
    • We introduce two new infinite families of APN functions, one on fields of order [math]\displaystyle{ 2^{2k} }[/math] for [math]\displaystyle{ k }[/math] not divisible by [math]\displaystyle{ 2 }[/math], and the other on fields of order [math]\displaystyle{ 2^{3k} }[/math] for [math]\displaystyle{ k }[/math] not divisible by [math]\displaystyle{ 3 }[/math]. The polynomials in the first family have between three and [math]\displaystyle{ k+2 }[/math] terms, the second family's polynomials have three terms.


  • An APN permutation in dimension six
    • KA Browning, JF Dillon, MT McQuistan, AJ Wolfe
    • A map [math]\displaystyle{ f : GF(2^m) \rightarrow GF(2^m) }[/math] is almost perfect nonlinear, abbreviated APN, if [math]\displaystyle{ x \mapsto f(x+a) - f(x) }[/math] is 2-to-1 for all nonzero [math]\displaystyle{ a }[/math] in [math]\displaystyle{ GF(2^m) }[/math]. If [math]\displaystyle{ f(0) = 0 }[/math], then this condition is equivalent to the condition that the binary code [math]\displaystyle{ C_f }[/math] of length [math]\displaystyle{ 2^m - 1 }[/math] with parity-check matrix [math]\displaystyle{ H_f = \left[ \begin{array}{ccc} \ldots & \omega^j & \ldots \\ \ldots & f(\omega^j) & \ldots \end{array} \right] }[/math] is double-error-correcting, where $\omega$ is primitive in $GF(2^m)$. A commonly held belief is that, if the dimension [math]\displaystyle{ m }[/math] is even, then an APN map on [math]\displaystyle{ GF(2^m) }[/math] cannot be a permutation. We give a counterexample in dimension [math]\displaystyle{ m = 6 }[/math].


  • An infinite class of quadratic APN functions which are not equivalent to power mappings
    • L. Budaghyan, C. Carlet, P. Felke, G. Leander
    • We exhibit an infinite class of almost perfect nonlinear quadratic polynomials from F2n to F2n (n ges 12, n divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function and that they are CCZ-inequivalent to any Gold function. In a forthcoming full paper, we shall also prove that at least some of these functions are CCZ-inequivalent to any Kasami function


  • Two Classes of Quadratic APN Binomials Inequivalent to Power Functions
    • L. Budaghyan, C. Carlet, G. Leander
    • This paper introduces the first found infinite classes of almost perfect nonlinear (APN) polynomials which are not Carlet-Charpin-Zinoviev (CCZ)-equivalent to power functions (at least for some values of the number of variables). These are two classes of APN binomials from F2n to F2n (for n divisible by 3, resp., 4). We prove that these functions are extended affine (EA)-inequivalent to any power function and that they are CCZ-inequivalent to the Gold, Kasami, inverse, and Dobbertin functions when n ges 12. This means that for n even they are CCZ-inequivalent to any known APN function. In particular, for n = 12,20,24, they are therefore CCZ-inequivalent to any power function.


  • Classes of Quadratic APN Trinomials and Hexanomials and Related Structures
    • L. Budaghyan, C. Carlet
    • A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from [math]\displaystyle{ F_{2^{2m}} }[/math] to [math]\displaystyle{ F_{2^{2m}} }[/math]. We check for [math]\displaystyle{ m = 3 }[/math] that some of these functions are CCZ-inequivalent to power functions.



  • A new class of monomial bent functions
    • A. Canteaut, P. Charpin, G. Kyureghyan
    • We study the Boolean functions [math]\displaystyle{ f_{\lambda}:\mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n} ,n=6r }[/math], of the form [math]\displaystyle{ f(x)=\rm{Tr}(\lambda x^d) }[/math] with [math]\displaystyle{ d=2^{2r}+2^r+1 }[/math] and [math]\displaystyle{ \lambda \in \mathbb{F}_{2^n} }[/math]. Our main result is the characterization of those [math]\displaystyle{ \lambda }[/math] for which [math]\displaystyle{ f_\lambda }[/math] are bent. We show also that the set of these cubic bent functions contains a subset, which with the constantly zero function forms a vector space of dimension [math]\displaystyle{ 2^r }[/math] over [math]\displaystyle{ \mathbb{F}_2 }[/math]. Further we determine the Walsh spectra of some related quadratic functions, the derivatives of the functions [math]\displaystyle{ f_\lambda }[/math].


  • Constructing new APN functions from known ones
    • L. Budaghyan, C. Carlet, G. Leander
    • We present a method for constructing new quadratic APN functions from known ones. Applying this method to the Gold power functions we construct an APN function [math]\displaystyle{ x^3+\rm{Tr}(x^9) }[/math] over [math]\displaystyle{ \mathbb{F}_{2^n} }[/math]. It is proven that for [math]\displaystyle{ n \ge 7 }[/math] this function is CCZ-inequivalent to the Gold functions, and in the case [math]\displaystyle{ n=7 }[/math] it is CCZ-inequivalent to any power mapping (and, therefore, to any APN function belonging to one of the families of APN functions known so far).


  • Differential cryptanalysis of DES-like cryptosystems
    • Biham E, Shamir A.
    • The Data Encryption Standard (DES) is the best known and most widely usedc ryptosystem for civilian applications.It was developed at IBM and adopted by the National Buraeu of Standards in the mid 70's, and has successfully withstood all the attacks published so far in the open literature. In this paper we develop a new type of cryptanalytic attack which can break the reduced variant of DES with eight rounds in a few minutes on a PC and can break any reduced variant of DES (with up to 15 rounds) in less than 256 operations.The new attack can be applied to a variety of DES-like substitution/permutation cryptosystems, and demonstrates the crucial role of the (unpublished) design rules.


  • Linear Cryptanalysis Method for DES Cipher
    • M. Matsui
    • We introduce a new method for cryptanalysis of DES cipher, which is essentially a known-plaintext attack. As a result, it is possible to break 8-round DES cipher with [math]\displaystyle{ 2^{21} }[/math] known-plaintexts and 16-round DES cipher with [math]\displaystyle{ 2^{47} }[/math] known-plaintexts, respectively. Moreover, this method is applicable to an only-ciphertext attack in certain situations. For example, if plaintexts consist of natural English sentences represented by ASCII codes, 8-round DES cipher is breakable with [math]\displaystyle{ 2^{29} }[/math] ciphertexts only.


  • Differentially uniform mappings for cryptography
    • K. Nyberg
    • This work is motivated by the observation that in DES-like ciphers it is possible to choose the round functions in such a way that every non-trivial one-round characteristic has small probability. This gives rise to the following definition. A mapping is called differentially uniform if for every non-zero input difference and any output difference the number of possible inputs has a uniform upper bound. The examples of differentially uniform mappings provided in this paper have also other desirable cryptographic properties: large distance from affine functions, high nonlinear order and efficient computability.


  • Almost Perfect Nonlinear Power Functions on [math]\displaystyle{ GF(2^n) }[/math]: A New Case for n Divisible by 5
    • H. Dobbertin
    • We prove that for [math]\displaystyle{ d = 2^{4s} + 2^{3s} + 2^{2s} + 2^s - 1 }[/math] the power function [math]\displaystyle{ x^d }[/math] is almost perfect nonlinear (APN) on [math]\displaystyle{ L = GF(2^{5s}) }[/math], i.e. for each [math]\displaystyle{ a \in L }[/math] the equation [math]\displaystyle{ (x + 1)^d + x^d = a }[/math] has either no or precisely two solutions in [math]\displaystyle{ L }[/math]. The proof of this result is based on a new “multi-variate” technique which was recently introduced by the author in order to confirm the conjectured APN property of Welch and Niho power functions.


  • Almost Perfect Nonlinear Power Functions on [math]\displaystyle{ GF(2^n) }[/math]: The Niho Case
    • H. Dobbertin
    • Almost perfect nonlinear (APN) mappings are of interest for applications in cryptography. We prove for odd [math]\displaystyle{ n }[/math] and the exponent [math]\displaystyle{ d=2^{2r}+2^r-1 }[/math], where [math]\displaystyle{ 4r+1 \equiv 0 mod n }[/math], that the power functions [math]\displaystyle{ x^d }[/math] on [math]\displaystyle{ GF(2^n) }[/math] is APN. The given proof is based on a new class of permutation polynomials which might be of independent interest. Our result supports a conjecture of Niho stating that the power function [math]\displaystyle{ x^d }[/math] is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequences of degree [math]\displaystyle{ n }[/math] and a decimation of that sequence by [math]\displaystyle{ d }[/math] takes on precisely the three values [math]\displaystyle{ -1 }[/math], [math]\displaystyle{ -1 \pm 2^{(n+1)/2} }[/math].
  • Almost Perfect Nonlinear Power Functions on [math]\displaystyle{ GF(2^n) }[/math] : The Welch Case
    • H. Dobbertin
    • We summarize the state of the classification of almost perfect nonlinear (APN) power functions [math]\displaystyle{ x^d }[/math] on [math]\displaystyle{ GF(2^n) }[/math] and contribute two new cases. To prove these cases we derive new permutation polynomials. The first case supports a well-known conjecture of Welch stating that for odd [math]\displaystyle{ n=2m+1 }[/math], the power function [math]\displaystyle{ x^{2m+3} }[/math] is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree [math]\displaystyle{ n }[/math] and a decimation of that sequence by [math]\displaystyle{ 2^{m}+3 }[/math] takes on precisely the three values [math]\displaystyle{ -1 }[/math], [math]\displaystyle{ -1 \pm 2^{ m+1} }[/math].


  • A new almost perfect nonlinear function which is not quadratic
    • Y. Edel, A. Pott
    • Following an example in [13], we show how to change one coordinate function of an almost perfect nonlinear (APN) function in order to obtain new examples. It turns out that this is a very powerful method to construct new APN functions. In particular, we show that the approach can be used to construct “non-quadratic” APN functions. This new example is in remarkable contrast to all recently constructed functions which have all been quadratic.


  • A new APN function which is not equivalent to a power mapping
    • Y. Edel, G. Kyureghyan, A. Pott
    • A new almost-perfect nonlinear function (APN) on [math]\displaystyle{ \mathbb{F}_{2^{10}} }[/math] which is not equivalent to any of the previously known APN mappings is constructed. This is the first example of an APN mapping which is not equivalent to a power mapping.