Introduction Our main result: DDH implies P Q DDH

Emmanuel Bresson1

Description

Introduction Our main result: DDH implies (P,Q)-DDH Applications: Diffie-Hellman-based protocols A symbolic logic for Diffie-Hellman exponentials and encryption A generalization of DDH with applications to protocol analysis and computational soundness Emmanuel Bresson1, Yassine Lakhnech2, Laurent Mazare3, Bogdan Warinschi4 DCSSI Crypto Lab, VERIMAG Grenoble, Amadeus SAS, University of Bristol, July 4, 2007 ENS — June 21, 2007 A Generalization of DDH and Applications

• ddh


• generalizing ddh


• pseudo-random generators


• protocol analysis


• adversary must


• secure public-key


• make protocol


• multiple challenges


• key exchange

Sujets

• Protocol analysis

Informations

• Publié par: pefav
• Nombre de lectures: 12
• Langue: Français

Extrait

Introduction OuramnierustlD:HDmiieplP,s(-DQ) Ap DH cilpoitaD:sn-effiiman-Helldprobasesl sA otoc illcmyobrDfoicogllHee-iffinopxenamaslaitneitnodnnercpy ENS—JanDHfDnoioatizalreneGA7002,12enu

A generalization of DDH with applications to protocol analysis and computational soundness

Amadeus SAS,[e-mail]

VERIMAG Grenoble,[e-mail]

DCSSI Crypto Lab,[e-mail]

Emmanuel Bresson 1 , Yassine Lakhnech 2 ,LaurentMazare´ 3 , Bogdan Warinschi 4

s

University of Bristol,[e-mail]

July 4, 2007

itnoilacAdpp

nera7AGe,200ne21aHdnfoDDitnoilaz

DDH assumption

Giveng x andg y , it is computationally diffi- cult to distinguish betweeng xy andg r

Simple:so easy to state Nice:properties such as random self-reducibility Applications:numerous. . . secure public-key encryption [EG85,CS98] pseudo-random functions [NR97,Can97] pseudo-random generators [BM84] key exchange: seminal application [DH76]

