抄録
A-022
格子簡約アルゴリズムを用いたナップサック暗号への攻撃についての考察
格子簡約アルゴリズムを用いたナップサック暗号への攻撃についての考察
ナップサック暗号は部分和問題と呼ばれる問題の困難さを安全性の根拠にする暗号である.部分和問題は有名なNP完全問題であるが,密度と呼ばれるパラメータが小さい場合,格子簡約アルゴリズムを用いた攻撃によって効率的に解けることがLagariasらによって示されている.しかしこの方法は近似アルゴリズムのため,問題のサイズが大きくなるとこの手法で解を求めることが難しくなる.
この論文では,この攻撃手法がサイズの大きい問題に対してどの程度有効かを考察する.また,より精度を高めるための方法と,密度が大きい部分和問題への適用についても検討する.
この論文では,この攻撃手法がサイズの大きい問題に対してどの程度有効かを考察する.また,より精度を高めるための方法と,密度が大きい部分和問題への適用についても検討する.
