認証プロトコル - 暗号理論教室

---

認証プロトコルとその安全性定義

認証プロトコルとは効率的な確率的アルゴリズムの3つ組(K, P, V)である：

• (pk, sk) ← K(1^k)
• 0/1 ← (P(sk), V(pk))　
• ※ 0/1 は検証者Vが証明者Pを拒否したか受理したかを示す

完全性(completeness)条件として、

• Pr[ (pk, sk) ← Gen(1^k) : (P(sk), V(pk)) = 1 ] = 1

を要求する。

IMP-PA

認証プロトコルID=(K, P, V)とそれに対する攻撃者A=(A₁, A₂)について
以下の試行を定義する:

試行 PA_ID,A(k):

• (pk, sk) ← K(1ⁿ)
• st ← A₁^O(pk)
  • O : 問い合わせがあったら、プロトコル(P(sk), V(pk))を実行し、そのトランスクリプトを返す。
• d ← (A₂(st), V(pk))
• return d =^? 1

定義(IMP-PA)
認証プロトコルID=(K, P, V)が受動的攻撃に対し安全(IMP-PA)であるとは、
任意の効率的な攻撃者A=(A₁, A₂)に対し、その成功確率

• Pr[ PA_ID,A(k) = 1 ]

が（kについて）ネグリジブルであることをいう。

IMP-AA

認証プロトコルID=(K, P, V)とそれに対する攻撃者A=(A₁, A₂)について
以下の試行を定義する:

試行 AA_ID,A(k):

• (pk, sk) ← K(1ⁿ)
• st ← (P(sk), A₁(pk))
• d ← (A₂(st), V(pk))
• return d =^? 1

定義(IMP-AA)
認証プロトコルID=(K, P, V)が能動的攻撃に対し安全(IMP-AA)であるとは、
任意の効率的な攻撃者A=(A₁, A₂)に対し、その成功確率

• Pr[ AA_ID,A(k) = 1 ]

が（kについて）ネグリジブルであることをいう。

IMP-CA

認証プロトコルID=(K, P, V)とそれに対する攻撃者A=(A₁, A₂)について
以下の試行を定義する:

試行 CA_ID,A(k):

• (pk, sk) ← K(1ⁿ)
• st ← (P(sk)|P(sk)|・・・|P(sk), A₁(pk))
  • A₁はすきなだけ多くの証明者クローンP(sk)を呼び出せる。
  • それらの複数の証明者クローンP(sk)とのメッセージのやり取りに関し、A₁は任意のスケジューリングを用いてよい。
• d ← (A₂(st), V(pk))
• return d =^? 1

定義(IMP-CA)
認証プロトコルID=(K, P, V)がコンカレント攻撃に対し安全(IMP-CA)であるとは、
任意の効率的な攻撃者A=(A₁, A₂)に対し、その成功確率

• Pr[ CA_ID,A(k) = 1 ]

が（kについて）ネグリジブルであることをいう。

注意
以上のIMP-PA, IMP-AA, IMP-CAはいずれも攻撃を

• 「学習段階」と
• 「なりすまし段階」

の2段階で定義。中間者攻撃に対する安全性は関知せず。

安全な認証プロトコルの構成

チャレンジレスポンス型プロトコル

構成(チャレンジレスポンス)
プロトコル (K, P, V):

• [部品] : Σ=(GenSig, Sig, Vfy) : 署名スキーム
• [鍵生成 K] : 1^kを入力として、
  • (vk, sk) ← GenSig(1^k)
  • pk = vk, sk = sk.
• [証明者Pの入力] sk
• [検証者Vの入力] pk
• [プロトコル]　 ※ チャレンジ (r), レスポンス (y).
  • V → P : r ← {0,1}^k, rを送る。　　
  • P → V : y ← Sig(sk, r), yを送る。
• [検証者Vの出力] Vfy(vk, r, y) ≡^? 1.

定理(チャレンジレスポンス)
署名スキームΣが適応的選択文書攻撃において存在的偽造不可能ならば、
構成(チャレンジレスポンス)はコンカレント攻撃に対し安全である。

注意
構成(チャレンジレスポンス)は中間者攻撃に脆弱。

ゼロ知識証明型プロトコル

キャノニカルプロトコルとリセット補題

