# Difference between revisions of "Papers on Boolean Functions"

(Created page with "* [http://ieeexplore.ieee.org/abstract/document/1683931/ On Almost Perfect Nonlinear Functions Over $\mathbb{F}_2^n$] ** T.P. Berger , A. Canteaut , P. Charpin , Y. Laigle-Cha...") |
|||

Line 1: | Line 1: | ||

− | * [http://ieeexplore.ieee.org/abstract/document/1683931/ On Almost Perfect Nonlinear Functions Over | + | * [http://ieeexplore.ieee.org/abstract/document/1683931/ On Almost Perfect Nonlinear Functions Over <math>\mathbb{F}_2^n</math>] |

** T.P. Berger , A. Canteaut , P. Charpin , Y. Laigle-Chapuy | ** 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 | ** 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 | ||

Line 41: | Line 41: | ||

* [http://www.sciencedirect.com/science/article/pii/S1071579707000718 New families of quadratic almost perfect nonlinear trinomials and multinomials] | * [http://www.sciencedirect.com/science/article/pii/S1071579707000718 New families of quadratic almost perfect nonlinear trinomials and multinomials] | ||

** C. Bracken, E. Byrne, N. Markin, G. McGuire | ** C. Bracken, E. Byrne, N. Markin, G. McGuire | ||

− | ** We introduce two new infinite families of APN functions, one on fields of order | + | ** We introduce two new infinite families of APN functions, one on fields of order <math>2^{2k}</math> for <math>k</math> not divisible by <math>2</math>, and the other on fields of order <math>2^{3k}</math> for <math>k</math> not divisible by <math>3</math>. The polynomials in the first family have between three and <math>k+2</math> terms, the second family's polynomials have three terms. |

Line 61: | Line 61: | ||

* [http://ieeexplore.ieee.org/abstract/document/4494676/ Classes of Quadratic APN Trinomials and Hexanomials and Related Structures] | * [http://ieeexplore.ieee.org/abstract/document/4494676/ Classes of Quadratic APN Trinomials and Hexanomials and Related Structures] | ||

** L. Budaghyan, C. Carlet | ** 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 | + | ** 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>F_{2^{2m}}</math> to <math>F_{2^{2m}}</math>. We check for <math>m = 3</math> that some of these functions are CCZ-inequivalent to power functions. |

Line 71: | Line 71: | ||

* [http://www.sciencedirect.com/science/article/pii/S1071579707000160 A new class of monomial bent functions] | * [http://www.sciencedirect.com/science/article/pii/S1071579707000160 A new class of monomial bent functions] | ||

** A. Canteaut, P. Charpin, G. Kyureghyan | ** A. Canteaut, P. Charpin, G. Kyureghyan | ||

− | ** We study the Boolean functions | + | ** We study the Boolean functions <math>f_{\lambda}:\mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n} ,n=6r</math>, of the form <math>f(x)=\Tr(\lambda x^d)</math> with <math>d=2^{2r}+2^r+1</math> and <math>\lambda \in \mathbb{F}_{2^n}</math>. Our main result is the characterization of those <math>\lambda</math> for which <math>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>2^r</math> over <math>\mathbb{F}_2</math>. Further we determine the Walsh spectra of some related quadratic functions, the derivatives of the functions <math>f_\lambda</math>. |

* [http://www.sciencedirect.com/science/article/pii/S1071579708000622 Constructing new APN functions from known ones] | * [http://www.sciencedirect.com/science/article/pii/S1071579708000622 Constructing new APN functions from known ones] | ||

** L. Budaghyan, C. Carlet, G. Leander | ** 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 | + | ** 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>x^3+\Tr(x^9)</math> over <math>\mathbb{F}_{2^n}</math>. It is proven that for <math>n \ge 7</math> this function is CCZ-inequivalent to the Gold functions, and in the case <math>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). |

Line 86: | Line 86: | ||

* [https://link.springer.com/chapter/10.1007%2F3-540-48285-7_33 Linear Cryptanalysis Method for DES Cipher] | * [https://link.springer.com/chapter/10.1007%2F3-540-48285-7_33 Linear Cryptanalysis Method for DES Cipher] | ||

** M. Matsui | ** 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 | + | ** 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>2^{21}</math> known-plaintexts and 16-round DES cipher with <math>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>2^{29}</math> ciphertexts only. |

Line 94: | Line 94: | ||

− | * [https://link.springer.com/chapter/10.1007/978-3-642-56755-1_11 Almost Perfect Nonlinear Power Functions on | + | * [https://link.springer.com/chapter/10.1007/978-3-642-56755-1_11 Almost Perfect Nonlinear Power Functions on <math>GF(2^n)</math>: A New Case for n Divisible by 5] |

** H. Dobbertin | ** H. Dobbertin | ||

− | ** We prove that for | + | ** We prove that for <math>d = 2^{4s} + 2^{3s} + 2^{2s} + 2^s − 1</math> the power function <math>x^d</math> is almost perfect nonlinear (APN) on <math>L = GF(2^{5s})</math>, i.e. for each <math>a \in L</math> the equation <math>(x + 1)^d + x^d = a</math> has either no or precisely two solutions in <math>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. |

− | * [http://www.sciencedirect.com/science/article/pii/S089054019892764X Almost Perfect Nonlinear Power Functions on | + | * [http://www.sciencedirect.com/science/article/pii/S089054019892764X Almost Perfect Nonlinear Power Functions on <math>GF(2^n)</math>: The Niho Case] |

** H. Dobbertin | ** H. Dobbertin | ||

− | ** Almost perfect nonlinear (APN) mappings are of interest for applications in cryptography. We prove for odd | + | ** Almost perfect nonlinear (APN) mappings are of interest for applications in cryptography. We prove for odd <math>n</math> and the exponent <math>d=2^{2r}+2^r−1</math>, where <math>4r+1 \equiv 0 mod n</math>, that the power functions <math>x^d</math> on <math>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>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>n</math> and a decimation of that sequence by <math>d</math> takes on precisely the three values <math>−1</math>, <math>−1 \pm 2^{(n+1)/2}</math>. |

− | * [https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=761283 Almost Perfect Nonlinear Power Functions on | + | * [https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=761283 Almost Perfect Nonlinear Power Functions on <math>GF(2^n)</math> : The Welch Case ] |

** H. Dobbertin | ** H. Dobbertin | ||

− | ** We summarize the state of the classification of almost perfect nonlinear (APN) power functions | + | ** We summarize the state of the classification of almost perfect nonlinear (APN) power functions <math>x^d</math> on <math>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>n=2m+1</math>, the power function <math>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>n</math> and a decimation of that sequence by <math>2^{m}+3</math> takes on precisely the three values <math>-1</math>, <math>-1 \pm 2^{ m+1}</math>. |

Line 115: | Line 115: | ||

* [http://ieeexplore.ieee.org/abstract/document/1580810/ A new APN function which is not equivalent to a power mapping] | * [http://ieeexplore.ieee.org/abstract/document/1580810/ A new APN function which is not equivalent to a power mapping] | ||

** Y. Edel, G. Kyureghyan, A. Pott | ** Y. Edel, G. Kyureghyan, A. Pott | ||

− | ** A new almost-perfect nonlinear function (APN) on | + | ** A new almost-perfect nonlinear function (APN) on <math>\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. |

## Revision as of 01:40, 26 November 2018

- On Almost Perfect Nonlinear Functions Over
- 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.

- Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems
- C. Carlet, P. Charpin, V. Zinoviev
- Almost bent functions oppose an optimum resistance to linear and differential cryptanalysis. We

- 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
- TODO

- 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 for not divisible by , and the other on fields of order for not divisible by . The polynomials in the first family have between three and terms, the second family's polynomials have three terms.

- An APN permutation in dimension six
- KA Browning, JF Dillon, MT McQuistan, AJ Wolfe
- TODO

- 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 to . We check for that some of these functions are CCZ-inequivalent to power functions.

- New classes of almost bent and almost perfect nonlinear polynomials
- L. Budaghyan, C. Carlet, A. Pott
- New infinite classes of almost bent and almost perfect nonlinear polynomials are constructed. It is shown that they are affine inequivalent to any sum of a power function and an affine function

- A new class of monomial bent functions
- A. Canteaut, P. Charpin, G. Kyureghyan
- We study the Boolean functions , of the form
**Failed to parse (unknown function "\Tr"): {\displaystyle f(x)=\Tr(\lambda x^d)}**with and . Our main result is the characterization of those for which 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 over . Further we determine the Walsh spectra of some related quadratic functions, the derivatives of the functions .

- 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
**Failed to parse (unknown function "\Tr"): {\displaystyle x^3+\Tr(x^9)}**over . It is proven that for this function is CCZ-inequivalent to the Gold functions, and in the case 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 known-plaintexts and 16-round DES cipher with 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 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 : A New Case for n Divisible by 5
- H. Dobbertin
- We prove that for
**Failed to parse (syntax error): {\displaystyle d = 2^{4s} + 2^{3s} + 2^{2s} + 2^s − 1}**the power function is almost perfect nonlinear (APN) on , i.e. for each the equation has either no or precisely two solutions in . 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 : The Niho Case
- H. Dobbertin
- Almost perfect nonlinear (APN) mappings are of interest for applications in cryptography. We prove for odd and the exponent
**Failed to parse (syntax error): {\displaystyle d=2^{2r}+2^r−1}**, where , that the power functions on 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 is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequences of degree and a decimation of that sequence by takes on precisely the three values**Failed to parse (syntax error): {\displaystyle −1}**,**Failed to parse (syntax error): {\displaystyle −1 \pm 2^{(n+1)/2}}**.

- Almost Perfect Nonlinear Power Functions on : The Welch Case
- H. Dobbertin
- We summarize the state of the classification of almost perfect nonlinear (APN) power functions on 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 , the power function is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree and a decimation of that sequence by takes on precisely the three values , .

- [Y. Edel, A. Pott https://pdfs.semanticscholar.org/0d6c/71fac2ec96cfe437a02e558fd26a33ea5bed.pdf]
- A new almost perfect nonlinear function which is not 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.

- 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
**Failed to parse (syntax error): {\displaystyle \mathbb{F}_{2^{10}}**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.