ラマヌジャン・グラフの整数論による耐量子計算機暗号へのアプローチ
| 整理番号 | 20210008 |
|---|---|
| 種別 | 若手研究-短期共同研究 |
| 研究計画題目 | ラマヌジャン・グラフの整数論による耐量子計算機暗号へのアプローチ |
| 研究代表者 | Jo Hyungrok（横浜国立大学先端科学高等研究院・特任助教） |
| 研究実施期間 |
2021年8月30日(月) ～
2021年9月2日(木) 2021年12月13日(月) ～ 2021年12月17日(金) |
| 研究分野のキーワード | 耐量子計算機暗号、ラマヌジャン・グラフ、同種写像暗号 |
| 本研究で得られた成果の概要 |
耐量子計算機暗号（Post-Quantum Cryptography）とは、量子アルゴリズムを実現する大規模な量子計算機が出現しても安全な暗号技術である。耐量子計算機暗号の有力な候補である同種写像暗号は、ラマヌジャン・グラフの一種である超特異楕円曲線の同種写像グラフの経路探索問題の困難性に基づいている。 本研究の目的は二つであった。まず、一つ目の目的は同種写像暗号の安全性を、その背後にある整数論の観点から評価することであった。一環として、組織委員と非公開セミナー２の参加者はコンパクトな鍵サイズと既存の同種写像ベース署名方式より更なる効率性を持つSQISign(Short Quaternion and Isogeny Signature)の構成やその安全性についてしっかり理解することを目指し、SQISignの数学および情報理論的な背景（四元数代数、KLPTアルゴリズム、ゼロ知識証明など）を適切に分担し、講演会を行った。非公開セミナー２（講演会）から得られた今後の課題は以下の通りである。 １．SQISignを用いた高機能暗号化への応用は可能か。 ２．SQISignの定数時間アルゴリズムは実現可能か。 ３．数学的なアプローチによりSQISignのアルゴリズムの改良は可能か。(KLPTアルゴリズムの改良によるSQISignの実行時間の短縮など) 二つ目の目的は、数学や暗号学の専門家の横断的なチームを構成することで、暗号学の観点のみでは得られなかった知見から新たな暗号方式の提案を目指すことであった。その一環として、非公開セミナー１の講演者の一人である熊本大学の佐竹翔平氏との共同研究で、大きい内周を持つ3正則グラフ（Triplet graphs, Sextet graphs）の上でハッシュ関数を構成した。この共同研究結果[1]は国内研究集会「2022年情報とセキュリティシンポジウム」で講演し、査読付国際会議に論文を投稿予定である。 最近では、暗号学に使われている数学の範囲が大きく広がっている。整数論だけではなく、代数的グラフ理論、組合せ論、代数幾何学などの様々な数学分野の専門家の活躍により、多様な観点から既存の暗号方式の安全性を評価することが望まれる。本研究の意義として、同種写像暗号の安全性を調査・研究するのは暗号技術の開発や分析に貢献すると共に、様々な数学の専門家の暗号研究への新規参入を促し新たな暗号方式の開発などを目指すきっかけとなることがあげられる。 [1] H. Jo and S. Satake, “Cryptographic hash functions based on Triplet and Sextet graphs,” Proceedings of the 39th Symposium of Cryptography and Information Security (SCIS2022), 2022. |
| 組織委員(研究集会) 参加者(短期共同利用) |
Jo Hyungrok（横浜国立大学先端科学高等研究院・特任助教） 國廣 昇（筑波大学システム情報系・教授） 山﨑 義徳（愛媛大学大学院理工学研究科数理物質科学専攻・教授） 野崎 寛（愛知教育大学数学教育・准教授） 池松 泰彦（九州大学マス・フォア・インダストリ研究所・助教） 小貫 啓史（東京大学大学院情報理工学系研究科数理情報学専攻・特任助教） 相川 勇輔（三菱電機株式会社情報技術総合研究所・研究員） 守谷 共起（東京大学大学院情報理工学系研究科数理情報学専攻・博士課程 2年） |
| アドバイザー | 高島 克幸（早稲田大学 教育・総合科学学術院・教授） |