構成(キャノニカルプロトコル)
キャノニカルプロトコルID = (K, P, V = (ChSet,DEC)):

• [鍵生成] (pk, sk) ← K
• [証明者Pの入力] (sk, R)
• [検証者Vの入力] pk
• [プロトコル] 　※ (CMT), (CH), (RSP).
  • P → V : st = (sk, R), (CMT, st) = P(ε; st), CMTを送る。
  • V → P : CH ← ChSet_pk, CHを送る。
  • P → V : (RSP, st) = P(CH; st), RSPを送る。
• [検証者Vの出力] d = DEC_pk(CMT, CH, RSP).

補題(Reset) [BP03]
キャノニカルプロトコル ID = (K, P, V = (ChSet,DEC)) と任意の証明者Qについて、
2つのイベントACCとRESを定義する：

• ACC(pk,sk) :
  • 『 R ← ランダムテープ, st = (sk, R),
  • (CMT, st) = Q(ε; st), CH ← ChSet_pk, (RSP, st) = Q(CH; st)　：
    • DEC_pk(CMT, CH, RSP) = 1 』
• RES(pk,sk) :
  • 『 R ← ランダムテープ, st = (sk, R),
  • (CMT, st) = Q(ε; st),
  • CH₁ ← ChSet_pk, (RSP₁, -) = Q(CH₁; st), d₁ = DEC_pk(CMT, CH₁, RSP₁),
  • CH₂ ← ChSet_pk, (RSP₂, -) = Q(CH₂; st), d₂ = DEC_pk(CMT, CH₂, RSP₂)　：
    • d₁ = 1 ∧ d₂ = 1 ∧ CH₁ ≠ CH₂ 』

このとき、任意の(pk, sk)について、

• Pr[ACC(pk, sk)] ≦ |ChSet_pk|^-1 + Pr[RES(pk, sk)]^1/2

が成り立つ。

証明

GQプロトコル

構成(GQプロトコル)
GQプロトコル(K, P, V):

• [鍵生成 K] : 1^kを入力として、
  • (N, e, d) ← primeGenRSA(1^k)　 ※ eは奇素数.
  • x ← Z_N*, X = x^e mod N
  • pk = (N, e, X), sk = (N, e, x).
• [証明者Pの入力] sk = (N, e, x)
• [検証者Vの入力] pk = (N, e, X)
• [プロトコル]　 ※ コミットメント (Y), チャレンジ (c), レスポンス (z).
  • P → V : y ← Z_N*, Y = y^e mod N, Yを送る。
  • V → P : c ← {0,1}^l, cを送る。　　※ 2^l < e （ とくに gcd(c, e) = 1 ）.
  • P → V : z = y x^c mod N, zを送る。
• [検証者Vの出力] z^e ≡^? YX^c (mod N).

定理(GQ1) [GQ 88]
チャレンジ長lがスーパーログ（すなわち、2^l >> poly(l) ）で
primeGenRSAに対しRSA仮定が成り立つならば、
GQプロトコルは受動的攻撃に対し安全である。

証明

RSAパラメータ生成アルゴリズムGenRSAについて、
以下の試行OneMoreRSAを定義する。

試行 OneMoreRSA_GenRSA,A(k):

• (N, e, d) ← GenRSA(1^k)
• (N, e)を入力としてAを起動する：
  • Aが逆変換オラクルに問い合わせYを発したら、
    • Y^d mod N を返す。
  • Aが挑戦オラクルに（i番目の）問い合わせを発したら、
    • W_i ← Z_N* を返す。
• Aが (w₁,...,w_n) を出力して停止したら、
  • w_i^e ≡ W_i 　(i = 1..n) ∧　逆変換オラクルへの質問回数が n より小さいならば、
  • ※ すなわち、AがワンモアRSA問題を解いたならば、
    • 1を出力。
  • そうでないなら、0を出力。

定義(OMRSA)
RSAパラメータ生成アルゴリズムGenRSAがワンモアRSA仮定をみたすとは、
どのような効率的な攻撃者Aに対しも、

• Pr[OneMoreRSA_GenRSA,A(k) = 1]

が（kについて）ネグリジブルであることをいう。

