インターネットの急速な普及にみられるように,情報の送受や種々の経済活動がこれまでに無い規模でコンピュータネットワークを介して行なわれようとしている.このようなシステムでは,例えば経済活動を行なう場合,我々が従来経験してきた状況とは異なり,顔と顔を合わせることなしに情報のやり取りのみによって手続きが進むこと,またやり取りされるディジタル情報は容易に複製・消去・改竄が可能であることから情報を保護する技術,いわゆる情報セキュリティ技術が非常に重要な役割を果たすと考えられる.セキュリティ技術の内,現在もっとも体系的に研究されている暗号技術は,今から20年程前,米国での標準暗号DESの制定,公開鍵暗号の提案という二つの重要な出来事を契機として,商用システムへの応用と言う立場から広く研究されるようになった.特に,公開鍵暗号の提案はオープンなネットワークにおけるセキュリティ課題の多くを解決するものと期待されたが,具体的に提案されたRSA方式等の有力な方式では、十進数数百桁の整数を法(モジュロ)とするべき乗剰余演算を基本演算とするために,多大な処理ステップを要し実用的処理時間を達成するためにその高速化が重要な研究課題となってきた.

　このような背景を踏まえて,本研究はべき乗剰余演算を短時間で処理する方式に関する研究をまとめたものである.ここでべき乗剰余演算とは

　の右辺の計算を指し、公開鍵暗号に用いる場合にはNを500から1000ビットの値に設定する場合が多い.べき乗剰余演算の高速化のために本論文では(1)テーブル参照アルゴリズム,と(2)依頼計算と呼ばれる2者間のプロトコル,という二つの手法について性能解析と安全性評価を行うと共に,これらの手法の実用面での有効性を検証するために暗号機能付き電子メールシステムを開発した結果について論じたものであり8章からなる.

　第1章は「序論」であり,情報セキュリティ技術が研究されている背景を述べるとともに研究の目的,意義,結果の概要を述べている.特に,十進数百桁の整数を法とするべき乗剰余演算の処理の高速化が公開鍵暗号の実用化に必須であることを述べている.

　第2章は「テーブル参照による高速べき乗剰余計算」と題し,RSA暗号,DH鍵配送など整数論に基づく公開鍵暗号で広く用いられているべき乗剰余演算の高速化について検討し,べき乗を二進法に基づいて剰余乗算の繰り返しに分解した場合,その1/3は変数に定数を掛ける乗算であること,またすべての剰余乗算の法(モジュロ)は共通であることを利用して事前に幾つかの代表的剰余値の表(テーブル)を作成しておくことによって高速化をはかる手法を提案し,提案方式の適用により従来方式よりも約17%処理時間が短縮できることを示している.

　第3章から第6章はべき乗計算のための依頼計算プロトコルについて論じている.依頼計算とはクライアントと呼ばれる第1の装置が所持する秘密情報を外部に漏らすことなく,サーバと呼ばれる第2の装置の補助を借りて,秘密情報に関わる演算を単独で計算するよりも高速に行うためのプロトコルを指す.

　ここでは特に次式で表されるようなRSA暗号のディジタル署名作成の場面を想定した方式について検討する.

　ここでMはメッセージ、SはMに対する署名文であり、D,Nは署名作成者の鍵情報であるが、この内Dは本人以外には知られてはいけない秘密鍵である.第2章で論じた高速アルゴリズムは基本的に単独の計算機がべき乗剰余計算を高速に行なうという想定であったのに対して、依頼計算では2つの装置が作業を分担するという点、またべき指数Dはクライアント以外は知らないという前提を置いている点が異なっている.依頼計算はICカードのように計算力は小さいが秘密情報を格納された装置が、外部の計算機の計算力を安全に借りるために使えるプロトコルとして研究されてきた.

　まず第3章は「べき乗用依頼計算の性能解析」と題し,88年に松本らが提案したS2プロトコルの性能解析を行い,多様なサーバの性能,種々の通信回線速度での処理時間削減効果を解析している.この解析によりS2プロトコルは実用的に優れた方式であることが確認されたが,S2プロトコルはサーバに渡される依頼情報が,秘密のべき指数と完全には独立でないために,秘密指数がクライアント以外に漏れないという証明ができないという問題を抱えていた.

