Knapsack cryptosystems とは

ナップザック暗号システムは、セキュリティがナップザック問題を解決する硬度に基づいている暗号システムです。このようなシステムはかなり長い間存在していましたが、そのようなシステムの多くが壊れていたため、かなり人気がありません。しかしながら、そのタイプの暗号システムは、ポスト量子暗号のための良い候補である。
最も有名なナップザック暗号は、RSA暗号と同じ年に出版された最初の公開鍵暗号システムの1つであるMerkle-Hellman公開鍵暗号です。しかし、このシステムはいくつかの攻撃、Shamirからの攻撃、Adlemanによる攻撃、低密度攻撃によって壊れています。
しかし、現代のナップザック暗号システムが存在し、これまで安全であると考えられていた。その中にはNasako-Murakami 2006がある。
これらのシステムで興味深いのは、攻撃が見つからなかった設定でのナップザック問題は、量子コンピュータでも解決するのが難しいと考えられることです。これは、RSAが大きな整数を因数分解する問題に頼っているため、Shorのアルゴリズムで多項式時間に解決される問題ではありません。