[PDF] On the Affine Equivalence and Nonlinearity Preserving Bijective

View - Download On the Affine Equivalence and Nonlinearity Preserving Bijective

Previous PDF

Next PDF

On the Affine Equivalence and Nonlinearity

Preserving Bijective Mappings

Isa Sertkaya1,2and Ali Doganaksoy1,3

1

Institute of Applied Mathematics,

Middle East Technical University, Ankara, Turkey

2National Research Institute of Electronics and Cryptology,

T¨UBITAK-UEKAE, Gebze, Kocaeli, Turkey

3Department of Mathematics,

Middle East Technical University, Ankara, Turkey

isa@uekae.tubitak.gov.tr, aldoks@metu.edu.tr Abstract.It is well-known that affine equivalence relations keep non- lineaerity invariant for all Boolean functions. The set of all Boolean func- tions,Fn, over IFn2, is naturally regarded as the 2ndimensional vector space, IF 2n

2. Thus, while analyzing the transformations acting onFn,

S

22n, the group of all bijective mappings, defined from IF2n

2onto itself

should be considered. As it is shown in [1-3], there exist non-affine bijec- tive transformations that preserve nonlinearity. In this paper, first, we prove that the group of affine equivalence relations is isomorphic to the automorphism group of Sylvester Hadamard matrices. Then, weshow that new nonlinearity preserving non-affine bijective mappings also ex- ist. Moreover, we propose that the automorphism group of nonlinearity classes, should be studied as a subgroup ofS22n, since it contains trans- formations which are not affine equivalence relations. Keywords:Boolean functions, nonlinearity, affine equivalence, auto- morphism groups, Sylvester Hadamard matrices

1 Introduction

A very basic and natural way to study and analyze a large algebraic set is to partition it under an equivalence relation, and then to choose a representative for each class to analyze the reduced sized set composing of representative elements. Such a procedure is a very important problem for Boolean functions due to their importance in different disciplines such as switching theory, coding theory and cryptography. The study of the actions of basic transformations on Booleanfunctions date back to Harrison [4,5], and later [6-8] where the main concern is the switching theory. In coding theory, affine transformations are analyzed especially for the

Reed-Muller codes, [9-11].

In cryptography, one of the main design criteria is nonlinearity which is defined as the minimum Hamming distance of a function to the affine functions. Hence, partitioning the set of Boolean functions into disjoint classes with respect to their nonlinearity values, enumerating highly nonlinear Boolean functions, constructing new function types with desired properties are important, yet open problems. Due to the previous studies and their simple structures, generally affine equivalence relations are used for determining the equivalence classes. Meier and Staffelbach, in [12], showed that nonlinearity is invariant under the action ofAGLn, then Preneel, in [13], proved affine equivalence relations (mappings belonging toAGLn?An), also preserve nonlinearity. Moreover, in [14], so called CCZ-equivalence is proposed, but in [15], it is proved that two Boolean functions are CCZ-equivalent if and only if they are affine equivalent. Further reading can be found in [16-18]. Naturally, the set of all Boolean functions can be seen as the2ndimensional vector space IF 2n

2over IF2. Hence, expanding the set of transformations to all

bijective transformations that can be defined over IF 2n

2, namely toS22n, is a

reasonable extension. In [1-3], the authors analyzed such mappings, and showed existence of non-affine mappings. In this paper, first, we give notations and review affine equivalence relations, then we prove that the group of affine equivalence relations exactly determines, and thus is isomorphic to, the automorphism group of Sylvester Hadamard ma- trices. Then, we give examples of new nonlinearity preserving non-affine map- pings. Moreover, we discuss the main concerns about the automorphism group of Boolean functions, nonlinearity classes and instead of the restricting to affine equivalence relations, we propose that it should be studiedas a subgroup ofS22n.

2 Preliminaries

In this section, we fix the notation and state the necessary definitions relating to Boolean functions and nonlinearity criteria in cryptography.

Let IF

n

2be the set of alln-tuples of elements belonging to IF2(Galois field

of order two). Naturally, IF n

2possesses ann-dimensional vector space structure

over IF

2and assumeslexicographicalordering. Hence, it is possible to represent

the vectors of IF n

2as;α0= (0,0,...,0)< α1= (0,0,...,0,1)< ... < α2n-1=

