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

青果云(590元/年),美国vps洛杉矶CN2 GIA主机测评 1核1G 10M

青果网络QG.NET定位为高效多云管理服务商,已拥有工信部颁发的全网云计算/CDN/IDC/ISP/IP-VPN等多项资质,是CNNIC/APNIC联盟的成员之一,2019年荣获国家高薪技术企业、福建省省级高新技术企业双项荣誉。那么青果网络作为国内主流的IDC厂商之一,那么其旗下美国洛杉矶CN2 GIA线路云服务器到底怎么样?官方网站:https://www.qg.net/CPU内存系统盘流量宽带...

HoRain Cloud:国内特价物理机服务器,镇江机房,内地5线BGP接入,月付499元起

horain怎么样?horain cloud是一家2019年成立的国人主机商家,隶属于北京辰帆科技有限公司,horain持有增值电信业务经营许可证(B1-20203595),与中国电信天翼云、腾讯云、华为云、UCloud、AWS等签署渠道合作协议,主要提企业和个人提供云服务器,目前商家推出了几款特价物理机,都是在内地,性价比不错,其中有目前性能比较强悍的AMD+NVMe系列。点击进入:horain...

BlueHost 周年庆典 - 美国/香港虚拟主机 美国SSD VPS低至月32元

我们对于BlueHost主机商还是比较熟悉的,早年我们还是全民使用虚拟主机的时候,大部分的外贸主机都会用到BlueHost无限虚拟主机方案,那时候他们商家只有一款虚拟主机方案。目前,商家国际款和国内款是有差异营销的,BlueHost国内有提供香港、美国、印度和欧洲机房。包括有提供虚拟主机、VPS和独立服务器。现在,BlueHost 商家周年活动,全场五折优惠。我们看看这次的活动有哪些值得选择的。 ...

63aaa.com为你推荐
网易网盘关闭入口网易网盘怎么打不开了openeuler谁知道open opened close closed的区别吗留学生认证留学生前阶段双认证认证什么内容?巨星prince去世Whitney Houston因什么去世的?www.7160.com电影网站有那些陈嘉垣马德钟狼吻案事件是怎么回事百度关键词分析怎样对关键词进行分析和选择长尾关键词挖掘工具怎么挖掘长尾关键词,可以批量操作的那种网站检测请问,对网站进行监控检测的工具有哪些?抓站工具仿站必备软件有哪些工具?最好好用的仿站工具是那个几个?
虚拟主机价格 花生壳域名 日本私人vps 代理域名备案 老左 oneasiahost ix主机 gateone 台湾谷歌网址 三拼域名 韩国名字大全 股票老左 域名评估 流量计费 网络空间租赁 重庆双线服务器托管 双线机房 东莞idc lamp怎么读 腾讯云平台 更多