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

フワシ。

Circuit SAT

。。Circuit SAT。ハcircuit satisfiability。ヒ、ネ、マ。「SAT。ハマタヘシー、ホスシツュイトヌスタュフ萃遙ヒ、ホイマゥネヌ、ヌ、「、。」スミホマ、ャ1、ヒ、ハ、、隍ヲ、ハニホマ、ャツクコ゚、ケ、、ネ、ュ、ヒ。「、ス、ホイマゥ、Circuit SAT、ネ、、、ヲ。」

。ヨC(w)=1。ラ「ヘ。ヨC「コCircuit SAT。ラ

。。ヘソ、ィ、鬢、ソイマゥ、ャCircuit SAT、ヌ、「、、ォ、ノ、ヲ、ォ、トエ、ル、、ホ、マコ、ニ、ヌ、「、。」ニホマ、ャnクト、「、セケ遑「チナ、熙ヌトエ、ル、、ハ、鬢ミ2nイトエ、ル、ハ、ア、、ミ、ハ、鬢ハ、、。」、ウ、、ヌ、マツソケ狆ーサエヨニ筅ヒスェ、、鬢ハ、、。」

Circuit SAT、ネNPエーチエ

[トヘ]
Circuit SAT、マNPエーチエ、ヌ、「、。」

[ケヘサ。]トセエムナェ、ヒ、マCircuit SAT、ヌ、「、、ォ、ノ、ヲ、ォ、トエ、ル、クホィナェ、ハハヒ。、マ、ハ、、、ネ、、、ヲ、ウ、ネ。」

[セレフタ]Circuit SAT、ャ。「NP、ヒツソケ狆ーエヤクオ、ヌ、ュ、、ウ、ネ、シィ、ケ。」

。。A。ァNPクタク、ネイセト熙ケ、。」
。。A、マツソケ狆ーサエヨク。セレシヤ。ハpoly-time verifier。ヒ、ヌ、「、・「・・エ・・コ・澤、サ、ト。」V、マ、、、ッ、ト、ォ、ホy、ヒツミ、キ、ニ<x,y>、accept、ケ、、ネ、ュ、タ、ア。「x「コA、ヒ、ハ、、ネ、、、ヲタュシチ、サ、ト。」

。。、オ、鬢ヒ。「poly-size circuit、ヌ、「、C、マV、ネナイチ、ネ、、、ヲサシツ、ャ、「、。」C、ホニホマ。ハx,y。ヒ、マ、チ、遉ヲ、ノV、ホニホマ、ヒツミア、キ、ニ、、、。」、ス、キ、ニ。「x、ネy、ホトケ、オ、ヘソ、ィ、poly timeニ筅ヌ。「C、マケステロ、ヌ、ュ、。」

。。、隍テ、ニ。「Circuit SAT、ホ・、・・ケ・ソ・・ケ、ャNP、ホ・、・・ケ・ソ・・ケ、ヒハムエケ、ヌ、ュ、ソ。」

[トヘ]
、ケ、ル、ニ、ホNPエーチエフ萃熙マCircuit SAT、ヒオ「テ螟ヌ、ュ、。」

[ケヘサ。]NPエーチエフ萃熙マSAT、ヒオ「テ螟ヌ、ュ、。」SAT、マCircuit SAT、ヒオ「テ螟ヌ、ュ、。」

Circuit SAT、ネーナケ賚マタ

。。Circuit SATフ萃遙ハNPエーチエフ萃遙ヒ、ヘヘム、キ、ニ。「シ。、ホーナケ讌ラ・・ネ・ウ・、コ、、ウ、ネ、ャ、ヌ、ュ、。」

  • NIZK proof
    • ニホマテヘ、witness、ネ、キ。「セレフタシヤ、ヒヘソ、ィ、鬢、。」
    • ヌ、ーユ、ホcircuit C、マNAND・イ。シ・ネ、タ、ア、ヌケスタョ、オ、、、ホ、ヌ。「NAND・イ。シ・ネ、タ、ア、ケヘ、ィ、、ネ、隍、。」
    • NAND・イ。シ・ネ、ホニホマ2、ト、ネスミホマ1、ト、ホテヘ、commitment scheme、ヌア」、キ、ニ。「ク。セレシヤ、ヒチ、。」、ウ、、ヒ、隍鷸Kタュ、ヒ、ソ、ケ。」
    • ・レ・「・・・ー、サ、ソ、サ、、ネ。「commitmentセハ、ホ、゙、゙タオ、キ、ッキラササ、キ、ソ、ネ、、、ヲセレフタ、ク。セレ、ヌ、ュ、。」
  • NIZK argument