Gap Diffie-Hellman(GDH)グループを用いた短い署名方法の紹介

Gap Diffie-Hellman(GDH)グループを用いた短い署名方法の紹介 お知らせ
Table of Contents

本稿では、この論文を扱います。
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∈G2h∈G1を 入力し、h^a∈G1を計算する

  • DDH:g2, g2^a∈G2h, 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問題を解く確率は以下の式のようになる
file
ここでアルゴリズム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の3つのアルゴリズムで成り立つ

(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/FqE(Fq)の中にm個の点を持つ楕円曲線とする
p^2 not| mである素数pを満たすE(Fq)上の部分群をPとする
Fpqの次数がαの場合、部分群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署名検証よりも遅い。

この署名方法の利用法としては、その短さから、署名が人間によって入力されるシステム、低帯域幅のチャネルを介して送信されたりするシステムがあげられる。

タイトルとURLをコピーしました