本稿では、この論文を扱います。
https://link.springer.com/content/pdf/10.1007/s00145-004-0314-9.pdf
この記事で紹介する内容
ある楕円・超楕円曲線上でのDiffie-Hellman仮定に基づく短い署名方式を示す。ここで扱うDiffie–Hellman問題は､Computational Diffie–Hellman (CDH)問題は困難であるが､Decision Diffie–Hellman (DDH)問題は簡単なGap Diffie-Hellman(GDH)グループである。
GDHグループについて
CDHとDDHについて
G1とG2は2つの素数pの乗算的な環状基、g1,g2はG1,G2の固定関数発生器、ψはG2からG1への同型写像で、ψ(g2) = g1、eをG1×G2→GTとなる双線型写像とする。
このとき
-
CDH：
g2, g2^a∈G2とh∈G1を 入力し､h^a∈G1を計算する -
DDH：
g2, g2^a∈G2とh, h^b∈G1を入力し､もしa=bならyes､a≠bならばnoを出力し、答えがyesの場合(g2,g2^2,h,h^a)はDiffie-Hellmanの組であるといえる。
GDHグループ
先に述べたようにGDHグループはDDHは簡単だが､CDHは難しい(G1,G2)のグループである
アルゴリズムAがCDH問題を解く確率は以下の式のようになる
ここでアルゴリズムAが実行される時間が最大でt､ Succ co-CDHが最小でもεであることを(t,ε)と表す
このとき
・G1, G2の群操作､ ψの計算時間は最大でτ
・G1, G2でのDDHにかかる時間は最大でτ
・(t,ε)を満たすアルゴリズムが存在しない
を満たすG1, G2が(τ, t, ε)-GDHグループであり、このようなGDH群の例は双線型写像のみである
双線型写像e はG1×G2→GT(|G1|=|G2|=|GT|)であり以下を満たすものである
全てのu∈G1, v∈G2, a,b∈Zに対して e(u^a, v^b) = e(u, v)^ab
このとき
a=b mod p ⇔ e(h, g2^a)=e(h^b, g2)
が成り立つ
従って(G1, G2)が(τ,t,ε)-双線型写像であるならば、(G1, G2)はまた(2τ,t,ε)-双線型写像でもある
GDHグループに基づいた署名スキーム
署名方式はGDHグループのペア(G1, G2)で動作し、KeyGenelation, Sign, Verifyの３つのアルゴリズムで成り立つ
(G1, G2)を(t,ε)-co-GDHグループのペアとし､|G1|=|G2|=pとする
双線型写像σをG1の要素とする
フルドメインのハッシュ関数H :{0, 1} ∗→G1をおく
-
KeyGenelating
Pick random x R←Zp, compute v←g2
v∈G2が公開鍵であり､xが秘密鍵である -
Signing
公開鍵x∈Zp, message M∈{0, 1}∗ が与えられ､h←H(M)∈G1,σ←h^xを計算する -
Verification
公開鍵v∈G2, message M∈{0, 1}∗, 署名σ∈G1が与えられ､h←H(M)∈G1を計算し(g2, v, h,σ)が有効なDiffie–Hellmanを満たす組であるかを確認する
もし満たすのであれば出力は有効であり､そうでないなら無効である
このアルゴリズムでは署名はG1の一つの要素であり､ 短い署名のためにはG1の要素が短いGDHグループのペアが必要である
楕円曲線から短いGDHグループのペアを得る
qを素数とし､ E/FqをE(Fq)の中にm個の点を持つ楕円曲線とする
p^2 not| mである素数pを満たすE(Fq)上の部分群をPとする
Fpのqの次数がαの場合、部分群Pの安全性乗数はαとなる
つまり
全てのk=1,2,...,α−1で
p | q^α−1 , p not| q^k−1
このときα=6である曲線について考える
α=6を持つ楕円曲線
q=(2l)^2+1,p=(2l)^2−2l+1とおくと､pが素数のとき、pの点を持つ曲線E/Fqのαは6となる
q=(t^2 + Dy^2)/4…① をみたす整数y, t, D=3 mod 4を置く
複素乗法を用いてq+1-tを持つ楕円曲線E/Fqは時間D^2(log q)^3で得られる
このとき$$q=(2l)^2+1$$,p=(2l)^2−2l+1であり､t=q+1−p=2l+1とすると
点pを持ちα=6を満たす楕円曲線が複素乗法によって得られる
このとき
①⇔(6l−1)^2−3Dy^2 =−8
が満たされる
GDHグループペア(G1,G2)
設定したE/Fq, p, P, αを用いてGDHグループペアである(G1,G2)を得るには
1.α=6であるからPから線形に独立な点がE(Fq^α)上に存在し、その点をQ∈E(Fq^α)とする
2.G1=P, G2=Qとする
この署名スキームの性能
DSAのような離散対数に基づく標準的な署名は2つの要素を必要とするのに対し、ここで扱ったGDHに基づいた署名は有限場の中では1つの要素に過ぎないため、同じ安全性を持つ現行のDSAのすべてのバリエーションよりもはるかに短い。
具体的には 171ビットの署名で1024ビットのセキュリティを持つ。
また時間については、署名生成は楕円曲線上の単純な乗算に過ぎず、RSA署名生成よりも高速である。一方で署名検証には双線形写像の2回の計算が必要であり、RSA署名検証よりも遅い。
この署名方法の利用法としては、その短さから、署名が人間によって入力されるシステム、低帯域幅のチャネルを介して送信されたりするシステムがあげられる。
