UCSB has been the site of a meeting dealing with current topics in cryptography starting with CRYPTO ’81 in 1981. Adi Shamir electrified the attendees at CRYFTO ’82 by presenting an analysis of the Merkle–Hellman cryptosystem. A program running on an Apple during his lecture illustrated the solution technique that we now describe.
The mapping Tω−1,m: s = (s0, s1, …, sn−1) → a = (a0, a1, …, an−1) from the super-increasing to the public knapsack vector is nonlinear and this was the basis for believing that the Merkle–Hellman scheme provided a secure public-key encipherment scheme.
For define the modular mapping (function) ϕa,m(w) for 0 ≤ a, w < m (Fig. 11.1) by
where kj is an integer <m. According ...