A MATRIX CONSTRUCTION OF BOOLEAN FUNCTIONS WITH MAXIMUM ALGEBRAIC IMMUNITY

《A MATRIX CONSTRUCTION OF BOOLEAN FUNCTIONS WITH MAXIMUM ALGEBRAIC IMMUNITY》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、JSystSciComplex(2012)25:792–801AMATRIXCONSTRUCTIONOFBOOLEANFUNCTIONSWITHMAXIMUMALGEBRAICIMMUNITY∗YonghongXIE·LeiHUDOI:10.1007/s11424-012-0286-zReceived:15November2010/Revised:27May2011cTheEditorialOfficeofJSSC&Springer-VerlagBerlinHeidelberg2012AbstractBooleanfunc

2、tionsusedinacryptographicsystemshouldhavehighalgebraicimmunitytoresistalgebraicattacks.ThispaperpresentsamatrixmethodforconstructingbalancedBooleanfunctionsachievingmaximumalgebraicimmunity.KeywordsAlgebraicimmunity,blockuppertriangularmatrix,Booleanfunction.1Int

3、roductionBooleanfunctionsplayanimportantroleinthedesignofcryptographicsystems.Forex-ample,inabasicLFSR(linearfeedbackshiftregister)basedstreamcipher,aBooleanfunctionisusedtocombinetheoutputsoftheregistertogenerateanonlinearstreamofbitsfortheencryption[1].Afterthr

4、eedecadesofstudy,peoplehavefoundthatBooleanfunctionsusedinacryptographicsystemmustrequiresomenecessaryproperties[2−4].Forexample,inordertoresistagainstlinearcryptographicattack[5]andalgebraicattack[6−7],Booleanfunctionsshouldhaveahighnonlinearityandahighalgebraic

5、immunity(AI),respectively.ItisalsowellknownthataBooleanfunctionusedinastreamciphershouldalsopossessbalancednessandahighalgebraicdegree.Inotherwords,theresearchofcryptographicpropertiesofBooleanfunctionsiscloselyinterconnectedwithcryptographicattacks.Thealgebraica

6、ttackisarelativelynewthreattostreamciphers.Itexploitsover-definedsystemsofmultivariatenonlinearequationstorecoverthesecretkeyofthecipher[6−7].TheseequationsgenerallyinvolvethebitsofthecipherkeyviaanonlinearBooleanfunctionf,wherefistheoutputfunctionwhichgeneratesth

7、ekeybitsofthecipher.Ifsuchequationsarefoundinlowdegrees,algebraicattackscanefficientlyfindthecipherkey.CourtoisusedwellchosenlowdegreeannihilatorsofBooleanfunctionsforf+1,insteadoffitself,togeneratesuchequations[7].Hereanannihilatoroffisafunctiongsuchthatfgisthezero

8、function.Thenthenotionofalgebraicimmunity(AI)ofaBooleanfunctionisintroduced[8],anditisdefinedastheminimumdegreeofallsuchannihilators.Itisknownthatforanyn-variab