1976年のDiffie and Hellmanによる公開鍵暗号系の提案以後,数多くの研究がなされている.その研究の成果は,現在の情報社会の基礎となっており,電子商取引,電子現金等が現実のものとなりつつある.しかし,依然,安全性を不安視する意見もあり,問題が全て解決されているわけではない.例えば,完全に安全性が証明され,なおかつ,実用に耐えうる暗号は未だ提案されていない.それゆえ,新たな暗号の提案が今も活発に行われている.新たに提案された暗号が,広く世の中に浸透するかどうかは次の二つの問い:「その暗号は十分安全であるか?」,「その暗号は実用上十分な速度を持っているか?」にどう答えるかにかかっている.その観点から,我々は,公開鍵暗号の安全性に関する研究,及び高速化に関する研究を行った.その研究の成果として,安全性に関する成果4件,高速化に関する成果1件を得た.安全性に関する研究については,(1)素因数分解の高速化,(2)RSA型楕円曲線暗号の安全性評価,(3)ElGamal型楕円曲線暗号の安全性評価,(4)RSA暗号の改良法の安全性評価,を行った.高速化に関しては,(5)べき乗計算の高速化を行っている.

(1)素因数分解の高速化について

　いくつかの公開鍵暗号,特にRSA暗号の安全性は素因数分解の困難さに根拠をおいている.我々は,素因数分解を効率的に行うアルゴリズムを提案した.具体的には,有効な素因数分解法である楕円曲線法に改良を加え,ある仮定の下で,従来よりもより短い時間で,素因数分解に成功する方法を提案した.さらに,その有効性を理論的考察により示した.その方法は,「剰余環上で定義された楕円曲線の点の個数が,与えられた素数で割り切れるかを判定する多項式時間アルゴリズム」の存在を仮定し,このアルゴリズムを有効に利用することにより,事前に良い性質の楕円曲線の選別を行うという特徴を持っている.ここで,「良い性質の楕円曲線」とは,その点の個数が小さな素数の積を因数に持つ楕円曲線を指す.この選別により生成された良い性質の楕円曲線に対してのみ,楕円曲線法を適用することにより,高速化を実現している.その結果,見つけたい素因数pが1030から1050程度の時,提案方式は従来の楕円曲線法よりも,3から4倍高速化されている.また,漸近的には,(logp)0.318倍高速化されることを,理論的解析により明らかにした.

(2)RSA型楕円曲線暗号の安全性評価について

　ついで,公開鍵暗号の一つであるRSA型の楕円曲線暗号の安全性解析を行っている.このタイプの代表例であるKMOV暗号は,素因数分解の困難さに安全性の根拠を置いているとともに,「剰余環上の楕円曲線の点の個数を求める問題」の困難さにも安全性の根拠を置いている.我々は,この二つの問題が,実は,計算量的に等価であることを示した.前者の問題を解くオラクルを用いれば,後者の問題が簡単に解けることは自明であるので,その逆,後者の問題を解くオラクルを用いれば,前者の問題が解けることを示した.具体的には,楕円曲線の点の個数を求めるオラクルを用いて,確率的多項式時間で素因数分解を行うアルゴリズムを提案した.このアルゴリズムは,ある合成数nとEulerのφ関数φ(n)が与えられ時に,nの素因数分解を行うMillerのアルゴリズムを基にしている.さらにこの結果を利用して,前述の「点の個数を求める問題」よりも直感的には易しいと考えられる問題:「剰余環上の楕円曲線上の点の個数を,与えられた素数で割った余りを求める問題」も素因数分解問題と計算量的に等価であることを示した.さらに,「剰余環上での楕円離散対数問題」を解くオラクルを用いれば,素因数分解が確率的多項式時間で可能であることを示した.

(3)ElGamal型楕円曲線暗号の安全性評価

　ついで,公開鍵暗号の一つであるElGamal型の楕円曲線暗号の解析を行っている.このタイプの暗号は,暗号として用いる曲線として,特殊な曲線(anomalousやsupersingular elliptic curve)を選んでしまうと,簡単に解読されてしまうことが解っている.anomalous elliptic curveに関しては,Ruck,Semaev,Smart,Satoh-Arakiらがほぼ同時にその攻撃法を提案している.我々は,まずこのanomalous elliptic curveの概念を拡張したsuper-anomalous elliptic curveを定義し,ついで,この曲線上の離散対数問題を確定的多項式時間で解くアルゴリズムを2つ提案した.我々の提案したアルゴリズムは,Ruckが提案したアルゴリズムとSatoh-Arakiが提案したアルゴリズムをそれぞれ拡張した形になっている.さらに,提案したアルゴリズムにより解読されてしまう暗号に関しても考察を行っている.

