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 a1,a2,an which is a superincreasing sequence. She then picks di=1nai and h comprime with d. Using the euclidean algorithmMathworldPlanetmath, she finds h-1 such that hh-11(mod d).

Alice now generates her public key b1,b2,bn where bi=hai(mod d) and sends this to Bob.

Bob breaks up his message into binary strings of length n. To send the string m1m2mn to Alice, he forms C=i=1nmibi and sends C to Alice.

On receiving C, Alice forms V=h-1C(mod d). Now, since bi=hai(mod d), we have that V=i=1nmiai. Since ai is a superincreasing sequence, it is easy to recover the mi if you know V and ai, and it takes O(n) arithmetic operations.

In 1982, a fast algorithmMathworldPlanetmath 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 bi 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