Merkle-Hellmanナップサック暗号とは、1978年にラルフ・マークルとマーティン・ヘルマンが発表したナップサック問題（正確には部分和問題）を利用した公開鍵暗号の一つである。この暗号方式は、秘匿用途の方式であり、認証（デジタル署名など）を目的としたものではない。公開鍵暗号の提案は1976年であり、比較的初期に提案された方式である。1982年に解読方法が発見されたため、現在は使用されていない。近年になり、鍵の生成に量子コンピュータを用いることにより、量子コンピュータでも解けない暗号として機能することが示され、ふたたび注目を浴びている。Merkle-Hellmanナップサック暗号は部分和問題（ナップサック問題の特別なインスタンス）に基づいている。部分和問題は、整数の列（"a"...,"a"）と目標となる整数（"t"）を入力とし、formula_1となる部分集合formula_2を求める問題（"a" で"t" を合成する問題）である。一般の部分和問題は、NP完全であることが知られている。しかし、超増加列と呼ばれる数列を用いた場合には、簡単に解けることが分かっている。Merkle-Hellmanナップサック暗号は、合成が簡単にできる超増加列を、見かけ上は合成がむずかしい整数列に変換し、また逆に戻せることに基づいている。超増加列とは、各項がそれまでの全ての項の和よりも大きい数列のことである。この暗号方式は発表時から安全性に疑問をもたれていたが、1982年にアディ・シャミア (Adi Shamir) によって一般的解読方法が発見された。これは部分和問題自体を解いたのではなく、超増加列を変換した数列を用いた場合には、どのように変換しても元の超増加という性質が残り、容易に解けることを示したものである。シャミアの解読以降、多くのナップサック暗号の変形版が提案されているが、そのほとんどが解読可能であることが判明している。用語については、暗号の用語および暗号理論の用語を参照のこと。"n" ビットの平文を暗号化するために、まず"n" 個の数からなる超増加列を生成する（"n" はセキュリティパラメータであり、100ビット以上の数にすることが推奨されている）。次に、整数"q" を "q"  > formula_3を満たすようにランダムに選ぶ。更に、整数 "r" を gcd("r

出典:wikipedia