# 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 MerkleHellmanScheme 2013-03-22 15:12:40 2013-03-22 15:12:40 aoh45 (5079) aoh45 (5079) 5 aoh45 (5079) Definition msc 94A60 Merkle-Hellman cryptosystem