定理(LinearTBE)の証明 - 暗号理論教室

定理(LinearTBE)の証明のアイデア

攻撃者Aが構成(LinearTBE)のタグt*、公開鍵

• pk = (q, g₁, g₂, z, u₁, u₂)

に関する暗号文

• c_tbe* = (c*₁=g₁^r1, c*₂=g₂^r2, d₁ = z^t*r1 u₁^r1, d₂ = z^t*r2 u₂^r2, e = m z^r1+r2)

を入手したとする。

判定線形仮定より、上のz^r1+r2は群G上のランダムな要素と思ってよい。
よって、c_tbe* はmの情報を漏らさない。

• 厳密には、d₁やd₂にもr₁, r₂が含まれるので、この議論は不十分。

攻撃者Aが構成(LinearTEB)の妥当な暗号文 c_tbe = (c₁, c₂, d₁, d₂, e) を生成できたとする。

• 正しいd₁, d₂を計算したのだから、Aはc_i=g_i^riとなるr₁, r₂を知っているだろう。
• そうならば、m = e/z^r1+r2なので、

攻撃者Aは最初からmを知っていることとなり、復号オラクルは役に立たないはず。

定理(LinearTBE)の証明

構成(LinearTBE)に対する任意のタグ選択攻撃者をAとする。Aを用いて判定線形仮定における識別者Dを構成する：

識別者D: (g₁, g₂, z, g₁^r1, g₂^r2, w)を入力として、

• ※ Dはwについて、w=z^r1+r2 なのか、それとも独立なランダム要素なのか、識別したい。
• 1ⁿを入力としてタグ選択攻撃者Aを起動し、ターゲットタグt*を受け取る。
• γ₁,γ₂ ← Z_q, u₁ = z^-t*g₁^γ1, u₂ = z^-t*g₂^γ2
• pk = (g₁, g₂, z, u₁, u₂)をAに送る。
• ※ タグt*についてだけは、u₁z^t*, u₂z^t*のg₁,g₂に関する離散対数γ₁, γ₂がわかる！
• ※ x₁ := log_g1(z), x₂ := log_g2(z), y₁ := log_g1(u₁) = -t*x₁ + γ₁, y₂ := log_g2(u₂) = -t*x₂ + γ₂.
• Aからチャレンジクエリ(m₀,m₁)を受け取ったら、
  • b ← {0,1} をランダムに選択し、
  • c_tbe* = (c₁*=g₁^r1, c₂*=g₂^r2, d₁* = (g₁^r1)^γ1, d₂* = (g₂^r2)^γ2, e* = m_bw)を返す。
  • ※ d_i* = (g_i^ri)^γi = (u_iz^t*)^ri.
  • ※ よって、w = z^r1+r2のとき、c_tbe*はm_bの正当な暗号文。
• Aからタグ t (≠t*) について復号クエリ c_tbe = (c₁, c₂, d₁, d₂, e) を受け取ったら、
  • Pv_tbe(pk, t, c_tbe) =^? 0 : ランダムメッセージを返す。
  • else k = ( (d₁ d₂)/(c₁^γ1 c₂^γ2) )^1/(t-t*), m = e/k を返す。
    • ※ d_i = c_i^tx_i+y_i = c_i^{tx_i+(-t*x_i+γ_i)} = (c_i^x_i)^t-t* c_i^γ_i.
    • ※ ∴ (d_i/c_i^γ_i)^1/(t-t*) = c_i^x_i.
• Aが出力b' で終了したら、b =^? b' を出力して終了。

識別者Dの解析：

• w = z^r1+r2のとき、Pr[D=1] = Pr[Aが成功].
• wがランダムのとき、Pr[D=1] = 1/2.

よって、Dの識別利得 = Aの識別利得 ≦ ネグリジブル(n).
Q.E.D.

上へ

---