On the linear structures of balanced functions and quadratic APN functions
- PDF / 439,269 Bytes
- 22 Pages / 439.642 x 666.49 pts Page_size
- 28 Downloads / 235 Views
On the linear structures of balanced functions and quadratic APN functions A. Musukwa1 · M. Sala2 Received: 21 September 2019 / Accepted: 19 March 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The set of linear structures of most known balanced Boolean functions is non-trivial. In this paper, some balanced Boolean functions whose set of linear structures is trivial are constructed. We show that any APN function in even dimension must have a component whose set of linear structures is trivial. We determine a general form for the number of bent components in quadratic APN functions in even dimension and some bounds on the number are produced. We also count bent components in any quadratic power functions. Keywords Boolean functions · Linear space · APN functions · Bent functions Mathematics Subject Classification 2010 06E30 · 94A60 · 14G50
1 Introduction A Boolean function is any function from Fn2 to F2 . A vector v in a vector space Fn2 is a linear structure of a Boolean function f if the derivative of f at v is constant. In this paper, the set of linear structures of a Boolean function is called linear space. Balancedness is an important cryptographic property of Boolean functions as it is often desirable for cryptographic primitives to be unbiased in output. By recognising such importance, a lot of papers have been written on construction of balanced functions along with other cryptographic properties (see for example [5, 8, 10, 16]). Most authors are concerned with construction of balanced Boolean functions with high nonlinearity. However, in this study we are interested in something different. We believe that most known balanced functions do have non-trivial linear spaces. A typical example of a balanced function with This article belongs to the Topical Collection: Boolean Functions and Their Applications IV Guest Editors: Lilya Budaghyan and Tor Helleseth A. Musukwa
[email protected] M. Sala [email protected] 1
Mzuzu University, P/Bag 201, Luwinga, Mzuzu 2, Malawi
2
University of Trento, Via Sommarive, 14, Povo, 38123, Trento, Italy
Cryptography and Communications
non-trivial linear space is g(x1 , ..., xn−1 )+xn , where n is positive integer. It is a well-known balanced function and its linear space is non-trivial as it clearly includes the nonzero vector (0, ..., 0, 1). In this paper, we construct some balanced functions whose linear spaces are trivial and in some cases we give a lower bound on their nonlinearities. The nonlinearity and differential uniformity of a vectorial Boolean function (a mapping from Fn2 to Fn2 ) are properties which are used to measure the resistance of a function towards linear and differential attacks, respectively. APN and AB functions provide optimal resistance against the said attacks. This gives a justification as to why there are many studies regarding APN and AB functions. In this paper, we show that there must be at least one component of an APN function in even dimension that has a trivial linear space. In partic
Data Loading...
