reducing63aaa.com

63aaa.com  时间:2021-04-08  阅读:()
SCIENCECHINAInformationSciencesMarch2020,Vol.
63139111:1–139111:3https://doi.
org/10.
1007/s11432-018-9495-xcScienceChinaPressandSpringer-VerlagGmbHGermany,partofSpringerNature2020info.
scichina.
comlink.
springer.
com.
LETTER.
ImproveddistinguishersearchtechniquesbasedonparitysetsXiaofengXIE&TianTIAN*NationalDigitalSwitchingSystemEngineering&TechnologicalResearchCenter,P.
O.
Box407,Zhengzhou450001,ChinaReceived12February2018/Accepted15June2018/Publishedonline10February2020CitationXieXF,TianT.
Improveddistinguishersearchtechniquesbasedonparitysets.
SciChinaInfSci,2020,63(3):139111,https://doi.
org/10.
1007/s11432-018-9495-xDeareditor,DivisionpropertywasatechniqueproposedbyTodoatEUROCRYPT2015tosearchintegraldis-tinguishersagainstblockciphers[1].
Todo[2]ap-pliedthistechniquetoperformstructuralevalu-ationagainstboththeFeistelandtheSPNcon-structionsandattackedthefullMISTY1.
Sub-sequently,manyimprovedtechniquesbasedonthedivisionpropertywereproposed[3,4].
AtFSE2016,TodoandMorii[3]introducedthebit-baseddivisionpropertyandproveditseective-nesstonddistinguishersagainstnon-S-box-basedciphers.
Althoughmoreaccurateintegraldistinguisherswerefoundbyusingthebit-baseddivisionprop-erty,itcouldnotbeappliedtocipherswhoseblocklengthismorethan32becauseofitshightimeandmemorycomplexities.
BasedonTodo'swork,Xiangetal.
[5]convertedthedistinguishersearchalgorithmbasedonthebit-baseddivisionpropertyintoanMILPproblematASIACRYPT2016.
Withthismethod,theyobtainedaseriesofimprovedresultsincludinga9-roundPRESENTdistinguisherwithonebalancedbit.
Thisdistin-guisherisoneofthebest-knowndistinguishersre-latedtoroundnumbers.
AtCRYPTO2016,BouraandCauteaut[6]introducedtheparitysettostudythedivi-sionproperty.
TheyutilizedtheparitysettoexploitfurtherpropertiesofthePRESENTS-boxandthePRESENTlinearlayer,leadingtoseveralimproveddistinguishersagainstreduced-roundPRESENT.
BecausemorepropertiesoftheS-boxandthelinearlayerareutilized,paritysetscanndmoreaccurateintegralcharacteris-tics.
However,althoughtheauthorsdidnotpointout,aparitysetrequireshighertimeandmemorycomplexitiesthanthedivisionpropertydoes.
Ourworkaimsatreducingtimeandmemorycomplex-itieswhenusingparitysetstosearchintegraldis-tinguishers.
Asaresult,weintroducetheideaofmeet-in-the-middleintothedistinguishersearch.
Toillustrateourtechniques,weperformedexten-siveexperimentsonPRESENTandfounda9-rounddistinguisherwith22balancedbits.
Notation1(Bitproductfunction).
Letu,x∈Fn2.
Denotexu=ni=1x[i]u[i],andforu,x∈Fn12*Fn22Fnm2,wherex=(x1,x2,xm),u=(u1,u2,um),denebitproductfunctionasxu=mi=1xuii.
Notation2(Comparisonbetweenvectors).
Fora,b∈Zm,denoteabifaibiforall0bifabbuta=b.
Foru∈Fn2,letusdenotePrec(u)={v∈Fn2:vu},Succ(u)={v∈Fn2:uv}.
*Correspondingauthor(email:tiantiand@126.
com)XieXF,etal.
SciChinaInfSciMarch2020Vol.
63139111:2Theorem1.
Ifu,v∈Fnt2satisfyuv,thenW(u)W(v).
Notation3(Comparisonbetweensets).
LetAandBbetwosetswhoseelementsareinFn2.
De-noteABifthereexista∈Aandb∈Bwithab,andABifnoneofsuchcoupleexists.
Proposition1.
LetAandBbetwosetswhoseelementsareinFn2withAB.
Iftherearea1,a2∈A,b1,b2∈Bsuchthata2a1andb1b2,thenA\{a1}B\{b1}.
Notation4(Roundfunction).
LetFbeaper-mutationofFn2denedbyF:x=(x1,x2,xn)→y=(y1,y2,yn).
TheneveryyicanbeseenasaBooleanfunctiononx1,x2,xn,denotedbyyi=Fi(x).
Forapositiveintegerr,wedenoteFrasacompositionofrpermutationF.
Denition1(Divisionproperty[1]).
LetXbeamultisetwhoseelementsbelongtoFn2.
Then,XhasthedivisionpropertyDnkwhenitfulllsthefollowingconditions:Foru∈Fn2,theparityofxuoverallelementsinXisalwaysevenwhenwt(u)Forfurtherstudyofthedivisionprop-erty,pleasereferto[1,4]indetail.
Denition2(Parityset[6]).
LetXbeasetwhoseelementstakevaluesofFn2.
TheparitysetofXisdenotedbyU(X)anddenedasfollows:U(X)=u∈Fn2:x∈Xxu=1.
Remark1.
IftheparitysetU(X)ofXisknown,thenthedivisionpropertyofXisgivenbyDnk,wherek=minu∈U(X)wt(u).
ForthepropagationrulesoftheparitysetonSPN,pleasereferto[1].
ForaninputsetXandaroundfunctionE,de-notetheparitysetafterr1-roundencryptionasU(Er1(X)),andthealgebraicnormalform(ANF)ofthei-thoutputbitafterr2-roundencryptionasEr2i(x).
IfallthetermsappearinginEr2i(x)arenotdivisiblebyanytermin{xu:u∈U(Er(X))},thenthei-thoutputbitof(r1+r2)-roundencryp-tionisbalanced.
Basedonthisobservation,weimprovedthein-tegraldistinguishersearchbyutilizingthemeet-in-the-middletechniquewhichdividesthen-roundpropagationofparitysetsinton1-roundpropaga-tionofparitysetsand(nn1)-roundpropagationoftheANF.
Next,weproposeanewconcept,whichwecalltermset,todescribetheANFandshowtheprop-agationrulesofthetermsetonSPN.
Denition3(Termset).
Letf(x)beann-variableBooleanfunction.
Thetermsetoff(x)denotedbyT(f)isthesubsetofFn2denedbyT(f)={u∈Fn2:xuappearsintheANFoff(x)}.
Proposition2.
LetSbeanS-boxoverFm2.
De-noteTs(u)={v∈Fm2:xvappearsintheANFofSu(x)}.
Thenforanm-variableBooleanfunctionfwiththetermsetT(f),wehaveT(f(S(x)))u∈T(f)Ts(u).
Proposition3.
LetSbeapermutationofFmt2whichconsistsoftparallelindepen-dentS-boxesoverFm2,namely,S(x1,xt)=(S(x1)S(xt)).
Foranmt-variableBooleanfunctionfwiththetermsetT(f),wehaveT(f(S))(u1,···,ut)∈T(f)Ts1(u1)Tst(ut).
Proposition4.
Letfbeann-variableBooleanfunctionwiththetermsetT(f).
Foranyk∈Fn2,thetermsetoff(kx)=(x1k1,xnkn)satisesT(f(kx))u∈T(f)Prec(u).
Then,thetermsetafteroneroundencryptioncanbededucedbyPropositions2and4,i.
e.
,T(f(S(xk)))u∈T(f)v∈Ts(u)Prec(v),fork∈Fn2.
Theproofsofthesepropositionscouldbefoundthroughhttps://eprint.
iacr.
org/2018/447.
Wecanalsosearchdistinguishersbytermsetsonly.
Ifthereexistsau∈Fn2satisfyingSucc(u)T(Eri)=,thenar-rounddistinguisherwhoseinputsetisPrec(u)isfound.
However,thetimeandmemorycomplexitieswillbeveryhigh.
Thus,wetookadvantageofthemeet-in-the-middletechniquesothatthetermsetandtheparitysetcouldbecombinedtoreducetimeandmemorycomplexities.
Inordertondadistinguisher,weneedtocom-pareT(Er2i)withU(Er1(X))andverifywhetherT(Er2i)U(Er1(X)).
Ourdistinguishersearchalgorithmconsistsofvesteps,whichcanbede-scribedasfollows.
XieXF,etal.
SciChinaInfSciMarch2020Vol.
63139111:3Step1.
Choosethepropagationroundnum-bersr1andr2fortheparitysetandthetermsetrespectively,wherer1+r2=r.
Step2.
ChooseaninputsetX.
Step3.
CalculatetheparitysetU(Er1(X)).
Step4.
CalculatethetermsetsT(Er2i)for1in.
Step5.
CompareU(Er1(X))withT(Er2i)for1in.
IfU(Er1(X))T(Er2i),thenthei-thoutputbitinr-roundencryptionisbalanced.
Ifnoneofsuchintersectionsisempty,thenchooseanotherXandgotoStep2.
Wealsoproposesomenoveltechniquestomakeouralgorithmmoreecient.
Sizereduceoperation.
ForthetermsetT(Eri(x)),thesizereduceoperationRtremovesalltheelementsv∈T(Eri(x))suchthatthereisanelementv′∈T(Eri(x))withv′v.
Asforaparityset,theoperationRuremovesalltheelementsu∈U(Er1(X))suchthatthereisanelementu′∈U(Er1(X))withuu′.
ItcanbededucedfromProposition1thatthecom-parisonresultofT(Eri(x))andU(Er1(X))isthesameasthecomparisonresultofRt(T(Eri(x)))andRu(U(Er1(X))).
Observation1.
ThePRESENTsuperS-boxescanworkindependentlyinthe2-roundencryption.
Reducinglook-uptable.
BasedonObserva-tion1,wecaneasilyconstructa2-roundpropaga-tiontableforthesuperS-boxbycalculatingRuU(S(P(S(X))))forallpossibleinputs,whereSisapermutationofF4n2consistingoffourPRESENTS-boxesS(x1,x2,x3,x4)=(S(x1),S(x2),S(x3),S(x4)).
Multiplecomparison.
Thistechniqueat-temptstoremovethetermsthathavenomultipleinU;ifnotermisdivisiblebyavectorinU,thenitisclearthattheoutputbitisbalanced.
Wetriedtojudgesuchdivisibilityintermsofdegreeorderandalphabetorder.
Forthedetailsofthistech-nique,refertohttps://eprint.
iacr.
org/2018/447.
Toillustrateourtechniques,weapplyouralgo-rithmtothePRESENTdistinguishersearch.
Observation2.
ThecubictermsintheANFsofthesecondandfourthcoordinatesofthePRESENTS-box(sayS2andS4)arethesame[7].
Asaresult,thexorofthesetwocoordinatesS2S4=1x1x2x3x2x4x3x4hasonlydegree2.
Moreover,everyterminS2S4hasamultipleinS2andS4respectively.
Hence,S2S4maybebalancedevenifS2andS4areunbalanced.
Wetriedtond10-roundPRESENTdistin-guishersrst,buttheresultoftherightmostout-putbitisunbalancedforalltheinputsetswithdimension63.
ItseemsthattheANFofthisout-putbitisthesimplestamong64outputbits,andtherefore,ourresultsshowthatthePRESENTprobablyhasno10-roundintegraldistinguishersbyonlyusingthedivisionproperty.
Then,wefo-cusonthe9-roundPRESENT,andndadistin-guisherwith22balancedoutputbits.
Input:(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac),Output:b3b3bb2b2bb1b1bbbbbbbbbbbbbbbbb),where"c"meansaconstantbit,"a"meansanac-tivebit,""meansanunknownbit,and"b"meansabalancedbit.
Inaddition,thepresenceofbitswiththesamenotationbimeanstheiradditionisbalanced.
Conclusion.
Inthisstudy,weproposedacon-ceptcalledthetermsettopropagateinformationoftheANF.
Withtermsets,weimprovedthedis-tinguishersearchmethodbasedontheparitysetintermsofbothmemoryandtimecomplexities.
Fromtherelationbetweentheparitysetandthebit-baseddivisionproperty,itwasfoundthatthetermsetcouldalsobeappliedtoimprovethedis-tinguishersearchmethodbasedonthebit-baseddivisionproperty.
AcknowledgementsThisworkwassupportedbyNa-tionalNaturalScienceFoundationofChina(GrantNo.
61672533).
References1TodoY.
Structuralevaluationbygeneralizedintegralproperty.
LectNotesComputSci,2015,9056:287–3142TodoY.
IntegralcryptanalysisonfullMISTY1.
JCryptol,2017,30:920–9593TodoY,MoriiM.
Bit-baseddivisionpropertyandap-plicationtosimonfamily.
LectNotesComputSci,2016,9783:357–3774SunL,WangW,WangMQ.
Automaticsearchofbit-baseddivisionpropertyforARXciphersandword-baseddivisionproperty.
LectNotesComputSci,2017,10624:128–1575XiangZJ,ZhangWT,BaoZZ,etal.
ApplyingMILPmethodtosearchingintegraldistinguishersbasedondivisionpropertyfor6lightweightblockciphers.
LectNotesComputSci,2016,10031:648–6786BouraC,CanteautA.
Anotherviewofthedivisionproperty.
LectNotesComputSci,2016,9814:654–6827BogdanovA,KnudsenLR,LeanderG,etal.
PRESENT:anultra-lightweightblockcipher.
LectNotesComputSci,2007,4727:450–466