(1,1,...,1). A Boolean functionf: IFn2→IF2maps a binaryn-tuple to a single binary output. Most common ways to represent a Boolean functionf: IFn2→IF2 uniquely is either by its truth table or algebraic normal form: -Thetruth tableoffis the 2ntuple T f= (f(α0),f(α1),...,f(α2n-1)) whereαi?IFn2are as defined above. -Thealgebraic normal formoffis f(xn,xn-1,...,x1) =c0?c1x1?···?cnxn?c12x1x2?···?c12···nx1x2···xn wherec0,c1,...,c12···n?IF2. The set of all Boolean functions defined on IFn2is denoted byFnand trivially its cardinality|Fn|is 22n. Indeed, by considering the truth tables or the coefficients of algebraic normal form as a vector of length 2 nwith elements from IF2,Fn can regarded as IF2n 2. The degree,deg(f), of the algebraic normal form a functionfis calledalge- braic degree, or shortly degree, off. A Boolean functionfis calledaffineif its degree is at most 1, i.e. it is of the form f(xn,xn-1,...,x1) =c0?c1x1?···?cnxn or, equivalently, f(xn,xn-1,...,x1) =?c,x??c0. wherec0?IF2and?c,x?=c1x1?···?cnxnis thestandard inner productdefined over IF n

2. The set of all affine Boolean functions on IFn2is denoted byAn.

TheHamming weightof a vectorα?IFn2, denoted byw(α), is the number of ones inα. Thesupportof a functionf? Fnis defined to be the set{α? IF n

2|f(α) = 1}and is denoted bySupp(f). Obviously, Hamming weight off,

w(f), is equal to the cardinality of the support off, i.e.w(f) =|Supp(f)|. TheHamming distancebetween two functionsf,g? Fnis defined as the number of different components in their truth tables, or the Hamming weight of f?g,w(f?g), is denoted byd(f,g). Thenonlinearity,Nf, of a functionfis its distance to the nearest affine function: N f= ming?And(f,g)

TheWalsh transform4of a functionfis defined as

W f(ω) =? x?IFn2(-1)f(x)??x,ω? whereω?IFn2and?x,ω?being the standard inner product on IFn2. The truth table of the Walsh transform, W f= (Wf(α0),Wf(α1),...,Wf(α2n-1)) is called theWalsh Spectrumoffand it can also be expressed as, W signed function(-1)f(x)offandHnis the 2n×2nSylvester Hadamard matrix. Nonlinearity of a functionfcan also be expressed with the Walsh transform offas N f= 2n-1-maxω?IFn2|Wf(ω)|.

4It is also calledWalsh Hadamard transform, and is thediscrete Fourier transform

of the function (-1)f(x). A functionfis calledbent function[19,20], ifWf(w) =±2n/2for anyw?IFn2. Bent functions attains maximal nonlinearity, but they onlyexist whennis even.

The set of bent functions is, denoted byBn.

Ann×nmatrixHwith all entries±1 is calledHadamard matrixifH·Ht= nI nwhereInbeing the identity matrix of ordern. Hadamard matrices were first investigated by Sylvester [21], and then Hadamard [22] studied such matrices as solutions to the problem of maximum determinant of matrices, for further reading please refer to [23-25]. Definition 1.[23] Twon×nHadamard matrices are equivalent if one can be obtained from the other by performing a finite sequence of permuting the rows or the columns and multiplying a row or a column by-1. LetSnbe the group of all permutation matrices of ordernandDnbe the group of all diagonal matrices of ordernwith diagonal entries being 1 or-1. Then, the group of monomial matrices, denoted byS±n, is the semi direct product S n?DnofSnwithDn. Hadamard equivalence, in terms of row and column permutations and negations, is in fact, equivalent to the action of monomial matrices on Hadamard matrices. Under this action, naturally the automorphism group of the given matrix will be the stabilizer. Definition 2.[23] The automorphism groupAut(H)of a Hadamard matrix H of ordern, is the group of all monomial matrix pairs(P,Q)satisfyingPHQ=H with the group operation◦defined as, (P1,Q1)◦(P2,Q2) = (P1P2,Q1Q2). Hence, the automorphism group of a Sylvester Hadamard matrixHnof order 2 nis

Aut(Hn) ={(P,Q)?S±2n|PHnQ=Hn}.

3 Affine equivalence

Definition 3.[10] Denote byGLnthe group of all nonsingular matrices of order nonIF2, i.e. the general linear group. Denote byAGLnthe group {(A,α)|A?GLn,α?IFn2}, which is the semi direct productGLn?IFn2ofGLnwithIFn2. The group operation ◦is defined by (A,α)◦(B,β) = (AB,βA?α) (A,α)-1= (A-1,αA-1)

