KDDIおよび九大の研究チーム、「世界で誰にも解読されていない」という暗号問題を初めて解読

　KDDI研究所と九州大学の研究チームが、「これまで誰も解読に成功していなかった」という60次元のLearning with Errors（LWE）問題の解読に成功したと発表した。

　n次元のLWE問題とは、m×nサイズの行列Aとn×1サイズのベクトルbが与えられた場合にA・x＋e＝bを満たすxを求めるというものである。Aおよびe、bがすべて既知であれば単純な問題であるが、LWE問題ではAおよびbのみが与えられ、eについては未知（非公開）であることがポイントとなる。

　現在、この問題を解くためのコンテスト「TU Darmstadt Learning with Errors Challenge」が行われており、KDDI研究所と九州大学だけが解読に成功している状況だ。このコンテストでは次元数およびeの分散が異なる複数の問題が用意されているが、次元数や分散が多いほど解を得るのが難しく、60次元のLWE問題を解いたのは同チームが初めてだという。

　KDDIおよび九州大学が開発した手法についての詳細は明らかにされていないが、分枝限定法という、解を探索しながら条件を満たす解の候補の集合を小さくしていく手法に分類されるもののようだ。

　スラドのコメントを読む | セキュリティセクション | スパコン | セキュリティ | 暗号

　関連ストーリー：
SHA-1はもう安全ではない？　専門家チームが利用廃止の前倒しを提言 2015年10月13日
米大学でBitcoinなどの暗号通貨の活用が進む 2014年09月05日
生物学をモデルにした新しい暗号化方式、クラックはほぼ不可能 2014年04月10日
セキュリティコンテスト「SECCON CTF」第1回開催へ 2012年02月16日