The Knapsack Scheme (Merkle and Hellman, 1978) Given X=(x1,x,,,Xn)and an integer s Finding b=(b, b, .,bn)where b;=0 or 1 such that s=<X,B>=∑b1x NP-Complete in general5 The Knapsack Scheme (Merkle and Hellman, 1978) • Given X = (x1 , x2 ,…, xn ) and an integer s • Finding B = (b1 , b2 ,…, bn ) where bi = 0 or 1 such that s = < X, B> =  bi xi • NP-Complete in general