、ウ、ホ・レ。シ・ク、、マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、爨マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ 、ウ、ホ・レ。シ・ク、livedoor ・ッ・・テ・ラ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、瀝ivedoor ・ッ・・テ・ラ

フワシ。

タナチ

。。ナ・オ・、・ネ、ヒ、ェ、ア、ーナケ讀ヒエリ、ケ、・レ。シ・ク、ヌ、マ。「タ篶タ、ャツュ、熙ハ、ォ、テ、ソ、遙「ク、テ、ソオュスメ、、キ、ニ、、、ソ、熙ケ、、ネ、ウ、、ャ、「、熙゙、ケ。」コ」ク蝪「セッ、キ、コ、トス、タオ、ケ、ヘスト熙ヌ、ケ。」

。。ーナケ賚マタ、ホ。リーナケ豬サスム、ホ、ケ、ル、ニ。ル、ャネッヌ荀オ、、ニ、、、゙、ケ。」ス鯀エシヤク、ア、ホーナケ賤ワ、ヌ、ケ。」、ウ、、゙、ヌーナケ賤ワ、ヒイソナル、ォトゥタ、キ、ト、ト、篌テダ、キ、ニ、キ、゙、テ、ソハ。「ウリケサ、ホインツ熙ヌヌコ、、ヌ、、、ハ。「サウハサクウ、ヒ、ニーナケ讀ホフ萃熙ャカシ熙ハハ、ハ、ノ、ヒ、ェエォ、皃ヌ、ケ。」

。リーナケ豬サスム、ホ、ケ、ル、ニ。ルタナチ・オ・、・ネ

。。カスフ」、ャ、「、ハ、マタナチ・オ・、・ネ、サイセネ、キ、ニ、ッ、タ、オ、、。」Amazon、ヌ、篳ッヌ菘讀ヌ、ケ。」

standard commitment scheme based on one-way function。ハノヤエーチエ。ヒ

。。one-way function、ャツクコ゚、ケ、、ミ。「PRG。ハオシサヘソタクタョエ。ヒ、ャツクコ゚、ケ、[Nao91][HILL98]。」PRG、サネ、テ、ニ。「シ。、ホ、隍ヲ、ヒケスタョ、ケ、、ミstandard commitment scheme、ケステロ、ヌ、ュ、、ネサラ、、、。ハシツコン、マ、゙、タノヤエーチエ。ヒ。」、ウ、、マサ熙テ、ニシォチウ、ハ・「・、・ヌ・「、ヌ、「、。」

。。G、マ。「k・モ・テ・ネ、ニホマ、ネ、キ、ニ。「3k・モ・テ・ネ、ホオシサ・鬣・タ・狹ヘ、タクタョ、ケ、PRG、ネ、ケ、。」

タュシチ

computationally hiding

。。PRG、ホトオチ、隍遙「commitmentセハ、タ、ア、ォ、鬢マ・鬣・タ・狹ヘ、ォオシサ・鬣・タ・狹ヘ、ォ、ホカ靆フ、マノユ、ォ、ハ、、。」、ト、゙、遙「b、マア」、オ、、ニ、、、。」。。「「

binding、ヌ、ハ、、。ハpoly-time sender、ホ、ネ、ュ、ヌ、オ、ィ。ヒ

。。binding、ヌヒ、・「・ノ・ミ。シ・オ・遙シA、ャツクコ゚、キ、ソ、ネ、ケ、。」

  • com~=~x
  • dec_0~=~decom~=~s
  • dec_1~=~decom~=~random
  • ヒ、ソ、ケ、ル、ュセキ。ァx=G~\(~s~\)~=G~\(~random~\)

。。ヒ、ソ、ケ、ル、ュセキシー、ォ、鮠。、ャタョ、ホゥ、ト。」

x=G~\(~s~\)~=G~\(~random~\)
s=random

。。、ウ、、ャタョ、ホゥ、ト、隍ヲ、ヒA、マs、ネrandom、ヒスミホマ、ヌ、ュ、。」、ト、゙、遙「dec0、ネdec1、ホスミホマ、ャーテラ、ケ、、隍ヲ、ハA、ハ、饕inding、ヌヒ、テ、ニ、キ、゙、テ、ニ、、、、ウ、ネ、ヒ、ハ、。」。。「「

