ウェブページを閲覧する際などに用いられる公開鍵暗号方式は、特定の計算問題の困難性を根拠にしていますが、数学的にはまだ安全性が証明されていません。私は回路最小化問題を用いて計算量を解析し、絶対的に安全な暗号の確立に向けた研究を行っています。
研究背景・目的
現代の情報通信社会においては、私たちの通信の秘密を守るために多くの暗号技術が用いられています。例えば、普段ウェブページを閲覧する際には、背後で公開鍵暗号方式と呼ばれる技術が用いられており、解読することが困難であるように暗号化しながら通信が行われています。ただし、実は数学的に安全性が証明されている公開鍵暗号方式は現在のところ存在しません。現状では「大きい桁数の素因数分解をするのに時間がかかる」といった、特定の計算問題の困難性に関する予想に基づいていますが、その予想は証明されていません。私はそのような計算困難性を解析する計算量理論の研究を行っています。
研究内容
安全な暗号の解析で最も重要となるのは「平均時計算量」を解析することです。例えば、「素因数分解の計算に時間がかかる」という予想に基づいて暗号を構成するとき、「ある合成数を素因数分解することに時間がかかる」（最悪時計算量）だけではなく、「多くの合成数において平均的に素因数分解することに時間がかかる」（平均時計算量）という、より強い仮定を置く必要があります。より安全な暗号を構成するには、最悪時計算量と平均時計算量をつなぐことによって多くの入力における計算問題の難しさを理解する必要があります。私は回路最小化問題と呼ばれる、入力として与えられたブール値関数を計算するような小さい論理回路を求める問題（図）について、最悪時計算量と平均時計算量がほとんど同じであることを示しました。
産業応用の可能性
ビットコインなどのブロックチェーンの技術においては、プルーフ・オブ・ワークと呼ばれる暗号技術を用いることにより安全性を担保していますが、現在使われているようなプルーフ・オブ・ワークが本当に安全かどうかは（「P対NP問題」よりも難しい）未解決問題です。近年の平均時計算量に関する進展により、より安全性がもっともらしいプルーフ・オブ・ワークを作ることができる可能性があります。
図）回路最小化問題:入力としてブール値関数が与えられたときに、最小のゲート数の論理回路を求める問題
