、ウ、ホ・レ。シ・ク、、マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、爨マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ 、ウ、ホ・レ。シ・ク、livedoor ・ッ・・テ・ラ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、瀝ivedoor ・ッ・・テ・ラ
*フワシ。 [#d2fec6b0]

#contents


*UAHC。ハUC Adaptive Hamiltonicity Commitment。ヒ [#xd903b11]

。。aHC、マ[[CRS・筵ヌ・]]、ヒ、ェ、、、ニ。「computationally hiding。「computationally binding。「equivocality、ネ、、、ヲ3、ト、ホタュシチ、サ、ト、ウ、ネ、ャ、、ォ、テ、ソ。」、ウ、ホaHC、ネクウォクーーナケ讌ケ・ュ。シ・爨ヘヘム、キ、ニ。「、オ、鬢ヒextractability、サ、トソキ、キ、、commitment scheme、コ、、ウ、ネ、ャ、ヌ、ュ、。」、ウ、、ャ''UAHC。ハUC Adaptive Hamiltonicity Commitment。ヒ''、ヌ、「、。」

[ハ荵ヨ]UAHC。ワCRS・筵ヌ・、マ。「hiding,binding,equivocality,extractability、ホ4、ト、ホタュシチ、サ、ト。」、ト、゙、遙「[[UC commitment scheme]]、ヒ、ハ、テ、ニ、、、。」plain・筵ヌ・、ヌ、マUC Commitment・ラ・・ネ・ウ・、ャツクコ゚、キ、ハ、、、ウ、ネ、ャセレフタ、オ、、、ャ。「CRS・筵ヌ・、タ、ネク螟マーナケ讀ホタ、ウヲ、ヌーネフナェ、ハ・ラ・・゚・ニ・」・ヨ。ハホ网ィ、ミ。「one-way permutation、ハ、ノ。ヒ、サネ、ヲ、ウ、ネ、ヌUC commitment scheme、ャツクコ゚、ケ、、ウ、ネ、ャシィ、オ、、、、ア、ヌ、「、。」

。。UHAC、ホサナヘヘ、マシ。、ホトフ、熙ヌ、「、。」、ソ、タ、キ。「クオ。ケUC commitment schemeヘム、ネ、キ、ニナミセ、キ、ソ、ホ、ヌ。「sid、舖sid、ハ、ノ、ホUC、ホタ、ウヲ、ヌサネ、、、ノユイテセハ、ノユ、ア、ソ、゙、゙。「サナヘヘ、スメ、ル、。」UC、ネ、マエリキク、ハ、ッイシ皃ケ、セケ遉マ。「シォヘウ、ヒノユイテセハ、シ隍ス、、、ニペ、キ、、。」

-PSUB{i};。ァSender
-PSUB{j};。ァReceiver

[1]CRS

-y。ァone-way function f、ホテヘー隍ォ、鬣鬣・タ・爨ヒ、メ、ネ、トシ隍テ、ソテヘ
-E。ァIND-CPAーツチエ、ハクウォクーーナケ讌ケ・ュ。シ・爨ホクウォクー
-ESUB{cca};。ァIND-CCA2ーツチエ、ハクウォクーーナケ讌ケ・ュ。シ・爨ホクウォクー

[2]COMMIT・ユ・ァ。シ・コ

。。PSUB{i};、マ(commit,sid,ssid,Pi,Pj,b)、ニホマ、ネ、キ、ニシ、アシ隍。」、ソ、タ、キ。「b「コ{0,1}、ヌ、「、。」k・モ・テ・ネ、ホ・鬣・タ・狹ヘr、チェ、モ。「z=aHC(b:r)、キラササ、ケ、。」、ス、キ、ニ。「シ。、ホ、隍ヲ、ヒCSUB{b};、ネCSUB{1-b};、キラササ、ケ、。」

-&mimetex("C_b = E(E_{cca} (P_i,P_j,sid,ssid,r ; s_1) ; s_2)");
-&mimetex("C_{1-b} \overset{$}{\leftarrow} \{ 0,1 \}^{|C_b|}");

。。、ウ、ウ、ヌ。「sSUB{1};、ネsSUB{2};、マ・鬣・タ・爭ウ・、・。「E、ネEcca、マクウォクー、ヌーナケ豐ス、キ、ソ、ウ、ネ、ーユフ」、ケ、。」(sid,ssid,PSUB{i};,r,sSUB{1};,sSUB{2};,b)、オュマソ、ケ、。」、ス、ホク蝪「PSUB{j};、リc=(sid,ssid,PSUB{i};,z,CSUB{0};,CSUB{1};)、チ、。」PSUB{j};、マc、シ、アシ隍テ、ソ、鬘「c、オュマソ、キ、ニ、ォ、鬘「(receipt,sid,ssid,PSUB{i};,PSUB{j};)、・。シ・ォ・スミホマ、ケ、。」

[3]REVEAL・ユ・ァ。シ・コ

。。PSUB{i};、マ(reveal,sid,ssid)、ニホマ、ネ、キ、ニシ、アシ隍。」、ケ、、ネ。「オュマソ、オ、、ニ、、、・ヌ。シ・ソ・ル。シ・ケ、ネネ豕モ、キ、ニ。「(sid,ssid)、ャーテラ、ケ、ケヤ、テオ、ケ。」ツクコ゚、ケ、、ミ。「、ス、ホケヤ、ホセハ、ヘヘム、キ、ニ。「PSUB{j};、リ(sid,ssid,r,sSUB{1};,sSUB{2};,b)、チソョ、ケ、。」~
。。PSUB{j};、マ・ヌ。シ・ソ・ル。シ・ケ、ネネ豕モ、キ、ニ。「(sid,ssid)、ャーテラ、ケ、ケヤ、テオ、ケ。」ツクコ゚、ケ、、ミ。「、ス、ホケヤ、ホセハ、ヘヘム、キ、ニシ。、ホ2、ト、ホク。セレシー、・チ・ァ・テ・ッ、ケ、。」

。。、ウ、ホサナヘヘ、ゾシィ、ケ、、ネシ。、ホ、隍ヲ、ヒ、ハ、。」

#img(http://security2600.sakura.ne.jp/main2/image2/UAHC1.jpg)
COMMIT・ユ・ァ。シ・コ
#img(,clear)

#img(http://security2600.sakura.ne.jp/main2/image2/UAHC2.jpg)
REVEAL・ユ・ァ。シ・コ
#img(,clear)

。。CSUB{b};、ホキラササ、ヌ、、カ、、カ2スナ、ヒーナケ豐ス、、キ、ニ、、、、ホ、マ。「IND-CCA2、ホーナケ讌ケ・ュ。シ・爨ヌオシサ・鬣・タ・爨ヒ、ハ、、筅ホ、マテホ、鬢、ニ、、、ハ、、、ォ、鬢ヌ、「、。ハ[[・鬣・タ・爭ェ・鬣ッ・・筵ヌ・]]、ヌ、マーアツクコ゚、ケ、。ヒ。」ferfect binding commitment、マオシサ・鬣・タ・爨ハCPA、ホーナケ讌ラ・・゚・ニ・」・ヨ、ヒハムエケ、ヌ、ュ、、ウ、ネ、ャツソ、、。」ツィ、チ。「IND-CPA、ホーナケ讌ケ・ュ。シ・爨ヌオシサ・鬣・タ・爨ヒ、ハ、、筅ホ、マ、ソ、ッ、オ、、「、。」、ト、゙、遙「COMMIT・ユ・ァ。シ・コ、ヒ、ェ、ア、commitmentセハ、ャ・鬣・タ・狹ヘ、ネカ靆フ、ヌ、ュ、ハ、、、隍ヲ、ヒ。「オシサ・鬣・タ・爨ハIND-CPAーナケ讀サワ、キ、ニ、、、、、ア、タ。」

。。、゙、ソテーユ、キ、ニペ、キ、、ナタ、ャ、゙、タ、「、。」。ヨy=f(x)、ォ、騙、オ皃皃。ラ、ネ、、、ヲフ萃遙「ツィ、チ。ヨx、ネy、ォ、馭SUP{-1};、オ皃皃。ラ、ネ、、、ヲフ萃熙マ。「NPフ萃熙ヌ、「、。」NPフ萃熙マNPエーチエフ萃熙ヒクホィナェ、ヒ。ハpoly-time、ヌ。ヒス、ュトセ、サ、。」、ト、゙、遙「、ウ、ウ、ヌ、マ。ヨ・ー・鬣ユG、ォ、鬣マ・゚・・ネ・・オ・、・ッ・H、オ皃皃。ラ、ネ、、、ヲNPエーチエフ萃熙ヒス、ュエケ、ィ、ニサネ、ヲ、ウ、ネ、ャ、ヌ、ュ、。」シツコン。「aHC、ホニホマ、ヌ、マG、ャサネ、、、ニ、、、ソ、マ、コ、タ。」

。。コヌク螟ホテーユナタ、マ。「commitmentセハ、ホトケ、オ、ヌ、「、。」UAHC、サネ、テ、ニcommit、キ、ソ、、テヘb、マ1・モ・テ・ネ、ヌ、「、テ、ソ。」・モ・テ・ネ・ウ・゚・テ・ネ・皈・ネ、タ、テ、ソ、ォ、鬘「CSUB{0};,CSUB{1};、ホ2、ト、タ、ア、ヌ、隍ォ、テ、ソ。」、キ、ォ、キ。「・ケ・ネ・・・ー・ウ・゚・テ・ネ・皈・ネ、ハ、鬢ミ。「・ケ・ネ・・・ー、ホ・モ・テ・ネトケ、ヒネ賽网キ、ニ。「C、ホソ、ャチ、ィ、ニ、キ、゙、ヲ、ホ、タ。」


**タュシチ [#c3027a2f]

***computationally hiding [#qf4139f6]

。。。ヨ0、ホcommitmentセハ。ラ、ネ。ヨ1、ホcommitmentセハ。ラ、ャキラササホフナェ、ヒシアハフノヤイトヌス、ヌ、「、、ウ、ネ、シィ、キ、ソ、、。」ツ1タョハャ、ォ、鯆3タョハャ、マ、゙、ヌ、マホセハ、ネ、筝ヲトフ、ハ、ホ、ヌスウー、キ。「ツ4タョハャ、ホz、ネツ5タョハャ、ネツ6タョハャ、ホCSUB{0};、ネCSUB{1};、ホ、ネ、ウ、、ヒテフワ、ケ、。」

。。、゙、コ。「チーシヤ、マシ。、ホ、隍ヲ、ヒス、ア、。」

&mimetex("(z,C_0,C_1) = (aHC(0 ; r_0) , E(E_{cca}(P_i,P_j,sid,ssid,r_0 ; s_1) ; s_2),U_{|C_0|})");

。。シ。、ヒ。「ク蠑ヤ、マシ。、ホ、隍ヲ、ヒス、ア、。」

&mimetex("(z,C_0,C_1) = (aHC(1 ; r_1)) ,U_{|C_1|}, E(E_{cca}(P_i,P_j,sid,ssid,r_1 ; s_1) ; s_2)");

。。ウニタョハャ、ホ・モ・テ・ネトケ、マーテラ、、、、ホ、ヌ。「、ス、、セ、、ホタョハャ、ネ豕モ、キ、ニ、、、ア、ミ、隍、。」E、ヌーナケ豐ス、オ、、ニ、、、ノハャ、マオシサ・鬣・タ・爨ハ、ホ、ヌ。「・鬣・タ・爭ケ・ネ・・・ー、ホU、ネカ靆フ、ヌ、ュ、ハ、、。」、ト、゙、シ。、ャタョ、ホゥ、ト。」

-&mimetex("E(E_{cca}(P_i,P_j,sid,ssid,r_0 ; s_1) ; s_2) \overset{c}{\approx} U_{|C_1|}");
-&mimetex("U_{|C_0|} \overset{c}{\approx} E(E_{cca}(P_i,P_j,sid,ssid,r_1 ; s_1) ; s_2)");

。。ク螟マz、ホノハャ、ウホ、ォ、皃、ミ、隍、。」、ウ、ウ、ヌrSUB{0};、ネrSUB{1};、マーナケ豐ス、オ、、ニ、ェ、テホ、、ウ、ネ、マ、ヌ、ュ、ハ、、。」、ス、ヲ、、、テ、ソセカキ、ヒ、ェ、、、ニ、マaHC、ホhiding、隍シ。、ャタョ、ホゥ、ト。」

&mimetex("aHC(0 ; r_0) \overset{c}{\approx} aHC(1 ; r_1)");

。。、讀ィ、ヒ。「UAHC、マcomputationally hiding、サ、ト。」。。「「


***computationally binding [#yd8c65b9]

。。binding、ヌヒ、A、ャツクコ゚、キ、ソ、ネ、ケ、。」

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

。。、ウ、ホA、マ・サ・ュ・螂・ニ・」・ム・鬣癸シ・ソk、ニホマ、ネ、キ、ニ。「シ。、ホ(com,decSUB{0};,decSUB{1};)、スミホマ、ケ、。」

-&mimetex("com = (sid,ssid,P_i,z,C_0,C_1)");
-&mimetex("dec_0 = (sid,ssid,r,s_1,s_2,0)");
-&mimetex("dec_1 = (sid,ssid,r',s'_1,s'_2,1)");

。。、ウ、ホ、ネ、ュシ。、ホ、隍ヲ、ハマ「ホゥハトシー、ャ、、、ィ、。」

-&mimetex("z=aHC(0 ; r) \wedge C_0 = E(E_{cca}(P_i,P_j,sid,ssid,r ; s_1 ) ; s_2)");
-&mimetex("z=aHC(1 ; r') \wedge C_0 = E(E_{cca}(P_i,P_j,sid,ssid,r' ; s'_1 ) ; s'_2)");

。。ツ1シー、ホチーネセ、ネツ3シー、ホチーネセ、ヒテフワ。」z、ャーテラ、キ、ニ、、、、ホ、ヌ。「シ。、ャ、、、ィ、。」

&mimetex("z=aHC(0 ; r)=aHC(1 ; r')");

。。シ。、ホゾ、ホ、隍ヲ、ヒUAHC、ホbinding、ヌヒ、A、ャツクコ゚、ケ、、ネ。「aHC、ホbinding、ヌヒ、B、ャコ、、ニ、キ、゙、ヲ。」

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

。。、キ、ォ、キ。「aHC、マcomputationally binding、サ、ト、ホ、ヌ。「フキス筍」、隍テ、ニ。「A、マツクコ゚、キ、ハ、、。」

。。、讀ィ、ヒ。「UAHC、マcomputationally binding、サ、ト。」。。「「


***equivocality [#jdb6c1d6]

。。CRS、ホtrapdoor、・「・ノ・ミ。シ・オ・遙シ、ャサネ、ィ、、ハ、鬘「binding、ヌヒ、、ウ、ネ、シィ、ケ。」CRS、ホ・ネ・鬣テ・ラ・ノ・「、ネ、マ。「、ウ、ウ、ヌ、マシ。、ホ3、ト、ヌ、「、。」

-x=fSUP{-1};(y)
-SK。ァE、ホネフゥクー
-SKSUB{cca};。ァESUB{cca};、ホネフゥクー

。。、ウ、ホ、ネ、ュ。「・キ・゚・螂。シ・ソ。ハ・、・ヌ・「・・「・ノ・ミ。シ・オ・遙シ。ヒS、マ。「trapdoor、サネ、テ、ニ。「aHC、ホbinding、ヌヒ、・「・ノ・ミ。シ・オ・遙シA、クニ、モスミ、ケ、ウ、ネ、ャ、ヌ、ュ、。」ク螟マ。「A、ホスミホマ、イテケゥ、キ、ニ。「(com,dec0,dec1)、コ、スミ、ケ、ウ、ネ、ャ、ヌ、ュ、。」、ト、゙、遙「trapdoor、ャ、「、、ミ。「UAHC、ホbinding、ヌヒ、テ、ソ、ウ、ネ、ヒ、ハ、。」、ウ、、ゾシィ、ケ、、ネシ。、ホ、隍ヲ、ヒ、ハ、。」。。「「

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


***extractability [#m0b8dc37]

。。extractability、シィ、ケ、ヒ、マ。「S、ヒcom、ネtrapdoor、ニホマ、ネ、キ、ニヘソ、ィ。「b、スミホマ、ヌ、ュ、、ミ、隍、。」

。。、゙、コ。「S、マcom=(sid,ssid,PSUB{i};,z,CSUB{0};,CSUB{1};)、ホニホマ、ネニアサ、ヒ。「CRS、ホtrapdoor、ヌ、「、シ。、ホ3、ト、ホセハ、テホ、、ウ、ネ、ャ、ヌ、ュ、。」

-x=fSUP{-1};(y)
-SK。ァE、ホネフゥクー
-SKSUB{cca};。ァESUB{cca};、ホネフゥクー

。。、ケ、、ネE、ホネフゥクー、ネESUB{cca};、ホネフゥクー、ォ、鬢ス、、セ、、ホクウォクー・ケ・ュ。シ・爨ヒツミ、キ、ニノケ讀ャ、ヌ、ュ、。」

&mimetex("(P'_i,P'_j,sid',ssid',r' ; s'_1) \leftarrow D_{cca}^{SK_{cca}} (D^{SK} ( C_0 ))");

。。、ス、ホノケ豺イフ&mimetex("(P'_i,P'_j,sid',ssid',r' ; s'_1)");、隍遙「シ。、ホク。セレシー、ウホ、ォ、皃、ウ、ネ、ャ、ヌ、ュ、。」

&mimetex("z = aHC(0 ; r')");

。。、筅キ、ウ、ホク。セレシー、ャタョホゥ、キ、ソ、鬘「b=0、スミホマ、キ。「、ス、ヲ、ヌ、ハ、ア、、ミb=1、スミホマ、ケ、、ミ、隍、。」。。「「

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


*サイケヘハクク・ [#m02256f7]

-Lindell. "Composition of Secure Multi-Party Protocols"