既知の攻撃法に耐性をもつナップザック暗号

摘要

LLLアルゴリズムを用いる攻撃（LLLアタック）とShamirアルゴリズムを用いる攻撃（Shamirアタック）に耐性をもつナップザック暗号を提案する。LLLアタックは暗号文Cが公開鍵Kの要素k_iの線形和で与えられるときに有効であるが、暗号文Cに公開鍵Kの要素k_iの非線形和を含む場合には、LLLアルゴリズムを適用するための行列の構成が困難になり、解読が困難になる。Shamirアタックは公開鍵Kの各要素k_iが超増加性をもつ場合に有効であるが、公開鍵Kの各要素k_iを、各々、2つに和分解し、2つの公開鍵K_11とK_2の各要素に超増加性がない場合には、超増加性の条件を用いて秘密鍵と同等の超増加数列を求めるShamirアルゴリズムを適用しても、超増加数列を求めることはできない。%We propose a knapsack cryptosystem resisting well-known attacks which use LLL algorithm andrnShamir's algorithm.