Merkle-Hellman scheme

The Merkle-Hellman cryptosystem was one of the earliest examples of public key cryptography, and depends on the NP-complete problem “SUBSET SUM” for its security.

Suppose Bob wants to send Alice a message.

Alice generates private key ${a_{1},a_{2},\dots a_{n}}$ which is a superincreasing sequence. She then picks $d\gg\sum_{i=1}^{n}a_{i}$ and $h$ comprime with $d$ . Using the euclidean algorithm, she finds $h^{-1}$ such that $hh^{-1}\equiv 1\quad(\textrm{mod }d)$ .

Alice now generates her public key ${b_{1},b_{2},\dots b_{n}}$ where $b_{i}=ha_{i}\quad(\textrm{mod }d)$ and sends this to Bob.

Bob breaks up his message into binary strings of length $n$ . To send the string $m_{1}m_{2}\dots m_{n}$ to Alice, he forms $C=\sum_{i=1}^{n}m_{i}b_{i}$ and sends $C$ to Alice.

On receiving $C$ , Alice forms $V=h^{-1}C\quad(\textrm{mod }d)$ . Now, since $b_{i}=ha_{i}\quad(\textrm{mod }d)$ , we have that $V=\sum_{i=1}^{n}m_{i}a_{i}$ . Since ${a_{i}}$ is a superincreasing sequence, it is easy to recover the $m_{i}$ if you know $V$ and ${a_{i}}$ , and it takes $O(n)$ arithmetic operations.

In 1982, a fast algorithm was found for recovering the message knowing only the public key and the cryptogram $C$ . It takes advantage of the fact that the public key ${b_{i}}$ is not generated in a random way, but comes from a superincreasing sequence.

Title	Merkle-Hellman scheme
Canonical name	MerkleHellmanScheme
Date of creation	2013-03-22 15:12:40
Last modified on	2013-03-22 15:12:40
Owner	aoh45 (5079)
Last modified by	aoh45 (5079)
Numerical id	5
Author	aoh45 (5079)
Entry type	Definition
Classification	msc 94A60
Synonym	Merkle-Hellman cryptosystem