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

ܼ

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

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

ذŹ浻ѤΤ٤ơ

̣򻲾ȤƤAmazonǤȯǤ

ElGamalŹ

  • Źΰ
  • CDHβOW-CPAǤ롣
  • ElGamalŹθ르ꥺɤΤˡĥElGamalŹȤΤ¸ߤ롣
    • ĥElGamalŹDDHβIND-CPAǤ롣

ElGamalŹλ

ElGamalŹϸ르ꥺࡢŹ沽르ꥺࡢ楢르ꥺ3ĤΥ르ꥺफ鹽롣

[1]

ԥꥹϡޤ礭ǿp\mathbb{Z}_{p}^{*}θϸg֡

ˡx~\in~\mathbb{Z}_{p-1}ӡy=gx (mod p)׻롣

Ǹˡꥹpk=(p,g,y)ȤƸsk=x̩Ȥ̩ݻ롣

äơpk=(p,g,y)̩xȤ롣y=gx (mod p)

[2]Ź沽

ԥܥ֤ϡꥹθpk=(p,g,y)ʿʸm~\in~\mathbb{Z}_{p}^{*}ϤȤơŹʸC=(c1,c2)򼡤Τ褦ˤƵ롣

r~\leftarrow~\mathbb{Z}_{p-1}ӡ׻롣

c1=gr (mod p)c2=myr (mod p)

äơŹʸC=(c1,c2)=(gr,myr)

[3]

ꥹϡ̩xȰŹʸC=(c1,c2)ϤȤơʿʸm򼡤Τ褦椹롣

c2c1p-1-x (mod p)

c2c1p-1-x (mod p)
=myrgr(p-1-x)
=mgrxgr(p-1-x)ʢy=gx (mod p)
=mgr(p-1)
m1rʢեޡξ
=m (mod p)

ƿ

ElGamalŹΰCDHκ

ElGamalŹβɤDHƱ٤˺񤫤ɤϤ狼äƤʤʤɥС꡼ΥпǤ̩xʳˡDzɤǽϤ롣

ʤ顢ElGamalŹΰCDHκ񤵤Ǥ뤳Ȥ狼äƤ롣

[]
ElGamalŹˤơpk=(p,g,y)ӰŹʸc=(c1,c2)ʿʸmΨŪʥ르ꥺA¸ߤ
ΡCDH򤯸ΨŪʥ르ꥺB¸ߤ

[]ˡǹͤ롣

[1]ʢͤ򼨤

å롣

R=my^{r}=m\(g^{x}\)^{r}=mg^{xr}

å롣

\frac{R}{m}=\frac{R}{R~\cdot~g^{r\(~p-1-x~\)}}~\,~\(mod~\,~p\)=\frac{R}{R~\cdot~g^{r~\(p-1~\)}~\cdot~g^{-gr}}=\frac{R}{R~\cdot~g^{-gr}}=\frac{1}{g^{-gr}}=g^{gr}

[2]ʢ򼨤

å롣餫

å롣

\frac{my^{r}}{g^{xr}}=\frac{mg^{xr}}{g^{xr}}=mQ.E.D.

[ͻ]ǤElGamalŹ򤯥르ꥺबʤСDH򤯥르ꥺϤˤȤ򼨤Ƥ롣

жСCDHΨ1Dz򤯤ȤǤʤСElGamalŹΨ1DzɤϤǤʤȡפ̣롣

Ψ1ʤƤ⡢㤨гΨ0.1Dzɤ륢åA¸ߤСŹϤϰȤϤʤ

ǤϡŨΨšʡ0ˤDzɤȲꤷ硢DHϤɤΤ餤γΨDz򤱤ΤʲpqꤷdzΨͤ롣

Ҥ:ξˤơåA뤫ɤAؤϤΤߤˤäꤵ롣

ȡPr(A)ϼN0,N1Ѥơɽ롣

N0(y,c1,c2)
N1Aɤ(y,c1,c2)

Pr(A)=N1/N0

:ξˤơAȤäCDH򤳤ȤBϡRѤƤ롣Τ褦ϰʳѤ륢르ꥺΨŪ르ꥺȸƤ֡ΨŪ르ꥺνϤϡϤRˤäƷꤵ롣

äơBΨǤPr(B)ϼN'0,N'1Ѥơɽ롣

N'0(gx,gr,R)
N'1Bgxr׻Τ(gx,gr,R)pqϸǤä

Pr(B)=N'1/N'0

Τ褦줿ΨѤȡƳȤǤ롣

[]

ȴˤäưȼ

ElGamalŹѤץꥱȯԤ̤˼ˡʬȴ򤷤礭Ȥ롣򤳤ǾҲ𤹤롣

Ź沽٤rѤʤȤȼ

[̿]
ElGamalŹǤϡʿʸmŹ沽٤ˡrѤʤСŹϤΰݤƤʤ

[]

2Ĥʿʸm1,m2Τ줾ΰŹʸc1=(a1,b1),c2=(a2,b2)Ȥ롣

ǡa1gr1,a2gr2ΩĤrƱʤΤǡa1=a2ˤʤ롣

Ĥޤꡢ2ĤΰŹʸc1=(a,b1),c2=(a,b2)Ȥʤ롣

\frac{m_{2}}{m_{1}}~=~\frac{b_{2}}{b_{1}}

äơΥ졼Ωġ

b1,b2ϰŹʸİФ狼롣

ˡʿʸm1򲿤餫ˡåƤޤȡm2狼äƤޤȤˤʤ롣

pͤȤȼ

ElGamalŹΥпκ˴ŤpͤȤΥп꤬򤱤Ƥޤ

㡧pk=(p,g,y)=(5,2,3)ǤElGamalŹˤȤŨˤĤƹͤ롣
ΤȤ̩sk衣

32x (mod 5)xΥпǤ롣

x\mathbb{Z}_{p-1}~=~\mathbb{Z}_{5-1}~=~\bigl{~0,1,2,3,4~\bigr}νǤʤΤǡ5ĤοˤĤǼɤĴ٤롣
ȡx=3ΤȤȤ狼Ϥ

äơsk=x=3Ǥ롣

ʸ

  • ظŹδÿ
  • Sequences of Games:A Tool for Taming Complexity in Security Proofs