廣瀬 健二朗
現在広く使用されている公開鍵暗号は素因数分解や離散対数問題といった数論の計算困難な問題を安全性 の根拠としている. しかし,量子計算機の実用化に伴いこれらの問題は多項式時間で解かれることが証明さ れており,量子計算機に耐性のある耐量子計算機暗号の実用化が急がれている. Ring-Learningwith Errors （Ring-LWE）問題は耐量子計算機暗号である格子暗号を構成する数学問題の一種である. Ring-LWE問題 の解法アルゴリズムは4つに大別することができる. 格子基底簡約アルゴリズムに基づく手法,代数的手法, 組み合わせ的手法,および全探索アルゴリズムである. その中でも本研究では,これまで十分に研究されて こなかった組み合わせ的手法であるBlum-Kalai-Wasserman（BKW）アルゴリズムを取り扱う. BKWア ルゴリズムは3つのステップからなり,中でもReductionステップでは復号に用いるサンプルを得るために 必要なサンプル数の量がボトルネックとなっているため,限られたサンプルから効率よく処理を行う手法が 研究されている. その中でもRing-BKWアルゴリズムは環の特性を利用することによってサンプル数を増 やすことを可能にした. 本研究では,Ring-BKWアルゴリズムのReductionステップにおいて, 固定されて いたブロックサイズを動的に決定する機構を導入し,復号に用いることができるサンプル数を増加させる新 たな攻撃手法を提案する.
