安永研究室

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

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

セキュリティの定量化

暗号技術の安全性を評価したいときに，その安全性の程度を知りたくなります．多くの暗号技術は，証明されていない計算量的な仮定（素因数分解の困難性など）にもとづいているので，安全性の程度を証明つきで保証することは現状できませんが，現時点で知られているアルゴリズムを踏まえて見積もることはできます．一般的にビットセキュリティと呼ばれている安全性の強度を表す指標について，操作的な意味をもつ量として定式化する枠組みを最近与えました．0 か 1 かを答える判定タイプの安全性について，従来は正解する確率が 1/2 + ε のときに ε という量に着目していましたが，提案した枠組みでは仮説検定の理屈から，次数 1/2 の Rényi 情報量で評価すべきという結論が導かれました．確率分布の近さを議論するときには，全変動距離よりも Hellinger 距離で評価するほうがより正確であることもわかりました．先行研究では，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です．教員側の興味の範囲は，大枠としては理論計算機科学で，より具体的には暗号理論や符号理論（誤り訂正符号）をこれまで主に研究対象としてきました．計算量理論・計算の複雑さ・ゲーム理論・情報理論なども興味の対象です．最近の暗号理論では，量子攻撃者に対する安全性や量子情報を活用した新技術の実現可能性という話もあるので，量子計算時代の暗号技術設計などもありです．

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

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