定理(GQ2) [BP 03]
チャレンジ長lがスーパーログで
primeGenRSAに対しワンモアRSA仮定が成り立つならば、
GQプロトコルはコンカレント攻撃に対し安全である。

証明

シュノアプロトコル

構成(シュノアプロトコル)
シュノアプロトコル(K, P, V):

• [鍵生成 K] : 1^kを入力として、
  • (q, g) ← GenG(1^k)　
  • x ← Z_q, X = g^x
  • pk = (q, g, X), sk = (q, g, x).
• [証明者Pの入力] sk = (q, g, x)
• [検証者Vの入力] pk = (q, g, X)
• [プロトコル]　 ※ コミットメント (Y), チャレンジ (c), レスポンス (z).
  • P → V : y ← Z_q, Y = g^y, Yを送る。
  • V → P : c ← {0,1}^l,　cを送る。　 ※ 2^l < q.
  • P → V : z = y + c x mod q,　zを送る。
• [検証者Vの出力] g^z =^? YX^c.

定理(Schnorr1) [Schnorr 91]
チャレンジ長lがスーパーログで
GenGに対し離散対数仮定が成り立つならば、
シュノアプロトコルは受動的攻撃に対し安全である。

群生成アルゴリズムGenGについて、以下の試行OneMoreDLを定義する。

試行 OneMoreDL_GenG,A(k):

• (q, g) ← GenG(1^k)
• (q, g)を入力としてAを起動する：
  • Aが逆変換オラクルに問い合わせYを発したら、
    • Y = g^y となる y を返す。
  • Aが挑戦オラクルに（i番目の）問い合わせを発したら、
    • W_i ← <g> を返す。
• Aが (w₁,...,w_n) を出力して停止したら、
  • g^w_i = W_i （i = 1..n） かつ逆変換オラクルへの質問回数が n より小さいならば、
  • ※ すなわち、Aがワンモア離散対数問題を解いたならば、
    • 1を出力。
  • そうでないなら、0を出力。

定義(OMDL)
群生成アルゴリズムGenGがワンモア離散対数仮定をみたすとは、
どのような効率的な攻撃者Aに対しも、確率

• Pr[OneMoreDL_GenG,A(k) = 1]

が（kについて）ネグリジブルであることをいう。

定理(Schonorr2) [BP 03]
チャレンジ長lがスーパーログで
GenGに対しワンモア離散対数仮定が成り立つならば、
シュノア認証プロトコルはコンカレント攻撃に対し安全である。

岡本プロトコル

構成 (岡本プロトコル)
岡本プロトコル(K, P, V):

• [鍵生成 K] : 1ⁿを入力として、
  • (q, g) ← GenG(1ⁿ),　 g₁, g₂ ← <g>
  • x₁, x₂ ← Z_q, X = g₁^x1g₂^x2
  • pk = (q, g₁, g₂, X), sk = (q, g₁, g₂, x₁, x₂).
• [証明者Pの入力] sk = (q, g₁, g₂, x₁, x₂)
• [検証者Vの入力] pk = (q, g₁, g₂, X)
• [プロトコル]　 ※ コミットメント (Y), チャレンジ (c), レスポンス (z₁, z₂).
  • P → V : y₁, y₂ ← Z_q, Y = g₁^y1g₂^y2, Yを送る。
  • V → P : c ← {0,1}^l,　cを送る。　 ※ 2^l < q.
  • P → V : z₁ = y₁ + c x₁ mod q, 　z₂ = y₂ + c x₂ mod q,　(z₁, z₂)を送る。
• [検証者Vの出力] g₁^z1g₂^z2 =^? YX^c.

注意

• 岡本プロトコルでは、公開鍵Xは秘密鍵x₁, x₂を一意に定めない。無数（q個）にある。
• 任意のcについて、オネストなトランスクリプト(Y), (c), (z₁, z₂)はそれら秘密鍵x₁, x₂の取り方によらない。

実際、任意のcについて、オネストなトランスクリプト(Y), (c), (z₁, z₂)は検証式

• g₁^z1g₂^z2 =^? YX^c

をみたす(Y), (z₁, z₂)上一様に分布。
（z₁, Yを一様ランダムに選ぶとz₂が一意に定まる。）

定理(Okamoto) [Okamoto 92]
チャレンジ長lがスーパーログで
GenGに対し離散対数仮定が成り立つならば、
岡本プロトコルはコンカレント攻撃に対し安全である。