　第4章では「安全性の証明付き依頼計算」と題し,前記S2プロトコルの問題点を解決するために高速なべき乗計算アルゴリズム(Yao法,Knuth法)を(A)べき指数に依存する部分と,(B)べき指数に依存しない部分に分けて,(B)をサーバに行わせると言う方針で設計した依頼計算を4種類提案し,サーバがどのようにプロトコルから逸脱してもクライアントがプロトコルに従っている限り,クライアントから指数Dに関する新たな知識は漏れないこと(零知識性)を証明している.安全性が証明付きで与えられている点,また同じ安全性を実現する従来方式に比べ高速な方式である点で提案方式は優れている.

　第4章で提案した依頼計算プロトコルではサーバが(意図的に)プロトコルから逸脱した場合,計算結果は逸脱の仕方と秘密指数Dに依存して正しい場合と正しくない場合とが生じる.これまではこの正誤情報はサーバに渡らないと仮定して零知識性を証明したが,正誤情報がサーバに渡る場合には零知識性は保証されない.そこで第5章は「正誤情報の通報による秘密の漏洩解析」と題し,クライアントがサーバに正誤情報を漏らした場合に,どのようなメカニズムで秘密指数Dに関する情報が漏れるのかについて情報理論的尺度を用いて論じ,プロトコルの通信量が比較的大きいパラメータが選ばれた場合には,秘密指数Dをクライアントから取り出す具体的手順が存在することを示している.さらに,攻撃法に対する現実的な対策を示し,その有効性を情報量の尺度を用いて示している.

　第6章は「正誤情報の通報にも強い依頼計算」と題し,第5章で論じたように正誤情報から秘密指数に関する情報が漏れることを考慮して,正誤情報をサーバに漏らしても従来方式より安全性が保たれるプロトコルを提案している.具体的には,秘密指数Dを毎回ランダムな2つの整数A,Bの積に分解し,第4章で提案したべき乗計算のための依頼計算をサブプロトコルとして,2度に分けて依頼計算を行なう手法を検討している.2度に分けて依頼計算が行なわれるのでサーバのプロトコルからの逸脱が何時行なわれるかによって,クラス1攻撃:最初の依頼の時のみ逸脱する,クラス2攻撃:2度目の依頼の時のみ逸脱する,クラス3攻撃:最初の依頼と2度目の依頼の両方で逸脱する,という3種類の攻撃が分類できる.このように分類した場合,提案方式はクラス1と2攻撃に対して零知識で有る事を証明できる.クラス3攻撃に対しては証明が与えられていないが,秘密漏洩のメカニズムについて考察し,提案方式が前章のプロトコルよりもはるかに高い安全性を有すると予想される理由を述べている.

　第7章は「システム応用-暗号電子メール-」と題し,LAN上で稼働している電子メールに守秘と認証機能を付加した暗号電子メールシステムについてプロトタイプを製作し,Fiat-Shamir法に基づいて新たに提案した鍵配送メカニズムを中心に,その構成を述べている.鍵配送メカニズムにはべき乗計算が基本演算として用いられており,第2章で提案したべき乗アルゴリズムを適用して実装するとともに,第3章で解析した依頼計算を本システムに適用した場合の有効性を検討している.

　第8章は「結論」であり,本研究の成果を要約し,今後の研究方向を展望している.

　以上,本論文はRSA暗号,DH方式など代表的な公開鍵暗号の基本演算であるべき乗剰余演算の高速化について検討し,テーブル参照と依頼計算の二つの手法についていくつかの新たな方式を提案し,暗号メールのプロトタイプ開発を通してその実用性を示した.特に,依頼計算については計算量的安全性の尺度である零知識性や情報量の尺度であるエントロピーを用いた厳密な評価を初めて行ない,その方法論は他の依頼計算にも適用しうるものである.先に述べたように,べき乗剰余演算の効率的で安全な演算は公開鍵暗号実用化のために解決されるべき重要な課題の一つであり,本研究はそれに新しい解を与えるものと位置づけられる.

　本論文は「べき乗剰余演算の依頼計算と高速化に関する研究」と題し,通信・情報システムのセキュリティを実現するために公開鍵暗号方式の実用化を目的として,RSA暗号をはじめとする多くの公開鍵方式の基本演算であるべき乗剰余演算の高速化について論じており,(1)テーブル参照を利用したアルゴリズムと,(2)依頼計算と呼ばれる2者間のプロトコル,という二つの手法を検討するともに、これらの手法の有効性を検証するために暗号機能付き電子メールシステムを開発した結果について論じたものであり8章からなる.

　第1章は「序論」であり,情報セキュリティ技術が研究されている背景を述べるとともに研究の目的,意義,結果の概要を述べている.特に,十進数で数百桁の整数を法(モジュラス)とするべき乗剰余演算の処理の高速化が公開鍵方式の実用化に必須であることを述べている.

