Merkle-Hellmanナップサック暗号とは、ナップサック問題の難解さを利用した暗号化方法です。

ナップサック問題とは、一番良い答えを見つける手順がごり押ししかない問題の一つです。つまり、最もよい回答を知りえなければ、頑張って見つけるしかありませんが、とてつもなく時間がかかってしまうということです。ナップサック問題の最適解を鍵として扱い、暗号化を行います。

そもそもナップサック問題というのがどういう問題かというと、大きさの異なる複数の荷物をナップサックに入れ込むとき、一番ナップサックを使わない入れ方を考えるものです。荷物は形状を考えませんので、水袋をナップサックに入れると思ってください。

最もナップサックを使わない入れ方を見つけることはできるのですが、早く答えを見つかると言い切れるアプローチがないのです。