低密度攻撃(LDA)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/01/04 10:46 UTC 版)
「Merkle-Hellmanナップサック暗号」の記事における「低密度攻撃(LDA)」の解説
密度が低い場合、高確率で格子の最短ベクトルを求める問題 (最短ベクトル問題, Shortest Vector Problem, SVP) へ帰着できる。最短ベクトル問題は、ユークリッド距離ではRandomized帰着の元でNP困難な問題であることが知られている。また、格子の次元が低い場合、LLLアルゴリズム(Lenstra, Lenstra, Lovasz, 1982)を用いて解けることが多い。 LO法(Lagarias, Odlyzkoにより提案) は，密度の低いナップザック問題への解法。 CLOS法(Coster, LaMacchia, Odlyzko,Schnorrにより提案) は，より密度の高いナップザック問題に対しても有効である改良手法。 (参考：格子_(数学)) (stub)
※この「低密度攻撃(LDA)」の解説は、「Merkle-Hellmanナップサック暗号」の解説の一部です。
「低密度攻撃(LDA)」を含む「Merkle-Hellmanナップサック暗号」の記事については、「Merkle-Hellmanナップサック暗号」の概要を参照ください。
ウィキペディア小見出し辞書の「低密度攻撃」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 低密度攻撃のページへのリンク
