基于格的群签名方案

JournalofChineseComputerSystems20111111Vol.32No．1120112011-07-222011-09-07609701[e-mail]2010．．．TP309A1000-1220201111-2243-05GroupSignatureSchemeBasedonLatticeWUYong-dong121DepartmentofComputerScienceShanghaiJiaotongUniversityShanghai200240China2ShanghaiKeyLaboratoryofScalableComputingandSystemShanghaiJiaotongUniversityShanghai200240ChinaAbstractAnattackismountedonagroupsignatureschemebasedonlatticepostedinAsiaCrypt2010．Itshowsthegroupsignatureschemeisvulnerabletotrapattacksandadishonestgroupmanagercangetallgroupmembers'signingkeysandthenforgeallgroupmembers'validsignatures．Meanwhiletheschemecan'tincreaseordeletegroupmembersflexiblyandefficientlywhichisnotappli-cabletodynamicgroups．Everytimeanewmemberjoinsthesystemhastoupdatethepublickeyandallgroupmembers'signingkeyswhichareofhugecalculationandlowefficiency．Alsotheschemedoesn'tprovideaneffectivemethodtorevokegroupmem-bers．Usingstatisticalzero-knowledgeproofsandtimeparametersanimprovedschemebasedonthehardnessoftheclosestvectorproblemisproposed．Theimprovedschemeisanti-trapattacksandcandynamicincreaseordeletesgroupmembersmoreefficientlyandapplicably．Keywordsgroupsignaturetrapattackstatisticalzero-knowledgeproofdynamicgroup1D．ChaumE．Van．Heyst19911．、、2-4、、5．．2010S．DovGordon、JonathanKatzVinodVaikun-tanathan6GKV．12．7．1．2．．3．．2n．2．11．nmm≤nb1b2…bmLb1b2…bm=∑mi=1λibi|λi∈Z．b1b2…bm．GKV∧AT=y∈Zmq|y=ATsmodq∧┴A=w∈Zmq|Aw=0modqA∈Zn×mqs∈Znq∧┴A∧AT．x‖x‖x．xy‖x－y‖=∑mi=1|xi－yi|槡2．zdist∧ATz=mins∈Znq‖ATs－zmodq‖．2．22．SVPShortestVectorProblem．υμ‖υ‖≤‖μ‖．3．CVPClosestVectorProblemyy．υμ‖υ－y‖≤‖μ－y‖．NP8．2．3LWELWELearningWithError．4．s＞0c、smDsc=1sm·exp－π‖x－c‖s2x∈R5．∧∈Zmmx∈∧D∧scx=Dscx∑y∈∧Dscy6．LWE9nM≥nq≥2s∈ZnqRmXZn×mq×0qm1LWEmqXsA∈Zn×mqe←XAATs+e2UmqA∈Zn×mqy∈0qmAyPPTDΔ=|Prs←ZnqAy←LWEmqXsDAy=1－PrAy←UmqDAy=1|ΔLWEmqXss．LWEmqXsXDαqcXLWEmqDαqcsLWEmqαGKVmqnpolynα1/polynα·q＞2槡nLWEmqαs．LWEmqXsXDZmαqLWEmqDzmαqsLWE^mqαGKV16．m=mnq=qnα=αnα×q=ω槡lognLWEmqαLWE^mqα．2．4GPVGKVGPV．210．PPTProbabilisticPolynomialTimeTrapSamp1n1mqq≥2m≥8nlogqA∈Zn×mqT∈Zm×mqAZn×mqT∧┴AA·T=0modq．GentryPeikertVaikuntanathan11TrapSamp．qnm≥8nlogqs=ω槡nlogqlognGPVGen1nGPVInvertATsμGPVGen1nTrapSamp1n1mqATAfAe=Aemodqe∈Zm‖e‖≤槡sm．DZmsGPVInvertATsμt∈ZmAt=μmodqe←D∧┴A+tse．2．5GKV．36．PPTSuperSamp1n1mqq≥2m≥n+8nlogqB∈Zn×mA∈Zn×mqT∈Zm×mqABT=0modqAZn×mqT∧┴AA·T=0modq．2．6．GKVNIWINoninteractiveWitness-Indistinguisha-ble．NIWIGKV344222011D．MicciancioS．P．Vadhan20037．74．3GKVGKV6．GKV、．GKV4G．KeyGen、、G．Sign、G．Verify、G．Open．q=polynm≥8nlogqs=ω槡nlogqlognH3．1G．KeyGen1n1NB1S1…BNSN←TrapSamp1n1mq1≤i≤NAiTi←SuperSamp1n1mqBi．PK=AiBiNi=1TK=SiNi=1gsk=TiNi=1．3．2G．SigngskjMjMγ←01nM=M‖γ1≤i≤Nhi=HM‖i·ej←GPVInvertAjTjshj·i≠jei∈ZmqAiei=himodq1≤i≤Nsi←ZnqZi=BTisi+eimodq∈Zmq．NIWIπ6．σ=γZi…ZNπ．3．3G．VerifyPKMσM=M‖γππ1≤i≤NAiZi=HM‖imodq10．3．4G．OpenTKMσSi1≤i≤Ndist∧BTiZi≤槡smdist∧BTiZii．3．53．5．1G．KeyGenGKV．3．5．2．．4GKV．GKV．4．1G．KeyGen1n1NTcurrentN－1PK=AiBiN－1i=1TbeforeTbeforeN－1TK=SiN－1i=1Tbeforei1≤i≤N－1Ti．LPKLTK．UN1BNSN←TrapSamp1n1mqy∈Zmqt∈R+BN、ytUN．2UNANTN←SuperSamp1n1mqBNAN．7aUNTNATNww∈Znμ=y－ATNw、c1…ck∈01k=polyn、r1…rk∈β0gt/2g=Ω槡n/logni*‖ri*+2ci*－1μ‖≤gt/2i*=1ci*=0ri*=μ/2‖ri*+2ci*－1μ‖≤gt/2．mi=ciy+rimodATN1≤i≤kkm1…mk．bkq∈01UN．cq=iciUNciATNvi=mi－ri+ciy1≤i≤kq≠iciUNci*ATNvi*1－ci*ATNvi*+2ci*－1y－μ．dkc1…ckkATNv1…ATNvki1≤i≤k∑ici=qmod2‖mi－ATNvi+ciy‖≤gt/2UNUNPK=AiBiNi=1TcurrentTcurrentUNPKLPKTK=SiNi=1TcurrentTKLTKi1≤i≤N－1NTN．4．2G．SigngskjMTcurrentjMγ←01nM=M‖γ‖TcurrentTcurrent542211Nhi=HM‖i1≤i≤N·ej←GPVInvertAjTjshj·i≠jei∈ZmqAiei=himodq1≤i≤Nsi←ZnqZi=BTiSi+eimodq∈Zmq．NIWIπ．σ=γTcurrentZi…ZNπ．4．3G．VerifyPKMσTcurrentLPKPK=AiBiNi=1TcurrentM=M‖γ‖TcurrentππNσZi1≤i≤NAiZi=HM‖imodq10．4．4G．OpenTKMσTcurrentLTKTK=SiNi=1Tcurrent1≤i≤Ndist∧BTiZi≤槡smdist∧BTiZii．4．5G．DeletekTdeleteUkPK=AiBiNi=1＆i≠kTdeleteTdeleteUkPKLPKTK=SiNi=1＆i≠kTdeleteTKLTK．55．1σ=γTcurrentZi…ZNππ31≤i≤NAiZi=AiBTisi+ei=Aiei=HM‖imodq1．GPVInvertejZmq11Zj=BTjsj+ejmodq∈ZmqBTjsjdist∧BTjZj=mins∈Znq‖BTjs－Zjmodq‖s=sjdist∧BTiZi≤槡smj．．5．2、6．LWE^mqα．Zi=BTisi+eimodqi≠jeiZmqej←D∧┴A+ts1LWE^mqαejeisi←Znq1≤i≤NZjZi．G．KeyGen7．5．3、6．GPV．PPTAGPVPPTFFA6．AFGPVGPV．5．4GKV．．G．KeyGen7．5．5Uiσ=γTcurrentZi…ZNπ1N．2NAiUiAiZi≠HM‖imodq．．．．．5．6．．．．64222011．62010．．References1ChaumDVanHeystE．GroupsignaturesA．InProceedingsoftheAdvancesinCryprology-EUROCRYPT'91C．BerlinSpringer-Verlag1991257-265．2CamenischJStadlerM．EfficientgroupsignatureschemesforlargegroupsA．InProceedingsoftheAdvancesinCryprology-CRYPTO'97C．BerlinSpringer-Verlag1997410-424．3AtenieseGCamenischJJoyeMetal．Apracticalandprovablyse-curecoalition-resistantgroupsignatureschemeA．InProceed-ingsoftheAdvancesinCryptology-CRYPTO2000C．Heidel-bergSpringer-Verlag2000255-270．4DanBonehXavierBoyenHovavShacham．ShortgroupsignatureA．InProceedingsoftheAdvancesinCryptology-CRYPTO'04C．BerlinSpringer-Verlag200441-555ShorPW．Polynomial-timealgorithmsforprimefactorizationanddiscretelogarithmsonaquantumcomputerJ．SIAMJournalofComputing19972651484-1509．6DovGordonSJonathanKatzVinodVaikuntanathan．Agroupsig-natureschemefromlatticeassumptionsA．InProceedingsoftheAdvancesinCryptology-ASIACRYPT'1