ストレージ証明 - 暗号理論教室

---

ストレージ証明の機能

ストレージ証明とは、証明者（サーバ）P が、検証者（クライアント）V から預ったデータ M を（捨てたり壊したりしないで）完全に保持していることを証明するプロトコル。

ストレージ証明においては、データMは非常に大きなサイズとなることを想定している。証明サイズを、データMのサイズに比べ、なるべく小さくすることがポイント。

（ストレージ証明は、その証明サイズがデータサイズと同程度でよいのなら、通常のデジタル署名やMACで容易に実現される。）

ストレージ証明 (Kg, St, V, P)：

• (pk, sk) ← Kg()
• (t, M*) ← St(sk, M) 　　　※ a file-storing algorithm
• 0/1 ← (V(pk, t, sk), P(pk, t, M*))　

完全性(completeness)

∀(pk, sk) ← Kg(), 　∀M ∈ {0,1}*, 　∀(t, M*) ← St(sk, M)

• (V(pk, t, sk), P(pk, t, M*)) = 1.

ストレージ証明の安全性

セットアップゲーム

• (pk, sk) ← Kg()
• 公開鍵pkを入力として攻撃者Aを起動：
  • AがファイルMのストアを要求したら、
    • (t, M*) ← St(sk, M) を計算し、(t, M*)をAに返す。
  • Aが、あるファイルMをストアさせる際に得たタグtについて、そのストレージ証明の実行を要求したら、
    • V(pk, t, sk)にしたがって相手をする。
