KDDIとKDDI総合研究所は12月26日、次世代暗号(耐量子暗号)として標準化が進められている「Classic McEliece」方式において、これまでは総当たりによる探索での解読には1兆年以上要するとされてきた1409次元の暗号を、わずか29.6時間で解読に成功し、2023年11月13日に世界記録を更新したことを共同で発表した。詳細は、2024年1月23～26日に長崎で開催される「2024年 暗号と情報セキュリティシンポジウム(SCIS2024)」で発表される予定。
1409次元の暗号とは、10の56乗(=1阿僧祇(あそうぎ)=100兆×100兆×100兆×100兆)通りの解の候補が存在し、現在の最速のスーパーコンピュータを用いたとしても、総当たりによる探索で解読するには1兆年以上かかるため、解読困難とされてきた。
今回の挑戦では、まず独自開発の解読アルゴリズムが用いられ、解の候補を10の36乗(1澗(かん)=1兆×1兆×1兆)分の1程度にまで絞り込むことで解読の難しさを引き下げるところからスタート。さらに、約2700万の解読処理を同時に実行できる並列コンピューティング環境を構築。その結果、1409次元のClassic McElieceを29.6時間で解読し、世界記録を樹立した。またこの解読の結果を通じ、1409次元のClassic McElieceの暗号の解読に要する計算量が2の63乗であることが実証され、その暗号強度が突き止められたとした。