第八章基于身份的密码学和无证书密码学

Identity-BasedCryptographyandCertificatelessPublicKeyCryptography

PublicKeyCryptography(PKC)Alsoknownasasymmetriccryptography.Eachuserhastwokeys:publicandprivate.Alice'spublickeytypicallyusedfor:encryptiontoAlicebyBob.verificationofAlice'ssignaturesbyBob.Alice'sprivatekeytypicallyusedfor:decryptionbyAlice.signingbyAlice.NoneedforAliceandBobtoshareacommonkeybeforetheybeginsecurecommunications!Comparewithsymmetrickeycryptography.TheNeedforPKIWeneedsomewayofenablingBobtoactuallyfindAlice’skey.Adirectoryserviceforencryptionapplications.Ordeliveredaspartofaprotocol,oralongwithasignature.ButhowdoesBobknowthat

Alice'spublickeyreallyisAlice's(andnot

Eve's)?Weneedsomewayofbindingpublickeyswithidentities.Certificatesinmostcircumstances.Wewillalsoneedsomewayofsignallingthatapublickeyisnolongertobereliedupon.Alice’sprivatekeymightbecomeexposed,orshemightchangerolesorleavethecompany.Arevocationmechanism.PublicKeyInfrastructures

Definition:APublicKeyInfrastructure(PKI)isanysystemsupportingthedeploymentofPublicKeyCryptographyBytheterm“traditionalPKI”wemean:acombinationofhardware,softwareandpolicies;neededtodeployandmanagecertificates;toproducetrustinpublickeys;usedinaparticularapplicationorsetofapplications.PKIComponentsRegistrationAuthority(RA).Authenticatesindividuals/entities,optionallychecksforpossessionofprivatekeymatchingpublickey.PassesoffresulttoCertificationAuthority.CertificationAuthority(CA).Issuescertificates:CAissuessignaturesbindingpublickeysandidentities.RelyingpartiesneedauthenticcopyofCA’spublickey…DirectoryService.Directoryofpublickeys/certificates.RevocationService.MayinvolvedistributionofCertificateRevocationList(CRL)oron-linecertificatestatuschecking(OCSP).UsingPKIRACAKeyPair“IssueCert”DirectoryCRLExamplePKIsSSLservercertificates,authenticatedviarootcertificateembeddedinbrowser.Certificatehierarchy.Providesserver(notclient!)authenticationfore-commerce.Rareexampleof“open”PKI.IPSeccertificates.Gateway-gatewayVPNandremoteaccesssolutions.PKCenablesauthenticationofendpointsviaIKEprotocol.GenerallyclosedPKI.CertificateManagementProblemsRevocationStorageDistributionComputationalcostofcertificateverificationComplexityandPKIThereisamassivecomplexitygapbetweentheconceptofpublickeycryptographyanditsrealisationintheformofatraditionalPKIFromanapplicationperspective,theabilitytoprovidenon-repudiationseemstobetheuniquefeatureseparatingpublickeyfromsymmetrickey.Onceoneappreciatesthereal-worldcomplexities,symmetrickeysystemsappearequallyattractiveinmanycircumstances!CertificatesandtheirmanagementarethesourceofsomeproblemsSosomehowgettingridofcertificatesmighthelp?Identity-basedCryptographyOriginalideaduetoShamir(1984):Publickeysderiveddirectlyfromsystemidentities(e.g.ane-mailaddressorIPaddress).Privatekeysgeneratedanddistributedtousersinbyatrustedauthority(TA)whohasamasterkey.Aslongas:BobissureofAlice’sidentityand.TheTAhasgiventheprivatekeytotherightentity,thenBobcansafelyencrypttoAlicewithoutconsultingadirectoryandwithoutcheckingacertificate.Identity-basedCryptographyTAPrivateKeyAlice’sIDPublicKeyIdentity-basedCryptographyApparently,eliminationofcertificatesproducesafarsimplerinfrastructure.Identifieroftenusedinplaceofidentity.Reflectingideathatanystringcanbeusedtoderivepublickeys.IBE=Identity/Identifier-basedencryption.ID-PKE=ID-basedpublickeyencryption.ID-PKC=ID-basedpublickeycryptography.IBE–AShortHistoryShamirdevisedonlyanidentity-basedsignaturescheme.Constructionoftruly

practicalandsecureidentity-basedencryptionschemeanopenproblemuntil2001IBE–AShortHistorySakai,OhgishiandKasahara(SCIS,Jan.2001)Pairing-basedIBEscheme,butnosecuritymodelorproofs.BonehandFranklin(Crypto,August2001)Pairing-basedIBEscheme,practicalandprovablysecure.Cocks’scheme(IMAConference,Dec.2001)IBEschemebasedonquadraticresidue,notbandwidthefficientApparentBenefitsofID-PKCCertificate-free.Noproduction,checking,managementordistributionofcertificates.Directory-less.BobcanencryptforAlicewithoutlooking-upAlice’spublickeyfirst.Indeed,AliceneednothaveherprivatekeywhenshereceivesBob’sencryption.ApparentBenefitsofID-PKCAutomaticrevocation.Simplyextendidentifiertoincludeavalidityperiod.Alice’sprivatekeybecomesuselessatendofeachperiod.Aliceneedstoobtainprivatekeyforcurrentperiodinordertodecryptnewmessages.NoneedforCRLsorOCSP.Built-insupportforkeyrecovery.TAcancalculateprivatekeyforanyuser.Maybeneeded,forexample,whenuserleavestheorganisation.Alsoenablesapplicationslikecontentscanningofe-mailatserver.ApplicationsofID-PKCID-PKCandpairing-basedcryptohaveundergoneanextraordinarilyrapiddevelopmentsince2001.Boneh-Franklinhas4315citationsonGooglescholar.Growingcommercialinterest.WeexaminesomepotentialapplicationsforID-PKC.Securee-mail.Domain-basedsecurity.GRIDsecurityinfrastructure.Manyotherapplicationshavebeenproposed.ID-PKCandSecureE-mailID-PKCseemswell-suitedtoencryptionfore-mailandothermessagingtechnologiesincorporateenvironments.ThereisanaturalcandidateforTA.Lowinteractionwithinfrastructureforsender.Recipientofencryptede-mailneednotbepre-enrolled.Potentialforlowercoststhroughlightweightinfrastructurerequirements(comparedtoPKI-basedsolution).Seemslikelytobefirstmass-marketapplicationofID-PKCID-PKCandSecureE-mailBut…Difficulttobuildnon-repudiationserviceswithoutresortingtotraditionalPKI.MayneedtointegratewithexistingPKI-basedauthenticationservices.VoltageSecuritywhitepaper,March2005:“CombiningIBEwithPKIenablesasecuremessagingenvironmenttobenefitfromtheadvantagesofbothsystems.”

PracticalIssuesforID-PKCWehavefocusedsofaronpositiveaspectsofID-PKC:Certificate-free,Directory-less,Automaticrevocation,Supportforkeyrecovery.WenextexaminethepracticalissuesassociatedwithID-PKC.PublicParametersBobneedsanauthenticcopyoftheTA’spublicparametersbeforehecansafelyencrypttoAlice.Topreventman-in-middleattacks.Onesolutionistohard-codeTAparametersintoclientapplications.Mayworkforclosedapplications,butnotveryflexible.Couldusehierarchicalapproachtosupportmultipleapplicationsandparties.Anothersolution:CertifyTAparametersusingaPKI.Ahybridsolution,asadoptedbySmettersandDurfee.Stillneedtodistributeandcheckthesecertifiedparameters.RegistrationAsecureenrollmentprocessisstillneeded.Pre-enrollmentcanbeavoided,butAlicedoesneedtoenrollatsomepoint!AsecureprocessisneededtoensurethatAlice’sprivatekeyisreallybeingdeliveredtoAlice.PKIonlyneedsanauthenticchannel.ID-PKCneedsachannelthatisbothauthenticandconfidential.RegistrationAsecurechannelisneededforregistrationanddeliveryofprivatekeys.Howisthistobeachievedinpractice?Howoftenwillthechannelbeused?Whatsecurityleveldoesitneedtoprovide?*Forexample,isdeliveryviae-mailappropriate?Ifwehavesuchachannel,whatalternativeusesmightbefoundforit?Whereshouldwestoreprivatekeysoncewe’vedistributedthem?RealityofID-basedCryptographyTASecurechannelAuthenticpublicparametersAlice’sIDEffectofCatastrophicCompromiseWhatisthecostofcompromiseofthemastersecret?PotentiallyhigherthancostofcompromiseofCAsigningkeyinPKI:CAinPKIcouldre-issueallcertificatesundernewsigningkey.Noclientprivatekeysarecompromised.Onlytemporaryexposuretothreatofroguecertificatesbeingusedbyencrypting/verifyingparty.Meanwhile,inID-PKC,allpastencryptedmessagesareexposedandalloldsignaturesbecomeworthless.KeyEscrowAninevitableconsequenceofthekeyrecoveryfeature:TAcancalculatealltheprivatekeysinthesystem.SoneedtotrustTAnottoabusethisprivilege.PKIismoreflexibleinthisrespect.MaylimitapplicabilityofID-PKCtocertainapplicationswheresomedegreeoftrustinTAisinherent.E.g.Securecorporatee-mailsystem.InabilitytoProvideNon-repudiationAnotherconsequenceofkeyescrow.TAcouldforgesignaturesifanidentity-basedsignaturewereadopted.SoneedtotrustTAnottodothat.Sinceacertificatecanalwaysbesentalongwithasignature,ID-PKCdoesnotseemtohaveabigadvantageoverPKIhereanyway.RevocationinID-PKCRevisitedArevocationmechanismisneededinID-PKCjustasintraditionalPKI.Ineventofkeycompromiseorchangeofstatusofentityrelatedtoidentifier.Buthowcanyourevokeanidentifier?Thesimple“automaticrevocation”solution:BobsimplyextendAlice’sidentifiertoincludeavalidityperiod.Granularityofexpirytimesdeterminesrateofprivatekeyissuance(yearly,weekly,daily,…).CouldconvenientlyspecifyexpirypolicyinTA’sparameters.Hence“noneedforCRLsorOCSP”.RevocationinID-PKCRevisitedValidityperiodalsodeterminesmaximumexposuretimebetweencompromiseofprivatekeyandupdateofpublickey.Sohighersecurityapplicationwouldneedshortervalidityperiodandhencehigherrateofprivatekeyissuance.ExtraworkloadonTA.TAmayneedtobehighlyavailable.Securechannelneedstobeusedatfrequentintervals.Syntaxforidentity-basedencryption

Identity-BasedEncryptionSetupExtractEncryptDecryptAsenderdoesnotneedtolookuptherecipient’spublickeybeforesendingoutanencryptedmessage.

TheencryptionstepsPKGsAliceBobPpubmCIDBobskBobmIdentity-basedencryption-BFschemeItwasproposedbyBonehandFranklininCrypto2001.Itusesbilinearmapsoversupersingularellipticcurves.LetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,andG2beacyclicmultiplicativegroupofthesameorderq.Abilinearpairingisamapê:G1×G1→G2withthefollowingproperties:Bilinearity:ê(aP,bQ)=ê(P,Q)abforallP,Q∈G1,and

a,b∈Zq*.Non-degeneracy:ThereexistsPandQinG1suchthatê(P,Q)≠1.Computability:Thereisanefficientalgorithmtocomputeê(P,Q)forallP,QinG1.BFscheme—SetupLetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,andG2beacyclicmultiplicativegroupofthesameorderq.ê:G1×G1→G2isabilinearmap.Messagespaceis{0,1}nandciphertextspaceisG1*×{0,1}n

。DefinetwohashfunctionH1：{0,1}*→G1*andH2：G2→{0,1}n

。PKGchoosesamastersecretkeys∈Zq*randomlyandcomputesPpub=sP。PKGpublishessystemparameters{G1,G2,q,n,ê,P,Ppub,H1,H2}andkeepsthemasterkeyssecret。BFscheme—ExtractGivenanidentityID,thePKGcomputesthecorrespondingprivatekeySID=sQIDandsendsittoitsownerinasecureway.HereQID

=H1(ID).BFscheme—EncryptToencryptamessagem∈{0,1}n，chooser∈Zq*,randomlyandcomputeU=rP,V=m⊕H2(gIDr)HeregID=ê(QID,Ppub).TheciphertextisC=（U,V）.BFscheme—DecryptTodecryptaciphertextC=(U,V),compute：

m=V⊕H2(ê(SID,U))Theconsistencyofthisschemecanbeeasilyverified.SinceSID=sQIDandPpub=sP,soê(SID,U)=ê(sQID,rP)=ê(QID,srP)=ê(QID,Ppub)r=gIDrThisschemeisonlychosenplaintextsecurity.WecangetchosenciphertextsecuritybyFujisaki-Okamototransformation.Pleaserefertothefollowingpaperfordetail.

D.Boneh,M.Franklin.Identity-basedencryptionfromtheweilpairing.InProc.CRYPTO2001,LNCS2139,2001,pp.213-229Identity-basedsignature(IBS)Identity-BasedsignatureSetupExtractSignVerifyHessscheme—SetupLetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,andG2beacyclicmultiplicativegroupofthesameorderq.ê:G1×G1→G2isabilinearmap.DefinetwohashfunctionH1：{0,1}*→G1*andH2：{0,1}*

×G2→Zq*。PKGchoosesamastersecretkeys∈Zq*randomlyandcomputesPpub=sP。PKGpublishessystemparameters{G1,G2,q,ê,P,Ppub,H1,H2}andkeepsthemasterkeyssecret。Hessscheme—ExtractGivenanidentityID,thePKGcomputesthecorrespondingprivatekeySID=sQIDandsendsittoitsownerinasecureway.HereQID

=H1(ID).Tosignamessagem,choosekrandomlyComputeThesignatureis(u,v)Hessscheme—SignComputeCheckHessscheme—VerifyKeyagreementprotocolN.P.Smart.Identity-basedauthenticatedkeyagreementprotocolbasedonWeilpairing.ElectronicsLetters,Vol.38,No.13,2002,pp.630-632Ppub=sP

，SA，SBprivatekey,V

keyderivationfunction

TA=aPTB=bPk=V（kA）=V（kB）

OneRoundThreePartyKeyAgreementProtocolA.Joux,AoneroundprotocolfortripartiteDiffie-Hellman,ProcofANTS4,LNCS1838,pp.385-394,2000.MoredetailF.Hess.Efficientidentitybasedsignatureschemesbasedonpairings.SelectedAreasinCryptography-SAC2002,LNCS2595,Berlin:Springer-Verlag,2003:310--324.AlternativeInfrastructuresCertificate-basedencryption(CBE).SimplifiesrevocationintraditionalPKIs.Certificatelesspublickeycryptography(CL-PKC).Athirdparadigmforgeneratingtrustinpublickeys.LiesmidwaybetweentraditionalPKIandID-PKCintermsoftrustmodelandfunctionality.Certificate-basedEncryptionIntroducedbyGentry(Eurocrypt2003).SimplifiesrevocationintraditionalPKIs.Alice’sprivatekeyconsistsoftwocomponents:TheprivatepartSAofa“traditional”keypair(SA,PA).Atime-dependentcertificateSCA(t)pushedtoAliceonaregularbasisbytheCA,solongasAlicenotrevoked.Bobcancomputeamatchingpublickeyusingonly

theCA’spublicparameters,timetandAlice’spubliccomponentPA.

BobisassuredthatAlicecanonlydecryptiftheCAhasissuedcertificateSCA(t)forthecurrenttimeintervalt.SimplicityofrevocationtradedforrequirementonCAtoregularlypushcertificates.Certificate-basedEncryption(CBE)Key“Pair”CApublicparametersSCA(t)PA+PASA+

SCA(t)tCACertificatelessPublicKeyCryptography(CL-PKC)IntroducedbyAl-RiyamiandPaterson(Asiacrypt2003).Nowathrivingsub-areaofID-PKC.Designobjective:RemovethekeyescrowinherentinID-PKCwithoutintroducingcertificates.CL-PKE:certificatelesspublickeyencryption.TA-generatedpartialprivatekeyPPKAcombinedwithuser-generatedsecret

xAtoformprivatekeySA.UsersecretxAdeterminespublickeyPA.TApublicparameters,publickeyPAandidentifierIDAusedforencryption.CL-PKEKeyPairTApublicparametersPPKAPATAxAPASA

IDA‘EncryptionKey’CL-PKEFeaturesNokeyescrow.User-generatedsecretcomponentxA

protectsagainsteavesdroppingTA.Noexplicitcertificationofpublickeysrequired.Somustconsideradversarywhocanreplacepublickeys.ButadversarydoesnotknowpartialprivatekeyPPKA,socannotcalculatefullprivatekey.ExplicitassumptionisneededthatTAdoesnotengageinactiveadversarialbehaviour.Acompletesuiteofcertificatelesscryptographicprimitivesisavailable.Signatures,keyexchangeprotocols,hierarchicalschemes.CL-PKEcloselyrelatedtoCBE;conceptsdevelopedindependently.CertificatelessPublicKeyEncryptionCertificatelessPublicKeyEncryptionSetupPartial-Private-Key-ExtractSet-Secret-ValueSet-Private-KeySet-Public-KeyEncryptDecryptS.S.Al-RiyamiandK.G.Paterson,CertificatelessPublicKeyCryptography,ASIACRYPT2003,LNCS2894,pp.452–473AP—SetupLetG1beacyclicadditivegroupgeneratedbyP,whoseorderisaprimeq,andG2beacyclicmultiplicativegroupofthesameorderq.ê:G1×G1→G2isabilinearmap.Messagespaceis{0,1}nandciphertextspaceisG1*×{0,1}n

。DefinetwohashfunctionH1：{0,1}*→G1*andH2：G2→{0,1}n

。KGCchoosesamastersecretkeys∈Zq*randomlyandcomputesPpub=sP。KGCpublishessystemparameters{G1,G2,q,n,ê,P,Ppub,H1,H2}andkeepsthemasterkeyssecret。AP—Partial-Private-Key-ExtractGivenanidentityID,theKGCcomputesthecorrespondingprivatekeySID=sQIDandsendsittoitsownerinasecureway.HereQID

=H1(ID).Set-Secret-Value:userchoosesarandomnumbe