ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

ȤˤŹ˴ؤڡǤϡ­ʤäꡢäҤ򤷤ƤꤹȤޤ塢ĽͽǤ

ŹΡذŹ浻ѤΤ٤ơ٤ȯ䤵Ƥޤ鿴ԸΰŹܤǤޤǰŹܤ˲٤ĩ路ĤĤޤƤޤäعβǺǤʻˤưŹ꤬ʤɤˤǤ

ذŹ浻ѤΤ٤ơ

̣򻲾ȤƤAmazonǤȯǤ

DDHꡢϥåؿࡼβSS

[]
Hashed ElGamalŹϡDDHȥϥåؿࡼǤȤSSǤ롣
ʤߤˡࡼȤΤϥϥåͤʬͥǤ뤳ȡ

[]Sequences of Games

A⥢르ꥺAdversary

[1]Game0

Game0ˤAưϼ̤ꡣ

S0defthe event that b=^b in Game0

[2]Game1

Game1ˤAưϼ̤ꡣ

S1defthe event that b=^b in Game1

Τ褦ư륢르ꥺD(,,)롣

ddh(D)ȤΤϡDDHβǡפȤ̣

|Pr[S0]-Pr[S1]|neg

[3]Game2

Game2ˤAưϼ̤ꡣ

S2defthe event that b=^b in Game2

Τ褦ư륢르ꥺD'(k,h)롣

es(D')ϥȥԡࡼ󥰤Ȥ̣

|Pr[S1]-Pr[S2]|neg

ˡPr[S2]=1/2Ǥ롣

äơ[1][2][3]ꡢ

|Pr[S0]-Pr[S2]|
|Pr[S0]-Pr[S1]|+|Pr[S1]-Pr[S2]|
=ddh+es
=šQ.E.D.

ʸ

  • Sequences of Games:A Tool for Taming Complexity in Security Proofs