証明

署名スキームへの変換

フィアット・シャミア変換

定義(LongCMT)
キャノニカルプロトコルID = (K, P, V = (ChSet,DEC))について、
そのコミットメント長が十分長いとは、任意のCMTについて、確率

• Pr[ CMT' ← P(sk) 　:　 CMT = CMT']

がネグリジブルであることをいう。

構成(FS変換)
[部品]

• キャノニカルプロトコル ID = (K, P, V = (ChSet,DEC))
• ハッシュ関数 H : {0,1}* → ChSet

[フィアット・シャミア変換] FS_H(ID) = (Gen, Sgn, Vfy):

• Gen(1ⁿ) :
  • (pk, sk) ← K(1ⁿ),　return vk=pk, sk=sk.
• Sgn(sk, m) :
  • (CMT, st) ← P(sk),　CH = H(CMT, m),　(RSP, -) ← P(CH, st)
  • return σ=(CMT, RSP).
• Vfy(vk, m, σ=(CMT, RSP)) :
  • CH = H(CMT, m)
  • return DEC_pk(CMT, CH, RSP).

定理(FS変換)
キャノニカルプロトコルIDが受動的攻撃に対し安全で、そのコミットメント長が十分長いならば、
それをフィアット・シャミア変換して得られる署名スキーム FS_H(ID) は、
ハッシュ関数Hに関するランダムオラクルモデルのもとで、
適応的選択文書攻撃に対し存在的偽造不可能である。

証明

フィアット・シャミア変換2

検証者の判定アルゴリズムDECが、ある確定的な関数D(・,・)について、

• DEC(CMT, CH, RSP) = 1 ⇔ CMT = D(CH, RSP)

とかけるとき、フィアット・シャミア変換は以下の形で使われることが多い。

構成(FS変換2)
[部品]

• キャノニカルプロトコル ID = (K, P, V = (ChSet,DEC))
  • ただし、ある確定的な関数D(・,・)について、
    • DEC(CMT, CH, RSP) = 1 ⇔ CMT = D(CH, RSP).
• ハッシュ関数 H : {0,1}* → ChSet

[フィアット・シャミア変換2] FS2_H(ID) = (Gen, Sgn, Vfy):

• Gen(1ⁿ) :
  • (pk, sk) ← K(1ⁿ),　return vk=pk, sk=sk.
• Sgn(sk, m) :
  • (CMT, st) ← P(sk),　CH = H(CMT, m),　(RSP, -) ← P(CH, st)
  • return σ=(CH, RSP).
• Vfy(vk, m, σ=(CH, RSP)) :
  • CMT' = D(CH,RSP)
  • return CH =^? H(CMT', m).

定理(FS変換2)
キャノニカルプロトコルIDが受動的攻撃に対し安全で、そのコミットメント長が十分長いならば、
それをフィアット・シャミア変換2して得られる署名スキーム FS2_H(ID) は、
ハッシュ関数Hに関するランダムオラクルモデルのもとで、
適応的選択文書攻撃に対し存在的偽造不可能である。

シュノア署名

シュノアプロトコルにフィアット・シャミア変換2を適用して、シュノア署名を得る。

構成(シュノア署名)
[部品]

• 群生成アルゴリズム GenG
• ハッシュ関数 H : {0,1}* → {0,1}^l

[スキーム]

• Gen(1^k) :
  • (q, g) ← GenG(1^k)　
  • x ← Z_q, X = g^x
  • vk = (q, g, X), sk = (q, g, x).
• Sign(sk = (q,g,x), m) :
  • y ← Z_q, Y = g^y
  • c = H(m, Y),　z = y + c x mod q
  • return σ=(c,z).
• Verify(vk = (q,g,X), m, σ = (c, z)) :
  • Y = g^zX^-c
  • return c =^? H(m, Y).

定理(Schnorr1)と定理(FS変換2)より、

定理(シュノア署名)
ハッシュ値の長さlがスーパーログで、GenGに対し離散対数仮定が成り立つならば、
ハッシュ関数Hに関するランダムオラクルモデルのもとで、
シュノア署名は適応的選択文書攻撃に対し存在的偽造不可能である。

上へ

---