Webhosting24:€15/年-AMD Ryzen/512MB/10GB/2TB/纽约&日本&新加坡等机房

Webhosting24是一家始于2001年的意大利商家,提供的产品包括虚拟主机、VPS、独立服务器等,可选数机房包括美国洛杉矶、迈阿密、纽约、德国慕尼黑、日本、新加坡、澳大利亚悉尼等。商家VPS主机采用AMD Ryzen 9 5950X CPU,NVMe磁盘,基于KVM架构,德国机房不限制流量,网站采用欧元计费,最低年付15欧元起。这里以美国机房为例,分享几款套餐配置信息。CPU:1core内存...

Sharktech云服务器35折年付33美元起,2G内存/40G硬盘/4TB流量/多机房可选

Sharktech又称SK或者鲨鱼机房,是一家主打高防产品的国外商家,成立于2003年,提供的产品包括独立服务器租用、VPS云服务器等,自营机房在美国洛杉矶、丹佛、芝加哥和荷兰阿姆斯特丹等。之前我们经常分享商家提供的独立服务器产品,近期主机商针对云虚拟服务器(CVS)提供优惠码,优惠后XS套餐年付最低仅33.39美元起,支持使用支付宝、PayPal、信用卡等付款方式。下面以XS套餐为例,分享产品配...

