Abstract. Boolean functions on GF (2) which satisfy the Strict Avalanche Criterion (SAC) play an important role in the art of information security. In this paper, we extend the conception SAC to finite fields GF (p). A necessary and sufficient condition is
STRICTAVALANCHECRITERIONOVERFINITEFIELDS
YUANLIANDT.W.CUSICK
Abstract.BooleanfunctionsonGF(2)whichsatisfytheStrictAvalancheCriterion(SAC)playanimportantroleintheartofinformationsecurity.Inthispaper,weextendtheconceptionSACto nite eldsGF(p).Anecessaryandsu cientconditionisgivenbyusingspectralanalysis.Also,basedonaninterestingpermutationpolynomialtheorem,weprovevariousfactsabout(n 1)-thorderSACfunctionsonGF(p).Wealsoconstructmanysuchfunctions.
1.Introduction
Resilientfunctions,bentfunctionsandfunctionswhichsatisfySAChaveim-portantcryptographicapplications.SACwasintroducedbyWebsterandTavares[16]inconnectionwithastudyofthedesignofS-boxes.ABooleanfunctioninnvariablesissaidtosatisfySACifcomplementinganyoneoftheninputbitsresultsinchangingtheoutputbitwithprobabilityexactlyonehalf.Forr´e[5]extendedthisconceptionbyde ningthehigherorderSAC.ABooleanfunctionofnvariablessatis estheSACoforderk(SAC(k)),0≤k≤n 2,ifwheneverkinputbitsare xedarbitrarily,theresultingfunctionofn kvariablessatis esSAC.ThepropertiesofSACfunctionshavebeenwellstudied(see[1],[2],[3],[8],[9],[17]).Recently,CusickandYuan[4]describedamethodto ndk-thordersymmetricSACfunctionsforanyk,k≤n 2.Ontheotherhand,it’snaturaltoextendthevariouscryptographicconceptionsfromGF(2)toGF(p)orGF(p)n.Forexample,[14]and[19]studiedtheresilientfunctionsonGF(p).Also,[7],[11],[12]investi-gatedthegeneralizedbentfunctionsonGF(p)n.Inthispaper,we rstlyintroducethede nitionofSAConGF(p).Similarto[5],wegiveaspectralanalysis,andanecessaryandsu cientconditionforSACisgiven.Basedonaninterestingresultwhichwasindependentlyprovedbythreeresearchgroupsbetween1989and1990,weprovevariousfactsabout(n 1)-orderSAConGF(p).Incontrust,onGF(2)thehighestorderofSACisonlyn 2.Usingsomeelementarynumbertheory,weconstructmanySAC(n 1)functions.Section2willlistsomewellknownre-sultsaboutFouriertransform.Section3willintroducethede nitionofSACanddiscussitsspectralanalysis.Insection4,anexplanationofSACisgivenfromadi erentpointofview.Wegivethede nitionofhigherorderSACinsection5andaspectralanalysisisprovidedforSAC(1).Insection6weconstructmanySAC(n 1)functions.Someopenquestionsarelistedinsection7.
Keywordsandphrases.Fouriertransform,cryptography,Booleanfunctions,algebraicnormalform,strictavalanchecriterion,resilience,bentfunctions,permutationpolynomials, nite eld,quadraticresidue,Legendresymbol,
1
64-bit blockcipher with key length of 128 bits, submitted by MediaCrypt AG...ect and the degree of strict avalanche criterion of the cipher are computed...
热门文档