Construction of Bent Functions via Niho Power Functions

English
21 Pages
Read an excerpt
Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 7
Language English
Report a problem
ConstructionofBentFunctionsviaNihoPowerFunctionsHansDobbertin1,GregorLeander1,AnneCanteaut2,ClaudeCarlet2,PatrickFelke1,PhilippeGaborit31DepartmentofMathematics,Ruhr-UniversityBochum,D-44780Bochum,Germany2INRIA-ProjectCODES,BP105,78153LeChesnayCedex,France3EquipeArithmétiqueCodageetCryptographie,UniversitedeLimoges,France29thMarch2004AbstractABooleanfunctionwithanevennumbern=2kofvariablesiscalledbentifitismaximallynonlinear.Wepresenthereanewcon-structionofbentfunctions.Booleanfunctionsoftheformf(x)=tr(α1xd1+α2xd2),α12,xF2n,areconsidered,wheretheexpo-nentsdi(i=1,2)areofNihotype,i.e.therestrictionofxdionF2kislinear.Weproveford1=2k+1andd2=32k11,d2=2k+3ifkisodd,d2=(2k+5)/3ifkiseven,resp.,thatfisabentfunctionifα1+α1=1andα2=1.1IntroductionBentfunctionsaremaximallynonlinearBooleanfunctionswithanevennum-berofvariables.BentfunctionswereintroducedbyRothaus[11]in1976.Becauseoftheirownsakeasinterestingcombinatorialobjects,butalsobe-causeoftheirrelationstocodingtheory(Reed-Mullercodes)andapplica-tionsincryptography(designofstreamciphers),theyhaveattractedalotofresearch,speciallyinthelasttenyears.Acompleteclassificationofbentfunctionsiselusiveandlookshopeless.Despitetheirsimpleandnaturaldefinition,bentfunctionshaveturnedouttoadmitaverycomplicatedstructureingeneral.Ontheotherhandmanyspecialexplicitconstructionsareknown,primaryonesgivingbentfunctionsfromthescratchandsecondaryonesbuildinganewbentfunctionfromoneorseveralgivenbentfunctions.Allknownprimaryconstructionsofbentfunction,withonlyonerecentexception(see[3]and[1]),areweaklynormal(cf.[4]).ABooleanfunctionwithnvariables,neven,iscalledweakly1
normal(resp.normal)ifitisaffine(resp.constant)onsomeaffinesubspaceofdimensionn/2.InthepresentpaperwestudytracesofalinearcombinationoftwoNihopowerfunctions.ApowerfunctiononF2niscalledaNihopowerfunctionifitsrestrictiontoF2kislinear.Theconsideredfunctionsarethereforeweaklynormal.Inthisway,undercertainconditions,wegetasourmainresults(Theorems1,2and3)threeprimaryconstructionofbentfunctions.ThestartingpointofourproofsconfirmingthebentpropertyisbasedonaclassicaltheoremofNiho[9]andnewmethodstohandleWalshtransformsofNihopowerfunctionsfrom[7].2PreliminariesThroughoutletL=F2nbeafinitefieldofcharacteristic2,wheren=2k,andletK=F2kthesubfieldofLwith[L:K]=2.ThefieldextensionL/KhasamazingsimilaritieswiththeextensionC,thefieldofcomplexnumbers,overthefieldofrealnumbersR.TheconjugateofxLoverKwillbedenotedbyx,i.e.,x=x2k.WedenotetheabsolutetraceonLbyiXtrL(x)=x2,xL,n<idnatrL/K(x)=x+xreferstotherelativetracefromLontoK.NotethataccordingtothetransitivitylawforthetracefunctionwehavetrL=trKtrL/K.TherelativenormwithrespecttoL/KisdefinedasnormL/K(x)=xxandmapsLontoK.ThecanonicaladditivecharacteronLisdefinedasχL(x)=(1)trL(x).TheunitcircleofListhesetS={uL:uu=1}ofallelementshavingrelativenorm1.InotherwordsSisthegroupof(2k+1)-strootsofunity,andthereforetheorderofSis2k+1,sinceLiscyclicand2k+1divides2n1.2