(4)RSA暗号の改良法の安全性評価

　RSA暗号の提案以後,いくつかの改良版が提案されている.我々は,そのうちの一つ,Koyama暗号方式の一般化を行い,その一般化された暗号方式(以後,多変数RSA暗号方式)の暗号化,復号の速度評価及び安全性解析を行った.多変数RSA暗号方式は,(1)送りたい長いメッセージをいくつかのブロックに分割し,(2)そのブロックを多変数有理関数を用いて処理し,(3)処理後のブロック一つだけに対して,べき乗演算を行う,方式である.この暗号の速度に関しては,通常のRSA暗号よりも高速であることを理論的考察により明らかにした.また,安全性解析の結果としては,(1)盗聴者にブロックの一つが厳密にわかったとき,メッセージは全て解読されてしまう,(2)盗聴者がブロック間の関係を知ったとき,メッセージは全て解読されてしまう,(3)メッセージを2回送り,なおかつ・そのメッセージ中に,関連のブロックが含まれていた時,メッセージは2つとも全て解読されてしまう,ことを示した.以上の考察により,多変数RSA暗号方式の総合的な評価は,次のようになる.従来の方式と比較して十分高速であるが,その反面,若干の安全性の低下を招いている.しかし,安全性が低下する使用条件に注意すれば,十分安全で高速な暗号方式とみなすことができる.

(5)べき乗計算の高速化

　公開鍵暗号の高速化に関しては,べき乗計算C=Me mod nの高速化,特に,べき乗計算におけるかけ算回数を減らす目的で,より短いAddition chainの構成法に関する研究を行った.我々は,二つの効率的なアルゴリズム,(1)Run-length法,(2)Hybrid法を提案し,理論的解析,及び数値実験による解析を行った.その結果,この二つの方法は,eの2進系列中の1の個数ωが大きい時に,従来の方法(例えば,Window method)よりも効率的であることを示した.より具体的には,eの2進系列の長さをLとすると,

　・0.8〓ω/L〓1の時,Run-length法が,

　・0.6〓ω/L〓0.8の時,Hybrid法が,

　・0〓ω/L〓0.6の時,Window法が,最適であることを明らかにした.また,ω/L=0.95の時,Run-length法は,Window法より,8%短いAddition chainを構成することを示した.

　この研究を通して,公開鍵暗号の安全性に関して,ある一定の新たな寄与をすることができた.これらの成果を利用することにより,従来提案されている暗号のより厳密な安全性評価が可能となった.さらに,これらの成果は,今後新たに提案される多くの暗号に対する設計指針を与えたことになる.また,高速な暗号化手法を与え,より快適な公開鍵暗号の使用を可能とした.

　本論文は,「Security and Efficiency Analyses of Public Key Cryptosystems(公開鍵暗号の安全性解析と高速化手法)」と題し,8章から構成されている.情報化社会を支える不可欠な技術として暗号技術があり,その中でも公開鍵暗号は,電子商取引や電子現金などを始めとするさまざまな情報・通信システムのセキュリティを支える基礎技術となっており,その安全性や処理の高速化が重要な研究テーマになっている.本論文では,安全性に関して,(1)素因数分解の高速化,(2)RSA型楕円曲線暗号の安全性評価,(3)ElGamal型楕円曲線暗号の安全性評価,(4)RSA暗号の改良法の提案とその安全性評価を行っており,また高速化に関しては,(5)べき乗計算の高速化を行い,こられに対して新しい知見を与えている.

　第1章「Introduction」は,序論であり,研究の背景と目的を述べるとともに,従来の公開鍵暗号研究に対する本論文の位置付けを与えている.また,本論文の構成を示している.

　第2章「Preliminaries」では,公開鍵暗号の基礎となる整数論および楕円曲線理論を要約すると共に,重要な公開鍵暗号方式の暗号化・復号化アルゴリズムとその安全性などの特徴を紹介している.