Similarly, the groupAGLn?An,

or, withτ:x?→xA?αandf(x) =?x,β? ?a, simply, {(τ,f)|τ?AGLn,f? An} is the semi direct product ofAGLnwith the affine Boolean functionsAn, where the group operation◦is (τ,f)◦(σ,g) = (τ◦σ,τ(g) +f) (τ,f)-1= (τ-1,τ-1(f))

The action of the groupAGLn?Anis defined by

(τ,l) :Fn?→ Fn f(x)?→f(xA?α)? ?x,β? ?a For any functionsf,g? Fn,fandgare calledaffine equivalentif there exists an bijective mapping (τ,l)?AGLn?Anwithτ:x?→xA?αand l(x) =?x,β? ?asuch that f(x) =g(xA?α)? ?x,β? ?a .(1) Preneel, as stated below, proved that the action of an affine equivalence relation results in a signed permutation on the Walsh spectra of the function. Under the action ofAGLn?An, algebraic degree, the distribution of absolute Walsh spec- tra, hence nonlinearity and the distribution of absolute autocorrelation spectra remains invariant [17]. Proposition 1.[13] Letf,g? Fnbe two affine equivalent functions such that f(x) =g(xA?α)??x,β??a, then for the Walsh transform offandgthe fol- lowing relation holds. W f(ω) = (-1)?α,(ω?β)(A-1)t?+aWg((ω?β)(A-1)t) In [3], the authors prove that there exists a correspondencebetweenAGLnand Aut(Hn), such that, for anyτ?AGLn, (resp.A?GLn), there exists a unique (P,Q)?Aut(Hn) withP?S2nandQ?S±2n\S2n, (resp.Q?S2n). As we state in Theorem 1, we prove that this correspondence extends to anisomorphism betweenAGLn?AnandAut(Hn). Theorem 1.For any functionsf,g? Fn,fandgare affine equivalent with Equation 1 if and only if there exists a unique monomial matrix pair(P,Q)?

Aut(Hn)such that

W fQ=Wg or, equivalently, In fact, Theorem 1 gives more insight for the affine equivalence relations as follows. Corollary 1.For any affine equivalent functionsf,g? Fn, with f(x) =g(xA?α)??x,β??a the monomial matrix pair(P,Q)?Aut(Hn)satisfies the following properties:

1.P?S2nif and only ifβ= 0,a= 0, indeed,Q?S2nif and only ifα= 0.

2.P,Q?D2nif and only ifAis the identity matrix of ordernandα= 0.

4 Nonlinearity preserving bijective mappings

Since, the truth table of a function is a vector of length 2 nwith elements belong- ing to IF

2, the set of all Boolean functions onnvariables,Fncan be regarded

as the vector space IF 2n

2. Hence, any map acting on the truth table of a Boolean

function can be seen as a map defined from IF 2n

2into itself. Moreover, if a map

is bijective (invertible) then obviously, it is a permutation of IF2n

2, and hence is

an element ofS22n.

Any mapψ?S22nfrom IF2n

2to IF2n

2, is in fact a vectorial Boolean function5.

Any vectorial Boolean functionψ: IF2n

2→IF2n

2can be represented in the form

T f?→ψ(Tf), that is ψ(x0,x1,...,x2n-1) = (f0(x0,x1,...,x2n-1),...,f2n-1(x0,x1,...,x2n-1)) where eachfiis a Boolean function from IF2n

2to IF2and called thecoordinate

orcomponent functionofψand eachxibeingf(αi), i.e. the value of the acted

Boolean function atαi?IFn2.

Since, eachfi? F2n, it can be represented by its unique algebraic normal form: f i(x0,x2,···,x2n) =c(i)

0?c(i)

1x0?...?c(i)

12···2nx1x2···x2n.

Hence, we have,

