23.7 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

23.7 Exercises

  1. Find a reduced basis and a shortest nonzero vector in the lattice generated by the vectors (58, 19), (168, 55).

    1. Find a reduced basis for the lattice generated by the vectors (53, 88), (107, 205).

    2. Find the vector in the lattice of part (a) that is closest to the vector (151, 33). (Remark: This is an example of the closest vector problem. It is fairly easy to solve when a reduced basis is known, but difficult in general. For cryptosystems based on the closest vector problem, see [Nguyen-Stern].)

  2. Let v1, , vn be linearly independent row vectors in Rn. Form the matrix M whose rows are the vectors vi. Let a=(a1, , an) be a row by v1, , vn, and show that every vector in the lattice can be written in this way.

  3. Let {v1, v2} be a basis of a lattice. Let a, b, c, d be integers with adbc=±1, and let

    w1=av1+bv2, w2=cv1+dv2.
    1. Show that

      v1=±(dw1bw2), v2=±(cw1+aw2).
    2. Show that {w1, w2} is also a basis of the lattice.

  4. Let N be a positive integer.

    1. Show that if j+ki(modN), then Xj+kXi is a multiple of XN1.

    2. Let 0i<N. Let a0, , aN1, b0, , bN1 be integers and let

      ci=j+kiajbk, 

      where the sum is over pairs j, k with j+ki(modN). Show that

      ciXij+kiajbkXj+k

      is a multiple of XN1.

    3. Let f and g be polynomials of degree less than N. Let fg be the usual product of f and g and let fg be defined as in Section 23.4. Show that fgfg is a multiple of XN1.

  5. Let N and p be positive integers. Suppose that there is a polynomial F(X) such that f(X)F(X)1(modp). Show that f(1)0mod  p. (Hint: Use Exercise 5(c).)

    1. In the NTRU cryptosystem, suppose we ignore q and let c=pϕh+m. Show how an attacker can obtain the message quickly.

    2. In the NTRU cryptosystem, suppose q is a multiple of p. Show how an attacker can obtain the message quickly.