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

*フワシ。 [#pb9fb8af]

#contents

*タナチ [#rd011e0a]

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

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

[[&ref(http://s-akademeia.sakura.ne.jp/main/books/cipher/img/cover_mini.jpg,nolink,。リーナケ豬サスム、ホ、ケ、ル、ニ。ルタナチ・オ・、・ネ);>http://s-akademeia.sakura.ne.jp/main/books/cipher/]]

。。カスフ」、ャ、「、ハ、マ[[タナチ・オ・、・ネ:http://s-akademeia.sakura.ne.jp/main/books/cipher/]]、サイセネ、キ、ニ、ッ、タ、オ、、。」[[Amazon:https://www.amazon.co.jp/dp/4798148814/securityakade-22]]、ヌ、篳ッヌ菘讀ヌ、ケ。」


*standard commitment scheme based on one-way function。ハノヤエーチエ。ヒ [#jf435f81]

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

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

#img(http://security2600.sakura.ne.jp/main2/image2/PRG_commitment.jpg)
#img(,clear)


**タュシチ [#c7425d87]

***computationally hiding [#neb1eae8]

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


***binding、ヌ、ハ、、。ハpoly-time sender、ホ、ネ、ュ、ヌ、オ、ィ。ヒ [#ne6f56df]

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

#img(http://security2600.sakura.ne.jp/main2/image2/binding_A.jpg)
#img(,clear)

-&mimetex("com = x");
-&mimetex("dec_0 = decom = s");
-&mimetex("dec_1 = decom = random");
-ヒ、ソ、ケ、ル、ュセキ。ァ&mimetex("x=G \( s \) =G \( random \)");

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

&mimetex("x=G \( s \) =G \( random \)");~
&mimetex("s=random");

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

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


*standard commitment scheme based on one-way function。ハス、タオネヌ。ヒ [#pdde716e]

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

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

#img(http://security2600.sakura.ne.jp/main2/image2/PRG_commitment2.jpg)
#img(,clear)


**タュシチ [#jdd92633]

***computationally hiding [#l6a39405]

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

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

[セレフタ]

ヲナ(k)。ァPr[RSUP{*}; outputs 1|S commits 1]-Pr[RSUP{*}; outputs 1|S commits 0]~
、ネ、ケ、。」

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

#img(http://security2600.sakura.ne.jp/main2/image2/fix1.jpg)
#img(,clear)

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

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

&mimetex("Pr[ D \, outputs \, 1]");
&mimetex(" = Pr[ ( R^{*} \, outputs \, 0 ) \wedge \( S \, commits \, to \, 0 )] + Pr[ ( R^{*} \, outputs \, 1 ) \wedge \( S \, commits \, to \, 1 )]");~
&mimetex("= 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 ]");~
&mimetex("=\frac{1}{2} \cdot Pr[ R^{*} \, outputs \, 0 | S \, commits \, to \, 0 ] + \frac{1}{2} \cdot Pr[ R^{*} \, outputs \, 1 | S \, commits \, to \, 1 ]");~
&mimetex("=\frac{1}{2} \( Pr[ R^{*} \, outputs \, 0 | S  \, commits \, to \, 0 ] + Pr[ R^{*} \, outputs \, 1 | S  \, commits \, to \, 1 ] \)");~
&mimetex("=\frac{1}{2} \( 1 - Pr[ R^{*} \, outputs \, 1 | S  \, commits \, to \, 0] + Pr[ R^{*} \, outputs \, 1 | S  \, commits \, to \, 1 ] \)");~
&mimetex("= \frac{1}{2} + \frac{\epsilon \( k \)}{2}");

。。ーハ。「x、ャ・鬣・タ・爨ホ、ネ、ュ。「RSUP{*};、ホView、マb、ネニネホゥ、ヌ、「、。」、ハ、シ、ハ、鬢ミ。「&mimetex("\forall r_0 ; x \, or \, x \oplus r_0");、マーヘヘハャノロ、タ、ォ、鬢ヌ、「、。」

。。、隍テ、ニ。「&mimetex("Pr[D \, outputs \, 1| x : random] = \frac{1}{2}");

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

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

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

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


***perfect binding [#q5ab2a1c]

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

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

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

#img(http://security2600.sakura.ne.jp/main2/image2/S_binding.jpg)
#img(,clear)

&mimetex("y = G \( s \) \wedge r_0 = y \oplus G \( s' \)");

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

&mimetex("G \( s \) \oplus G \( s' \) = r_0");

。。、ウ、ホエリキクシー、ヒ、ハ、、隍ヲ、ハrSUB{0};、bad、ネクニ、ヨ、ウ、ネ、ヒ、ケ、。」

。。、ウ、ウ、ヌ。「s,s'、マk・モ・テ・ネ、ハ、ホ、ヌ。「bad、ハテヘrSUB{0};、マセッ、ハ、ッ、ネ、2SUP{2k};クト、「、。」

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