[PDF] [PDF] Design and Analysis of Secure Encryption Schemes - DI ENS

View - Download [PDF] Design and Analysis of Secure Encryption Schemes - DI ENS

Previous PDF

Next PDF

UNIVERSITYOFCALIFORNIA,SANDIEGO

DesignandAnalysisof

SecureEncryptionSchemes

inComputerScience by

MichelFerreiraAbdalla

Committeeincharge:

ProfessorMihirBellare,Chairperson

ProfessorYeshaiahuFainman

ProfessorAdrianoGarsia

ProfessorMohanPaturi

ProfessorBennetYee

2001

Copyright

MichelFerreiraAbdalla,2001

Allrightsreserved.

onmicro¯lm: Chair

UniversityofCalifornia,SanDiego

2001
iii

DEDICATION

Tomyfather(inmemorian)

iv

TABLEOFCONTENTS

v vi

LISTOFFIGURES

II.2TheschemeDHIES=(

E;D;K),where:SYM=(E;D)isasym-

oflengthtLen;G=(G;g; ;")isarepresentedgroupwhosegroup vii viii

LISTOFTABLES

ix

ACKNOWLEDGEMENTS

andhavinghimasafriend. partofmythesiscommittee. x

Zadrozny,andDmitriiZagorodnov.

xi VITA

June27,1970Born,RiodeJaneiro,Brazil

1993{1994IndiceDesenvolvimentodeSistemas

1996M.S.,COPPE/UFRJ,Brazil

2001DoctorofPhilosophy

UniversityofCalifornia,SanDiego

PUBLICATIONS

T.Okamotoed.,Springer-Verlag,2000.

Number4,pp.443{454,August,2000.

Networks,Campinas,Brazil,May1997.

xii

FIELDSOFSTUDY

MajorField:ComputerScienceandEngineering

StudiesinCryptographyandNetworkSecurity.

ProfessorMihirBellareandBennetYee

ProfessorYeshaiahuFainman

StudiesinMathematics.

ProfessorAdrianoGarsia

StudiesinComplexityandTheory.

ProfessorsMohanPaturi

xiii

ABSTRACTOFTHEDISSERTATION

DesignandAnalysisof

SecureEncryptionSchemes

by

MichelFerreiraAbdalla

DoctorofPhilosophyinComputerScience

UniversityofCalifornia,SanDiego,2001

ProfessorMihirBellare,Chair

e±cientandpractical. standardSECG[71]. xiv situations. xv

ChapterI

Introduction

nowbeingusedformanydi®erentpurposes. thecommunication.

I.AEncryption

knowledgeprotocols. 1 2

I.A.1Background

ciphertextitreceived. 3 tostorecanincreasesigni¯cantly.

I.A.2PerfectPrivacy

4

I.A.3Moderncryptography

abouttheplaintextfromtheciphertext. 5

I.A.4Public-keyEncryption

I.A.5BroadcastEncryption

6 exampleisbroadcastencryption. thresholdencryptionandkeydistribution.

I.A.6ProvableSecurity

thecryptographicprimitivesaresecure. 7 violatingGP. anyspeci¯ccryptanalyticattacksonS. functionssuchastheRSAone-wayfunction.

I.A.7ConcreteSecurity

desirableinthesesituations. A impliestheabsenceofpracticalattacksonS. 8 asymptoticanalysesofreductions.

I.BContributions

9 10

Wool[4,5].

ChapterII

E±cientpublic-keyencryption

schemes 11 12

PhillipRogaway[2,3].

II.AIntroduction

Hellmanbasedencryption.

DHESandasDHAES.Itisallthesamescheme.

securityguarantees. 13 throughsucharesult. 14 theDi±e-Hellmanproblem. tooneother. 15 approachcanbeprovensound. practical.

CCA2in[9].

16 centralrole. amuchweakerone. largeclassofe±cientattacks. proachforalloftheresultsabove. 17

II.BDe¯nitions

II.B.1Representedgroups

elementsinG.Wethusrequireaninjectivemap :G!f0;1ggLenassociatedtoG, operators. returnsxi.WewillcallthetupleG=(G;g; ;")arepresentedgroup.

II.B.2MessageAuthenticationCodes

18 writtenasasubscript. T letFbeanadversary.Considertheexperiment experimentExpsuf-cma MAC;F k

RÃmKey

thenreturn1elsereturn0 Adv mac

MAC;F=Pr[Expsuf-cma

MAC;F=1]:

Adv mac

MAC(t;qt;¹t;qv;¹v)=maxFfAdvmac

MAC;Fg

viaaquerytothetagoracle. 19 thereisnodi®erence.

II.B.3SymmetricEncryption

20 signi¯cantlymorethanhalfthetime. letAbeanadversary.Considertheexperiment experimentExpind-cpa-fg SYM;A k

RÃeKey

(x0;x1;s)ÃAE(k;¢)(¯nd) b

RÃf0;1g

yÃE(k;xb) e bÃAE(k;¢)(guess;y;s) if eb=bthenreturn1elsereturn0 Adv ind-cpa-fg

SYM;A=2¢Pr[Expind-cpa-fg

SYM;A=1]¡1

advantageofSYMas Adv ind-cpa-fg

SYM(t;q;¹)=maxAfAdvind-cpa-fg

SYM;Ag

timeoftheexperimentExpind-cpa-fg

SYM;AplusthesizeofthecodeforA,allinsome

¯xedRAMmodelofcomputation.

21

II.B.4AsymmetricEncryption

ofalgorithmsASYM=( y=

D(sk;y)2Message[fBADg.

Thekeygenerationalgorithm

K,forall

x2Messageandr2Coins,wehavethat

D(sk;E(pk;x;r))=x.The¯rstargument

to

EandDmaybewrittenasasubscript.

De¯nitionII.B.3LetASYM=(

E;D;K)beanasymmetricencryptionscheme

andletAanadversary.Considertheexperiment experimentExpind-cpa-fg

ASYM;A

(sk;pk)Ã K (x0;x1;s)ÃA(¯nd;pk) b

RÃf0;1g

yÃ

Epk(xb)

e bÃA(guess;pk;y;s) if eb=bthenreturn1elsereturn0 Adv ind-cpa-fg

ASYM;A=2¢Pr[Expind-cpa-fg

ASYM;A=1]¡1

22

ASYMas

Adv ind-cpa-fg

ASYM(t;c)=maxAfAdvind-cpa-fg

ASYM;Ag

lengthatmostcbits.} discussion.

De¯nitionII.B.4LetASYM=(

E;D;K)beanasymmetricencryptionscheme

experimentExpind-cca-fg

ASYM;A

(sk;pk)Ã K (x0;x1;s)ÃA

Dsk(¯nd;pk)

b

RÃf0;1g

yÃ

Epk(xb)

e bÃA

Dsk(guess;pk;y;s)

if eb=bthenreturn1elsereturn0 Adv ind-cca-fg

ASYM;A=2¢Pr[Expind-cca-fg

ASYM;A=1]¡1

ASYMas

Adv ind-cpa-fg

ASYM(t;c)=maxAfAdvind-cpa-fg

ASYM;Ag

23
macKeyencKeysecretvalueMake H encMM ephemeralPKMakerecipient's publickey ephemeralPKsecretvalue T E tagg uv u gug v

II.CTheSchemeDHIES

LetG=(G;g;

encryptionschemeDHIES=(

E;D;K).WewillwriteDHIES[[G;SYM;MAC;H]]

24
tiontaggeneratedbytheMAC. p),oneshould feedgutoH.

II.DAttributesandAdvantagesofDHIES

25
algorithmK begin vÃf1;:::;jGjg;pkÃg"v;skÃv return(pk;sk) end algorithmE(pk;M) begin uÃf1;:::;jGjg

XÃpk"u

UÃg"u

hashÃH(X) macKeyÃhash[1::mLen] encKeyÃhash[mLen+1:: mLen+eLen] encMÃE(encKey;M) tagÃT(macKey;M)

EMÃUkencMktag

returnEM endalgorithmD(sk;EM) begin

UkencMktagÃEM

XÃU"sk

hashÃH(X) macKeyÃhash[1::mLen] encKeyÃhash[mLen+1:: mLen+eLen] ifV(macKey;encM;tag)=0 thenreturnBAD

MÃD(encKey;encM)

returnM end ;")is

H:f0;1ggLen!f0;1geLen+mLen.

26
torecoverM.

II.D.2De¯cienciesofElGamalEncryption

havejustdescribed. fallshortofallpotentialmessages. 27
knownas\semanticsecurity." p,thereareattacksshowingthatsome thedescriptionofonesuchattack. u,v,andz.Thisisaverystrongassumption. 28
andchosen-ciphertextsecurity.

AttacksontheElGamalScheme

p.Tosupport scheme. 29
onlyifMisanon-square. f isnotdependentonwhichgroupGisbeingused. g f ofEM. tagesofDHIESincludethefollowing. 30
automatically. havebeenraisedaboutthismodel[26]. 31
randomoracle.

II.EDi±e-HellmanAssumptions

experimentExpcdh G;A u

RÃf1;:::;jGjg;UÃgu

v

RÃf1;:::;jGjg;VÃgv

ZÃA(U;V)

ifZ=guvthenbÃ1elsebÃ0 returnb 32
sumptionas Adv cdh

G;A=Pr[Expcdh

G;A=1]:}

;")be experimentExpddh-real G;A u

RÃf1;:::;jGjg;UÃgu

v

RÃf1;:::;jGjg;VÃgv

ZÃguv

bÃA(U;V;Z) returnb experimentExpddh-rand G;A u

RÃf1;:::;jGjg;UÃgu

v

RÃf1;:::;jGjg;VÃgv

zquotesdbs_dbs29.pdfusesText_35

[PDF] El Gran Libro Del Dibujo Book PDF

[PDF] Sommaire - BMCE Bank

[PDF] el kybalion los misterios de hermes tres iniciados - Logia Teosófica

[PDF] el kybalion los misterios de hermes tres iniciados - Logia Teosófica

[PDF] luchas indígenas y estado plurinacional en ecuador - Universidad

[PDF] El libro de los Cerdos - CEPLI

[PDF] el álbum ilustrado: el libro de los cerdos de anthony browne

[PDF] El libro de los Cerdos - CEPLI

[PDF] Descargar guía de lectura: El libro de los cerdos - CEPLI

[PDF] Descargar guía de lectura: El libro de los cerdos - CEPLI

[PDF] Descargar guía de lectura: El libro de los cerdos - CEPLI

[PDF] La organización municipal y la participación en la gestión local

[PDF] periodismo y democracia - Consejo de Redacción

[PDF] el periodismo en el siglo de las redes sociales the journalist in the

[PDF] COMPOSICIÓN YPROPIEDADES DEL PETROLEO 1 Qué son el