Transcript No Slide Title

TCS Forum the 9th of November 2007
Professor Jorma Jormakka
PhD in Mathematics University of Helsinki
2000 - 2004 Professor, Networking laboratory,
Department of Electrical Engineering, TKK
2000
Professor, National Defence University
On existence of polynomial-time algorithms for the
Merkle-Hellman knapsack problem
Helsinki University of Technology
Laboratory for Theoretical Computer Science
1/2
Merkle-Hellman Knapsack Cryptosystem
 An asymmetric-key cryptosystem
 Unlike RSA, the public key is used only for encryption, and the
private key is used only for decryption.
 The Merkle-Hellman system is based on the subset sum problem:
given a list of numbers and a third number, which is the sum of a
subset of these numbers, determine the subset.
 Subset sum problem is known to be NP-complete.
 If the set of numbers is super-increasing, that is, each element of the
set is greater than the sum of all the numbers before it, the problem is
'easy' and solvable in polynomial time with a simple greedy algorithm.
 Private key is composed of a super-increasing set of numbers, and a
multiplier and a modulus, which are used to convert the easy subset
sum problem to a difficult one.
 Public key is the difficult subset sum problem.
Helsinki University of Technology
Laboratory for Theoretical Computer Science
2/2