Computer Security and Cryptography

11.1 SUBSET SUM AND KNAPSACK PROBLEMS

The original (one-dimensional) knapsack problem is a problem of combinatorial optimization; items of different weights are to be packed into a knapsack (container) of total capacity S.

Given: An integer S and a knapsack vector a = (a₀, a₁, …, a_n−1) of knapsack lengths {a_i},

Find: All solutions of with x_i ∈ {0,1} (0 ≤ i < n).

Different variants of the knapsack problem exist, including

• Bin packing, in which the number or total length of the items to be packed into N > 1 bins (containers) each of capacity b is to be maximized;
• Stock cutting, in which several (one-dimensional) items (e.g., rolls of paper or perhaps extraordinarily long kosher sausages) each of length b are to be cut into pieces of possible lengths {a_i} with minimal wastage;
• The (0,1)-knapsack problem in dimension M > 1 where items of specified shapes of areas (volumes) {a_i} can be packed into an M-dimensional knapsack of total area (volume).

Solutions of these knapsack problems are in general, difficult to obtain and therefore they are candidates for problems that might lead to strong public key cryptosystems as described in Chapter 10. We formulate a (0, 1)-knapsack problem in two guises as shown in Table 11.1. Note that S-SUM{a, b} and K{a, b} are NP-complete.

Proposition 11.1: S-SUM{a, b} and K{a, b} are equivalent.

Proof: Suppose ALG{a, b} is an algorithm whose output is ...