。。binding、サ、ソ、ハ、、、ネ、、、ヲフ萃熙マ。「sender、ャb=1、commit、ケ、、ネ、ュ、ヒヌ、ーユ、ホネフゥ、サネ、ヲサネ、ヲノャヘラ、ャ、ハ、、、ネ、、、ヲサシツ、ヒオ「テ螟オ、、。」b、ホテヘ、ャ0、ヌ、1、ヌ、筍「ネフゥ、サネ、ヲ、隍ヲ、ヒス、タオ、ケ、、ル、ュ、ヌ、「、。」

standard commitment scheme based on one-way function。ハス、タオネヌ。ヒ

。。、ウ、、マ。「セ蠏ュ、ホstandard commitment scheme based on one-way function、ャbinding、サ、ソ、ハ、、、ネ、、、ヲフ萃熙イキ隍キ、ソ・ラ・・ネ・ウ・、ヌ、「、。」

  • b「コ{0,1}。ァ1・モ・テ・ネ
  • G。ァ{0,1}k「ェ{0,1}3k、ホPRG

タュシチ

computationally hiding

。。hiding、マシ。、ホシ酘・、ォ、鬢、、ィ、。」、ト、゙、遙「PRG、イセト熙キ、ニ、、、、、ア、ハ、ホ、ヌ。「hiding、ヌヒ、・「・ノ・ミ。シ・オ・遙シ、マツクコ゚、キ、ハ、、、ネ、、、ヲ、ウ、ネ、ヌ、「、。」

[シ酘・]
R*。ハPPT cheating receiver。ヒ、ャREVEAL・ユ・ァ。シ・コ、ヒニ、チー、ヒ0、ホcommitmentセハ、ネ1、ホcommitmentセハ、カ靆フ、ケ、、ネ、ケ、。」
、ウ、ホ、ネ、ュ。「R*、マPRG、ヌヒ、。」

[セレフタ]

ヲナ(k)。ァPr[R* outputs 1|S commits 1]-Pr[R* outputs 1|S commits 0]
、ネ、ケ、。」

。。、ウ、ホ、ネ、ュ。ヨヲナ(k)。ァneg。ラ、ヌ、「、、ウ、ネ、シィ、キ、ソ、、。」、ス、ウ、ヌ。「R*、サネ、テ、ニ。「PPT distinguisher D。ハニホマx、・鬣・タ・狹ヘ、ォオシサ・鬣・タ・狹ヘ、ォ、シアハフ、ケ、シアハフサメ。ヒ、コ、。」

。。、ウ、ウ、ヌ。「x、ャオシサ・鬣・タ・狹ヘ、ホ、ネ、ュ。「D、マhonest sender、ネエーチエ、ヒニア、ク、ヒニー、ッ、ウ、ネ、ャ、、ォ、。」

。。、ス、、ヌ、マ。「D、ャ1、スミホマ、ケ、ウホホィ、トエ、ル、ニ、゚、隍ヲ。」

Pr[~D~\,~outputs~\,~1] =~Pr[~(~R^{*}~\,~outputs~\,~0~)~\wedge~\(~S~\,~commits~\,~to~\,~0~)]~+~Pr[~(~R^{*}~\,~outputs~\,~1~)~\wedge~\(~S~\,~commits~\,~to~\,~1~)]
=~Pr[S~\,~commits~\,~to~\,~0~]~\cdot~Pr[~R^{*}~\,~outputs~\,~0~|~S~\,~commits~\,~to~\,~0~]~+~Pr[S~\,~commits~\,~to~\,~1~]~\cdot~Pr[~R^{*}~\,~outputs~\,~1~|~S~\,~commits~\,~to~\,~1~]
=\frac{1}{2}~\cdot~Pr[~R^{*}~\,~outputs~\,~0~|~S~\,~commits~\,~to~\,~0~]~+~\frac{1}{2}~\cdot~Pr[~R^{*}~\,~outputs~\,~1~|~S~\,~commits~\,~to~\,~1~]
=\frac{1}{2}~\(~Pr[~R^{*}~\,~outputs~\,~0~|~S~~\,~commits~\,~to~\,~0~]~+~Pr[~R^{*}~\,~outputs~\,~1~|~S~~\,~commits~\,~to~\,~1~]~\)
=\frac{1}{2}~\(~1~-~Pr[~R^{*}~\,~outputs~\,~1~|~S~~\,~commits~\,~to~\,~0]~+~Pr[~R^{*}~\,~outputs~\,~1~|~S~~\,~commits~\,~to~\,~1~]~\)
=~\frac{1}{2}~+~\frac{\epsilon~\(~k~\)}{2}

