KDDI、耐量子署名の暗号解読において世界記録を達成

September, 11, 2024, 東京--KDDIとKDDI総合研究所は2024年6月27日、暗号解読コンテスト「Challenges for code-based problemsの量子コンピュータに耐性を持つ電子署名方式（耐量子署名）に関する問題において、従来の世界記録であった解よりも4～10倍の計算量を要する、より探索が難しい解の発見に世界で初めて成功した。

今回取り組んだ問題は、電子署名で使用される暗号技術における公開鍵から秘密鍵を計算する問題に相当する。この成果は、標準化が進められている暗号方式が耐量子署名として成り立つためのパラメータを精緻に見積もるために活用される。
KDDIとKDDI総合研究所は、耐量子暗号の実用化に向けた取り組みの一環として、同コンテストに継続して参加している。

今回の成果
KDDIとKDDI総合研究所は2024年6月27日、「Low-weight Codeword問題」において、従来の世界記録であった解よりも4～10倍の計算量を要する、より探索が難しい解の発見に世界で初めて成功した。今回取り組んだ「Low-weight Codeword問題」は、「0」と「1」の二種類の数字で構成される長さ1,280の線形符号において、含まれる「1」の個数（ハミング重み）がより少ない符号語を探索する問題。線形符号内の「1」の個数（ハミング重み）が少なくなるにつれ、条件を満たす解が少なくなるため、解の探索における難易度が向上し、かかる時間も長くなる。

今回、この問題に適したデータ構造を設計して解の探索範囲を大幅に絞りこむとともに、探索処理に最適な並列実装を見いだした。その結果、合計7,600万の探索処理を同時に実行できるようになり、ハミング重み210と209の解の発見に世界で初めて成功した。
従来の世界記録はハミング重み211の解であり、今回の発見はその難易度の高さから世界記録を達成した。またハミング重み210と209の解を、従来の世界記録（ハミング重み211）の解読に要した時間の1/15以下となる、それぞれ22.7時間と64.1時間で求めることに成功した。

今回の解読結果をもとに、耐量子署名として使用が想定されているハミング重み値の秘密鍵の計算時間を推定した結果、量子コンピュータを用いた場合でも10億年程度が必要であることを確認し、その安全性を検証した。今回の成果は、NISTが選定を進めている符号暗号に基づく電子署名方式において、安全性と効率性を両立するパラメータの選択などにも活用される。
(詳細は、https://www.kddi-research.jp)