ψ:Tf?-→((((((c

(0) c (1) c (2n-1)

0?c(2n-1)

1f(α0)?...?c(2n-1)

t

Then we get,

ψ:Tf?-→(((((((((((??????

c (0) 0 c(1)0...c(2n-1)

0??????

0? ?c (0) 1 c(1)1...c(2n-1)

1??????

1f(α0)? ··· ???????c

(0) 2n c (1)

2n...c(2n-1)

2 n??????

2nf(α2n-1)?

5In the literature, different names are also used such (2n,2n)-functions, multi-output

Boolean functions, Boolean maps, Substitution boxes (S-Boxes). ??????c (0) 12 c(1)12...c(2n-1)

12??????

12f(α0)f(α1)? ··· ???????c

(0)

12···2n

c (1)

12···2n...c(2n-1)

12···2n??????

or equivalently,

ψ:Tf?→(λ0?ATtf?λ12f(α0)f(α1)? ··· ?λ12···2nf(α0)f(α1)···f(α2n-1))t,

(2) whereAis the matrix is constituted by [λ1λ2... λ2n]. Naturally, the bijective maps can be classified with respectto their algebraic forms, as follows. -ψ?S22nis calledlinearif it is of the formψ:Tf?→(ATtf)t, that is,

•λ0= [0 0...0]t,

•λi= [0 0...0]t, for alli /? {0,1,2,...,2n}, •A?GL2n, i.e.Ais an invertible matrix of order 2n. -ψ?S22nis calledaffineif it is of the formψ:Tf?→(λ0?ATtf)t, that is, •λi= [0 0...0]t, for alli /? {0,1,2,...,2n}, •A?GL2n, i.e.Ais an invertible matrix of order 2n. -ψ?S22nis callednon-affineif it has at least one non-zeroλi, fori /? {0,1,2,...,2n}. Denote byPN(Fn), the group of all nonlinearity preserving bijective maps acting on the functions withn-variables, i.e. P

N(Fn) ={ψ?S22n|Nf=Nψ(Tf), for allf? Fn}.

Note that, affine equivalence relations, reviewed in the previous section, are in fact a small subgroup of the affine bijective transformations of the formψ: T f?→(λ0?ATtf)t. Proposition 2.Any affine equivalence relation(τ,l)?AGLn?Anwithτ: x?→xA?αandl(x) =?x,β? ?a, i.e.f(x)?→f(xA?α)? ?x,β? ?a,for all f? Fn, can be uniquely represented asψ?S22n, such that, T f?→(λ0?PTtf)t whereP?S2nis a permutation matrix of order2nandλ0is the truth table of the affine functionl. In [3], by giving necessary and sufficient conditions to preserve nonlinearity (as stated in Theorem 2), the authors proved that not all of the affine bijective transformations of the formψ:Tf?→(λ0?ATtf)tare inPN(Fn). Furthermore, as recalled in Proposition 3, they also show the existence of non-affine nonlinearity preserving bijective transformations. Theorem 2.[3] Letψ?S22nbe an affine bijective transformation so that for allf? Fn,

ψ:Tf?→(Tl?ATtf)t,

wherel? FnandA?GL2nare fixed. Then,ψ? PN(Fn)if and only ifl? AnandA=B?P, whereP?S2n corresponds to an element ofAGLn, andBis the matrix of order2noverIF2 whose columns are the truth table of affine functions, not necessarily distinct. Proposition 3.[3] Letψ?S22nbe a mapping that satisfies the following con- ditions, with respect to Equation 2,

1.λ0is the truth table of an affine function,

2. the matrixAsatisfies the conditions mentioned in Theorem 2,

3.λi"s are the truth table of some affine Boolean functions for all

i? {12,13,...,12···2n}where not all are the zero affine function. Then,ψ? PN(Fn), i.e.ψis an non-affine bijective mapping that preserves nonlinearity. Remark 1.Trivially, the transformations defined in Proposition 3, are non-affine. However, instead of all Boolean functions, when their action on a fixed function fis considered, the image of such transformations forfwill be equivalent to an affine mapping. That is to say, such mappingsψ?S22nbecome T f?→(PTtf?Tl)t where the functionlis the summation of someλi"s which are strictly determined bySupp(f). Such summations will differ for different functions, therefore, when their algebraic normal form is concerned, these transformations will be non-affine transformations. n|S22n||PN(Fn)|

216!≈2448!×8!≈230

quotesdbs_dbs14.pdfusesText_20

[PDF] matrix bipartite graph r

[PDF] matrix generator

[PDF] matrix injective

[PDF] matrix inverse 2x2 calculator

[PDF] matrix inverse method

[PDF] matrix multiplication c++

[PDF] matrix multiplication calculator 2x2

[PDF] matrix multiplication calculator 3x3

[PDF] matrix multiplication calculator desmos

[PDF] matrix multiplication calculator emath

[PDF] matrix multiplication calculator online

[PDF] matrix multiplication calculator with steps

[PDF] matrix multiplication calculator with variables

[PDF] matrix multiplication calculator wolfram

[PDF] matrix multiplication example