「言語の複雑さと現代暗号」
Cryptography and the Complexity of Languages

静谷 啓樹 (東北大学大学院情報科学研究科)
Professor Hiroki Shizuya, Graduate School of Information Sciences, Tohoku University

現代暗号を形式言語の複雑さの理論との関連で概観します。 主な話題は一方向性関数とゼロ知識証明です。 一方向性関数とは、現代暗号の出発点となった概念ですが、候補となるものはたくさん知られていても、実在は証明されていません。そこで、そのような関数の存在条件が形式言語の複雑さの理論ではどのように表現されるのかを紹介します。ゼロ知識証明とは、ある命題が真であることを、なぜ真なのかの理由を示すことなく、真であるという事実のみ相手に納得させる証明方法で、現代暗号理論の一つの頂点にも位置付けられます。 講演では、ゼロ知識証明で証明できる言語のクラスはどこまで広がっているのかについて解説します。