射影格子上のDeepBKZ基底簡約とLWE問題の求解への応用

摘要

近年提案されている格子暗号の多くの方式の安全性はLearning with Errors （LWE）問題の求解困難性に基づいている．一方，LLLやBKZなどの格子基底簡約アルゴリズムはLWE問題を求解する上で必須の技術である．近年，LLLの自然な一般化であるDeepLLL基底簡約をBKZのサブルーチンとして呼ぶ出すDeepBKZ基底簡約アルゴリズムが提案された．BKZに比べて，DeepBKZ基底簡約は小さなブロックサイズでもかなり短い格子べクトルを見つけることができる．本稿では，射影格子上のDeepBKZ基底簡約アルゴリズムを開発する．さらに，その基底簡約アルゴリズムを2016年から公開されているLWEチャレンジ問題の求解に適用し，その求解時間などを報告する．