1978 年に Merkle と Hellman が発明した 部分和問題の難しさを利用した公開鍵暗号です。
【鍵生成】
Bob は 超増加数列 (s1, s2, ..., sn) を生成し,この数列全ての和よりも大きい法 P と、
P と互いに素な秘密の整数 w を用いて、数列 (a1, a2, ..., an) に変換し、この数列を公開する。
P > s1 + s2 + ... + sn, gcd(w,P)=1
ai = w si mod P
( i = 1,2, ..., n)
【暗号化】
Alice は Bob の 暗号化鍵 (s1, s2, ..., sn) を入手する。
Alice は nビットの平文 (m1, m2, ..., mn) を次式により暗号文 C に暗号化する。
C = a1m1 + a2m2 + ... + anmn
【復号】
Bob は 暗号文 C を w-1 倍して P で割った余りを中間平文 M とし、
超増加数列の性質を利用して大きい方(sn )から順に引けるか否かを判定し、
平文 (m1, m2, ..., mn) を復号する。
M = w-1 C mod P, M → (m1, m2, ..., mn)