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

  • トノイテ、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
  • コス、オ、、ソケヤ、マ、ウ、ホソァ、ヌ、ケ。」
*フワシ。 [#t86c829b]

#contents


*WI。ハWitnetss Indistingusihability。ヒ [#e253136c]

[トオチ]。ハ。ヨWitness Indistinguishable and Witness Hiding Protocols。ラ。ヒ~
。。WI、ネ、マ。「proof system、ホタュシチ、ホ、メ、ネ、ト、ヌ、「、[FS90]。」

[トオチ]~
セレフタ・キ・ケ・ニ・(P,V)、ャエリキクRセ螟ヌWI、ネ、マ。「シ。、ヒ、ソ、ケ、ネ、ュ、ヌ、「、。」~
&mimetex("\forall V' \( PPT \), \forall x \(large \, enough \, input \, of \, P \) , \forall w_1,w_2 \in w \( x \) , y \(input \, of \, V'\) ; \{ V'_{P \( x,w_1 \)} \( x,y \) \} \approx \{ V'_{P \( x,w_2 \)} \( x,y \) \}");

[ハ荵ヨ]WI、ホトオチ、ヒ、マ。「ZK、ホトオチ、ホ、ネ、ュ、ホ、隍ヲ、ハ・キ・゚・螂。シ・ソM、マケヘ、ィ、ハ、、。」

[トヘ]・ラ・・ネ・ウ・、ホーネフナェ、ハキケ遑ハgeneral compositon。ヒ、ヒ、ェ、、、ニ。「WI、マハンサ、オ、、。」

。。ーナケ讌ラ・・ネ・ウ・、チロチ、キ、ニ、゚、。」ホ网ィ、ミ。「ヌァセレ・ラ・・ネ・ウ・。「クークエケ・ラ・・ネ・ウ・、ハ、ノ。」、ス、、鬢ホーナケ讌ラ・・ネ・ウ・、マ。「シツケヤ、ホナル、ヒー网ヲニホマ、ャ、オ、。「、オ、鬢ヒーロ、ハ、・ム。シ・ニ・」。シ、ネ、荀シ隍熙ケ、。」

[トオチ]~
t。ァトソ~
RSUP{j};。ハ1。號。蚯。ヒ。ァrelations testable in polynomial time~
(PSUP{j};,VSUP{j};)。ァ・・。シ・キ・逾、ャRSUP{j};、ヌ、「、proof systems~
セ蠏ュ、ヌクタオレ、キ、ソtクト、ホ・・。シ・キ・逾、ホ、メ、ネ、ト、ヌ、「、・ラ・・ネ・ウ・(PSUB{i};,VSUB{i};)、ホーネフナェキケ遉マ。「concurrent execution、ヌ、「、。」~
xSUB{i};。ァ、ス、ホ・ラ・・ネ・ウ・、ヒツミ、ケ、ニホマ。」・オ・、・コ、マn。」~
ーロ、ハ、・ラ・・ネ・ウ・、ヌ、ホセレフタシヤ、ネク。セレシヤ、マpairwise distinct、ヌ、「、ノャヘラ、マ、ハ、、。」~
ニホマxSUB{i};,・・。シ・キ・逾RSUP{i};。ァpairwise distinct、ヌ、「、ノャヘラ、マ、ハ、、。」~
、ウ、ホ、ネ、ュ。「・ム。シ・ニ・」。シ、ホソヘソ。「・オ・、・コ。「サエヨ。ハrunning time。ヒ、ャnーハイシ、ヌ、「、、ネ、ュ。「''キケ遉ャpolynomial''、ネ、、、ヲ。」

**general composition、ホニテハフ、ハ・ア。シ・ケ [#fe8b5566]

-sequential composition
--、メ、ネ、ト、ホ・ラ・・ネ・ウ・、ャスェ、、テ、ニ、ォ、鬘「ハフ、ホ・ラ・・ネ・ウ・、ャサマ、゙、。」
-parallel composition
--、ケ、ル、ニ、ホ・ラ・・ネ・ウ・、ヒニア、クニホマ、ャヘソ、ィ、鬢、ニ。「オッニー、ケ、。」
--、ケ、ル、ニ、ホ・ラ・・ネ・ウ・、ヒ、ェ、ア、ウニ・ケ・ニ・テ・ラj、ヌ、マ。「ニア、ク、ネ、ュ、ヒシツケヤ、オ、、ニ、、、。」

[トオチ]~
ヌ、ーユ、ホセレフタシヤ、ホノハャスクケ躅=(PSUB{1};,。ト,PSUB{k};)。ハウニセレフタシヤ、マhonest、ヒニー、ッ。ヒ、ャ、「、テ、ニ。「ヌ、ーユ、ホ2、ト、ホスクケ轂itness &mimetex("W^1 = \( w_1^1,w_2^1, \cdots ,w_k^1 \)");、ネ&mimetex("W^2 = \( w_1^2,w_2^2, \cdots ,w_k^2 \)");、ャ、「、。」、ウ、ホ、ネ、ュ。「Pーハウー、ヒエ゙、゙、、ハ、、セレフタシヤ、ソ、チ、ネク。セレシヤ、ソ、チ、ャキツ、キ、ニ、筍「WSUP{1};、ネWSUP{2};、シアハフ、ヌ、ュ、ハ、、、ネ、ュ、ヒ。「''・ラ・・ネ・ウ・、ホpolynomial compositon、ャWI、ヌ、「、''、ネ、、、ヲ。」~
、ソ、タ、キ。「n、ススハャツ遉ュ、、、ネ、キ、ニ。「w、マn、ホエリソ、ネ、ケ、。」

[トヘ]~
WI、マ・ラ・・ネ・ウ・、ホpolynomial compositon、ホイシ、ヌハンサ、オ、、。」


*non-erasure WI [#uebfee2e]


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

-マタハク。ヨWitness Indistinguishable and Witness Hiding Protocols。ラ
-[FS90]マタハク。ヨWitness Indistinguishable and Witness Hiding Protocols。ラ