• Aは(t,P')を出力して停止する。 ただし、
  • t : AがあるファイルMをストアさせる際に得たタグ
  • P' : 証明者アルゴリズム。

P' がε-許容可能 であるとは、

• Pr[ (V(pk,t,sk), P') = 1 ] ≧　ε.

定義 (ε-健全)

ストレージ証明 (Kg, St, V, P)がε-健全であるとは、

• あるエクストラクタ Extr が存在し、
• 任意の攻撃者Aについて、
• Aがセットアップゲームの結果、あるファイルMについて、ε-許容可能である証明者P'を出力したならば、
  • ネグリジブルな確率の例外を除いて、ExtrがP'を利用してMを復元できること、すなわち
  • M = Extr(pk, sk, t, P')

であることを云う。

ストレージ証明の構成

私的検証可能ストレージ証明 Priv = (Kg, St, V, P)

部品

• ρ-erasure code（割合ρ以上の符号語から全体ファイルをデコード可能な線形符号）C
• 対象鍵暗号 Enc_kenc
• メッセージ認証子 MAC_kmac
• 擬似ランダム関数 f : {0,1}* x K_prf　→　Z_p

パラメータ

• B ⊆ Z_p : チャレンジ集合
• l : ランダムインデックス集合の大きさ

Kg() :

• k_enc ← K_enc
• k_mac ← K_mac
• return sk = (k_enc, k_mac).

St(sk, M) :

• { m_i }_1≦i≦n = M' ← C(M)　　　　　※ 以下、各符号語m_iは必要な場合はZ_pの要素と考える。
• k_prf ← K_prf, 　 α ← Z_p
• t₀ = n || Enc_kenc(k_prf || α), 　t = t₀ || MAC_kmac(t₀).
• i ∈ [1..n] : σ_i ← f_kprf(i) + α m_i　　　　　※ σ_iはm_iのMAC
• M* = M' ∪ { σ_i }_1≦i≦n
• return (t, M*).

(V(pk, t, sk), P(pk, t, M*)) :

• [V → P] :
  • (k_enc, k_mac) = sk,　t₀ || mac = t
  • k_mac を用いて、macの正しさを確認
  • k_enc を用いて、t₀から、k_prf とαを復号。
  • l個のランダムインデックス I（⊆ [1..n]）を選択、i ∈ I : v_i ← B
  • Send Q = {(i, v_i)}_{i ∈ I}.
• [P → V] :
  • { m_i } ∪ { σ_i } = M*
  • μ　←　Σ_{(i, vi)∈Q}v_i m_i
  • σ　←　Σ_{(i, vi)∈Q}v_iσ_i
  • Send (σ, μ).
• [V] :
  • return σ 　=^? 　Σ_{(i, vi)∈Q}v_if_kprf(i) + αμ.

スキームの観察

構成について

• 証明者Pはファイルの各ブロックm_iのMACであるσ_iを保持。
• 検証者Vは、ランダムに選択したl個のブロックのランダムな線形結合μ=Σ_{(i, vi)∈Q}v_i m_iのMACを要求する。
• 証明者PはチャレンジμのMACとして、各ブロックのMACの線形結合であるσ=Σ_{(i, vi)∈Q}v_iσ_iを答える。
  • 利用しているMACスキームの準同型性のおかげで、MACの線形結合σが意味を持つ。

安全性について

与えられたチャレンジQ = {(i, v_i)}_{i ∈ I}について、
検証式の係数であるf_kprf(i)やαは検証者にしか見えない乱数だから、

• σ 　=　 ^? Σ_{(i, vi)∈Q}v_if_kprf(i) + αμ

を満たす (σ, μ) を答えるためには、証明者は、インデックス集合Iに属するiについて、{m_i}も{σ_i}も捨てられない。

ところが、Q = {(i, v_i)}_{i ∈ I} においてインデックス集合Iはランダムに選ばれるから、証明者は結局どの{m_i}も{σ_i}も捨てられない。

定理 (私的検証可能ストレージ証明 Priv)

もしも

• MAC が偽造不可能で、
• ENC が意味論的安全で、
• f が擬似ランダム関数である

ならば、

• ω = 1/#B + (ρn)^l/(n-l+1)^l

とするとき、

• ε ≧ ω かつ ε-ωが非無視可能であるようなεについて、

私的検証ストレージ証明 Priv はε-健全と言える。

証明について

上に見たように、検証者Vを説得するには、正しい{m_i}について

• μ　←　Σ_{(i, vi)∈Q}v_i m_i

と計算するしかない。

ランダムに選ばれたQについて、O( n/(ε-ω) )回、P'にそのようなμを答えさせれば、線形代数（行縮約）を用いて、{m_i}の割合ρを復元できる。

公的検証可能ストレージ証明 Pub = (Kg, St, V, P)

部品

• ρ-erasure code（割合ρ以上の符号語から全体ファイルをデコード可能な線形符号）C
• 双線形写像 e : G x G → G_T, 　 G = <g> : 位数p
• ハッシュ関数 H : {0,1}* → G
• 署名スキーム (Skg, SSig, Svfy)

パラメータ

• B ⊆ Z_p : チャレンジ集合
• l : ランダムインデックス集合の大きさ

Kg() :

• (spk, ssk) ← SKg
• α ← Z_p,　 v = g^α
• return sk = (α, ssk), pk = (v, spk).

St(sk, M) :

• { m_i }_1≦i≦n = M' ← C(M)　　　　※ 以下、各符号語m_iは必要な場合はZ_pの要素と考える。
• (α, ssk) = sk
• name ← Z_p, 　u ← G
• t₀ = name||n||u, 　t = t₀||SSig_ssk(t₀)
• i ∈ [1..n] : σ_i ← ( H(name||i) u^m_i )^α 　　　※ σ_iはm_iの署名
• M* = M' ∪ { σ_i }_1≦i≦n
• return (t, M*).

(V(pk=(v,spk), t, sk), P(pk, t, M*)) :

• [V → P] :
  • spk を用いてタグtの正しさを確認して後、 name||n||u = t.
  • l個のランダムインデックス I（⊆ [1..n]）を選択、i ∈ I : v_i ← B
  • Send Q = {(i, v_i)}_{i ∈ I}.
• [P → V] :
  • { m_i } ∪ { σ_i } = M*
  • μ　←　Σ_{(i, vi)∈Q}v_i m_i
  • σ　←　Π_{(i, vi)∈Q}σ_i^v_i
  • Send (σ, μ).
• [V] :
  • return e(σ,g) 　=^? 　e(Π_{(i, vi)∈Q}H(name||i)^v_i u^μ, v).

スキームの観察

構成について

• 証明者Pはファイルの各ブロックm_iの署名であるσ_iを保持
• 検証者Vは、ランダムに選択したl個のブロックのランダムな線形結合μ=Σ_{(i, vi)∈Q}v_i m_iの署名を要求する。
• 証明者Pはチャレンジμの署名として、各ブロックの署名の（乗法的）線形結合であるσ=Π_{(i, vi)∈Q}σ_i^v_iを答える。
  • 利用している署名スキームの準同型性のおかげで、署名の線形結合σが意味を持つ。

安全性について

与えられたチャレンジQ = {(i, v_i)}_{i ∈ I}について、証明者*は、あるμについて、

• σ　=　( Π_{(i, vi)∈Q} H(name||i)^v_i u^μ )^α

を答えなければならない。（双線形写像の非退化性）

公開情報g, v=g^αから、このようなσ=w^αを作り出すのは、ハッシュ関数H(・)の操作不可能なランダム性を仮定すると困難。ここで、

• w 　= 　Π_{(i, vi)∈Q} H(name||i)^v_i u^μ の g に関する離散対数がわからないことが効く。

定理 (公的検証可能ストレージ証明 Pub)

もしも

• 署名スキームが存在的偽造不可能で、
• 群Gについて計算的ディフィー・ヘルマン仮定が成り立つ

ならば、

• ω = 1/#B + (ρn)^l/(n-l+1)^l

とするとき、

• ε ≧ ω かつ ε-ωが非無視可能であるようなεについて、

ハッシュ関数Hに関するランダムオラクルモデルのもとで、公的検証ストレージ証明 Pub はε-健全と言える。

証明について

上に見たように、検証者Vを説得するには、正しい{m_i}について

• μ　←　Σ_{(i, vi)∈Q}v_i m_i

と計算するしかない。

ランダムに選ばれたQについて、O( n/(ε-ω) )回、P'にそのようなμを答えさせれば、線形代数（行縮約）を用いて、{m_i}の割合ρを復元できる。

文献

• [SW 08]
• [AKK 09]
• [JK07]
• [BJO 09]

上へ

---