　第3章は,「Speeding up elliptic curve factoring method(素因数分解の高速化)」と題し,従来よりもより短い時間で素因数分解可能な方法を提案している.具体的には,素因数分解の一方式である楕円曲線法の改良として,「剰余環上で定義された楕円曲線の点の個数が,与えられた素数で割り切れるかどうかを判定する多項式時間アルゴリズム」の存在を仮定すれば,従来の楕円曲線法を適用する前に良い性質の楕円曲線を選び出すことができ,それにより,素因数が1030〜1050の時,従来の楕円曲線法よりも,3〜4倍高速化できることを理論的に明らかにしている.

　第4章は,「Difficulty of counting the number of points on elliptic curve over the ring Z/nZ(剰余環Z/nZ上の楕円曲線の点の個数を求める困難さ)」と題し,RSA型楕円曲線暗号の一つであるKMOV暗号の安全性を評価している.KMOV暗号は,「素因数分解の困難さ」に安全性の根拠を置いているとともに,「剰余環上の楕円曲線の点の個数を求める問題」の困難さにも安全性の根拠を置いているが,本章では,この二つの問題が,確率的多項式時間の意味で計算量的に等価であることを,理論的に証明している.

　第5章は,「Discrete log Problem for super-anomalous elliptic curve(超アノマラス楕円曲線に対する離散対数問題)」と題し,ElGamal型の楕円曲線暗号の安全性評価を行っている.この暗号は,楕円曲線として,特殊な曲線(anomalous curveやsupersingular elliptic curve)を選んでしまうと簡単に解読されてしまうことが解っているが,本章では,それら以外にも解読が可能な曲線があることを明らかにしている.具体的には,まず超アノマラス楕円曲線を定義し,この曲線上の離散対数問題を確定的多項式時間で解くアルゴリズムを2つ提案している.その結果,この超アノマラス楕円曲線を用いたElGamal型の楕円曲線暗号が安全でないことを明らかにしている.

　第6章は,「Multi-variate RSA cryptosystems and their security analyses(多変数RSA暗号方式とその安全性)」と題し,RSA暗号の改良型を提案すると共に,その処理速度と安全性の評価を行っている.提案方式は,Koyama暗号方式の一般化を行って多変数化したRSA暗号であるが,送りたい長いメッセージをいくつかのブロックに分割し,そのブロックを多変数有理関数を用いて処理し,処理後のブロック一つだけに対して,べき乗演算を行う方式であるため,通常のRSA暗号よりも高速である.ただし,盗聴者がブロック間の関係を知ったとき,メッセージは全て解読されてしまうため,安全性が少し低下するが,使用条件に注意すれば,十分に安全で高速な暗号方式とみなすことできる特徴を有している.

　第7章は,「How to generate shot addition chains(短い加算連鎖作成法)」と題し,公開鍵暗号で使用される「べき乗計算C=Me mod n」の高速化,特に,べき乗計算におけるかけ算回数を減らす方法を明らかにしている.べき乗計算は,それをかけ算に分解して計算するために,addition chainを利用して計算されるが,短いaddition chainを作成るための2つの効率的なアルゴリズム(Run-length法とHybrid法)を提案し,その性能を理論的に解析すると共に,数値実験によりその性能を確認している.これらの手法は,データ圧縮の理論を導入したユニークな方法であり,従来のWindow methodなどに比べて,効率的であることが示されている.

　第8章「Conclutions」は,結論であり,本論文の内容がまとめられていると共に,今後の研究課題が示されている.

　以上を要するに,公開鍵暗号の重要な方式であるRSA暗号,RSA型楕円暗号,ElGamal型楕円暗号の安全性に関して新しい知見を与えており,これらの成果を利用することにより,それらの暗号のより厳密な安全性評価が可能となっている.これらの成果は,今後新たに提案される多くの暗号に対する設計指針を与えたことにもなっている.また,高速なべき乗計算法を用いれば,公開鍵暗号の暗号化復号化処理をより高速に行うことができ快適な使用が可能になる.したがって,本論文は暗号理論の研究に大きく貢献するとともに,数理工学の進歩に対して寄与するところが大であり,博士(工学)の学位請求論文として合格と認められる.