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

フワシ。

タナチ

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

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

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

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

セレフタ・キ・ケ・ニ・爨ホーツチエタュ

。。セレフタ・キ・ケ・ニ・爨ホーツチエタュ、ネ、キ、ニ、マ。「コヌト羣ツシ。、ホ2、ト、ホタュシチ、ヒ、ソ、サ、ミ、隍、。ハシ。、ホ2、ト、ホタュシチ、サ、ソ、サ、ミコヌト羣ツ、ホーツチエタュ、マサ、ト、ネ、、、ヲーユフ」。ヒ。」

  • completeness。ハエーチエタュ。ヒ
    • x、ャネストフ萃ヲー、ホYESニホマ、ハ、鬘「V、マP、ホproof、セ、ヒaccept、ケ、。」
      • トセエムナェ、ヒクタ、ィ、ミ。「witness、テホ、テ、ニ、、、、ミ。「V、ホク。セレシー、ャタョ、ホゥ、ト。」
  • soundness。ハキチエタュ。ヒ
    • x、ャネストフ萃ヲー、ホNOニホマ、ハ、鬘「V、マP、ホproof、accept、ケ、ウホホィ、マカヒ、皃ニセョ、オ、、。」
      • トセエムナェ、ヒクタ、ィ、ミ。「witness、テホ、テ、ニ、、、、ミ。「V、ホク。セレシー、ャタョ、ホゥ、トウホホィ、マ、ロ、ネ、、ノ・シ・。」

[ハ荵ヨ]・シ・テホシアセレフタ、ホセケ遉マ。「、ウ、ホ2、ト、ヒzero-knowledge。ハ・シ・テホシアタュ。ヒ、ャノユソ、ケ、。」

WI。ハWitnetss Indistingusihability。ヒ

。。WI、ネ、マ。「proof system、ホタュシチ、ホ、メ、ネ、ト、ヌ、「、[FS90]。」

[トオチ]
セレフタ・キ・ケ・ニ・(P,V)、ャエリキクRセ螟ヌWI、ネ、マ。「シ。、ヒ、ソ、ケ、ネ、ュ、ヌ、「、。」
\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。ァトソ
Rj。ハ1。號。蚯。ヒ。ァrelations testable in polynomial time
(Pj,Vj)。ァ・・。シ・キ・逾、ャRj、ヌ、「、proof systems
セ蠏ュ、ヌクタオレ、キ、ソtクト、ホ・・。シ・キ・逾、ホ、メ、ネ、ト、ヌ、「、・ラ・・ネ・ウ・(Pi,Vi)、ホーネフナェキケ遉マ。「concurrent execution、ヌ、「、。」
xi。ァ、ス、ホ・ラ・・ネ・ウ・、ヒツミ、ケ、ニホマ。」・オ・、・コ、マn。」
ーロ、ハ、・ラ・・ネ・ウ・、ヌ、ホセレフタシヤ、ネク。セレシヤ、マpairwise distinct、ヌ、「、ノャヘラ、マ、ハ、、。」
ニホマxi,・・。シ・キ・逾Ri。ァpairwise distinct、ヌ、「、ノャヘラ、マ、ハ、、。」
、ウ、ホ、ネ、ュ。「・ム。シ・ニ・」。シ、ホソヘソ。「・オ・、・コ。「サエヨ。ハrunning time。ヒ、ャnーハイシ、ヌ、「、、ネ、ュ。「キケ遉ャpolynomial、ネ、、、ヲ。」

general composition、ホニテハフ、ハ・ア。シ・ケ

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

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

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

non-erasure WI

サイケヘハクク・

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