课件说明教案2 pubkey trapdoor

OnlineCryptographyCourse

DanBoneh

PublicKeyEncryp4on

fromtrapdoorpermuta4ons

Construc4ons

Goal: constructchosen-­‐ciphertextsecurepublic-­‐keyencryp4on

Trapdoorfunc4ons(TDF)

Def: atrapdoorfunc.X⟶Yisatripleofefficientalgs. (G,F,F-­‐1)

G(): randomizedalg.outputsakeypair (pk,sk)

F(pk,⋅): det.alg.thatdefinesafunc4on X⟶Y

F-­‐1(sk,⋅): definesafunc4on Y⟶X thatinverts F(pk,⋅)

Moreprecisely: ∀(pk,sk)outputbyG

∀x∈X: F-­‐1(sk,F(pk,x))=x

DanBoneh

SecureTrapdoorFunc4ons(TDFs)

(G,F,F-­‐1)issecureif F(pk,⋅) isa“one-­‐way”func4on:

canbeevaluated,butcannotbeinvertedwithoutsk

Adv.A

Chal.(pk,sk)G()

x⟵R X

pk, yF(pk,x) x’

Def: (G,F,F-­‐1)isasecureTDFifforallefficientA:

AdvOW[A,F]=Pr[x=x’] <negligible

DanBoneh

DanBoneh

Public-­‐keyencryp4onfromTDFs

(G,F,F-­‐1): secureTDF X⟶Y

(Es,Ds): symmetricauth.encryp4ondefinedover(K,M,C)

H:X⟶K ahashfunc4on

Weconstructapub-­‐keyenc.system(G,E,D):Keygenera4onG: sameasGforTDF

Public-­‐keyencryp4onfromTDFs

(G,F,F-­‐1): secureTDF X⟶Y

(Es,Ds): symmetricauth.encryp4ondefinedover(K,M,C)

H:X⟶K ahashfunc4on

E(pk,m):

x⟵R X,

k⟵H(x),

y⟵F(pk,x)

c⟵Es(k,m)

output (y,c)

D(sk,(y,c)):

x⟵F-­‐1(sk,y),

k⟵ m⟵Ds(k,c)output m

header

body

Inpictures:

SecurityTheorem:

If(G,F,F-­‐1)isasecureTDF, (Es,Ds)providesauth.enc.and H:X⟶K isa “randomoracle”

then (G,E,D) isCCAro secure.

IncorrectuseofaTrapdoorFunc4on(TDF)

NeverencryptbyapplyingFdirectlytointext:

E(pk,m):

output

c⟵F(pk,m)

D(sk,c):

output F-­‐1(sk,c)

Problems:

Determinis4c: cannotbeseman4ca