正則な格子における最近傍格子点問題の複雑さについて

摘要

格子暗号技術は整数論上の問題である素因数分解問題と離散対数問題のどちらにも依存しない暗号系として近年注目を集めている．格子暗号系は最短ベクトル問題や最近傍格子点問題という格子上の問題にその安全性を依存している．これらの問題はNP困難であることが知られており，またその近似問題についても多くの研究が行われている．しかし，実際の暗号系に用いられる格子は構造上の特徴があるため，その特徴を利用してそれらの問題を効率的に解く方法が存在する可能性もある．本論文では最近傍格子点問題の複雑さについて，格子構造の観点からアプローチするという新たな試みを行い，格子の基底行列を正則行列に制限してもその難しさがNP困難であることを示す．