Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Construction of Bent Functions via Niho Power Functions

21 pages
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


Voir plus Voir moins
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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin