デジタル署名とその安全性定義


デジタル署名とは効率的な確率的アルゴリズムの3つ組(Gen, Sign, Verify)である:
  • (vk, sk) ← Gen(1n)
  • σ ← Sign(sk, m)
  • 0/1 ← Verify(vk, m, σ).

完全性(completeness)条件として、メッセージ空間Mに含まれる全てのメッセージmについて
  • Pr[ (vk, sk) ← Gen(1n), σ ← Sign(sk, m) : Verify(vk,m,σ) = 1 ] = 1
を要求する。

EUF-CMA

デジタル署名Ω=(Gen, Sign, Verify)とそれに対する攻撃者Fについて
以下の試行を定義する:

試行 CMAΩ,F(n):
  • (vk, sk) ← Gen(1n)
  • (m*, σ*) ← FSign(sk,・)(vk)
  • return m* ≠ mi (for i = 1,...,t) ∧ Verify(vk, m*, σ*) = 1
    • ただし、Fが署名オラクルSign(sk,・)へ問い合わせたメッセージを{m1,...,mt}とする。

定義(EUF-CMA)
デジタル署名Ω=(Gen,Sign,Verify)が
選択文書攻撃において存在的偽造不可(EUF-CMA)であるとは、
任意の効率的な偽造者Fに対し、その成功確率
  • Pr[ CMAΩ,F(n) = 1 ]
が(nについて)ネグリジブルであることをいう。

  • 攻撃者Fの署名オラクルへの問い合わせ回数を高々1回に限定したときに、
存在的偽造不可(sEUF-CMA)である署名をワンタイム署名という。

sEUF-CMA

デジタル署名Ω=(Gen, Sign, Verify)とそれに対する攻撃者Fについて
以下の試行を定義する:

試行 sCMAΩ,F(n):
  • (vk, sk) ← Gen(1n)
  • (m*, σ*) ← FSign(sk,・)(vk)
  • return (m*,σ*) ≠ (mii) (for i = 1,...,t) ∧ Verify(vk, m*, σ*) = 1
    • ただし、Fが署名オラクルSign(sk,・)へ問い合わせたメッセージとその返答として得た署名の対を
      • {(m11),...,(mtt)}
    • とする。

定義(sEUF-CMA)
デジタル署名Ω=(Gen,Sign,Verify)が
選択文書攻撃において強い意味で存在的偽造不可(sEUF-CMA)であるとは、
任意の効率的な偽造者Fに対し、その成功確率
  • Pr[ sCMAΩ,F(n) = 1 ]
が(nについて)ネグリジブルであることをいう。

  • 攻撃者Fの署名オラクルへの問い合わせ回数を高々1回に限定したときに、
強い意味で存在的偽造不可(sEUF-CMA)である署名を強いワンタイム署名という。

EUF-NA-CMA

デジタル署名Ω=(Gen, Sign, Verify)とそれに対する攻撃者Fについて
以下の試行を定義する:

試行 NA-CMAΩ,F(n):
  • (m1,...,mt, st) ← F(1n)
  • (vk, sk) ← Gen(1n), σ1 ← Sign(sk, m1), ..., σt ← Sign(sk, mt)
  • (m*, σ*) ← F(vk, (σ1,...,σt), st)
  • return m* ≠ mi (for i = 1,...,t) ∧ Verify(vk, m*, σ*) = 1

定義(EUF-NA-CMA)
デジタル署名Ω=(Gen, Sign, Verify)が
非適応的選択文書攻撃に対し存在的偽造不可(EUF-NA-CMA)であるとは、
任意の効率的な偽造者Fに対し、その成功確率
  • Pr[ NA-CMAΩ,F(n) = 1 ]
が(nについて)ネグリジブルであることをいう。

安全なデジタル署名の構成

ジェネリックな構成

ランポート署名
構成(ランポート署名)
f : 一方向関数
l = l(n):メッセージ長(を表すnの多項式)
  • Gen(1n):
    • i ∈ [1..l]:
      • xi,0, xi,1 ← {0,1}n
      • yi,0 = f(xi,0), yi,1 = f(xi,1)
    • vk = (y1,0, y2,0, ・・・, yl,0 : y1,1, y2,1, ・・・, yl,1),
    • sk = (x1,0, x2,0, ・・・, xl,0 : x1,1, x2,1, ・・・, xl,1).
  • Sign(sk, m = m1 ・・・ml):
    • ※ m に対応する、秘密鍵の一部をダイレクトに署名とする。
    • return (x1,m1, x2,m2, ・・・, xl,ml).
  • Verify(vk, m = m1 ・・・ml, σ = x1 ・・・xl):
    • return ∧i=1..l f(xi) =? yi,mi.

定理(ランポート署名)
fが一方向関数ならば、構成(ランポート署名)は固定長メッセージの(強い)ワンタイム署名である。


Hash and Sign
構成(Hash-and-Sign)
Ω=(Gen, Sign, Verify) : 固定長(=l)メッセージの署名スキーム
Hk : {0,1}* → {0,1}l : ハッシュ関数
署名スキーム Ω' = (Gen', Sign', Verify') :
  • Gen'(1n) :
    • (vk, sk) ← Gen(1n), k ← {0,1}n
    • vk' = (vk, k), sk' = (sk, k).
  • Sign'(sk', m) :
    • return σ' ← Sign(sk, Hk(m)).
  • Verify'(vk', m, σ'):
    • return Verify(vk, Hk(m), σ').

定理(Hash-and-Sign)
Ωが固定長メッセージのEUF-CMA安全なディジタル署名(or ワンタイム署名)で、
Hが衝突困難なハッシュ関数ならば、
Ω'はEUF-CMA安全なディジタル署名(or ワンタイム署名)である。


ツリー署名
構成(ツリー署名)
Ω=(Gen, Sign, Verify) : ワンタイム署名

署名スキームΩ'=(Gen', Sign', Verify') :
※ m = m1・・・mn, i∈[0..n]について、m|i =def m1・・・mi. (ただし、m|0 := ε.)
  • Gen'(1n) :
    • (vkε, skε) ← Gen(1n)
    • return vk = vkε, sk = skε, st = skε.
  • Sign'(sk, m = m1・・・mn; st) :
  • ※ 根ノードεから葉ノードmに向かって、各ノードに署名を格納していく:
    • i∈[0..(n-1)] :
      • ※ ノード m|i に子ノードの検証鍵をオーサライズする署名を格納:
      • m|i, vkm|i,0, vkm|i,1> not∈ st :
        • (vkm|i,0, skm|i,0) ← Gen(1n)
        • (vkm|i,1, skm|i,1) ← Gen(1n)
        • σm|i ← Sign(skm|i, vkm|i,0 || vkm|i,1)
        • st = st ∪ <σm|i, vkm|i,0, vkm|i,1>
    • σm not∈ st :
      • ※ 葉ノード m にメッセージmの署名を格納:
      • σm ← Sign(skm, m), st = st ∪σm
    • return σ = <<σm|i, vkm|i,0, vkm|i,1>i=0..(n-1), σm>.
  • Verify'(vk = vkε, m, σ) :
    • ※ 根ノードεから葉ノードmに向かって、各ノードに格納された署名を検証:
    • i∈[0..(n-1)] :
      • Verify(vkm|i, vkm|i,0 || vkm|i,1, σm|i) =? 1
    • Verify(vkm, m, σm) =? 1.

定理(ツリー署名)
Ωがワンタイム署名ならば、
ツリー署名Ω'はEUF-CMA安全なディジタル署名である。


(EUF-CMA署名)
一方向関数と衝突困難なハッシュ関数が存在するならば、EUF-CMA安全なディジタル署名が存在する。

実は、
定理(EUF-CMA署名)
一方向関数が存在するならば、EUF-CMA安全なディジタル署名が存在する。
ことが知られている。

ランダムオラクルモデルにもとづく構成

フルドメインハッシュ
構成(FDH)
(G, {fi}i) : トラップドア置換
  • Gen(1n):
    • (i, ti) ← G(1n)
    • ハッシュ関数 H : {0,1}* → {0,1}n を選択。
    • vk = (i, H), sk = (ti, H).
  • Sign(sk = (ti,H), m):
    • tiを用いて、return s = fi-1(H(m)).
  • Verify(vk = (i,H), m, s):
    • return H(m) =? fi(s).

定理(FDH)
ハッシュ関数Hに対するランダムオラクルモデルにおいて、
{fi}iがトラップドア置換ならば、構成(FDH)は選択文書攻撃において存在的偽造不可である。


数論的仮定にもとづく構成

強RSA仮定に基づく構成
定義
RSAパラメータ生成アルゴリズムGenRSAが強RSA仮定をみたすとは、
任意の効率的なアルゴリズムAについて、その利得
  • Pr[ (p, q, N)← GenRSA(1k), s ← ZN*, (c, w) ← A(N, s) :
    • c > 1 かつ s ≡ wc (mod N) ]
