ディフィー・ヘルマン問題

ディフィー・ヘルマン問題（DHP）は、暗号学の分野でホイットフィールド・ディフィーとマーティン・ヘルマン^{[1]によって初めて提案された数学的問題であり、}ディフィー・ヘルマン鍵交換とその派生の理論的基礎となっています。この問題の動機は、多くのセキュリティシステムが一方向関数、つまり計算は速いが逆算が難しい数学的演算を使用していることです。たとえば、一方向関数ではメッセージを暗号化できますが、暗号化を元に戻すのは困難です。DHPを解くのが簡単であれば、これらのシステムは簡単に破られるでしょう。

ディフィー・ヘルマン問題は非公式には次のように述べられます。

要素とおよびの値が与えられた場合、 の値はいくらでしょうか?${\displaystyle g}$${\displaystyle g^{x}}$${\displaystyle g^{y}}$${\displaystyle g^{xy}}$

正式には、は何らかの群（通常は有限体の乗法群または楕円曲線群）の生成元であり、およびはランダムに選択された整数です。 ${\displaystyle g}$${\displaystyle x}$${\displaystyle y}$

たとえば、Diffie-Hellman 鍵交換では、盗聴者はプロトコルの一部として を観察して交換し、両者は共有鍵を計算します。DHP を高速に解決する手段があれば、盗聴者は Diffie-Hellman 鍵交換や、 ElGamal 暗号化などの多くのその変種のプライバシーを侵害できるようになります。 ${\displaystyle g^{x}}$${\displaystyle g^{y}}$${\displaystyle g^{xy}}$

暗号学では、特定のグループではDHP が困難であると仮定されており、これはしばしばDiffie-Hellman 仮定と呼ばれます。この問題は数十年にわたって精査されてきましたが、まだ「簡単な」解決策は公表されていません。

2006 年現在、DHP を解く最も効率的な方法は、離散対数問題(DLP) を解くこと、つまりgとg ^{x が}与えられたときにx を求めることです。実際、多くのグループでは DHP が DLP とほぼ同じくらい難しいことを示す大きな進歩がありました (den Boer、Maurer、Wolf、Boneh、Lipton による)。現在まで、一般グループを除いて、DHP または DLP のいずれかが難しい問題であるという証明はありません (Nechaev と Shoup による)。どちらかの問題が難しいという証明は、P  ≠  NPを意味します。

Diffie-Hellman 問題には多くの変種が考えられてきました。最も重要な変種は決定 Diffie-Hellman 問題(DDHP) で、これはg、g ^x、g ^yが与えられた場合に、 g ^{xy を}ランダムな群要素と 区別する問題です。DHP は、DDHP とより明確に区別するために計算 Diffie-Hellman 問題(CDHP)と呼ばれることもあります。最近、ペアリングのある群が人気になってきており、これらの群では DDHP は簡単ですが、CDHP は依然として難しいとされています。DHP のそれほど重要でない変種については、参考文献を参照してください。

• 離散対数問題
• 楕円曲線暗号