hi does anyone know about lattices and lattice based encryption

CO3326 Coursework assignment 1: Lattice-based Cryptography

Within the last twenty years new methods of cryptography have been developed, based on problems de- fined on integer lattices. These methods are too new to appear in your subject guide but have many features in common with those you are studying: hashing, asymmetric encryption, modular arithmetic, etc. This coursework assignment and Coursework assignment 2 aim to reinforce your understanding of these concepts while introducing you to some of the latest research in the area. Please note:

• You are expected to spend between 15 and 30 hours completing this coursework assignment. • Question 2 of this coursework assignment uses modular arithmetic (see the first page of Section 7.4

of the subject guide); Question 3 discusses hashing (see the first two sections of Chapter 6). If you have yet to reach this material in your study of the module do not worry — it will do no harm to read ahead a little!

An integer lattice consists of a pair of points, P and Q, in the xy plane, together with all weighted sums αP + βQ where α and β are integers. By making sure that P and Q do not lie in a straight line with O, the origin, this gives an infinite collection of points which covers the whole plane in a ‘regular’ manner. The most obvious example is the lattice of all integer points (0, 0), (1, 0), (0, 1), (1, 1, ), (0, 2), . . .. For this we might take P = (1, 0) and Q = (0, 1); then the point (4,−2), for example, is included in the lattice by choosing α = 4 and β = −2, to get 4 × (1, 0) + −2 × (0, 1) = (4, 0) + (0,−2) = (4,−2). A less obvious example uses P = (3, 1) and Q = (1, 2), as shown in Fig. 1 below. Even less obvious is the fact that P′ = (5, 5) and Q′ = (14, 13) generate the same lattice. Certainly they do lie in the lattice, as is clear from the figure.

Figure 1: the integer lattice generated by P = (3, 1) and Q = (1, 2) (heavy arrows) and also by P′ = (5, 5) and Q′ = (14, 13) (thin arrows).

Question 1 [Total marks: 20]

(a) Find integers α and β for which α×(5, 5) + β×(14, 13) = (1, 2); and integers γ and δ for which γ× (5, 5) + δ× (14, 13) = (3, 1). [6]

(b) Use your answer to part (a) to write down a formula for expressing a general point a(3, 1) + b(1, 2) in terms of P′ = (5, 5) and Q′ = (14, 13). [5]

2

(c) (i) Check that your formula in part (b) works for (3, 1) and (1, 2). [4] (ii) Use your formula to show that (61, 22) lies in the lattice generated by P′ = (5, 5) and

Q′ = (14, 13). [5]

3

Question 2 [Total marks: 30] Now we have established the idea of an integer lattice we investigate a lattice problem which is believed to be hard to solve, the Shortest (Nonzero) Vector Problem: given a lattice find the nonzero lattice point whose distance from the origin is least. The distance of (x, y) from the origin is defined to be

√ x2 + y2. This can be thought of as the length of an arrow (vector)

from the origin to (x, y).

(a) For the lattice in Fig. 1, find (i) the distances from the origin of the four points (vectors) indicated by the arrows; [8]

(ii) the shortest nonzero vector for this lattice. [4] (b) Suppose that an integer lattice is generated by (7, 7) and (14, 13). Show that the shortest

nonzero vector in this lattice has length 1. Compare this result with the shortest nonzero vector for the lattice of Fig. 1: what does it suggest in terms of the difficulty of finding a shortest vector in a given lattice? [10]

(c) Now we construct a particular kind of lattice for which it can be proved that the Shortest Vector Problem is hard. Thus: if q is an integer then the equation

ax + by = 0 mod q,

defines a lattice called a q-ary lattice. The definition is as follows: 1. Solution 1: take x = q, y = 0. This gives a first point for our lattice: (q, 0) 2. Solution 2: take x = b mod q and y = −a mod q. This gives a second point for our lattice:

(b mod q,−a mod q). (i) Apply this procedure to find the two lattice points given by the equation [4]

14x + 13y = 0 mod 5.

(ii) Show that these points give the lattice of Fig. 1 (that is, repeat the calculation of Ques- tion 1(a) for these points). [4]

Question 3 [Total marks: 50] Now we apply our 5-ary lattice from Question 2(c) in a cryptographic application. A hash function h (see subject guide, Chapter 6) maps a message m of arbitrary size to a reduced- size ‘digest’ h(m). This digest is intended to act as a certificate of authenticity of m:

1. if Alice sends m and h(m) to Bob then Bob can recompute h(m) and check he gets the same output. If Charles has changed m to m′ then the hash function output will be different unless Charles can find a collision: h(m′) = h(m) even though m′ , m;

2. Alice cannot repudiate her message m by subsequently claiming that her message was m′ unless, again, she can find a collision.

We will see that q-ary lattices give provably collision-resistent hashing. We choose integers q, a and b. Our hash function (presented by Miklós Ajtai in a breakthrough paper in 1996) is a 2-variable function: h(x, y) = ax + by mod q.

(a) For q = 5, a = 14, b = 13, compute h(17, 8), h(21, 16) and h ( (17, 8) − (21, 16)

) . [9]

(b) What do you deduce from your answer to part (a) about the point (17, 8) − (21, 16), regarding the 5-ary lattice you constructed in Question 2(c)? [10]

(c) What do you deduce about collisions in the hash functions h(x, y) and the Shortest Vector Problem, and what does this tell you about the hash function? [10]

(d) Use your hash function from part (a) and the decimal ASCII codes: A=65, B=66,. . . , Y=89, Z=90 and ‘space’=32 to produce a digest of the message “SELL RIO HOLDING”, consisting of 8 digits modulo 5. [21]

End of Coursework assignment 1

4