。。ーハ。「x、ャ・鬣・タ・爨ホ、ネ、ュ。「R*、ホView、マb、ネニネホゥ、ヌ、「、。」、ハ、シ、ハ、鬢ミ。「\forall~r_0~;~x~\,~or~\,~x~\oplus~r_0、マーヘヘハャノロ、タ、ォ、鬢ヌ、「、。」

。。、隍テ、ニ。「Pr[D~\,~outputs~\,~1|~x~:~random]~=~\frac{1}{2}

。。、讀ィ、ヒ。「シ。、ャタョ、ホゥ、ト。」

Pr[D~\,~outputs~\,~1|~x~:~non-random]
=~Pr[D~\,~outputs~\,~1]~-~Pr[D~\,~outputs~\,~1|~x~:~random]
=~\frac{1}{2}~+~\frac{\epsilon~\(~k~\)}{2}~-~\frac{1}{2}
=~\frac{\epsilon~\(~k~\)}{2}

。。R*、ホイセト熙隍遙「、ウ、ホウホホィ、マneg、ヌ、「、。」、隍テ、ニ。「ヲナ(k)、マneg、ヒ、ハ、。」

。。、キ、ソ、ャ、テ、ニ。「ヲナ(k)、ホトオチ、ォ、鬘「D、マ、ュ、チ、、ネx、ャ・鬣・タ・狹ヘ、ォオシサ・鬣・タ・狹ヘ、ォ、シアハフ、ヌ、ュ、ニ、、、。」、ト、゙、遙「イセト熙ホ、隍ヲ、ハR*、ャツクコ゚、ケ、、ミ。「x、ャ・鬣・タ・狹ヘ、ォオシサ・鬣・タ・狹ヘ、ォ、シアハフ、ケ、・「・・エ・・コ・爨ャツクコ゚、ケ、。」、キ、ォ、キ。「PRG、イセト熙ヒ、キ、ニ、、、、ホ、ヌ。「、ウ、、マフキス筍」、讀ィ、ヒ。「x、ャ・鬣・タ・狹ヘ、ォオシサ・鬣・タ・狹ヘ、ォ、シアハフ、ケ、・「・・エ・・コ・爨マツクコ゚、キ、ハ、、。」、隍テ、ニ。「hiding、ャタョ、ホゥ、ト。」。。「「

perfect binding

。。binding property、ホセレフタ、ホ、ロ、ヲ、ャカスフ」ソシ、、。」

。。R、honest、ネイセト熙キ、ニ。「all-powerful S*、ャ1、ト、ホcommitmentセハ、ヒツミ、キ、ニ。「2、ト、ホーロ、ハ、decommitmentセハ、ヒ・ェ。シ・ラ・、ヌ、ュ、ウホホィ、ャneg、ヌ、「、、ウ、ネ、シィ、ケ。」

。。、゙、コ。「S*、ャbinding、ヌヒ、、ネ、キ、ソ、鬘「シ。、ホ、隍ヲ、ハセキシー、ャタョ、ホゥ、ト。」

y~=~G~\(~s~\)~\wedge~r_0~=~y~\oplus~G~\(~s'~\)

。。2、ト、ホセキシー、チネ、゚ケ遉、サ、、ミ。「シ。、ホ、隍ヲ、ヒクタ、、エケ、ィ、、ウ、ネ、筅ヌ、ュ、。」

G~\(~s~\)~\oplus~G~\(~s'~\)~=~r_0

。。、ウ、ホエリキクシー、ヒ、ハ、、隍ヲ、ハr0、bad、ネクニ、ヨ、ウ、ネ、ヒ、ケ、。」

。。、ウ、ウ、ヌ。「s,s'、マk・モ・テ・ネ、ハ、ホ、ヌ。「bad、ハテヘr0、マセッ、ハ、ッ、ネ、22kクト、「、。」

。。ーハ。「r0、マ3k・モ・テ・ネ、ホーヘヘ・鬣・タ・狹ヘ、タ、テ、ソ、ホ、ヌ。「R、ャbad r0、チェ、ヨウホホィ、マ、サ、、、シ、、\frac{2^{2k}}{2^{3k}}~=~2^{-k}、ヌ、「、。」、讀ィ、ヒ。「neg、ヒ、ハ、。」。。「「