Linode($5/月),新用户注册送100美元,11个数据中心云服务器

关于Linode,这是一家运营超过18年的VPS云主机商家,产品支持随时删除(按小时计费),可选包括美国、英国、新加坡、日本、印度、加拿大、德国等全球十多个数据中心,最低每月费用5美元($0.0075/小时)起。目前,注册Linode的新用户添加付款方式后可以获得100美元赠送,有效期为60天,让更多新朋友可以体验Linode的产品和服务。Linode的云主机产品分为几类,下面分别列出几款套餐配置...

63aaa.com为你推荐
2020双十一成绩单2020年12月四级考试什么时候出成绩access数据库access数据库主要学什么bbs.99nets.com怎么打造完美SF777k7.comwww.777tk.com.怎么打不 开同一服务器网站同一服务器上可以存放多个网站吗?haokandianyingwang谁有好看电影网站啊、要无毒播放速度快的、在线等www.javmoo.comjavimdb怎么看杨丽晓博客杨丽晓是如何进入娱乐圈的?lcoc.topeagle solder stop mask top是什么层hao.rising.cn瑞星强制篡改主页 HTTP://HAO.RISING.CN 各位有什么办法可以解决吗?
美国域名 高防服务器租用选锐一 linuxapache虚拟主机 花生壳免费域名 已经备案域名 冰山互联 isatap 英文简历模板word 双11抢红包攻略 线路工具 服务器架设 绍兴高防 湖南服务器托管 中国智能物流骨干网 最好的免费空间 卡巴斯基试用版 亚马逊香港官网 太原网通测速平台 gtt 重庆电信服务器托管 更多