が(kについて)ネグリジブルであることをいう。

定義
ハッシュ関数族 H = {Hk}k∈Ngcd intractable であるとは、
任意の効率的な攻撃者Aに対し、
  • Pr[ h ← Hk, (X1,...,Xn, Y) ← A(h) :
    • Y ≠ Xi (for i=1..n) かつ gcd(h(Y),Πi=1..nh(Xi)) ≠1 ]
が(kについて)ネグリジブルであることをいう。

GHR署名
構成(GHR署名) [GHR 99]
Ω = (Gen, Sign, Verify) :
  • Gen(1k):
    • (p, q, N) ← GenRSA(1k), s ← ZN*
    • h ← Hk
    • vk = (N, s, h), sk = (vk, p, q)
  • Sign(sk, m) :
    • e = h(m)
    • ※ skに含まれるp,qを用いて
    • return σ = s1/e mod N.
  • Ver(vk, m, σ) :
    • e = h(m)
    • return σe? s (mod N).

定理(GHR署名) [GHR 99]
GenRSAに対し強RSA仮定が成立し、ハッシュ関数族Hがgcd intractableならば、
構成(GHR署名)は非適応的選択文書攻撃に対し存在的偽造不可である。


強DH仮定に基づく構成
定義
位数pの双線形群 (G1, G2) における q-強DH問題 とは、
ランダムなg1∈G1, g2∈G2について、入力
  • (g1, g2, g2x, g2x^2, ... , g2x^q)
を与えられて、出力
  • (c, g11/(x+c)) with c ∈ Zp*
を求める問題である。

q-強DH問題が困難であるという仮定をq-強DH仮定という。
より定量的に、
q-強DH問題を時間t以内に確率ε以上で解くことは困難であるという仮定を
(q,t,ε)-強SDH仮定という。

ShortSignature
構成(ShortSignature) [BB 04]
(G1, G2): 位数pの双線形群
  • g1∈G1, g2∈G2 : 生成元
  • Ψ: G2 → G1 : 準同型

Ω = (Gen, Sign, Verify) :
  • Gen:
    • x ← Zp*, v = g2x
    • vk = (g1, g2, v), sk = x.
  • Sign(sk, m):  ※ m∈Zp*
    • return σ = g11/(x+m)
  • Verify(vk, m, σ):
    • return e(σ, vg2m) =? e(g1, g2)

定理(ShortSignature) [BB 04]
双線形群(G1, G2)に対し強DH仮定が成り立つならば、
構成(ShortSignature)Ωは、非適応的選択文書攻撃に対し安全である。

より精密には、
双線形群(G1, G2)に対し(q,t',ε)-強DH仮定が成り立つならば、
構成(ShortSignature)Ωは、非適応的選択文書攻撃に対し、(t,qS,ε)安全である
(すなわち、時間t以内、署名クエリ回数qS以内では、
どのような偽造者も高々εの確率でしか署名の偽造に成功しない)。
ここで、
  • t ≦ t' - O(q2), qS < q.


構成(ShortSignatureFull) [BB 04]
(G1, G2): 位数pの双線形群
  • g1∈G1, g2∈G2 : 生成元
  • Ψ: G2 → G1 : 準同型

Ω = (Gen, Sign, Verify) :
  • Gen:
    • x, y ← Zp*, u = g2x, v = g2y
    • vk = (g1, g2, u, v), sk = (x, y).
  • Sign(sk, m):  ※ m∈Zp*
    • r ← Zp*, σ = g11/(x+m+yr)
    • return (σ, r)
  • Verify(vk, m, (σ,r)):
    • return e(σ, ug2mvr) =? e(g1, g2)

定理(ShortSignatureFull) [BB 04]
双線形群(G1, G2)に対し強DH仮定が成り立つならば、
ShortSignatureFull は、適応的選択文書攻撃に対し安全である。

より精密には、
ShortSignatureが非適応的選択文書攻撃に対し(t',qS,ε')安全ならば、
ShortSignatureFullは、適応的選択文書攻撃に対し、(t,qS,ε)安全である:
  • t = t' - O(qS), ε= 2 (ε' + qS/p) (≒ 2ε').


考察
非適応的な安全性を達成するために代数的なトリックを最大限に生かし、
さらに署名に乱数性を加えることで適応的な安全性をもたらしている。

判定線形仮定に基づく構成
Waters署名
構成(Waters署名) [Waters 09]
  • Gen:
    • G : 位数pの双線形群
    • g, v, v1, v2, w, u, h ← G
    • a1, a2, b, α ← Zp
    • τ1 = v v1a1, τ2 = v v2a2
    • vk = (gb, ga1, ga2, gb a1, gb a2, τ1, τ2, τ1b, τ2b, w, u, h, e(g, g)α a1 b),
    • sk = (g, gα, gα a1, v, v1, v2).
  • Sign(sk, m) :
    • r1, r2, z1, z2, tagkZp, r = r1 + r2
    • σ1 = gα a1vr, σ2 = gv1rgz1, σ3 = (gb)-z1, σ4 = v2rgz2
    • σ5 = (gb)-z2, σ6 = gr2 b, σ7 = gr1, σK = (umwtag_kh)r1
    • return σ = (σ1, ・・・, σ7, σK, tagk).
  • Verify(vk, m, σ) :
    • s1, s2, t, tagcZp
    • C1 = (gb)s1+s2, C2 = (gb a1)s1, C3 = (ga1)s1, C4 = (gb a2)s2
    • C5 = (ga2)s2, C6 = τ1s1τ2s2, C7 = (τ1b)s12b)s2w-t
    • E1 = (umwtag_ch)t, E2 = gt
    • A1 = e(C11) e(C22)・・・e(C55)
    • A2 = e(C66) e(C77)
    • A3 = A1 / A2
    • tagc ≠ tagk :
      • A4 = (e(E17) / e(E2K))1/(tag_c - tag_k)
      • return (e(g, g)α a1 b)s2 =? A3 / A4.

