幾人かの参加者からの入力に対し、何らかの出力を行う計算を考える。このとき、各々が自分で入力したデータ(と出力)以外の情報を全く得ることができないように計算を実行する方法はあるだろうか。この方法を達成するタスク(Secure function evaluation(以下SFE)と呼ばれる)に関する研究は、現代暗号学における最も重要な課題の一つとなっている。一般に、もしいかなる仮定も用いなければ、SFEを達成することは不可能であることが知られている。しかしながらそれと同時に、その存在を仮定することができれば、安全な分散処理の能力を全て引き出すことができる多くの条件も知られている。例えば、上記の計算への参加者の過半数を信頼することができること、および、ブロードキャスト型の通信路を使用することができる、ということの二つが仮定できるとしよう。この場合、どのような関数に対しても、SFEが達成できることができることが知られている。さらに、もし計算量に対する制限を仮定することができれば、信頼できる参加者は過半数である必要もない。

　本論文で考察されるのは、信頼できる参加者が過半数以下であり、かつ、計算量に対する制限も仮定できない状況である。従来、このような状況に対しては、各参加者に(何らかの方法で)予め分配されたなんらかのデータを使うことができる場合に、SFEのタスクを実行できることが示されてきた。Rivestは文献[1]の中で、ある特定のデータが事前に分配されていた場合、SFEを達成するために必要かつ十分な構成要素であるプロトコル、オブリビアストランスファ(OT)およびビットコミットメント(BC)を実装できることを証明した。また、CrepeauとKilianは、参加者すべてが二元対称通信路によりお互いに通信することが可能であれば、OTとBCを効率的に実装することができるという驚くべき結果を証明した[2]。(ここで「効率的」とは、「高々多項式の通信回数によって」という意味である。)さらに、信頼できるセンターによって分配されたデータを使って、一般的なSFEを達成するプロトコルを非常に効率よく構成する方法が、Beaverによって提案された[3]。これらの結果は、極めて重要な結果であり、現代暗号研究にとって大きな貢献であることは間違いない。しかしながら、同時に、以下のような重大な問題は未整理のままであった。

●このようなシナリオで、二者間あるいは多者間のSFEを安全に行うための、事前に配布されたデータが満たすべき必要十分条件。

●事前に分配されたデータや雑音のある通信路を資源としてSFEを達成する場合の効率。

●従来提案された方式の改良の可能性。

　本論文は、これらの問題について考察を行ったものである。本論文の構成は以下のようになっている。

　第2章では、非自明な離散メモリなし通信路によって、コミットメント方式が実装できることを証明する。(従来研究はすべて、二元対称通信路について議論したものであることに注意してほしい。)さらに、雑音のある通信路の最も効率のよいコミットメント方式への利用法を議論し、Shannon理論における通信路容量に相当する概念、すなわちコミットメント容量の概念を導出する。従来は、雑音のある通信路を使い一つのビットをコミットメントする方法(即ちビットコミットメント)が議論されてきたが、ここでは、大きなメッセージのセットから選んだ一つをコミットメントする、いわばストリングコミットメントが議論される。我々は、このコミットメント容量が、簡便な式で表現できること、さらにはこのコミットメント容量により、一般的な離散メモリなし通信路を完全に特徴付けられることを示す。また、これらの結果は、古典量子通信路の場合に拡張される。

　第3章では、Rivestによる事前に分散されたデータによるコミットメント方式[1]についてその限界を一般的に証明する。これは、文献[4]で提起された問題、即ち、Rivestの提案プロトコルが、その状況において、最も高い効率を達成したものであるかどうかという未解決問題への解答となっている。

　第4章では、雑音のある通信路について、一般的にどのような雑音(より正確には、その相関)がOT(あるいはそれによって達成されるSFE)を実装するための必要十分条件であるかという問題について考察する。これも、文献[2]で提起されて以来の未解決問題であった。我々は、非自明な雑音のある通信路であれば(それがどのようなものであっても)、それを利用することによりOTを達成することができることを証明する。

