Merkle-Hellmanナップサック暗号
密度が低い場合、高確率で格子の最短ベクトルを求める問題 (最短ベクトル問題, Shortest Vector Problem, SVP) へ帰着できる。最短ベクトル問題は、ユークリッド距離ではRandomized帰着の元でNP困難な問題であることが知られている。また、格子の次元が低い場合、LLLアルゴリズム(Lenstra, Lenstra, Lovasz, 1982)を用いて解けることが多い。
LO法(Lagarias, Odlyzkoにより提案) は,密度の低いナップザック問題への解法。
CLOS法(Coster, LaMacchia, Odlyzko,Schnorrにより提案) は,より密度の高いナップザック問題に対しても有効である改良手法。
(参考:格子_(数学)) (stub)