 Chor-Rivest knapsack encryption

The Chor-Rivest scheme is the only known knapsack public-key encryption scheme that does not use some form of modular multiplication to disguise an easy subset sum problem.

8.41 Algorithm Key generation for Chor-Rivest public-key encryption

SUMMARY: each entity creates a public key and a corresponding private key.

Each entity A should do the following:

• 1. Select a finite field Fg of characteristic p, where q = ph, p > h, and for which the discrete logarithm problem is feasible (see Note 8.45(ii>).
• 2. Select a random monic irreducible polynomial f(x) of degree h over Zp (using Algorithm 4.70). The elements of F,; will be represented as polynomials in Zp[x] of degree less than h, with multiplication performed modulo f{x).
• 3. Select a random primitive element g(x) of the field F,; (using Algorithm 4.80).
• 4. For each ground field element i € Zp, find the discrete logarithm a, = logg(X) (x + i) of the field element {x + i) to the base g(x).
• 5. Select a random permutation я on the set of integers {0,1,2,... ,p - 1}.
• 6. Select a random integer d, 0 < d < ph - 2.
• 7. Compute с, = (an(.*) + d) mod (ph1) ,0 < i < p — 1.
• 8. A’s public key is ((со, cb ... , cp^j),p, /г); A’s private key is (f(x),g(x), n, d).
• 8.42 Algorithm Chor-Rivest public-key encryption

SUMMARY: В encrypts a message m for A, which A decrypts.

• 1. Encryption. В should do the following:
• (a) Obtain A’s authentic public key ((со, ci,... , cp_i),p, h).
• (b) Represent the message m as a binary string of length [lg (£)J, where (}') is a binomial coefficient (Definition 2.17).
• (c) Consider m as the binary representation of an integer. Transform this integer into a binary vector M = (Mo, Mi,... , Mp_i) of length p having exactly h l’s as follows:

i. Set h.

ii. For i from 1 to p do the following:

Ifm > (Pj1) then set M,_i<—1, m-s—m - (pJl), U-l - 1. Otherwise, set Mf_i«-0. (Note: (”) = 1 for n > 0; (°) = 0 for / > 1.)

• (d) Compute c = Mc; mod (ph 1).
• (e) Send the ciphertext c to A.
• 2. Decryption. To recover plaintext m from c, A should do the following:
• (a) Compute r = (c — hd) mod (ph 1).
• (b) Compute u(x) = g(x)r mod f(x) (using Algorithm 2.227).
• (c) Compute .s(:r) = u(x) + f(x), a monic polynomial of degree h over Zp.
• (d) Factor s(x) into linear factors over Zp. s(x) = П?=1 (x + where Ь € Zp (cf. Note 8.45(iv)).
• (e) Compute a binary vector M = (M0, Mi,... , Mp_i) as follows. The components of M that are 1 have indices 7r-1(fj), 1 < j < h. The remaining components are 0.
• (f) The message m is recovered from M as follows:

i. Set m<— 0, l<—h.

u. For i from 1 to p do the following:

If M,_i = 1 then set m<-m + (p{"‘) and l*-l - 1.

Proof that decryption works. Observe that Since П?=о (x + 7r(*))Mi and s(a) are monic polynomials of degree h and are congruent modulo /(a), it must be the case that Hence, the h roots of s(x) all he in Zp, and applying тг-1 to these roots gives the coordinates of M that are 1.

8.43 Example (Chor-Rivest public-key encryption with artificially small parameters')

Key generation. Entity A does the following:

• 1. Selects p = 7 and h = 4.
• 2. Selects the irreducible polynomial /(a) = a4 + За3 + 5a-2 + 6a + 2 of degree 4 over Z7. The elements of the finite field F74 are represented as polynomials in Z7[a] of degree less than 4, with multiplication performed modulo f(x).
• 3. Selects the random primitive element д(х) = За3 + За2 + 6.
• 4. Computes the following discrete logarithms: • 5. Selects the random permutation 7r on {0,1,2,3,4,5,6} definedby л-(О) = 6,7г(1) = 4, 7г(2) = 0,7г(3) = 2, 7г(4) = 1, 7г(5) = 5,7г(6) = 3.
• 6. Selects the random integer d = 1702.
• 7. Computes 8. A’s public key is ((cq, ci, C2, сз, c4, c5, ce),p = 7 ,h = 4), while A’s private key is (f(x),g(x),n,d).

Encryption. To encrypt a message m = 22 for Л, В does the following:

• (a) Obtains authentic A’s public key.
• (b) Represents m as a binary string of length 5: m = 10110. (Note that |_lg (4)J = 5.)
• (c) Uses the method outlined in step 1(c) of Algorithm 8.42 to transform m to the binary vector M = (1,0,1,1,0,0,1) of length 7.
• (d) Computes с = (со + сг + сз + ее) mod 2400 = 1521.
• (e) Sends c = 1521 to A.

Decryption. To decrypt the ciphertext c = 1521, A does the following:

• (a) Computes r = (c - lid) mod 2400 = 1913.
• (b) Computes u(x) = 1913 mod f(x) = x3 + 3x2 + 2x + 5.
• (c) Computes s(x) = u(x) + f(x) = x4 + 4x3 + x2 + x.
• (d) Factors s(a;) = x(x + 2)(ж + 3)(a: + 6) (so t = 0, i2 = 2, t\$ = 3, t4 = 6).
• (e) The components of M that are 1 have indices 7г_1(0) = 2,7г_1(2) = 3,7r_1(3) = 6,

and 7г^х(6) = 0. Hence, M = (1,0.1,1,0,0.1).

(f) Uses the method outlined in step 2(f) of Algorithm 8.42 to transform M to the integer

m = 22, thus recovering the original plaintext. □

• 8.44 Note (security of Chor-Rivest encryption)
• (i) When the parameters of the system are carefully chosen (see Note 8.45 and page 318), there is no feasible attack known on the Chor-Rivest encryption scheme. In particular, the density of the knapsack set (co,ci,... , cp {) is p/ lg(maxcj), which is large enough to thwart the low-density attacks on the general subset sum problem (§3.10.2).
• (ii) It is known that the system is insecure if portions of the private key are revealed, for example, if g(x) and d in some representation of F,; are known, or if f(x) is known, or if я- is known.
• 8.45 Note (implementation)
• (i) Although the Chor-Rivest scheme has been described only for the case p a prime, it extends to the case where the base field Zp is replaced by a field of prime power order.
• (ii) In order to make the discrete logarithm problem feasible in step 1 of Algorithm 8.41, the parameters p and h may be chosen so that q = ph - 1 has only small factors. In this case, the Pohlig-Hellman algorithm (§3.6.4) can be used to efficiently compute discrete logarithms in the finite field F4.
• (iii) In practice, the recommended size of the parameters are p w 200 and h « 25. One particular choice of parameters originally suggested is p = 197 and h = 24; in this case, the largest prime factor of 19724 - 1 is 10316017, and the density of the knapsack set is about 1.077. Other parameter sets originally suggested are {p = 211, h = 24}, {p = 35, h = 24} (base field F3s), and {p = 2®, h = 25} (base field F2s).
• (iv) Encryption is a very fast operation. Decryption is much slower, the bottleneck being the computation of u(x) in step 2b. The roots of s(x) in step 2d can be found simply by trying all possibilities in Zp.
• (v) A major drawback of the Chor-Rivest scheme is that the public key is fairly large, namely, about (ph ■ lgp) bits. For the parameters p = 197 and h = 24, this is about 36000 bits.

(vi) There is message expansion by a factor of lg ph / lg (£). For p = 197 and h = 24, this is 1.797.