Construction of Bent Functions via Niho Power Functions

Description

Construction of Bent Functions via Niho Power Functions Hans Dobbertin1, Gregor Leander1, Anne Canteaut2, Claude Carlet2, Patrick Felke1, Philippe Gaborit3 1Department of Mathematics, Ruhr-University Bochum, D-44780 Bochum, Germany 2INRIA-Project CODES, BP 105, 78153 Le Chesnay Cedex, France 3Equipe Arithmétique Codage et Cryptographie, Universite de Limoges, France 29th March 2004 Abstract A Boolean function with an even number n = 2k of variables is called bent if it is maximally nonlinear. We present here a new con- struction of bent functions. Boolean functions of the form f(x) = tr(?1xd1 + ?2xd2), ?1, ?2, x ? F2n , are considered, where the expo- nents di (i = 1, 2) are of Niho type, i.e. the restriction of xdi on F2k is linear. We prove for d1 = 2k + 1 and d2 = 3 · 2k?1 ? 1, d2 = 2k + 3 if k is odd, d2 = (2k + 5)/3 if k is even, resp., that f is a bent function if ?1 + ?1 = 1 and ?2 = 1. 1 Introduction Bent functions are maximally nonlinear Boolean functions with an even num- ber of variables. Bent functions were introduced by Rothaus [11] in 1976.

• given bent


• bent functions


• boolean functions


• niho exponent


• walsh transforms


• exponent corresponding


• ??1 ?


• function

Sujets

• Boolean function

Informations

• Publié par: pefav
• Nombre de lectures: 8
• Langue: English

Extrait

ConstructionofBentFunctions viaNihoPowerFunctions HansDobbertin 1 ,GregorLeander 1 ,AnneCanteaut 2 , ClaudeCarlet 2 ,PatrickFelke 1 ,PhilippeGaborit 3 1 DepartmentofMathematics,Ruhr-UniversityBochum,D-44780Bochum,Germany 2 INRIA-ProjectCODES,BP105,78153LeChesnayCedex,France 3 EquipeArithmétiqueCodageetCryptographie,UniversitedeLimoges,France 29thMarch2004 Abstract ABooleanfunctionwithanevennumbern=2kofvariablesis calledbentifitismaximallynonlinear.Wepresenthereanewcon- structionofbentfunctions.Booleanfunctionsoftheformf(x)= tr(α 1 x d 1 +α 2 x d 2 ),α 1 ,α 2 ,x ∈ F 2 n ,areconsidered,wheretheexpo- nentsd i (i=1,2)areofNihotype,i.e.therestrictionofx d i on F 2 k is linear.Weproveford 1 =2 k +1andd 2 =3 ∙ 2 k−1 − 1,d 2 =2 k +3if k isodd, d 2 =(2 k +5)/3 if k iseven,resp.,that f isabentfunction if α 1 +α 1 =1 and α 2 =1 . 1Introduction BentfunctionsaremaximallynonlinearBooleanfunctionswithanevennum- berofvariables.BentfunctionswereintroducedbyRothaus[11]in1976. Becauseoftheirownsakeasinterestingcombinatorialobjects,butalsobe- causeoftheirrelationstocodingtheory(Reed-Mullercodes)andapplica- tionsincryptography(designofstreamciphers),theyhaveattractedalot ofresearch,speciallyinthelasttenyears. Acompleteclassificationofbentfunctionsiselusiveandlookshopeless. Despitetheirsimpleandnaturaldefinition,bentfunctionshaveturnedout toadmitaverycomplicatedstructureingeneral.Ontheotherhandmany specialexplicitconstructionsareknown,primaryonesgivingbentfunctions fromthescratchandsecondaryonesbuildinganewbentfunctionfromone orseveralgivenbentfunctions.Allknownprimaryconstructionsofbent function,withonlyonerecentexception(see[3]and[1]),areweaklynormal (cf.[4]).ABooleanfunctionwithnvariables,neven,iscalledweakly 1

normal(resp.normal)ifitisaffine(resp.constant)onsomeaffinesubspace ofdimension n/2 . InthepresentpaperwestudytracesofalinearcombinationoftwoNiho powerfunctions.Apowerfunctionon F 2 n iscalledaNihopowerfunction ifitsrestrictionto F 2 k islinear.Theconsideredfunctionsaretherefore weaklynormal.Inthisway,undercertainconditions,wegetasourmain results(Theorems1,2and3)threeprimaryconstructionofbentfunctions. Thestartingpointofourproofsconfirmingthebentpropertyisbasedona classicaltheoremofNiho[9]andnewmethodstohandleWalshtransforms ofNihopowerfunctionsfrom[7]. 2Preliminaries ThroughoutletL= F 2 n beafinitefieldofcharacteristic2,wheren=2k, andletK= F 2 k thesubfieldofLwith[L:K]=2.ThefieldextensionL/K hasamazingsimilaritieswiththeextension C ,thefieldofcomplexnumbers, overthefieldofrealnumbers R .Theconjugateofx ∈ LoverKwillbe denotedbyx,i.e., x=x 2 k . WedenotetheabsolutetraceonLby i X tr L (x)=x 2 ,x ∈ L, n<i dna tr L/K (x)=x+x referstotherelativetracefromLontoK.Notethataccordingtothe transitivitylawforthetracefunctionwehave tr L =tr K ◦ tr L/K . Therelativenormwithrespectto L/K isdefinedas norm L/K (x)=xx andmaps L onto K .Thecanonicaladditivecharacteron L isdefinedas χ L (x)=( − 1) tr L (x) . Theunitcircleof L istheset S = { u ∈ L:uu=1 } ofallelementshavingrelativenorm 1 .Inotherwords S isthegroupof (2 k +1)-strootsofunity,andthereforetheorderofSis2 k +1,sinceL ∗ is cyclicand2 k +1divides2 n − 1. 2