2つの演算を用いるナップザック暗号（その2）

摘要

We propose a knapsack cryptosystem using two operations addition and multiplication. This knapsack cryptosystem is proof against Shamir attack and LLL attack. This knapsack cryptosystem is possible high speed processing, but these key sizes grow big.%暗号化に和と横の2つの演算を用いるナップザック暗号を捉案する。秘密鍵は和と横の非線形演算で求められる密度の非常に低い超増加数列（以下、極超増加数列と呼ぶ）であり、これをモジュラー変換して公開鍵を生成する。平文を2進ベクトルで表すとき、暗号化は平文を1の要素を少なくとも1つ含む任意の偶数個に分割し、それらに対応する公開鍵の各々の和を2つずつ掛け合せ、それらすべてを加える。復号は秘密鍵の極超増加性を用いて一意に行う。鍵生成と暗号化に非線形演算を用いているため、線形問題の解法に適したShamirアルゴリズムやLLLアルゴリズムを本暗号に適用することは難しく、これらに対しては耐性をもつ。本暗号は高速な暗号処理が可能であるが、鍵のサイズが大きくなる。