nsioaticplApNEuJ—S ortnI Q)P,DH-D plApaticsnoiffiiD:eH-eamll duction OurmainreustlD:HDmilpei(s pxenamlleH-effiiDrcrenndsaaltienon ocslorotespd-nab icfoclogboliAsym PHDDlborP(eh-)Q, obprmaleTh em DHeD enariliz pyitno eG results T ngDDH Our sesuitnds

udortnI ur n O ioct sureinma nopxenamlleH-effiirDfoicogclliboym izgnarileGen itnocrypndenalsaenti cilpoita D-)Q pA HDieplP,s(:DltimDH otocsl sA abespdorHellman-ns:Diffie- ,Q(PDD)-roHPembl O HDD errutlus ehT s eGenarilizgnDDH noitDDfodnaHlppAaticnsio

Most famous: Group Diffie-Hellman [Ste96,BCP02b] giveng Q i x i , for up ton−1 exponents, decideg x 1 ∙∙∙x n vs. g r

Appear naturally when generalizing protocols two-party to multi-party key exchange

Make protocol analysissimpler still useful if the assumption can be reduced to a standard one make protocol construction moremodular

NE—SuJen12,2007AGeneraliza

PHorlbme eRaletwd sults The(P,Q)-DD kor neGAlare,12e7002DHfDdAanatiznoionos

Larger number of variables “group DH” problem [BCP02b], testg x 1 ∙∙∙x n “parallel DH” problem [BCP02c]: giveng x i , test theg x i r “multiple DDH” problem [BCP02a]: giveng x i , test theg x i x j

More general polynomials expressions [Kil01] g a andg b , and a (single) challengeg P(a,b)

Other extensions: General Diffie-Hellman Exponent (GDHE) [BBG05] Square Exponent [MW96,CS00,Shp02] Inverse Exponent [SS01]

ppilacitJ—nuESN tlD:HDmiamnierus ction Our Introdu ralizingDDH Ourre dnnercpyitno eGen nemaonxptiensaalcigoDrof-effiilleH ls As toco liclymbo am-neHllpdorabesioaticple-iffi:Dns ,P(seilp pA HDD-)Q

ions

Adversary sees someg p(x 1 ,x 2 ,...,x n ) wherepin a fixed set of, polynomialsP polynomialsinstead ofmonomials

1

foDDaHdnpAlpcita mene mo le ardnasdnengehalleencbetw noitazilareneGA700,221neJuS—EN ts iwht p g x( reelvadecanbeint sallowed edtsedicasreumyr n ),x dv 3 A x 21 ,..,. llHee-iffi:DnsioatcilppA HDD-)Q,P(splieDHimlt:DresuamniO n ru tcoiorud saalenndonxptienlleHenamDrof-effiiliclogic ls Asymbo pdorotocam-nabes tnI reasA 2 vdalleeschceivryre onimla m s Qt foopyl hallengeultiplec 2 x, 1 ..., segn x(q gqiresena n ),x he,w (P,Q s TheHPro)-DD uOGr lbme lazinere ontiypcr liraneGe O HDDgniz tluserru ioatfDnoDH

esnrairmHiDDt:ul dortnI uO noitcu luse hT st ,P(eD-)QPrDHleob ur m OneGearilazitnofoDDH el-HffieDiorcfgiloslaitnenopxenamln Gen ptioncryande uOrr DgHDzinirela )-,QH A DDlimp(Pes :snoeffiiDilppitac-basedpr-Hellman ysbmloci tocolo A s calionti

Adversary receives challengesg q(x 1 ,x 2 ,...,x n ) , whereqin a setQ of polynomials multiple challenges allowed can be interleaved withg p(x 1 ,x 2 ,...,x n )

2

s

1

Adversary sees someg p(x 1 ,x 2 ,...,x n ) , wherepin a fixed set of polynomialsP polynomialsinstead ofmonomials

oitaDfonnaHDppAd1,2007AGeneraliz elemtn E s SNJ—nu2e anesnglem e doandrtebedicelahcneewvers 3 Adustdarym

pAlpcitafoDDaHdnlization7AGenera12en002,NEuJ—S

2

Adversary sees someg p(x 1 ,x 2 ,...,x n ) , wherepin a fixed set of polynomialsP polynomialsinstead ofmonomials

Adversary receives challengesg q(x 1 ,x 2 ,...,x n ) , whereqin a setQ of polynomials multiple challenges allowed can be interleaved withg p(x 1 ,x 2 ,...,x n )

3

1

Adversary must decide between challenges and random elements

nsio nopxitneaslanednypcronti neGelira sl sAmyobillcgociforDiffie-Hellmane GruO melb zilarenefDnoioatDH DD O Hizgn ustlruer (P,Q s TheHPro)-DD taoisnD:ffii-eeHllman-basedprotoco userD:tlmiHDeilpP,s(-DQ) Ap DH icpl Itnctiorodu main n Our

radirbyh(foorpruizaleren)gntmegu odsmranadeivrpvoity o ibileducelfr rane!soicitccsla anncimbeduReioct ..htyeni auitno . s knownpracludeall

Q

Our Main Result

(P,Q)-DDH reduces to basic DDH !

under “natural” conditions onPand

ranezaliontiDDofdnaHlppAtacisnoi espreviousones EN—SuJen122,00A7eG aleren n GDHgDiniz ednaslaioitpyrcn DHPrQ)-Dmoble seluuOrr (e,P st hT amnoitcuder,ytilranegellfuIn lb(eioadnuva DD)Hal(Gentixponybee esehnitttilatfoyegtheren,d?)toue afris”tiedtnfi“ytely,wei g Fortuna uctitrodIn lu:trnsemria no uO)-,Q(PeslimpHiDD :snoitacilppA HDD lman-basDiffie-Hello A s ysbm derptoco orcfffieDiicolgiloopxetnenleH-naml

zingraliGene tionrcpydnnelaasneitonxpnemallHee-iffiDrofcigolcilobmy tocols As basedproeHllam-nsnD:ffii-eicplioat -DQ) Ap DHeilp,P(sD:tlmiHD OurMainResult Q,P(DD-)orPHmelb H O DD reurltsu he s T durontI ruO noitc userniam ticalippdAanDHfDonoitazilareneGA

In full generality, reduction may be exponential (GDDH) unavoidable (?), due to the generality of the setting

(P,Q)-DDH reduces to basic DDH ! under “natural” conditions onPandQ

nos nutale,yoFtrfy“fair”weidenti .. sn eht. utisoita lkalwnnoncyidelu ty ourproof(hybriadgrmune)tegenarzelirespouvineso SNE s nuJ—,12e7002 ticapracnarilsce decu so R ! acbnitnoverompeindraiadverflesmoilibicud