Incrementally Verifiable Computation (IVC)
1. Abstract
長い計算のうち途中までの計算が正しいことを伝えたい
PCP(Probabilistically Checkable Proof)システムを応用したComputationally sound Proof Systemを採用する
2. Introduction
2-1. Word Definition
M: チューリングマシン
α-増加のタイムライン: $ t_j - t_{j-1} ≤ αがすべてのαで成り立つもの
α-増加出力のチューリングマシン: α-増加のタイムラインの各時点で計算の時点表示を出力するチューリングマシン
実行可能なコンパイラ: ２入力の多項式時間の確率的アルゴリズムCであって入力(M, k)(|M| < k)に対して出力C(M, k)が$ k^c-増加出力のチューリングマシンを用いる空間が$ k^c未満であるもの
cは定数
チューリングマシンを受け取ると効率的な空間を用いて同程度の時間感覚で計算過程を出力するチューリングマシンに変換する
2-2. IVC Definition
実現可能なコンパイラCと多項式時間チューリングマシンのVの組であって、入力であるどんなチューリングマシンMとセキュリティパラメータkに対して、以下の3つの性質を満たすもの
正当性: $ m_jが本当にMのj番目の計算過程の出力である
完全性: 出力された証明$ \pi_j^rを検証者Vが必ず受理する
計算量的健全性: Pは偽りの計算過程に対してVを高い確率で納得させる証明を求めることができない
2-3. Non-interactive Proof of Knowledge
効率的なP
Proof Sizeがconstant
効率的なV
完全性
知識抽出性
3. IVC
3-1. Definition
言語$ L_cはチューリングマシン$ T_iとメッセージ$ x = (M, s_1, s_2)の組で$ T_iが(x, w)を$ k^c以内に受理するような長さ3|M| = 3kの証明wが存在するとき$ (T_i, x) \in L_cとする
チューリングマシン$ T_iの定義
$ T_0: $ x = (M, s_1, s_2)として$ ((M, s_1, s_2), w)を入力として受け取り、チューリングマシンMを計算状態$ s1から1秒間動作させて計算状態$ s_2になるかどうか検証する
wは無視する
$ T_{i + 1}: $ x = (M, s_1, s_3), $ w = (p_1, p_2, s_2)として(x, w)を入力として受け取る
p1, p2がそれぞれ$ (T_i, (M, s_1, s_2)) \in L_c, $ (T_i, (M, s_2, s_3)) \in L_cの証明であるかどうかを検証する
p1, p2はそれぞれPによる証明
3-2. Structure
Compiler C
Verifier V
Turing Machine M
Security Parameter k