Merkle-Hellmanナップサック暗号
Merkle-Hellmanナップサック暗号は部分和問題(ナップサック問題の特別なインスタンス)に基づいている。
部分和問題は、整数の列(a1,...,an)と目標となる整数(t)を入力とし、 ∑ i ∈ S a i = t {\displaystyle \sum _{i\in S}a_{i}=t} となる部分集合 S ⊆ { 1 , 2 , . . . , n } {\displaystyle S\subseteq \{1,2,...,n\}} を求める問題(ai でt を合成する問題)である。
一般の部分和問題は、NP完全であることが知られている。しかし、超増加列と呼ばれる数列を用いた場合には、簡単に解けることが分かっている。Merkle-Hellmanナップサック暗号は、合成が簡単にできる超増加列を、見かけ上は合成がむずかしい整数列に変換し、また逆に戻せることに基づいている。超増加列とは、各項がそれまでの全ての項の和よりも大きい数列のことである。
超増加列の例: (1,2,4,8,16)
この暗号方式は発表時から安全性に疑問をもたれていたが、1982年にアディ・シャミア (Adi Shamir) によって一般的解読方法が発見された。これは部分和問題自体を解いたのではなく、超増加列を変換した数列を用いた場合には、どのように変換しても元の超増加という性質が残り、容易に解けることを示したものである。
シャミアの解読以降、多くのナップサック暗号の変形版が提案されているが、そのほとんどが解読可能であることが判明している。
用語については、暗号の用語および暗号理論の用語を参照のこと。
Merkle-Hellmanナップサック暗号とは、1978年にラルフ・マークルとマーティン・ヘルマンが発表したナップサック問題(正確には部分和問題)を利用した公開鍵暗号の一つである。 この暗号方式は、秘匿用途の方式であり、認証(デジタル署名など)を目的としたものではない。
公開鍵暗号の提案は1976年であり、比較的初期に提案された方式である。 1982年に解読方法が発見されたため、現在は使用されていない。 近年になり、鍵の生成に量子コンピュータを用いることにより、量子コンピュータでも解けない暗号として機能することが示され、ふたたび注目を浴びている。