安永研究室

東京科学大学情報理工学院数理・計算科学系

最近の研究について紹介します

暗号の基礎理論

暗号理論の中でも基礎的な側面に興味を持って研究を行っています．ビットセキュリティと呼ばれている安全性の強度を表す指標について，操作的な意味をもつ量として定式化する枠組みを与えました． 0 か 1 かを答える判定タイプの安全性について，従来は正解する確率が 1/2 + ε のときに ε という量に着目していましたが，提案した枠組みでは仮説検定の理屈から，次数 1/2 の Rényi 情報量で評価すべきという結論が導かれました．先行研究では，0 と 1 だけでなく ⊥ という出力（回答保留に対応）を許す場合のビットセキュリティの評価法が示されていましたが，我々の枠組みにおいて ⊥ を許せば，２つの枠組みはほぼ同じ量を捉えていることが明らかになりました．分布間の距離の測り方を変えたとき，アルゴリズムの出力に ⊥ を許したとき，これまでの安全性解析をどのように見直せばよいのか（より良い解析手法はあるのか）という点に興味を持っています．

Shun Watanabe and Kenji Yasunaga. Unified View for Notions of Bit Security. Asiacrypt 2023. [ePrint]
Shun Watanabe and Kenji Yasunaga. Bit Security as Computational Cost for Winning Games with High Probability. Asiacrypt 2021. [ePrint]
Kenji Yasunaga. Replacing Probability Distributions in Security Games via Hellinger Distance. Information-Theoretic Cryptography (ITC) 2021. [ePrint]

ゲーム理論的な安全性をもつ暗号プロトコル

暗号プロトコルに参加する人は，設計どおりにプロトコルに従う正直な人とその正直な人が実現したいことを邪魔する悪者のどちらかでモデル化されることが多いです．この二つのタイプの中間的な存在をゲーム理論の意味で合理的なプレイヤーとしてモデル化して安全性を議論するのがこのテーマです．暗号プロトコルは十分に安全に設計しようとすると実現のためのコストが大きくなります．そこで最近は，攻撃者に合理性を仮定することで，暗号プロトコルを低コストで実現する方法に興味を持っています．

Keigo Yamashita and Kenji Yasunaga. Rational Broadcast Protocols against Timid Adversaries. GameSec 2023.
Maiki Fujita, Takeshi Koshiba, and Kenji Yasunaga. Perfectly Secure Message Transmission Against Rational Adversaries. GameSec 2018 & GameSec 2019. [arXiv]
Kenji Yasunaga and Kosuke Yuzawa. Repeated Games for Generating Randomness in Encryption. IEICE Trans. Fundamentals, 2018. [ePrint]

誤り訂正符号

誤り訂正符号を簡潔に述べると，良い構造をもつ単射関数 Enc : {0,1}^k → {0,1}ⁿ のことです．Enc(0···0) から Enc(1···1) が互いに離れていれば，Enc(m) に誤りが発生しても元の m に一意に復元できます．ランダム関数は高い確率で優れた（互いに離れた）符号を与えますが，再現性がないため，ランダム関数のように振る舞う「擬似ランダム」な関数の設計が良い符号の構成に繋がります．暗号技術やエクスパンダーグラフなどの擬似ランダム技術を用いた符号の設計，量子ノイズに耐性のある符号の設計などに最近は興味を持っています．

Kenji Yasunaga. Improved Asymptotic Bounds for Codes Correcting Insertions and Deletions. Designs, Codes and Cryptography, 2024. [arXiv]
Tomohiro Hayashi and Kenji Yasunaga. On the List Decodability of Insertions and Deletions. IEEE Trans. on Information Theory, 2020. [arXiv]
Kenji Yasunaga. Error Correction by Structural Simplicity: Correcting Samplable Additive Errors. The Computer Journal, 2018. [arXiv]

その他，学生との共同研究について

研究テーマは各学生と教員の間で相談しながら決めます．互いに興味をもてるテーマであれば基本的には何でもOKです．教員側の興味の範囲は，大枠としては理論計算機科学で，より具体的には暗号理論や符号理論（誤り訂正符号）が主な研究対象であり，計算量理論・計算の複雑さ・ゲーム理論・情報理論なども興味の対象です．量子情報を扱うテーマも興味の範囲内です．

学士論文・修士論文の題目

2025年修士論文
パウリ操作検知符号の構成とその応用
多項式時間制限通信路に対する公開鍵誤り訂正符号の構成法
鍵準同型署名の一般的構成法

2025年学士論文
検出回避攻撃者に対する定数ラウンドコンセンサスプロトコル

2024年学士論文
ゲーム理論的に安全なブロードキャストプロトコルにおける誤検出の防止
認証付き暗号方式の関連鍵攻撃に対する安全性