Diffie-Hellman公開鍵配送方式の安全性の解明

点击翻译按钮获取中文摘要

本研究の目標は、Diffie-Hellman公開鍵配送方式を破る問題(以下この問題をDHと書く)と離散対数問題(以下DLPと書く)の相互関係を明らかにすることである。このテーマに関して現在までに分かっていることは、次の2点である。(i)DHはDLPに多項式時間Turing帰着する。(ii)特別な場合または特別な仮定のもとではDLPはDHに多項式時間Turing帰着する。しかし、一般にDLPがDHに帰着するかどうかは不明である。すなわち、一般にはDHとDLPの等価性は知られていない。本研究では、主に標数pの有限素体上でDHとDLPを考察し、DHとDLPの中間に入るような難しさをもつ2つの鍵共有方式:Open Diffie-Hellman scheme及びParity-Sensitive Diffie-Hellman schemeが存在することを明らかにした。特に後者を破る問題をPSDHと書くと、PSDHについては次が成り立つ。(1) DHはPSDHに多項式時間で帰着する。(2)DHを解く能力があれば、PSDHは誤り率2^<-q(|p-1|)>で解ける。ここにqは多項式である。(3)PSDHは多項式時間でDLPに帰着する。(4)DLPは平均的多項式時間でPSDHに帰着する。要するにDHとDLPの間の難しさのギャップは、(2)の誤り率という尺度で表現できることを指摘した。これはDHとDLPの関係の解明という20年余りの未解決問題に対する一つの成果である。この結果は国際学術論文誌上で公表すべく準備中である。