People in Boolean Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
(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...")
 
No edit summary
(11 intermediate revisions by 2 users not shown)
Line 1: Line 1:
* [http://ieeexplore.ieee.org/abstract/document/1683931/ On Almost Perfect Nonlinear Functions Over $\mathbb{F}_2^n$]
* [http://christina-boura.info Christina Boura] (Versailles Saint-Quentin-en-Yvelines University)
** 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


* [https://people.uib.no/lbu061/ Lilya Budaghyan] (University of Bergen)


* [https://link.springer.com/chapter/10.1007/978-3-642-38348-9_24 New Links between Differential and Linear Cryptanalysis]
* Marco Calderini (University of Bergen)
** 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.


* [https://www.paris.inria.fr/secret/Anne.Canteaut/English/index.html Anne Canteaut] (INRIA)


* [https://link.springer.com/article/10.1023%2FA%3A1008344232130?LI=true Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems]
* [http://www.math.univ-paris13.fr/~carlet/ Claude Carlet] (Université Paris 8, University of Bergen)
** C. Carlet, P. Charpin, V. Zinoviev
** Almost bent functions oppose an optimum resistance to linear and differential cryptanalysis. We


* [https://www.rocq.inria.fr/secret/Pascale.Charpin/English/index.html Pascale Charpin ] (INRIA)


* [https://link.springer.com/chapter/10.1007/978-3-319-16277-5_5 Open Questions on Nonlinearity and on APN Functions]
* [http://www.math.udel.edu/~coulter/ Robert Coulter] (University of Delaware)
** 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.


* John Dillon (National Security Agency)


* [https://eprint.iacr.org/2017/516.pdf Characterizations of the differential uniformity of vectorial functions by the Walsh transform]
* [https://www.cse.ust.hk/faculty/cding/ Cunsheng Ding] (Hong Kong University of Science and Technology)
** C. Carlet
** TODO


* [https://www.mathi.uni-heidelberg.de/~yves/ Yves Edel] (Heidelberg University)


* [http://www.sciencedirect.com/science/article/pii/S0885064X03001158 Highly nonlinear mappings]
* [https://its-lab.hs-emden-leer.de/ Patrick Felke] (Hochschule Emden/Leer)
** 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.


* Keqin Feng (Tsinghua University)


* [https://link.springer.com/chapter/10.1007/BFb0053450 Links between differential and linear cryptanalysis]
* Faruk Göloglu (Charles University in Prague)
** 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.


* Anastasiya Gorodilova (Novosibirsk State University)


* [https://link.springer.com/article/10.1007/s10623-008-9194-6 On the classification of APN functions up to dimension five]
* [http://www.ii.uib.no/~torh/ Tor Helleseth] (University of Bergen)
** 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.


* [http://shell.cas.usf.edu/~xhou/index.htm Xiang-dong Hou] (University of South Florida)


* [http://www.sciencedirect.com/science/article/pii/S1071579707000718 New families of quadratic almost perfect nonlinear trinomials and multinomials]
* Valeriya Idrisova (Novosibirsk State University)
** C. Bracken, E. Byrne, N. Markin, G. McGuire
** We introduce two new infinite families of APN functions, one on fields of order $2^{2k}$ for $k$ not divisible by $2$, and the other on fields of order $2^{3k}$ for $k$ not divisible by $3$. The polynomials in the first family have between three and $k+2$ terms, the second family's polynomials have three terms.


* [https://pages.uoregon.edu/kantor/ William Kantor] (University of Oregon)


* [https://www.researchgate.net/publication/265815787_An_APN_permutation_in_dimension_six An APN permutation in dimension six]
* [https://www.csun.edu/~danielk/ Daniel Katz] (California State University Northridge)
** KA Browning, JF Dillon, MT McQuistan, AJ Wolfe
** TODO


* [http://w3.balikesir.edu.tr/%7Eskavut/index.html Selçuk Kavut] (Balıkesir University)


* [http://ieeexplore.ieee.org/abstract/document/4036450/ An infinite class of quadratic APN functions which are not equivalent to power mappings]
* Alexander Kholosha
** 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


* [http://cs.uky.edu/~klapper/ Andrew Klapper] (University of Kentucky)


* [http://ieeexplore.ieee.org/abstract/document/4608957/ Two Classes of Quadratic APN Binomials Inequivalent to Power Functions]
* [http://users.uop.gr/~nkolok/ Nicholas Kolokotronis] (University of Peloponnese)
** 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.


* Gohar Kyureghyan (University of Rostock)


* [http://ieeexplore.ieee.org/abstract/document/4494676/ Classes of Quadratic APN Trinomials and Hexanomials and Related Structures]
* [http://langevin.univ-tln.fr Philippe Langevin] (University of Toulon)
** 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 $F_{2^{2m}}$ to $F_{2^{2m}}$. We check for $m = 3$ that some of these functions are CCZ-inequivalent to power functions.


* [http://www.crypto.rub.de/staff/leander.html.en Gregor Leander] (Ruhr University Bochum)


* [http://ieeexplore.ieee.org/abstract/document/1603777/ New classes of almost bent and almost perfect nonlinear polynomials]
* [https://people.uib.no/chunlei.li/index.html Chunlei Li] (University of Bergen)
** 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


* Nian Li (Hubei University)


* [http://www.sciencedirect.com/science/article/pii/S1071579707000160 A new class of monomial bent functions]
* [http://cgi.di.uoa.gr/~klimn/ Konstantinos Limniotis] (National and Kapodistrian University of Athens)
** A. Canteaut, P. Charpin, G. Kyureghyan
** We study the Boolean functions $f_{\lambda}:\mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n} ,n=6r$, of the form $f(x)=\Tr(\lambda x^d)$ with $d=2^{2r}+2^r+1$ and $\lambda \in \mathbb{F}_{2^n}$. Our main result is the characterization of those $\lambda$ for which $f_\lambda$ 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 $2^r$ over $\mathbb{F}_2$. Further we determine the Walsh spectra of some related quadratic functions, the derivatives of the functions $f_\lambda$.


* [http://www.cecm.sfu.ca/~plisonek/ Petr Lisonek] (Simon Fraser University)


* [http://www.sciencedirect.com/science/article/pii/S1071579708000622 Constructing new APN functions from known ones]
* Mikhail Lobanov (Moscow State University)
** 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 $x^3+\Tr(x^9)$ over $\mathbb{F}_{2^n}$. It is proven that for $n \ge 7$ this function is CCZ-inequivalent to the Gold functions, and in the case $n=7$ 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).


* [https://www.isical.ac.in/~subho/ Subhamoy Maitra] (Indian Statistical Institute)


* [http://zoo.cs.yale.edu/classes/cs426/2012/bib/biham91differential.pdf Differential cryptanalysis of DES-like cryptosystems]
* Gary McGuire
** 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.


* [https://uclouvain.be/fr/repertoires/pierrick.meaux Pierrick Méaux] (Université catholique de Louvain)


* [https://link.springer.com/chapter/10.1007%2F3-540-48285-7_33 Linear Cryptanalysis Method for DES Cipher]
* Wilfried Meidl (Otto-von-Guericke-University)
** 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 $2^{21}$ known-plaintexts and 16-round DES cipher with $2^{47}$ 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 $2^{29}$ ciphertexts only.


* [http://www.math.univ-paris13.fr/~mesnager/index-en.html Sihem Mesnager] (Université Paris 8)


* [https://link.springer.com/chapter/10.1007/3-540-48285-7_6 Differentially uniform mappings for cryptography]
* [https://homes.esat.kuleuven.be/~snikova/ Svetla Nikova] (KU Leuven)
** 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.


* [https://users.ics.aalto.fi/knyberg/ Kaisa Nyberg] (Aalto University)


* [https://link.springer.com/chapter/10.1007/978-3-642-56755-1_11 Almost Perfect Nonlinear Power Functions on $GF(2^n)$: A New Case for n Divisible by 5]
* [http://www.ii.uib.no/~matthew/ Matthew Parker] (University of Bergen)
** H. Dobbertin
** We prove that for $d = 2^{4s} + 2^{3s} + 2^{2s} + 2^s − 1$ the power function $x^d$ is almost perfect nonlinear (APN) on $L = GF(2^{5s})$, i.e. for each $a \in L$ the equation $(x + 1)^d + x^d = a$ has either no or precisely two solutions in $L$. 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.


* Enes Pasalic (University of Primorska)


* [http://www.sciencedirect.com/science/article/pii/S089054019892764X Almost Perfect Nonlinear Power Functions on $GF(2^n)$: The Niho Case]
* [https://wwwen.uni.lu/snt/people/leo_paul_perrin Léo Paul Perrin] (INRIA)
** H. Dobbertin
** Almost perfect nonlinear (APN) mappings are of interest for applications in cryptography. We prove for odd $n$ and the exponent $d=2^{2r}+2^r−1$, where $4r+1 \equiv 0 mod n$, that the power functions $x^d$ on $GF(2^n)$ 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 $x^d$ is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequences of degree $n$ and a decimation of that sequence by $d$ takes on precisely the three values $−1$, $−1 \pm 2^{(n+1)/2}$.


* [https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=761283 Almost Perfect Nonlinear Power Functions on $GF(2^n)$ : The Welch Case ]
* George Petrides (University of Bergen)
** H. Dobbertin
** We summarize the state of the classification of almost perfect nonlinear (APN) power functions $x^d$ on $GF(2^n)$ 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 $n=2m+1$, the power function $x^{2m+3}$ is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree $n$ and a decimation of that sequence by $2^{m}+3$ takes on precisely the three values $-1$, $-1 \pm 2^{ m+1}$.


* [https://www.tudelft.nl/en/staff/s.picek/ Stjepan Picek] (TU Delft)


* [Y. Edel, A. Pott https://pdfs.semanticscholar.org/0d6c/71fac2ec96cfe437a02e558fd26a33ea5bed.pdf]
* [https://www.math.ovgu.de/Institute/IAG/Diskrete+Mathematik/Mitglieder/Pott.html Alexander Pott] (Otto von Guericke University of Magdeburg)
** 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.


* [http://www.ii.uib.no/~riera/ Constanza Riera] (Høgskulen på Vestlandet)


* [http://ieeexplore.ieee.org/abstract/document/1580810/ A new APN function which is not equivalent to a power mapping]
* [http://iml.univ-mrs.fr/~rodier/ François Rodier] (Aix-Marseille University)
** Y. Edel, G. Kyureghyan, A. Pott
 
** A new almost-perfect nonlinear function (APN) on $\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.
* [http://www.science.unitn.it/~sala/ Massimiliano Sala] (University of Trento)
 
* [http://faculty.nps.edu/pstanica/ Pantelimon Stanica] (Naval Postgraduate School)
 
* [http://comsec.uwaterloo.ca/~y24tan/ Yin Tan] (University of Waterloo)
 
* Chunming Tang (China West Normal University)
 
* Deng Tang (Southwest Jiaotong University)
 
* Yuriy Tarannikov (Moscow State University)
 
* [http://people.math.carleton.ca/~dthomson/ David Thomson] (Carleton University)
 
* [http://math.nsc.ru/~tokareva/ Natalia Tokareva] (Russian Academy of Sciences)
 
* [http://people.sabanciuniv.edu/alev/ Alev Topuzoğlu] (Sabancı University)
 
* Satoshi Yoshiara (Tokyo Woman’s Christian University)
 
* Xiangyong Zeng (Hubei University)
 
* Fengrong Zhang (China University of Mining and Technology)

Revision as of 09:39, 27 January 2021

  • Marco Calderini (University of Bergen)
  • John Dillon (National Security Agency)
  • Keqin Feng (Tsinghua University)
  • Faruk Göloglu (Charles University in Prague)
  • Anastasiya Gorodilova (Novosibirsk State University)
  • Valeriya Idrisova (Novosibirsk State University)
  • Alexander Kholosha
  • Gohar Kyureghyan (University of Rostock)
  • Nian Li (Hubei University)
  • Mikhail Lobanov (Moscow State University)
  • Gary McGuire
  • Wilfried Meidl (Otto-von-Guericke-University)
  • Enes Pasalic (University of Primorska)
  • George Petrides (University of Bergen)
  • Chunming Tang (China West Normal University)
  • Deng Tang (Southwest Jiaotong University)
  • Yuriy Tarannikov (Moscow State University)
  • Satoshi Yoshiara (Tokyo Woman’s Christian University)
  • Xiangyong Zeng (Hubei University)
  • Fengrong Zhang (China University of Mining and Technology)