NEWS RELEASE

                              平成10年4月16日

           新しい公開鍵暗号方式を開発
      −安全性が数学的に証明され、かつ高い実用性を持つ−

 NTTでは、安全性の高さが数学的に証明された、新しい公開鍵暗号方式※1"EPOC"
(Efficient Probabilistic Public-Key Encryption)を開発しました。
 EPOCは、暗号文を解読するには「スーパーコンピュータを用いても難しいと考えら
れている素因数分解問題を解く以外に方法はない」ことを数学的に証明した、安全性
の高い方式です(図)。
 また、暗号化/復号化に必要なコンピュータの処理量が、現在最も実用的な公開鍵暗
号方式であるRSA方式※2や楕円暗号方式※3とほぼ同等である高い実用性も、EPOC
の特長です。
 NTTでは、このEPOCをインターネットにおける安全確保のために暗号応用システムに
組み込んでいくと同時に、EPOCの特長を活かした新しいアプリケーションの創造にも
取り組んでいく予定です。


○ 開発の背景
 通信ネットワークを介して重要な情報が流通するようになり、その内容を外部から盗
聴されないようにするための暗号化技術が必要になってきています。
 その中にあって公開鍵暗号方式は、他人の私書箱に手紙を入れるように、誰でも他人
宛に暗号化を行なえ、インターネットのような不特定多数間での暗号通信を可能とする
方式として広く研究が行われています。
 公開鍵暗号方式で重要なのは、公開鍵(暗号鍵)から復号鍵が容易に算出できない、
という点です。代表的な公開鍵暗号方式であるRSA方式、楕円暗号方式においては、暗
号鍵からの復号鍵算出に前者では素因数分解問題、後者では楕円離散対数問題が使われ
ます。これらを解くにはスーパーコンピュータを用いても数百年以上という非現実的な
時間がかかると言われており、両暗号方式の解読に対する安全性はそれに依存するとさ
れてきました。しかし、これらの暗号方式では「素因数分解問題、楕円離散対数問題以
外の暗号文解読法はない」という証明はされていません。つまり、素因数分解問題、楕
円離散対数問題が難しくても、暗号文を簡単に解読する他の方法(抜け道)が存在する
可能性が残されているのです。
 また、RSA方式と同じく素因数分解問題に安全性を依存するラビン暗号方式※4があ
り、こちらは「素因数分解以外の暗号文解読法はない」という証明もされていますが、
それは暗号文全体の解読のことであり、部分情報の解読には「素因数分解以外の暗号文
解読法はない」という証明はされていません。

○ 新暗号方式のポイント
 新しく開発したEPOCは、RSA方式やラビン暗号方式と同じく、安全性を素因数分解
問題に依存しています。素因数分解問題は、暗号で用いられるその他の問題に比べると、
より長い期間にわたって数学者によって検討されてきた問題であり、突然効率的な解読
法が見つかる可能性はかなり低いと考えられます。さらに、EPOCは、指数関数に基づ
く落し戸付き離散対数問題※5を暗号の原理に用いることで、その数学的な特質から暗
号文の解読には素因数分解問題を解くしかない、という証明を可能としました。(なお、
RSA方式やラビン暗号方式は、多項式関数を用います。)さらに、このEPOCでは、暗
号文全体の解読のみならず部分情報を解読することすら「素因数分解以外の方法はない」
という証明ができました。
 つまり、素因数分解が難しい以上、どの1ビットの部分情報も解読できないことが証
明されたのです。また、EPOCは同じ平文を暗号化するたびに暗号文が異なる"確率暗号"
です。同じ平文を何度暗号化しても同じ暗号文にしかならない"確定暗号"であるRSA方
式やラビン暗号方式などに比べて高い安全性をもつものと言えます。

 なお、RSA方式や楕円暗号方式など現在実用化されている公開鍵暗号の基本的原理は
全て、公開鍵暗号が誕生した20年ほど前に発見されたものばかりです。EPOCは、それら
のいずれとも全く違った原理(落し戸付き離散対数問題)に基づいており、実用的で安全
性の保証された公開鍵暗号を実現する全く新しい原理を発見したものと言えます。

○今後の展開
 公開鍵暗号方式は、秘密鍵暗号方式※6に比べて計算量が大きいため、通常は秘密鍵暗
号の鍵配送に用います。NTT ではこのEPOCを鍵配送用途として、既存の暗号モジュール
に組み込んで利用していく予定です。また、EPOCは指数関数を用いているため、電子投
票や匿名通信に利用しやすいという従来の公開鍵暗号方式(RSA方式、ラビン暗号方式、
楕円暗号方式)にない特長を持っているため、新アプリケーションへの適用も検討してい
きます。
 なお、EPOCの理論的な詳細は、本年6月初旬にフィンランドで開かれる欧州暗号会議
(Eurocrypt'98)で発表する予定です。




※1 公開鍵暗号方式
平文を暗号化する暗号鍵を公開しておき、それによって暗号化され自分宛てに送られて
くる情報を自分だけが持つ復号鍵で平文に戻す、という暗号の方式。

※ 2 RSA方式
1978年に、Rivest,Shamir,Adlemanによって提案された、素因数分解問題の
難しさに基づく公開鍵暗号方式。公開鍵暗号の原理を初めて実現したもの。

※ 3 楕円暗号方式
1985年に、Miller,Koblitzによって独立に提案された、楕円離散対数問題の難し
さに基づく公開鍵暗号方式。但し、その基本原理は1976年のDiffie,Hellmanの方
式に基づく。

※ 4 ラビン暗号方式
1979年に、Rabinによって提案された、素因数分解問題の難しさに基づく公開鍵暗
号方式。暗号文全体を解読する方法が、公開鍵を素因数分解する方法以外にないことが、
初めて証明された公開鍵暗号方式。

※ 5 落し戸付き離散対数問題
ある秘密を知っていれば、効率的に解けるような離散対数問題。
このような離散対数問題は、以前は知られていなかった。

※ 6 秘密鍵暗号方式
公開鍵暗号方式とは異なり、情報の送り手と受け手が同じ鍵を持ち、それを暗号化と復
号化に用いる暗号方式。





NTT NEWS RELEASE