研究内容

暗号技術の安全性を証明するときに帰着（Reduction）とよばれる手法が用いられます．帰着とは，ある計算問題を別の計算問題へ変換する手法です．問題どうしの帰着が構成できれば，計算問題の難しさの関係を明らかにできます．暗号理論の研究においては，帰着は計算問題の困難性から暗号方式の安全性を証明するときに用いられます．本研究室では帰着を用いて安全性証明が可能である暗号技術の構成に取り組んでいます．また，既存の安全性証明を再検討し，証明に必要な計算量的仮定や帰着の効率などの観点から，安全性証明の改良にも取り組んでいます．

高機能暗号技術とは，従来の暗号技術に，より高度で柔軟な機能を付加した暗号技術です．その代表例の一つに関数型暗号（Functional Encryption）があります．関数型暗号では，秘密鍵が関数 f に対応付けられており，データ x の暗号文から x 自体を復号するのではなく，その秘密鍵に対応する関数の計算結果 f(x) のみを得ることができます．これにより，元のデータ x を秘匿したまま，利用者や目的に応じて必要な情報だけを取り出すことが可能になります．本研究室では，高機能暗号の安全性モデルの定義，暗号方式の構成，および安全性証明に取り組んでいます．

耐量子暗号（Post Quantum Cryptography）とは，古典コンピュータで動作できる，量子コンピュータにとって破ることが困難である暗号です．大量の量子ビットを扱うことができる量子コンピュータが完成すると，従来用いているRSA暗号などの安全性が破られます．量子コンピュータの完成に備えて，耐量子暗号の開発を行う必要があります．本研究室では格子や符号に関する計算問題の困難性を用いた耐量子暗号の構成に取り組んでいます．

計算複雑性理論（Complexity Theory）では，計算問題がどれほど難しいかを計算に必要な時間や領域などの尺度を用いて調べる学問です．特に，効率的に解くことが困難な計算問題が存在するのかという根本的な問いに関心があります．その中でも，P ≠ NP予想と，暗号技術の理論的基盤となる一方向性関数の存在との関係に興味があります．一方向性関数が存在すればP ≠ NPが成り立ちますが，逆にP ≠ NPから一方向性関数の存在が導かれるかどうかは，現在も未解決の問題です．

アルゴリズム理論（Algorithm Theory）は，さまざまな計算問題を効率的に解くためのアルゴリズムを設計し，その正しさや実行時間，必要な記憶領域などを数学的に解析する学問です．特に，アルゴリズムの実行時間や得られる解の精度について，理論的な保証を与えられるアルゴリズムの設計と解析に興味があります．例えば，計算問題の厳密解を効率的に求めるアルゴリズムや，厳密解を求めることが困難な問題に対して最適解に近い解を効率的に求める近似アルゴリズム，暗号技術にも広く用いられるランダムな選択を利用する，確率的アルゴリズムなどに関心があります．

理論計算機科学（Theoretical Computer Science）は，計算の仕組みや能力，限界を数学的な手法を用いて研究する学問です．本研究室で取り組む暗号理論，計算複雑性理論，アルゴリズム理論は，理論計算機科学に含まれます．このほかにも，計算可能性理論，オートマトン理論，形式言語理論，量子計算理論，計算論理学などが理論計算機科学に含まれます．本研究室では，理論計算機科学のさまざまな分野の知見や数学的手法を活用して研究を進めます．