定理(Waters署名) [Waters 09]
双線形群Gに対し判定線形仮定が成立するならば、
構成(Waters署名)は適応的選択文書攻撃に対し存在的偽造不可である。

EUF-NA-CMA署名からEUF-CMA署名への変換

Σプロトコル
Σプロトコルとは効率的な確率的アルゴリズムの4つ組Σ = (Gen, Com, Res, Det):
  • (pk, sk) ← Gen(1n)
  • (x, r) ← Com(pk)
  • y ← Res(sk, r, c)  (cはチャレンジ集合CHAの要素)
  • 0/1 ← Det(pk, x, c, y)

これらは、対話証明プロトコル (P,V) として以下のように用いられる:
  • [証明者Pの入力]: sk
  • [検証者Vの入力]: pk
  • [プロトコル] :  ※ (x), (c), (y).
    • P → V : (x, r) ← Com(pk), xを送る。
    • V → P : c ← CCHA, cを送る。
    • P → V : y ← Res(sk,r,c), yを送る。
  • [検証者Vの出力]:Det(pk,x,c,y).

ただし、
  • 完全性: (pk, sk) ← Gen(1n)について常に、 (P(sk), V(vk)) = 1.
  • 特別健全性: pk を与えられても、 c ≠ c' である2つの(xを共有する)説得的なトランスクリプト(x,c,y), (x,c',y')を生成することは困難。
  • HVZK性: ある効率的なアルゴリズムSimがあって、以下の2つの分布は計算的に識別不可能
    • { (x,y) ← Sim(pk, c) : (x,c,y) }pk,c  
    • { (x,r)←Com(pk), y ← Res(sk, r, c) : (x,c,y) }pk,c
を満たす。

変換
構成(NACMA+Σ) [KH 08]
EUF-NA-CMA署名 Ω=(Gen, Sign, Verify)
Σプロトコル Σ=(Gen, Com, Res, Det)
衝突困難なハッシュ関数 H : {0,1}* → CHA

Ω' = (Gen', Sign', Verify') :
  • Gen'(1n) :
    • (vk, sk) ← Ω.Gen(1n), (pkΣ, skΣ) ← Σ.Gen(1n)
    • vk' = (vk, pkΣ), sk' = (vk', sk, skΣ).
  • Sign'(sk', m) :
    • ※ Σプロトコルのコミットメントに非適応的な署名を付けて、FS'変換。
    • (x, r) ← Com(pkΣ), σ ← Sign(sk, x)
    • y ← Res(skΣ, r, H(m))
    • return σ' = (σ, x, y).
  • Verify'(vk', m, σ') :
    • return Det(pkΣ, x, H(m), y) ∧ Verify(vk, x, σ).

定理(NACMA+Σ) [KH 08]
Ωが非適応的選択文書攻撃に対し存在的偽造不可であるデジタル署名で、
ΣがΣプロトコルで、
Hが衝突困難なハッシュ関数ならば、
Ω' は適応的選択文書攻撃に対し存在的偽造不可であるデジタル署名である。


















最終更新:2011年11月19日 18:14