離散対数問題に基づく暗号系の帰着関係の研究

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

本研究の主要な目標は、離散対数問題に安全性の根拠を置くいくつかの暗号系について、これらを破ることの難しさの順序付けを行い、ある暗号系を破るアルゴリズムが発見された場合は、どの暗号系も破れるのかを明確にすることであった。暗号系としては、Shamirの3パス鍵配送方式、Okamotoの会議用鍵共有方式、ElGamalの公開鍵暗号方式、Bellare-Micaliの忘却伝送方式、Diffie-Hellmanの鍵共有方式の5方式を取り上げ、検討の対象とした。便宜上、それぞれを破る問題を3PASS,CONF,EG,BM,DHと表すことにする。検討の結果、以下のような事実を証明した。・これらの方式を破る問題の帰着関係は、共通の素数pを法とする有限素体上で、3PASS【less than or equal】^p_mCONF【less than or equal】^p_mEG≡^p_mBM≡^p_mDHである。ただし、【less than or equal】^p_mは多項式時間many-to-one帰着を表し、≡^p_mは【less than or equal】^p_mかつ【greater than or equal】^p_m(つまり同等)を表す。・p-1の素因数分解が公開され、法pの原始根の判定が決定性多項式時間で実行できるときは、逆転の帰着DH【less than or equal】^P_T3PASSが成立する(【less than or equal】^P_Tは多項式時間Turing帰着を表す)。すなわち、上記の問題は多項式時間Turing帰着の意味ですべて同等となる。・素数位数の楕円曲線の上で暗号系を構築した場合も、これらの暗号系を破る問題は多項式時間many-to-one帰着の意味ですべて同等となる。以上の成果は、平成7年5月にフランスで開催予定の暗号理論の国際会議(Eurocrypt'95)において公表される。