ȤˤŹ˴ؤڡǤϡʤäꡢäҤƤꤹȤޤ塢ĽͽǤ
ŹΡذŹ浻ѤΤ٤ơ٤ȯ䤵Ƥޤ鿴ԸΰŹܤǤޤǰŹܤ˲٤ĩ路ĤĤޤƤޤäعβǺǤʻˤưŹ꤬ʤɤˤǤ
̣ȤƤAmazonǤȯǤ
Źϸ르ꥺࡦŹ沽르ꥺࡦ楢르ꥺ3ĤΥ르ꥺǹ롣äơĥElGamalŹ3ĤΥ르ꥺǹƤ롣
ƥѥϤȤ롣
1q|p-1礭ǿp,q롣
2̿qȤʤ롢θ롣
30xqȤʤxΤ褦y롣
4pk=(p,q,,y)̩sk=xϤ롣
ǹθʿʸmȤmpkϤȤ롣
10rqȤʤr롣
2Τ褦c1,c2롣
3ƥå2Ƿc1,c2ȤȤơŹʸcȤ롣c=(c1,c2)Ϥ롣
Źʸc=(c1,c2)skϤȤ롣
1ƽϤ롣
ʾ3ĤΥ르ꥺबĥElGamalŹλͤˤʤ롣Ĥʬ롣
ElGamalŹѤǤä
ʬޤȤȤǡ
ΤȤDLꡦCDHꡦDDHΤˤʤΤǤ롣HGʬǤȤϡHGʬǤꡢʤHGȱ黻ƱǤ롣
ʬѤ꤬ˤʤȤ¤ѤΤĥElGamalŹǤ롣ΤᡢĥElGamalŹθ르ꥺˡʬȤνޤޤƤΤǤ롣
르ꥺΥƥå1ˤq|p-1פȤϡqp-1ڤȤ̣Ǥ롣㤨Сp=2q+1δطʤɤǤ롣Τ褦ʴطǤǿp,qϼΤ褦뤳ȤǤ롣
1礭ǿq롣
2rӡȤ롣
3pǿɤǧǿǤʤʤ饹ƥå1롣⤷pǿǤС(p,q)q|p-1Ƥ롣
ޤ르ꥺΥƥå2ˤơ̿ΰ̿ˤȤդо줷Ƥ롣gΰ̿kȤϡ褦ʺǾͤΤȤǤ롣
ƥå2Ǽĥ̿qȤʤθ¸ߤ뤳ȤݾڤΤϡƥå1ˤäq|p-1ΩĤǤ롣ΰ̿ȸϸ˴ط롣
ơΦˡϡθϸgơ
Ф褤Φΰ̿qˤʤäƤ롣¨
Ωġ⡢Φΰ̿qΤߤǤ롣λ¤ϼΤ褦˾Ǥ롣
p-1=2rqꡢ
p-1=2rq
ʢեޡξ
ޤȤʤi1iqˤ¸ߤȲꤹȡ
ʺա
ȷǤΤǡΩġ
gΰ̿2ri2rq=p-1꾮gϸǤ뤳Ȥȿ롣
äơȤʤi1iqˤ¸ߤʤ椨ˡΰ̿qΤߤǤ롣
ΩĤᡢǤդiФ
ȹͤФ褤Ĥޤꡢλؿmod qǹͤФ褤ΤǤ롣
äơΦνqĤǤꡢνǤˤʤ롣ν롣
르ꥺब줿ʤСޤǧɬפ롣ʸŹΡ˴Ȥ楢르ꥺ¹Ԥȡʿʸ뤳ȤǤ롣ĤޤꡢŸơmˤʤдΩġ
äơ줿
[]Ф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ο¬ȤϤ롣
Bơ
ΩäƤ1ʤǤz=xyΩäƤ뤳Ȥ̣ˤϤ
ΩäƤ0ʤǤzxyΩäƤ뤳Ȥ̣ˤϤ롣
ʾBιϴλǤ롣
ˡBΨĴ٤ɬפ롣
[1]z=xyξ
pkcϳĥElGamalŹλ̤pk,cʬۤޤäƱǤ롣
äơAʾγΨǡ
Ȥʤ
ϤϤǤ롣
椨ˡz=xyξBʾγΨ1Ϥ롣ĤޤꡢB
ʾγΨz=xyǤ뤳ȤȽǤ롣
[2]zxyξ
pkϳĥElGamalŹλ̤pkʬۤޤäƱǤ롣ޤc=(,mb)=(,mbz)Ǥ롣zͥ˼ƤΤǡǰʬۤƤꡢ
ǰʬۤǤ롣äơcϴbξƤ롣äơA
γΨǤ
Ȥʤ
Ϥ뤷ʤ
椨ˡzxyξBγΨ1Ϥ롣
äơ[1][2]ꡢBΨϼΤ褦˷Ǥ롣
ĤޤꡢBΨϦŰʾǤ뤳Ȥ狼äĤޤꡢA¸ߤꤷơB¸ߤȤǤ롣
ФDDH꤬Ǥ뤳ȤꤹСB¸ߤ̷⤹롣äơĥElGamalŹIND-CPAŨ¸ߤʤĤޤꡢФDDH꤬ǤʤСĥElGamalŹIND-CPAǤ뤳Ȥ롣