ランダム符号付きナップザック暗号

摘要

The knapsack cryptosystem invented by Merkle and Hellman is broken with high probability by Shamir's attack. A novel cryptosystem makes use of a randomly signed super-increasing sequence in the sense of absolute valeu. Owing to this random signs, Shami'r attack is not fully applicable. We describe the key generation method, algorithms of encryption and decryption of the system. The present system is as weak as the MH system against the low density attack of Lagarias and Odlyzko. We wilnot consider this problem in tis report.%Merkle-Hellmanのナップザック暗号は，秘密鍵に超増加列を使い，これに秘密の乗数と法と用いて公開鍵を生成する.この構成法の弱点をつく攻撃法にShamirの方法がある.本報告では，絶対値が超増加な正負の整数列を用いる.こうしてShamirの方法の適用を難しくする.この新しい方式についての鍵生成法，暗号化法，復号法について述べる.Lagarias-Odlyzkoの低密度攻撃に対しては別の対策が必要であり，本報告では述べない.