HMQV - 暗号理論教室

---

XCR署名

構成(4m-Schnorr)
(q, g) ← GenG(1^k)
各パーティBは鍵ペア(B, b)をもつ。(B = g^b)

• 検証者A: Bを入力として、
  • x ← Z_q, X = g^x、XをBに送信。
• 証明者B: (B, b)を入力として、Xを受け取ると、
  • y ← Z_q, Y = g^y, YをAに送信。
• 検証者A: Yを受け取ると、
  • e ← Z_q, eをBに送信。
• 証明者B: eを受け取ると、
  • s = y + e b mod q, S = X^s, SをBに送信。
• 検証者A: Sを受け取ると、
  • S =^? (Y B^e)^x を出力。

構成(XCR署名)
(q, g) ← GenG(1^k)
各パーティBは鍵ペア(B, b)をもつ。(B = g^b)
G : {0,1}* → {0,1}^l : ハッシュ関数（l = |q|/2, ハーフサイズ）

• 検証者A: (m, B)を入力として、
  • x ← Z_q, X = g^x、(m, X)をBに送信。
• 署名者B: (B, b)を入力として、(m, X)を受け取ると、
  • y ← Z_q, Y = g^y, σ = X^{y + G(Y,m) b}
  • (Y,σ)をAに送信。
• 検証者A: (Y,σ)を受け取ると、
  • Y ≠ ⊥ ∧ (Y B^G(Y,m))^x =^? σ : valid を出力。

Experiment ForgeXCR_F(k):

• B, X₀(=g^x0) ← <g>
• (B, X₀)を入力として、偽造者Fを起動する：
  • Fが署名オラクルBに m を問い合わせたら、
    • y ← Z_q, Y = g^y.
    • Y を答え、Fから X を受け取る。
    • σ = X^{y + G(Y,m) b} を返答する。
• Fが (Y₀, m₀, σ₀) を出力して停止したら、以下がともに成り立つとき（のみ）1を出力：
  • Y₀ ≠ ⊥ ∧ (Y₀ B^G(Y₀,m₀))^x0 =^? σ₀
  • (Y₀,m₀) はオラクルBの返答に含まれない。

定義(XCR署名の安全性)
XCR署名が安全であるとは、どのようなPPT偽造者Fについても Pr[ ForgeXCR_F(k) ] が（kについて）ネグリジブルであることをいう。

定理(XCR署名)
GenGに対する計算DH仮定が成り立つならば、Gについてのランダムオラクルモデルのもとで、
XCR署名は安全である。

証明

双対XCR署名

構成(双対XCR署名)
(q, g) ← GenG(1^k)
各パーティAは鍵ペア(A, a)をもつ。(A = g^a)
G : {0,1}* → {0,1}^l : ハッシュ関数（l = |q|/2, ハーフサイズ）

• A: (A, a, m₁)を入力として、
  • x ← Z_q, X = g^x、(X, m₁)をBに送信。
• B: (B, b, m₂)を入力として、
  • y ← Z_q, Y = g^y, (Y, m₂)をAに送信。
• A: (Y, m₂)を受け取ると、
  • d = G(X, m₂), e = G(Y, m₁)
  • (Y B^e)^{x + d a}を出力。
• B: (X, m₁)を受け取ると、
  • d = G(X, m₂), e = G(Y, m₁)
  • (X A^d)^{y + e b}を出力。

Experiment ForgeDXCR_F(k):

• B = g^b, X₀ = g^x0 ← <g>
• (B, X₀)を入力として、(A(=g^a), a)を補助入力として、偽造者Fを起動する：
  • Fが署名オラクルBに (m, m') を問い合わせたら、
    • y ← Z_q, Y = g^y.
    • Y を答え、Fから X を受け取る。
    • d = G(X, m'), e = G(Y, m)
    • σ = (X A^d)^{y + e b} を返答する。
• Fが (Y₀, m₀, m₁, σ) を出力して停止したら、以下がともに成り立つとき（のみ）1を出力：
  • d = G(X₀, m₁), e = G(Y₀, m₀)について、
    • Y₀ ≠ ⊥ ∧ (Y₀ B^e)^{x₀ + a d} =^? σ
  • (Y₀,m₀) はオラクルBの返答に含まれない。

定義(双対XCR署名の安全性)
双対XCR署名が安全であるとは、どのようなPPT偽造者Fについても Pr[ ForgeDXCR_F(k) ] が（kについて）ネグリジブルであることをいう。

定理(双対XCR署名)
GenGに対する計算DH仮定が成り立つならば、Gについてのランダムオラクルモデルのもとで、
双対XCR署名は安全である。ただし、A ≠ B とする。

証明

鍵共有プロトコルHMQV

構成(HMQV)
(q, g) ← GenG(1^k)
各パーティAは鍵ペア(A, a)をもつ。(A = g^a)
G : {0,1}* → {0,1}^l : ハッシュ関数（l = |q|/2, ハーフサイズ）
H : {0,1}* → {0,1}^k : ハッシュ関数

• A: (A, B)を入力として、
  • x ← Z_q, X = g^x、(A, B, X)をBに送信。
• B: (A, B, X)を受け取ると、
  • y ← Z_q, Y = g^y、(B, A, Y)をAに送信。
  • d = G(X, B), e = G(Y, A)
    • (※ 自身で生成した群要素Yとピアの公開鍵AとをセットにしてハッシュGに投入する。）
  • σ_B = (X A^d)^{y + e b}, K = H(σ_B)
    • (※ σ_Bはメッセージ(B,A)のBによる双対XCR署名。）
  • (B, A, (B,A,Y,X), K)を出力。　（※ (B,A,Y,X)はセッション識別子）
• A: (B, A, Y)を受け取ると、
  • e = G(Y, A), d = G(X, B)
  • σ_A = (Y B^e)^{x + d a}, K = H(σ_A)
    • (※ σ_Aはメッセージ(A,B)のAによる双対XCR署名。）
  • (A, B, (A,B,X,Y), K)を出力。

定理(HMQV)
GenGに対する計算DH仮定が成り立つならば、G,Hについてのランダムオラクルモデルのもとで、
HMQVプロトコルはCanetti-KrawczykモデルでフォーワードなしのSK安全性をもつ。

証明

上へ

---