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