　第5章では、もう一つの重要な分散型のプロトコルである紛失多項式評価(obivious　polynomial evaluation 以下、OPE)について、事前に分散したデータを使ったシナリオを議論する。OPEを達成するために必要な通信量についてその下限を証明し、実際にその下限を達成できるプロトコル(即ち最適なプロトコル)を提案した。また、この下限についての結果から、OTの実装のためにRivestによって提案されたプロトコルが最適であったことが証明される。

　第6章では、二者間のSFEを達成するための、相関のあるデータに基づいた一般的なプロトコルを提案する。これは、[3]で提案されているものより、簡便であり効率の意味でも優れたものになっている。続く第7章で、これを多者間の状況に拡張する。

　本論文は「Bounds and Constructions for Mutually Distrustful Information Theoretically Secure Cryptographic Protocols(情報論的に安全な暗号プロトコルの理論的考察)」と題し，二者間あるいは多者間で，相互に信頼しなくても，また，いかなる計算量的仮定を置くことなく安全に実行できる暗号プロトコルの理論的限界と構成法に関し，コミットメント容量などの新たな概念を導入し，それらに基づきプロトコルの効率などに対する理論的限界を導出するとともに，新たな暗号プロトコルを提案したものである．論文の構成は，「序論」「結言」を含めて8章からなる．

　 第1章は「Introduction(序論)」で，本研究の背景を明らかにした上で，研究の動機と目的について言及し，本論文の構成について述べている．

　以下の第2章から第7章までは三つの部分に分けられ，それぞれが二つの章からなる．最も基本的な暗号プロトコルとしてコミットメントと紛失通信(Oblivious Transfer)とがあるが，第2章，第3章ではコミットメントを，第4章，第5章では紛失通信を，そして第6章，第7章では一般のプロトコルをそれぞれ扱っている．

　 第2章は「Commitment Capacity of Discrete Memoryless Channel(離散無記憶通信路のコミットメント容量)」と題し，まず誤りのある離散無記憶通信路によって，情報量的に安全なコミットメントが実現できることを証明する．ついで，コミットメントできる情報量の限界を与えるコミットメント容量の概念を導入し，これが簡潔な式により表現できることを示す．これらの結果は量子通信路に対しても拡張できる．

　第3章は「Pre-distributed Commitment(事前分散コミットメント)」と題し，事前に分散されたデータに基づく情報量的に安全なコミットメントについて，その限界を一般的に証明している．これは，基本的な分散型の暗号プロトコルの一つであり，それについての最も重要な未解決問題を解決したと言うことができる．

　第4章は「Oblivious Transfer from any Genuine Noise(真性雑音に依る紛失通信)」と題し，雑音のある通信路において，情報量的に安全な紛失通信を実現するための必要十分条件について考察し，0でない雑音が存在する通信路では，紛失通信を実現できることを証明している．これは，15年以上にわたる暗号学の未解決問題を解決したものである．

　第5章は「Oblivious Polynomial Evaluation(紛失多項式評価)」と題し，もう一つの基本的分散型暗号プロトコルである情報量的に安全な紛失多項式評価について，それを実現するための通信量の下限を導き，それを達成する具体的プロトコルを提案している．

　第6章は「Secure Two-Party Computations(安全な二者間計算)」と題し，二者間の計算を安全に実現するために，相関のあるデータに基づいた情報量的に安全な一般的暗号プロトコルを提案している．

　第7章では「Secure Multiparty Computations and Verifiable Secret Sharing(安全な多者間計算と証明可能な秘密分散)」と題し，第6章の結果を多者間の場合に一般化している．

　最後に第8章は「Conclusion(結論)」で，本研究の総括を行い，併せて今後解決すべき課題について述べている．

　以上これを要するに，本論文は，情報量的に安全な暗号プロトコルに関し新しい概念を導入するとともに，それに基づいて，重要な未解決問題を解決し，情報量的に安全な暗号プロトコルの基礎理論を確立したものであり，これらの研究成果は電子情報学，特に情報セキュリティ分野に貢献するところが少なくない．

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