　第2章は「テーブル参照による高速べき乗剰余演算」と題し,べき乗を二進法に基づいて乗算の繰り返しに分解した場合,その1/3は変数に定数を掛ける乗算であること,またすべての法は共通であることを利用して事前に剰余値の表(テーブル)を作成しておくことによって高速化をはかる手法を提案し,提案方式の適用により従来方式よりも約17%処理時間を短縮できることを示す.

　第3章から第6章はべき乗剰余演算のための依頼計算プロトコルについて論じたものであるが,依頼計算とはクライアントと呼ばれる第1の装置が所持する秘密のべき指数Dを外部に漏らすことなく,サーバと呼ばれる第2の装置の補助を借りて,単独で計算するよりも高速に行うためのプロトコルを指す.

　第3章は「べき乗用依頼計算の性能解析」と題し,松本らが提案したS2プロトコルの性能解析を行い,多様なサーバの性能,種々の通信回線速度での処理時間削減効果を解析している.ただし、第3章で論じたS2プロトコルはサーバに渡される依頼情報が,秘密のべき指数と完全には独立でないために,秘密指数がクライアント以外に漏れないという証明ができないという問題を抱えていた.

　第4章は「安全性の証明付き依頼計算」と題し,前記問題点を解決するために高速なべき乗計算アルゴリズム(Yao法,Knuth法)を(A)べき指数に依存する部分と,(B)べき指数に依存しない部分に分けて,(B)をサーバに行わせると言う方針で設計した依頼計算を4種類提案し,サーバがどのようにプロトコルから逸脱してもクライアントがプロトコルに従っている限り,クライアントから指数Dに関する新たな知識は漏れないこと(零知識性)を証明している.安全性が証明付きで与えられている点,また同じ安全性を実現する従来方式に比べ高速な方式である点に特長がある.

　第4章で提案した依頼計算プロトコルではサーバがプロトコルから逸脱した場合,計算結果は逸脱の仕方と秘密指数Dに依存して正しい場合と正しくない場合が生ずる.第4章はこの正誤情報はサーバに渡らないと仮定して零知識性を証明しているが,正誤情報がサーバに渡る場合には零知識性は保証されない.そこで第5章は「正誤情報の通報による秘密の漏洩解析」と題し,クライアントがサーバに正誤情報を漏らした場合に,どのようなメカニズムで秘密指数Dに関する情報が漏れるのかについて情報理論的尺度を用いて論じ,プロトコルの通信量が比較的大きいパラメータが選ばれた場合には,秘密指数Dをクライアントから取り出す具体的手順が存在することを示している.さらに,攻撃法に対する現実的な対策を示し,その有効性を情報量の尺度を用いて示している.

　第6章は「正誤情報の通報にも強い依頼計算」と題し,第5章で論じたように正誤情報から秘密指数に関する情報が漏れることを考慮して,正誤情報をサーバに漏らしても従来方式より安全性が保たれるプロトコルを提案している.提案方式は攻撃を3種類に分類した場合,クラス1と2攻撃に対して零知識である事を証明できる.クラス3攻撃に対しては証明が与えられていないが,秘密漏洩のメカニズムについて考察し,提案方式が前章のプロトコルよりもはるかに高い安全性を有すると予想される理由を述べている.

　第7章は「システム応用-暗号電子メール-」と題し,LAN上で稼働している電子メールに守秘と認証機能を付加した暗号電子メールシステムについてプロトタイプを製作し,Fiat-Shamir法に基づいて新たに提案した鍵配送メカニズムを中心に,その構成を述べている.鍵配送メカニズムにはべき乗剰余演算が基本演算として用いられており,第2章、3章で検討したべき乗剰余演算アルゴリズムと依頼計算法を適用している.第8章は「結論」であり,本研究の成果を要約し,今後の研究方向を展望している.

　以上これを要するに,本論文はRSA暗号,DH方式など代表的な公開鍵方式の基本演算であるべき乗剰余演算の高速化について検討し,テーブル参照と依頼計算の二つの手法についていくつかの新たな方式を提案し,暗号メールのプロトタイプ開発を通してその実用性を示し,特に,依頼計算については計算量的安全性の尺度である零知識性を用いた厳密な評価を初めて行いその改良方式の提案は実用面のみならず計算量理論的にも意義深く,電気通信工学上貢献するところが少なくない.

　よって本論文は博士(工学)の学位請求論文として合格と認められる.