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

ܼ

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

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

ذŹ浻ѤΤ٤ơ

̣򻲾ȤƤAmazonǤȯǤ

ĥElGamalŹλ

Źϸ르ꥺࡦŹ沽르ꥺࡦ楢르ꥺ3ĤΥ르ꥺǹ롣äơĥElGamalŹ3ĤΥ르ꥺǹƤ롣

르ꥺ

ƥѥ᡼ϤȤ롣

1q|p-1礭ǿp,q롣

2̿qȤʤ롢\mathbb{Z}_q^*θ롣

30xqȤʤx򤷡Τ褦y׻롣

y=\alpha^x~\pmod{p}

4pk=(p,q,,y)̩sk=xϤ롣

Ź沽르ꥺ

ǹ󷲤θʿʸmȤmpkϤȤ롣

10rqȤʤr򤹤롣

2Τ褦c1,c2׻롣

c_1=\alpha^r~\pmod{p}

c_2=my^r~\pmod{p}

3ƥå2Ƿ׻c1,c2ȤȤơŹʸcȤ롣c=(c1,c2)Ϥ롣

楢르ꥺ

Źʸc=(c1,c2)skϤȤ롣

1\frac{c_2}{c_1^x}~\pmod{p}׻ƽϤ롣

르ꥺ­

ʾ3ĤΥ르ꥺबĥElGamalŹλͤˤʤ롣Ĥ­ʬ롣

äƤ뷲ˤĤ

ElGamalŹѤ\mathbb{Z}_q^*Ǥä\mathbb{Z}_q^*ʬ򤦤ޤȤȤǡ\mathbb{Z}_q^*ΤȤDLꡦCDHꡦDDH򤯤ΤˤʤΤǤ롣HGʬǤȤϡHGʬǤꡢʤHGȱ黻ƱǤ롣

ʬѤ꤬ˤʤȤ¤ѤΤĥElGamalŹǤ롣ΤᡢĥElGamalŹθ르ꥺˡ\mathbb{Z}_q^*ʬȤνޤޤƤΤǤ롣

르ꥺp,qˡ

르ꥺΥƥå1ˤq|p-1פȤϡqp-1ڤȤ̣Ǥ롣㤨Сp=2q+1δطʤɤǤ롣Τ褦ʴطǤǿp,qϼΤ褦뤳ȤǤ롣

1礭ǿq롣

2rӡp=2rq+1Ȥ롣

3pǿɤǧǿǤʤʤ饹ƥå1롣⤷pǿǤС(p,q)q|p-1Ƥ롣

¸ݾ

ޤ르ꥺΥƥå2ˤơ̿ΰ̿ˤȤդо줷Ƥ롣gΰ̿kȤϡg^k~\pmod{p}=1褦ʺǾͤΤȤǤ롣

ƥå2Ǽĥ̿qȤʤ\mathbb{Z}_q^*θ¸ߤ뤳ȤݾڤΤϡƥå1ˤäq|p-1ΩĤǤ롣ΰ̿ȸϸ˴ط

ˡ

ơΦˡϡ\mathbb{Z}_q^*θϸgơ\alpha~=g^{2r}~\pmod{p}׻Ф褤Φΰ̿qˤʤäƤ롣¨\alpha^q~\equiv~1~\pmod{p}Ωġ⡢Φΰ̿qΤߤǤ롣λ¤ϼΤ褦˾Ǥ롣

p-1=2rq\alpha~=g^{2r}~\pmod{p}

\alpha^q
=(g^{2r})^q
=g^{2rq}
=g^{p-1}p-1=2rq
=1~\pmod{p}ʢեޡξ

ޤ\alpha^i~\equiv~1~\pmod{p}Ȥʤi1iqˤ¸ߤȲꤹȡ

ʺա
=\alpha^i
\equiv~(g^{2r})^i
=g^{2ri}

ȷ׻ǤΤǡg^{2ri}~\equiv~1~\pmod{p}Ωġ

gΰ̿2ri2rq=p-1꾮gϸǤ뤳Ȥȿ롣

äơ\alpha^i~\equiv~1~\pmod{p}Ȥʤi1iqˤ¸ߤʤ椨ˡΰ̿qΤߤǤ롣

󷲡ˤĤ

\alpha^q~\equiv~1~\pmod{p}ΩĤᡢǤդiФ\alpha^i\alpha^{i~\pmod{q}}~\pmod{p}ȹͤФ褤Ĥޤꡢλؿmod qǹͤФ褤ΤǤ롣

äơΦν󷲤qĤǤꡢν󷲤Ǥ1~\pmod{p},\alpha~\pmod{p},\alpha^2~\pmod{p},~\cdots,~\alpha^{q-1}~\pmod{p},ˤʤ롣ν󷲤롣

