Top / 証明システムの安全性

証明システムの安全性

目次 †

宣伝 †

　当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

　暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

　興味がある方は宣伝サイトを参照してください。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とは、次を満たすときである。

[補講]WIの定義には、ZKの定義のときのようなシミュレータMは考えない。

[定理]プロトコルの一般的な結合（general compositon）において、WIは保持される。

　暗号プロトコルを想像してみる。例えば、認証プロトコル、鍵交換プロトコルなど。それらの暗号プロトコルは、実行の度に違う入力がされ、さらに異なるパーティーとやり取りする。

[定義]
t：定数
Rj（1≦j≦t）：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では、同じときに実行されている。

[定義]
任意の証明者の部分集合P=(P1,…,Pk)（各証明者はhonestに動く）があって、任意の2つの集合witness とがある。このとき、P以外に含まれない証明者たちと検証者たちが結託しても、W1とW2を識別できないときに、プロトコルのpolynomial compositonがWIであるという。
ただし、nを十分大きいとして、wはnの関数とする。

[定理]
WIはプロトコルのpolynomial compositonの下で保持される。

non-erasure WI †

参考文献 †

• [FS90]論文「Witness Indistinguishable and Witness Hiding Protocols」