決定的ディフィー・ヘルマン仮定

決定的ディフィー・ヘルマン（DDH）仮定は、巡回群の離散対数を含む特定の問題に関する計算困難性仮定です。これは、エルガマル暗号システムやクラマー・ショウプ暗号システムなど、多くの暗号プロトコルのセキュリティを証明するための基礎として使用されます。

位数、生成元の(乗法)巡回群を 考えます。DDH 仮定は、一様かつ独立に選択された に対して および が与えられた場合、値は内のランダムな要素「のように見える」というものです。 ${\displaystyle G}$${\displaystyle q}$ ${\displaystyle g}$${\displaystyle g^{a}}$${\displaystyle g^{b}}$${\displaystyle a,b\in \mathbb {Z} _{q}}$${\displaystyle g^{ab}}$${\displaystyle G}$

この直感的な概念は、次の 2 つの確率分布が計算上区別できない(セキュリティ パラメータ、) と述べることで正式に述べることができます。 ${\displaystyle n=\log(q)}$

• ${\displaystyle (g^{a},g^{b},g^{ab})}$ここで、および はからランダムかつ独立に選択されます。${\displaystyle a}$${\displaystyle b}$${\displaystyle \mathbb {Z} _{q}}$
• ${\displaystyle (g^{a},g^{b},g^{c})}$、ここで はからランダムかつ独立に選択されます。${\displaystyle a,b,c}$${\displaystyle \mathbb {Z} _{q}}$

第 1 種のトリプルは、DDH トリプレットまたはDDH タプルと呼ばれることがよくあります。

DDH 仮定は、離散対数仮定に関連しています。 で離散対数を効率的に計算できる場合、 では DDH 仮定は成立しません。 が与えられている場合、まず の離散値を取り、次に と比較することで、かどうかを効率的に判断できます。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle (g^{a},g^{b},z)}$${\displaystyle z=g^{ab}}$${\displaystyle \log _{g}}$${\displaystyle g^{a}}$${\displaystyle z}$${\displaystyle (g^{b})^{a}}$

DDH は離散対数仮定よりも強い仮定であると考えられています。これは、離散対数の計算は困難であると考えられる (したがって DL 仮定は真であると考えられる) グループがある一方で、DDH タプルの検出は容易である (したがって DDH は偽である) グループがあるためです。このため、グループ内で DDH 仮定が成立することを要求するのは、DL よりも厳しい要件であると考えられています。

DDH 仮定は、計算上の Diffie-Hellman 仮定(CDH) にも関連しています。から を効率的に計算できれば、上記の 2 つの確率分布を簡単に区別できます。 CDH が解ければ、つまり が得られれば、DDH の答えが明らかになるため、DDH は CDH よりも強力な仮定であると考えられます。 ${\displaystyle g^{ab}}$${\displaystyle (g^{a},g^{b})}$${\displaystyle g^{ab}}$

DDH タプルを検出する問題はランダム自己還元可能であり、大まかに言えば、入力のごく一部に対してさえ困難であれば、ほぼすべての入力に対して困難であり、入力のごく一部に対してさえ容易であれば、ほぼすべての入力に対して容易であることを意味します。

セキュリティが DDH 仮定に依存する暗号化プロトコルを使用する場合、DDH が保持すると考えられるグループを使用してプロトコルを実装することが重要です。

• 素数 を法とする - 番目の剰余群の部分群。も大きな素数です (シュノア群とも呼ばれます)。 の場合、これは安全な素数を法とする平方剰余群に対応します。${\displaystyle \mathbb {G} _{q}}$${\displaystyle k}$${\displaystyle p=kq+1}$${\displaystyle q}$${\displaystyle k=2}$
• 安全な素数の商群は、 剰余類で構成されます。これらの剰余類は で表すことができ、これは を意味します。と は同型であり、同型性は両方向で効率的に計算できるため、DDH はどちらのグループでも同様に困難です。${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$ ${\displaystyle p=2q+1}$ ${\displaystyle \{\{1,-1\},\ldots \{q,-q\}\}}$${\displaystyle \{x,-x\}}$${\displaystyle x}$${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}\equiv \{1,\ldots ,q\}}$${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$${\displaystyle \mathbb {G} _{q}}$
• が素数である体上の素数位数楕円曲線は 、大きな埋め込み次数を持ちます。${\displaystyle E}$ ${\displaystyle GF(p)}$${\displaystyle p}$${\displaystyle E}$
• 素数の被約因子を持つ体上の超楕円曲線のヤコビアン。ヤコビアンには大きな埋め込み次数があります。 ${\displaystyle GF(p)}$${\displaystyle p}$

重要なのは、DDH 仮定は乗法群 （は素数）では成り立たないことです。これは、が の生成元である場合、のルジャンドル記号によりが偶数か奇数かが明らかになるためです。 、、が与えられれば、 、 の最下位ビットをそれぞれ効率的に計算して比較することができ、ランダムな群の要素と 区別するための確率的方法が得られます。${\displaystyle \mathbb {Z} _{p}^{*}}$${\displaystyle p}$${\displaystyle g}$${\displaystyle \mathbb {Z} _{p}^{*}}$${\displaystyle g^{a}}$${\displaystyle a}$${\displaystyle g^{a}}$${\displaystyle g^{b}}$${\displaystyle g^{ab}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle ab}$${\displaystyle g^{ab}}$

DDH 仮定は、埋め込み次数が小さい (たとえば、 未満)上の楕円曲線には当てはまりません。このクラスには、超特異楕円曲線が含まれます。これは、 Weil ペアリングまたはTate ペアリングを使用して、次のように問題を直接解くことができるためです。このような曲線上で が与えられている場合、および を計算できます。ペアリングの双線型性により、2 つの式が等しいのは、の位数を法として である場合のみです。埋め込み次数が大きい場合 (たとえば、 のサイズ程度)、ペアリングを計算できないため、DDH 仮定は依然として有効です。埋め込み次数が小さい場合でも、曲線の一部のグループでは DDH 仮定が成立すると考えられます。 ${\displaystyle GF(p)}$${\displaystyle \log ^{2}(p)}$${\displaystyle P,aP,bP,cP}$${\displaystyle e(P,cP)}$${\displaystyle e(aP,bP)}$${\displaystyle ab=c}$${\displaystyle P}$${\displaystyle p}$

• ディフィー・ヘルマン問題
• ディフィー・ヘルマン鍵交換
• 計算困難性の仮定
• XDH仮定
• 決定線形仮定

• ボネ、ダン(1998)。「決定ディフィー・ヘルマン問題」。第3回アルゴリズム数論シンポジウムの議事録。コンピュータ サイエンスの講義ノート。第 1423 巻。pp. 48–63。CiteSeerX 10.1.1.461.9971。doi  :10.1007/ BFb0054851。ISBN 978-3-540-64657-0。