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

ܼ

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

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

ذŹ浻ѤΤ٤ơ

̣򻲾ȤƤAmazonǤȯǤ

μ

ľŪ

þΥƥΤȡ

  • completeness
    • Pμĥ硢ڼVϹΨǼĥ롣
  • soundness
    • Pμĥʤ硢ڼVϹΨǼĥʤ
  • μzero knowledge
    • Ԥǡ顢ʾڵΡμξϳƤʤ

[FS90]

proof system (P,V)طRZKZero KnowledgeˤȤϡ褦ʥߥ졼MPPTˤ¸ߤ뤳ȤǤ롣ĤޤꡢǤcompletenesssoundnessΩproof system¸ߤơ˼˼褦zero knowledgeɲäȤȤǤ롣

\forall~V'~\(~PPT~\),~\forall~\(~x,w~\)~\in~R,~\forall~y~\(input~\,~of~\,~V'\)~;\{~V'_{P~\(~x,w~\)}~\(~x,y~\)~\}~\approx~\{~M~\(~x,y~;~V'\)~\}

MV'򥵥֥롼ȤƻȤ롣

ߥ졼о줷ƺǽϸǤ⤷ʤܤƤߤ롣
ľŪzero knowledegeϡ֥ץȥΥǡΤʤꤵǡޤȤȥ󥹥ץȤˤ顢witnessμreceiver˴ϳʤפȤȤǤ롣ǡwitnessΤʤߥ졼ȤPPTƱץȥΥȥ󥹥ץȤ˺뤳ȤǤФ褤Ȥˤʤ롣ĤޤꡢreceiverREALsender̿Ƥ뤳Ȥȡߥ졼ˤsimulated sender̿Ƥ뤫̤ǤʤСzero knowledgeȤʤ뤳Ȥˤʤ롣ݥȤϥߥ졼witness wΤʤȤǤ롣

μξ

Pϡp,g,yˤФơy=gx mod pȤʤxΤäƤפȤμVΤ롣ʤߤˡqȤϡgΰ̿¨|g|=pǤ롣

  1. 򼨤
    • PΥпxΤʤ硢acceptΨ1/qȤʤ롣äơOK
  1. 򼨤
    • xΤäƤȤڼɬΩĤȤΤ롣餫
  1. μ򼨤
    • (a,c,v)˥ߥ졼ȤǤΤǡμϳʤ

ߥ졼ȤΤȤܡ

ޤc֡q̤ꤢ롣

ˡvꤦͤĴ٤ʤʤ顢vϲ餫θxP̩ǤΤʤ餫ˤǤꡢcϤǤ˾嵭Ƿꡣv=r+cx mod pʤΤǡr˰¸롣rq̤ꤢ뤫顢vq̤ꡣ

ȡv,cꤷΤǡa=\frac{g^{v}}{y^{c}}~\,~mod\,~paꤹ롣

Ʒꤷ(a,c,v)ΥåȤʪǤо줷Ƥ롣ĤޤꡢˤΤˤɬ롣ʪǤc0ϥǤ뤫顢1Ľʾˤ롣a0Ʊ͡v0ϼưŪ˷ꤹ롣

Τ򸫤ȡޤäxȤ鷺˥ߥ졼ȤǤƤʹбϰۤʤ뤬ʬۤƱˡäơʪȥߥ졼ȤϼԲǽǤ롣

ZKIPη

֤СP̩ξäƤʤVƤޤΨ򤤤Ǥ⸺餹ȤǤ롣㤨С̩ξäƤʤɥС꡼μþV뤳ȤΨ1/2ñ˥΢ɽƤȤˤȤƤޤȡZKIP򥢥ɥС꡼100Ϣ³V˼ƤޤΨ1/2^100ˤʤ롣

䤤碌򸺤餹Ȥ¸ץȥȤơNVZKIP롣

ZKIPα

Ѽǧ

V̩ϳʤդV̩ϤƤޤȰѤƤޤǽ롣ޤMITMƤȤƤ⡢̿üƤޤ̩ΤϳƤʤ

̿İƤ륢ɥС꡼̩ϳʤĤޤŹ沽ס

ʸ

  • [FS90]ʸWitness Indistinguishable and Witness Hiding Protocols