Merkle-Hellmanナップサック暗号

ウィキペディア

Merkle-Hellmanナップサック暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/03 15:37 UTC 版)

Merkle-Hellmanナップサック暗号とは、1978年にラルフ・マークルとマーティン・ヘルマンが発表したナップサック問題（正確には部分和問題）を利用した公開鍵暗号の一つである。 この暗号方式は、秘匿用途の方式であり、認証（デジタル署名など）を目的としたものではない。

公開鍵暗号の提案は1976年であり、比較的初期に提案された方式である。 1982年に解読方法が発見されたため、現在は使用されていない。 近年になり、鍵の生成に量子コンピュータを用いることにより、量子コンピュータでも解けない暗号として機能することが示され、ふたたび注目を浴びている。

概要

Merkle-Hellmanナップサック暗号は部分和問題（ナップサック問題の特別なインスタンス）に基づいている。

部分和問題は、整数の列（a₁,...,a_n）と目標となる整数（t）を入力とし、 $\sum _{i\in S}a_{i}=t$ カテゴリ