knapsack: one construct, many systems

In operations research, the knapsack problem asks which subset of items, each with a value and a weight, should be chosen to maximise total value without exceeding a fixed capacity. Dantzig's 1957 Discrete-variable extremum problems set it among the integer programming problems and gave the bound-based reasoning behind solving it, and it became a canonical example of a combinatorially hard optimisation problem. The referent is a constrained selection problem whose difficulty grows sharply with size, the same structural difficulty that cryptographers later borrowed to try to build a cipher.[1]

Unit

The maximum attainable total value of items packed under a capacity limit

Recovery means

Not applicable

Measured by

Studied through exact and approximate algorithms, worst-case running time, and optimality bounds

In cryptography, the knapsack (or subset-sum) cryptosystem turns the hardness of the same packing problem into a public-key cipher: the private key is an easily solved instance, which is disguised by modular arithmetic into a public instance that looks intractable to anyone without the trapdoor. Merkle and Hellman's 1978 Hiding information and signatures in trapdoor knapsacks proposed exactly this construction, though later cryptanalysis broke it, making it a cautionary case where a hard-on-average assumption proved false. The referent is the identical subset-sum structure of operations research, transposed into a cryptographic trapdoor, which is why the same word carries across both systems.[2]

Unit

The difficulty of recovering the chosen subset from a disguised public instance

Recovery means

Not applicable

Measured by

Assessed by the computational cost of solving the underlying subset-sum instance and by lattice-reduction attacks that break disguised ones