Consider a knapsack cipher of the type described in Section 7.6, where the superincreasing sequence is given by a_i = 2^i, and the public weights c_i are a permutation of the (t*a_i)%m. Show how to break this scheme.

7.6 Knapsack Ciphers There is no single 'knapsack cipher', but rather a family of ciphers using the same underlying mathematical problem, the knapsack or subset sum problem. Merkle and Hellman [Merkle, Hellman 1978) first made a cipher of this type. Adi Shamir (Shamir 1982] found a decisive attack. In fact, the progression of attacks and attempts to defeat them is representative of the kind of iterative processes by which real ciphers come into existence. We'll only describe the basic version here and briefly indicate the nature of Shamir's attack. Unfortunately, the number of times that various knapsack ciphers have been found problematical is large enough that many people have lost enthusiasm for them, even though the most improved versions seem not to have been broken. The knapsack problem is: given a list of positive integers di, . ..,an, and given another integer b, find a subset an ". ., aix so that an +...+on =b if this is possible. (Each element aj can be used at most once, although some of the values a; may be the same.) There are variants of this problem: one is to simply tell, for given a;'s and b, whether or not a solutionPublic-Key Ciphers Chapter 7 108 niting that a solution exists, find it. All of these are (provably'?) / P-complete, meaning approximately that it is hard to solve them, bain easy to verify the correctness of a solution. Certainly brute force search adding up all possible ?" subsets of the ay's will take a very long time if n - 300 or go exists. Another is, granting th For convenience of discussion, call a " (attra., as) the knapsack vector, and a the size of the knapsack even longer for n = 4098, for example- The al's which occur in a solution are in the knapsack of size &. A knapsack vector a = (ais.ward-) of length ni can be used to encrypt a vector = = (Fimazza) of bits (0's and I's) by computing a function that in structure resembles a dot product So this amounts to adding up only those among the a's for which the corresponding Ty is 1. Then the size b are transmitted. Decryption consists of finding (7) a subset of the knapsack vector entries which add up to the size. Thus, the decryption step amounts to solving a knapsack problem. knapsack vector a and the size b. We noted above that solving a knapsack problems in general is hard. So we are in the ridiculous situation that authorized as well as unauthorized decryption would in general be hard. Of course, there is the immediate issue of whether there might be more than one possible decryption, which would be bad. So a knapsack vector with the property that for a given size there is at most one solution to the knapsack problem is called Injective. It should not be surprising that with the function Jala)-nato.+Ind mentioned above as the possible decryption function for a string z of n bits, the knapsack vector a = air...dad Is injective if and only if Ja is injective. In particular, this requires that all the an's be different. Based on the N P-completeness of the general knapsack problem, we might be confident of the difficulty of unauthorized decryption of the cipher mentioned above, but as things stand the authorized decryptor has the same difficulties. To make it possible for the authorized decryptor to solve an easier problem (to do the decryption), the plan is to arrange things so that the authorized decryption amounts to solving a much easier rubproblem, which we now describe. A knapsack vector a w (area.xian) is superincreasing if each a, is strictly greater than the sum of the preceding elements in the vector, that is, for every index i al+..-+0-1 Co If the knapsack vector a = (six...its) is superincreasing, then there is a much easier method for solving the knapsack problem with size be . Nbdit..+0-7.7 NTRU Cipher Choosing m to be larger than the sum of the ar's is what causes this procedure sometimes to be called strong modular multiplication. She chooses another number (the multiplier) t relatively prime to m. 109 so that t has a multiplicative inverse modulo m. Then Alice computes =(taj) %m This gives a new knapsack vector c = (cim.,en), which Alice publishes as her public key to the cipher. Alice keeps the ? and m (and the inverse of ( modulo m) secret. For Bob to encrypt a message so that only Alice can read it, the encryption step is similar to what was done before, encrypting an n-bit message b= fe(x) = czy + . .1 4Cuzn first to compute with the altered knapsack vector c. Bob transmits the ciphertext b to Alice. Alice's decryption procedure is t-1 6%mmt-1 (curl +. .. +enza) = (t-ler)z, + . . . + (t-1cm)z, = a121 + . .* +0, In mod m meaning that Since m is larger than the sum of all the a,'s, this equality modulo m is actually an equality of integers, (trib) % m mazi +.. . +0,In ci's by Since Alice knows the superincreasing knapsack vector of a's, or in any case can compute them from the a, =t-1 . ci % m she can easily solve the knapsack problem and decrypt as above. So it would appear that we have a plausible public-key cipher. The legal recipient has a much easier problem to solve than the general knapsack problem, so if an adversary approaches a hostile decryption as a general knapsack problem, it will be hard. Problem: It turns out that an adversary need not find the secret t and m in order to convert the problem into a superincreasing knapsack problem. (And then certainly the adversary need not solve a general knapsack problem.) After all, if an adversary is lucky enough to find any !' and m' so that d' = (t'-ic1 % m',. . it"-1 en % m') is superincreasing, this converts the problem to an easy one, In this vein, Adi Shamir [Shamir 1978] found a way to find a pair (t', m') in polynomial time to convert the published vector to a superincreasing one. This breaks this simplest knapsack cipher. Remark: Note, too, that as it stood this cipher was completely vulnerable to chosen-plaintext attacks