르ꥺब줿ʤСޤǧɬפ롣ʸŹΡ˴Ȥ楢르ꥺ¹Ԥȡʿʸ뤳ȤǤ롣Ĥޤꡢ\frac{c_2}{c_1^x}~\pmod{p}ŸơmˤʤдΩġ

\frac{c_2}{c_1^x}~\pmod{p}
=\frac{my^r}{\alpha^{rx}}
=\frac{m\alpha^{xr}}{\alpha^{rx}}
=m

äơ줿

DDHIND-CPA

[]ФDDH꤬ǤʤСĥElGamalŹIND-CPAǤ롣

¨ФDDHβǡĥElGamalŹIND-CPAǤ롣

[]뤿жǹͤ롣ĤޤꡢINDCPA򤯥르ꥺA¸ߤʤСФDDH򤯥르ꥺB¸ߤ뤳Ȥ򼨤ȤǤФ褤AΨ(1/2)+ŤȤ롣

ˤϵˡȤAϤѤơB뤳ȤǤBΨŰʾǤФ褤ΤǤ롣

ޤBι򼨤
B(,,,)=(,x,y,z)ͿȤ롣BŪϤޤٹ򤹤뤳ȤˤꡢAϤѤơz=xy mod qɤͭդʳΨȽꤹ뤳ȤǤ롣
B(,,,)ϤȤpk=(p,q,,)A˸ȤͿ롣ΤȤpkĥElGamalŹθƱʬۤɬפ뤬p,q,,¤٤ƱʤŨBưƤ뤳Ȥ˵դʤΤǡʤ
ˡACPAԤʤΤ2Ĥʿʸm0,m1򳰤롣ABm0,m1롣BϤä顢1ӥåȤb򤹤롣ơBc=(,mb)ŹʸȤA롣BٹƤΤǤ롣cĥElGamalŹλ̤˺줿(c1,c2)ȤޤäƱʬۤ򼨤ᡢABˤ뤳Ȥ˵դʤᡢʤĤޤꡢAcٹƤΤ˵դʤΤǤ롣
AϺǸbο¬Ȥ\tilde{b}Ϥ롣
B\tilde{b}򸫤ơb~=~\tilde{b}ΩäƤ1ʤǤz=xyΩäƤ뤳Ȥ̣ˤϤb~\not{=}~\tilde{b}ΩäƤ0ʤǤzxyΩäƤ뤳Ȥ̣ˤϤ롣
ʾBιϴλǤ롣

ˡBΨĴ٤ɬפ롣

[1]z=xyξ

pkcϳĥElGamalŹλ̤pk,cʬۤޤäƱǤ롣
äơA\frac{1}{2}~+~\epsilonʾγΨǡb~=~\tilde{b}Ȥʤ\tilde{b}ϤϤǤ롣

椨ˡz=xyξB\frac{1}{2}~+~\epsilonʾγΨ1Ϥ롣ĤޤꡢB\frac{1}{2}~+~\epsilonʾγΨz=xyǤ뤳ȤȽǤ롣

[2]zxyξ

pkϳĥElGamalŹλ̤pkʬۤޤäƱǤ롣ޤc=(,mb)=(,mbz)Ǥ롣zͥ˼ƤΤǡ\alpha^z\mathbb{Z}_q^*ǰʬۤƤꡢm_b~\alpha^z\mathbb{Z}_q^*ǰʬۤǤ롣äơcϴbξ򱣤Ƥ롣äơA\frac{1}{2}γΨǤb~=~\tilde{b}Ȥʤ\tilde{b}Ϥ뤷ʤ

椨ˡzxyξB\frac{1}{2}γΨ1Ϥ롣

äơ[1][2]ꡢBΨϼΤ褦˷׻Ǥ롣

Adv(B)
=~\Pr[~B~\,~outputs~\,~1~\|z=xy]~-~\Pr[B~\,~outputs~\,1~\|z~\not{=}~xy~]
\ge~(\frac{1}{2}~+~\epsilon)~-~\frac{1}{2}
=~\epsilon

ĤޤꡢBΨϦŰʾǤ뤳Ȥ狼äĤޤꡢA¸ߤꤷơB¸ߤ򼨤ȤǤ롣

ФDDH꤬Ǥ뤳ȤꤹСB¸ߤ̷⤹롣äơĥElGamalŹIND-CPAŨ¸ߤʤĤޤꡢФDDH꤬ǤʤСĥElGamalŹIND-CPAǤ뤳Ȥ롣

ʸ

  • ظŹδÿ
  • ߥΡ
  • WB41