低密度多重選択ナップザック暗号

摘要

Merkle とHellman のナップザック暗号は，Lagarias-Odlyzko の低密度攻撃（LO 法）に対して弱い．LO 法への耐性を強めた改良方式の一つとして，“低密度暗号”がある．その特徴は秘密鍵乗数と暗号化乗数という2つの系列を有し，低密度ながらLO 法に耐性を有することである．本報告は，この低密度暗号において平文を2値でなく多情系列とするナップザック暗号を提案し，計算機実験により特性を調べるものである．%The knapsack cryptosystem invented by Merkle and Hellman is known to be insecure against the low density attack by Lagarias-Odlyzko (LO method). The "low density knapsack cryptosystem" is the one among various improved knapsack systems. In this report we propose a multiple choice knapsack version of the above system, and investigate its properties by computer experiments.