Mathematical Background on Lattices - A Deep Dive on Lattice-Based Cryptography

#cryptography #lattices

Table of Contents

This is the first post in the series: A Deep Dive on Lattice-Based Cryptography. We focus on lattices as an independent mathematical concept and its properties. However, we focus on aspects that would be useful in the study of Lattice-based Cryptography.

Throughout this series, we use 2-dimensions and 3-dimensions because they are easy to work with. In practice we use sufficiently higher dimensions.

The only prequisite to start this series is to understand the following:

  • R\mathbb{R} represents the set of all real numbers.
  • Z\mathbb{Z} represents the set of all integers.
  • Q\mathbb{Q} represents the set of all rational numbers.
  • Rn\mathbb{R}^n represents the set of all n-dimensional real vectors
  • Zn\mathbb{Z}^n represents the set of all n-dimensional integer vectors

What is a Lattice?

A Lattice LL is an infinite set of vectors v\mathbf{v} constructed based two condition: discreteness and additivity.

Formally, an nn-dimensional lattice LL is a discrete additive subgroup of Rn\mathbb{R}^n generated by a basis B={b1,b2,,bn}B = \lbrace b_1, b_2, …, b_n\rbrace as an integer linear combination: L=L(B):={i=1nzibi:ziZ}L = L(B):= \lbrace\sum_{i = 1}^{n}z_ib_i: z_i \in \mathbb{Z}\rbrace

where ziz_i is an arbitrary integer Z\mathbb{Z}

  • discrete: This means that every vector point vL\mathbf{v} \in L has some “neighborhood” in which v\mathbf{v} is the only lattice point. Loosely speaking, this means that, for every point v\mathbf{v} there is “good space” around it. By using an integer linear combination and not just linear combination we have achieve reasonable discreteness between vector points. This is shown below using rationals Q\mathbb{Q} as a counter example.
  • additive subgroup: a lattice LL is an additive subgroup if it contains identity element 0Rn0 \in \mathbb{R}^n(the zero vector), and if for any v,wL\mathbf{v}, \mathbf{w} \in L, we have v,wL-\mathbf{v}, -\mathbf{w} \in L and v+wL\mathbf{v} + \mathbf{w} \in L

Below, we will see what a lattice is and what it is not.

  • The singleton set {0}Rn\lbrace 0\rbrace \in \mathbb{R}^n is a lattice LL(for any positive integer nn). That is, the zero vector in any dimension is a lattice.

png

png

  • The integers ZR\mathbb{Z} \in \mathbb{R} form a 1-dimensional lattice LL.

png

png

png

png

png

  • The integer grid ZnRn\mathbb{Z}^n \in \mathbb{R}^n is an n-dimensional lattice

png

png

  • The set {xZn:i=1nxi2Z}\lbrace x ∈ \mathbb{Z}^n : \sum_{i=1}^nx_i ∈ 2\mathbb{Z}\rbrace is a lattice; it is often called the “checkerboard” or “chessboard” lattice, especially in two dimensions. It contains all nn-vectors of integers x=(x1,x2,,xn)Zx = (x_1, x_2,…,x_n) \in \mathbb{Z} such that the sum of the components of xx, i.e i=1xi\sum_{i = 1}^{x_i}, is an even integer. That is, the sum of elements in the vector is an even integer.

    The opposite is not true. That is {xZn:i=1nxi2Z+1}\lbrace x ∈ \mathbb{Z}^n : \sum_{i=1}^nx_i ∈ 2\mathbb{Z} + 1\rbrace is not a lattice. Although it is discrete, it is not an additive subgroup of Rn\mathbb{R}^n mainly because it doesn’t contain the identity element 0Rn0 \in \mathbb{R}^n(the all-zeros vector) as shown in non-example diagram below. Recall, that a lattice LL is an additive subgroup if it contains identity element 0Rn0 \in \mathbb{R}^n, and if any v,wL\mathbf{v}, \mathbf{w} \in L, we have v,wL-\mathbf{v}, -\mathbf{w} \in L and v+wL\mathbf{v} + \mathbf{w} \in L.

    Example: (0,0),(1,1),(2,4),(3,5),(2,2)(0,0),(1,1),(2,4),(−3,5),(−2,−2)

    Non-example(opposite): (1,0),(2,3),(1,2)(1,0),(2,3),(−1,2)

  • Example 1: Just even integers

png

png

  • Example 2: random 2-tuples and 3-tuples with sum of even integer

png

png

  • Non-example: random 2-tuples and 3-tuples with sum of odd integer

png

png

  • The rationals QR\mathbb{Q} \subset \mathbb{R} do not form a lattice, because although they form a subgroup, it is not discrete: there exist rational numbers that are arbitrarily close to zero.

    For two arbitrary rational numbers r1r_1 and r2r_2, where r1<r2r_1 \lt r_2 there are inifinitely many rational numbers between them therefore making it impossible for either r1r_1 and r2r_2 to be discrete.

    For example, below is a graph of points in Q\mathbb{Q} between 1 and 2.

png

png

  • The odd integers 2Z+12\mathbb{Z} + 1 do not form a lattice, because although they are discrete, they do not form a subgroup of R\mathbb{R}.

    The odd integers 2Z+12\mathbb{Z} + 1 do not contain 0


Basis

A basis B={b1,b2,,bn}RnB = \lbrace b_1, b_2, …, b_n\rbrace \subset \mathbb{R}^n of a lattice LL is a set of linearly independent vector whose integer linear combinations generate the lattice:L=L(B):={i=1nzibi:ziZ}L = L(B):= \lbrace\sum_{i = 1}^{n}z_ib_i: z_i \in \mathbb{Z}\rbrace

Recall two vectors b1b_1 and b2b_2 are said to be linearly independent if wib1b2w_i * b_1 \neq b_2 and wjb2b1w_j * b_2 \neq b_1 where wi,wjw_i, w_j is an arbitrary integers.

For example, b1=[1,2,3]b_1 = [1, 2, 3] and b2=[5,3,7]b_2 = [5, 3, 7] are linearly independent while b3=[1,2,3]b_3 = [1, 2, 3] and b4=[2,4,6]b_4 = [2, 4, 6] are not. Why? w1b3=b4w_1 * b_3 = b_4 and w2b4=b3w_2 * b_4 = b_3 where w1w_1 and w2w_2 are 22 and 12\dfrac{1}{2} respectively. But, we can’t find any wiw_i for which wib1=b2w_i * b_1 = b_2 and vice versa.

In general, the vectors B={b1,b2,,bn}B = \lbrace b_1, b_2, …, b_n\rbrace are said to be linearly independent if for any vector bib_i in the set, it cannot be generated by the linear combination of one, some or all of the other vectors in the set. That is, c1b1+c2b2++cmbmbic_1b_1 + c_2b_2 + … + c_mb_m \neq b_i where mm is an arbitrary natural number.

We can also represent a basis BB as a matrix. This is an nnn*n matrix where the basis vectors are the ordered columns of the matrix. This is a non-singular matrix.

With this we can represent a lattice L=BZn={Bz:zZn}L = B * \mathbb{Z}^n = \lbrace Bz: z \in \mathbb{Z}^n \rbrace

For example, given a basis B={b1,b2,b3}B = \lbrace b_1, b_2, b_3\rbrace where b1=[1,0,0]b_1 = [1, 0, 0], b2=[0,1,0]b_2 = [0, 1, 0] and b3=[0,0,1]b_3 = [0, 0, 1] respectively, we have a matrix B=[100010001]B = \begin{bmatrix} 1 & 0 & 0\\[0.3em] 0 & 1 & 0\\[0.3em] 0 & 0 & 1 \end{bmatrix} and the finite set of integer vectors z={v1,v2,v3}z = \lbrace v_1, v_2, v_3 \rbrace where v1=[1,2,5]v_1 = [1, 2, 5], v2=[5,7,9]v_2 = [-5, 7, 9] and v3=[9,3,7]v_3 = [-9, 3, 7] respectively, we can generate a lattice LL with three points [1,2,5][1, 2, 5], [5,7,9][-5, 7, 9] and [9,3,7][-9, 3, 7].

This way of representing the basis is instrumental in understanding the next topic: unimodular matrix

Unimodular Matrix

Bases B1B_1, B2B_2 generate the same lattice LL if and only if there exists a unimodular UZn×nU \in \mathbb{Z}^{n \times n} such that B1=B2UB_1 = B_2U.

An integer matrix is said to be unimodular if it determinant is ±1\pm1.

This property of two bases being able to generate the same lattice LL and some bases been better than others is what makes lattice-based cryptography possible. We will take about good and bad bases below.

We can efficiently test whether two given matrices B1B_1, B2B_2 generate the same lattice, by checking whether B11B2B_1^{-1}·B_2 is unimodular.


Norms

A norm or vector norm is a generalization of what we would normally call the length or magnitude of a vector.

Recall, v=v12+v22+v32+.+vn2||{\mathbf{v}}|| = \sqrt{v_1^2 + v_2^2 + v_3^2 + …. + v_n^2}, the magnitude or length or size of a vector v{\mathbf{v}}. This is a type of norm called the Euclidean norm v2||\mathbf{v}||_2.

Formally, a norm on a vector space VV over R\mathbb{R} or C\mathbb{C} is a function .:VR||.||:V \to \mathbb{R} that satisfies the properties for all vectors v\mathbf{v}, w\mathbf{w} \in VV and all scalars α\alpha:

  1. Non-negativity: v0||\mathbf{v}|| \geq 0, and v=0    v=0||\mathbf{v}|| = 0 \iff \mathbf{v} = 0

  2. Homogeneity: αv=αv||\alpha \mathbf{v}|| = |\mathbf{\alpha}|||\mathbf{v}||

  3. Triangle Inequality: v+wv+w||\mathbf{v} + \mathbf{w}|| \leq ||\mathbf{v}|| + ||\mathbf{w}||

For example, the Euclidean norm for the vector v=[3,4]\mathbf{v} = [3, 4] is v2=32+42=9+16=25=5||\mathbf{v}||_2 = \sqrt{3^2 + 4^2} = \sqrt{9 + 16} = \sqrt{25} = 5.

The graphical representation is displayed below. The length of the arrow is 55.

This graph would help us understand the next topic: ii-th successive minimum

png

Other norms include the Manhattan Norm, Maximum Norm and p-norm. For now, we only care about Euclidean norms.


Successive Minimum

The Euclidean Norm v2||\mathbf{v}||_2 of any vector v\mathbf{v} in a lattice LL can be interpreted as the radius rr of a circle (or sphere in higher dimensions) where the origin (0,0)(0, 0) of the graph is the centre of the circle as shown in the diagram below.

png

Given a lattice LL and a norm(i.e. the Euclidean norm), the ii-th successive minimum λi(L)\lambda_i(L) is the smallest radius rr such that LL contains at least ii linearly independent lattice vectors of norm at most rr within a ball of radius rr centered at the origin.

In other words, what is the smallest radius rr such that we can find ii linearly independent vectors v1,v2,,vi\mathbf{v_1}, \mathbf{v_2}, …, \mathbf{v_i} inside the circle(or sphere) with radius rr? Recall, that we interpret the norm of a vector as a radius rr when the centre is at the origin (0,0)(0, 0).

For example, if we generate the vectors v1=[4,2]\mathbf{v_1} = [4, 2], v2=[5,5]\mathbf{v_2} = [-5, -5] and v3=[2,11]\mathbf{v_3} = [2, 11] given the basis points b1=[2,1]\mathbf{b_1} = [2, 1] and b2=[1,3]\mathbf{b_2} = [1, 3] creating a lattice LL, what is the 1st successive minimum λ1(L)\lambda_1(L)? Or, What is ii-th successive minimum when ii is 1?

We start by finding the norm of the vectors(including the basis vectors):

  • b12=22+12=4+1=5=2.24||\mathbf{b_1}||_2 = \sqrt{2^2 + 1^2} = \sqrt{4 + 1} = \sqrt{5} = 2.24
  • b22=12+32=1+9=10=3.16||\mathbf{b_2}||_2 = \sqrt{1^2 + 3^2} = \sqrt{1 + 9} = \sqrt{10} = 3.16
  • v12=42+22=16+4=20=4.47||\mathbf{v_1}||_2 = \sqrt{4^2 + 2^2} = \sqrt{16 + 4} = \sqrt{20} = 4.47
  • v22=52+52=25+25=50=7.07||\mathbf{v_2}||_2 = \sqrt{-5^2 + -5^2} = \sqrt{25 + 25} = \sqrt{50} = 7.07
  • v32=22+112=4+121=125=11.18||\mathbf{v_3}||_2 = \sqrt{2^2 + 11^2} = \sqrt{4 + 121} = \sqrt{125} = 11.18

The smallest norm is 2.242.24 and if we draw a circle using this norm as the radius, we find the linearly independent vector b1=[2,1]\mathbf{b_1} = [2, 1] within the circle. Therefore, 2.242.24 is the the 1st successive minimum.

Notice how it is the closest vector to the origin. It is called the smallest nonzero vector in the lattice. Take note of this, we discuss this later in the series.

png

Good and Bad Bases

Given two bases B1=[1,0],[0,1]B_1 = { [1, 0], [0, 1] } and B2=[10,1],[9,1]B_2 = {[10, 1], [9, 1] } that generate the same lattice(see unimodular matrix), below they are labelled on the lattice they generate respectively.

png

png

If you are given basis B1B_1 and this lattice, and you are asked to find the first successive minimum λ1\lambda_{1}, it’s very easy to see that B1B_1 is the answer because it obviously has the smallest norm. But then, what if you are given only B2B_2 and this lattice and you asked to find the first successive minimum λ1\lambda_1, how hard could this be?

You can already see that this is a search problem and it gets harder to solve as the dimension increases. This is in two dimensions so it’s easy to solve but in practice we work in extremely higher dimensions.

That is the point of good and bad bases. Given a good basis it’s easy to find λ1\lambda_1 but it’s extremely hard to find given a bad basis.

Formally, we check that a basis is good or bad using the following:

  • Good bases are close to being orthogonal: Two vectors v,w\mathbf{v}, \mathbf{w} are orthogonal if their dot product is zero (i.e v.w=0\mathbf{v} . \mathbf{w} = 0). For example:
    • For B1B_1, [1,0].[0,1]=0[1, 0].[0, 1] = 0. This is called perfect orthogonality.
    • For v1=[2,1]v_1 = [2, 1] and v2=[1,3]v_2 = [1, 3], v1.v2=5v_1.v_2 = 5. This is not the “best basis” but it’s nothing close to a bad basis. Wait until you see that of B2B_2
    • For B2B_2, [10,1].[9,1]=91[10, 1].[9, 1] = 91. Now, this is not close to being orthogonal.
  • Bad bases have large Gram-Schmidt Norms: I won’t go into details of Gram-Schmidt Norms but keep this in mind.

Back to understanding successive minimum.

Successive Minimum (Cont’d)

Again, what is the 2nd successive minimum? We are looking for the smallest radius(i.e norm) that creates a circle containing two linearly independent vectors.

From the computed norms, we know that the second smallest vector is b2=[1,3]\mathbf{b_2} = [1, 3] with norm of 3.163.16. Drawing a circle using this norm as the radius, the circle contains b1\mathbf{b_1} and b2\mathbf{b_2}. Therefore, 3.163.16 is the 2nd successive minimum.

png

Thirdly, what is the 3rd successive minimum?

Probably 4.474.47, the third smallest norm. It turns out this is not the case. They are not linearly independent because v1\mathbf{v_1} was generated by b1b_1 and b2b_2 therefore there are only two linearly independent vectors(i.e b1\mathbf{b_1} and b2\mathbf{b_2}) in the circle with radius 4.474.47.

png

How about 7.077.07? The fourth smallest norm. This is still not the 3rd successive minimum for the same reason as before, v2\mathbf{v_2} was generated by b1\mathbf{b_1} and b2\mathbf{b_2} therefore the circle with radius 7.077.07 contains only two linearly independent vectors.

png

And, lastly, how about 11.1811.18? The largest norm. Is it the 3rd successive minimum? No, it’s not. For the same reason as before.

png

With this, it is safe to say the 3rd successive minimum and above does not exist because all other vectors were generated by the basis points b1\mathbf{b_1} and b2\mathbf{b_2}.

In general, the maximum ii in the ii-th successive minimum is the number of basis vectors.

It’s important to point out that a lattice LL might have multiple basis vectors and this is an instrumental property of lattices that makes certain types of lattice-based cryptography possible.


Fundamental domains and parallelepipeds

In order to understand fundamental domain and parallelepipeds, here’s a quick crash course on abstract algebra.

A group is a set GG with an operation * that satisfies four properties:

  • Closure: if aa, bGb \in G, then abGa * b \in G
  • Associativity: (ab)c=a(bc)(a * b) * c = a * (b * c) for all a,b,cGa, b, c \in G
  • Identity Element: There exists an element iGi \in G such that ia=ai=ai * a = a * i= a for all aGa \in G
  • Inverse Element: For every aGa \in G, there exists an element a1Ga^{-1} \in G such that aa1=a1a=ia * a^{-1} = a^{-1} * a = i(the identity element)

Example of a group:

  • The set of integers Z\mathbb{Z} under the operation, addition ++ forms a group:
    • Closure: if a,bZa, b \in \mathbb{Z}, then a+bZa + b \in \mathbb{Z}. For example, 1+5=61 + 5 = 6
    • Associativity: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). For example, (5+3)+9=5+(3+9)(5 + 3) + 9 = 5 + (3 + 9)
    • Identity: The number 00 satisfies 0+a=a+0=a0 + a = a + 0 = a. 00 is the identity element.
    • Inverses: Each aZa \in \mathbb{Z} has an inverse a-a, since a+(a)=0a + (-a) = 0. For example, 3+(3)=03 + (-3) = 0

A subgroup HH of a group GG is a subset of GG that is itself a group under the same operation. That is:

  • Closure: if aa, bHb \in H, then abHa * b \in H
  • Identity Element: The identity element of the group GG is in HH
  • Inverse Element: If aHa \in H, then a1Ha^{-1} \in H

Example of a subgroup:

  • The set of integers divisible by 55 5Z={,15,10,5,0,5,10,15,}5\mathbb{Z} = \lbrace…, -15, -10, -5, 0, 5, 10, 15,…\rbrace(i.e multipling 55 by all integers) is a subgroup of Z\mathbb{Z} under addition because:
    • Closure: The sum of two numbers divisible by 55 is divisible by 55 making it closed under addition.
    • Identity: 00 is in 5Z5\mathbb{Z}
    • Inverses: Every a5Za \in 5\mathbb{Z} has an inverse a-a. For example, 10+(10)=010 + (-10) = 0

Note: Associativity is automatically holds for subgroups. Ponder on why this is the case.

Let’s do a little experiment!

Imagine we added the numbers 00 to 99 to the elements in 5Z5\mathbb{Z} to create new sets and displayed them in two halves. That is:

First half:

  • 0=0+5Z={,15,10,5,0,5,10,15,}\underline{0} = 0 + 5\mathbb{Z} = \lbrace…, -15, -10, -5, 0, 5, 10, 15,…\rbrace
  • 1=1+5Z={,14,9,4,1,6,11,16,}\underline{1} = 1 + 5\mathbb{Z} = \lbrace…, -14, -9, -4, 1, 6, 11, 16,…\rbrace
  • 2=2+5Z={,13,8,3,2,7,12,17,}\underline{2} = 2 + 5\mathbb{Z} = \lbrace…, -13, -8, -3, 2, 7, 12, 17,…\rbrace
  • 3=3+5Z={,12,7,2,3,8,13,18,}\underline{3} = 3 + 5\mathbb{Z} = \lbrace…, -12, -7, -2, 3, 8, 13, 18,…\rbrace
  • 4=4+5Z={,11,6,1,4,9,14,19,}\underline{4} = 4 + 5\mathbb{Z} = \lbrace…, -11, -6, -1, 4, 9, 14, 19,…\rbrace

Second half:

  • 5=5+5Z={,10,5,0,5,10,15,20,}\underline{5} = 5 + 5\mathbb{Z} = \lbrace…, -10, -5, 0, 5, 10, 15, 20,…\rbrace
  • 6=6+5Z={,9,4,1,6,11,16,21,}\underline{6} = 6 + 5\mathbb{Z} = \lbrace…, -9, -4, 1, 6, 11, 16, 21,…\rbrace
  • 7=7+5Z={,8,3,2,7,12,17,22,}\underline{7} = 7 + 5\mathbb{Z} = \lbrace…, -8, -3, 2, 7, 12, 17, 22,…\rbrace
  • 8=8+5Z={,7,2,3,8,13,18,23,}\underline{8} = 8 + 5\mathbb{Z} = \lbrace…, -7, -2, 3, 8, 13, 18, 23,…\rbrace
  • 9=9+5Z={,6,1,4,9,14,19,24,}\underline{9} = 9 + 5\mathbb{Z} = \lbrace…, -6, -1, 4, 9, 14, 19, 24,…\rbrace

Do you notice anything about these sets!? Here are some observations:

  1. The sets in the second half are a repetition of the sets in the first half so we will only focus on the first half moving on. Try creating more sets with numbers greater than 99 or less than 00.
  2. The sets are disjoint(i.e, they have no elements in common). Every element appears in only one set.
  3. The “combination” of the sets makes up the set of integers Z\mathbb{Z}. That is, 01234=Z\underline{0} \cup \underline{1} \cup \underline{2} \cup \underline{3} \cup \underline{4} = \mathbb{Z} where \cup represents union.
  4. Each set contains element with the same remainder when divided by 55. For example, every element in 2\underline{2} would result in a remainder of 22 when divided by 55. These sets are called equivalent classes in modulo arithmetic. In this case, they are equivalent because they share the same remainders but equivalence relations can be of different forms as we will see later.
  5. If we add any element from a set to any element from another set, you get an element from a set. For example, if we add any number in 0\underline{0} to any number in 1\underline{1}, we get a number in 1\underline{1} and if we add any number in 2\underline{2} to any number in 4\underline{4}, we get a number in 1\underline{1}.
  6. If we add any number from a set to any number in 0\underline{0}, we get back a number in the same set. For example, if we add 1414 from 4\underline{4} to 1515 from 0\underline{0}, we get 44 from 4\underline{4}.
  7. If we add any number from 2\underline{2} to any number from 3\underline{3}, we get a number from 0\underline{0}, if we add any number from 1\underline{1} to any number from 4\underline{4}, we get a number from 0\underline{0} and if we add any number from 0\underline{0} to any number from itself, we get a number from 0\underline{0}.
  8. The last three observations implies closure, presence of an identity element and presence of an inverse element respectively. The sets are called cosets and they form a group called the quotient group Z/5Z={0,1,2,3,4}\mathbb{Z}/5\mathbb{Z} = \lbrace\underline{0}, \underline{1}, \underline{2}, \underline{3}, \underline{4}\rbrace. We call it a quotient group because we use a subgroup to divide the group into cosets. Not all subgroups create cosets that form a quotient group like 5Z5\mathbb{Z}, but when they do we call them normal subgroups. Our observations doesn’t show associativity but it holds and I urge you to try it out

Formally, a coset is formed when you take a subgroup HH of a group GG and partition GG into sets of the form gH={ghhH}gH = \lbrace g * h | h \in H\rbrace where gGg \in G and * is an operation.

Note: The cosets from 1\underline{1} to 4\underline{4} are not subgroups of Z\mathbb{Z} under addition. They don’t contain the identity element, they are not closed under addition and they don’t contain their inverses. Using 3\underline{3} as an example:

  • identity element: 00, the identity element is not in the set.
  • inverse element: It doesn’t contain the identity element so it cannot have an inverse element.
  • closure: 3+8=113 + 8 = 11 but 1111 is not in 3\underline{3}.

Now, back to lattices. How does all these help in understanding fundamental domain and parallelepipeds?

The above example shows we could take any arbitrary integer Z\mathbb{Z} and we must be able to represent it using one of the elements of the quotient group Z/5Z\mathbb{Z}/5\mathbb{Z}. A fundamental domain is synonymous to this in lattices.

Since a lattice LL is a subgroup of Rn\mathbb{R}^n, we can define the quotient group Rn/L\mathbb{R}^n/L, which divides Rn\mathbb{R}^n into cosets of LL in Rn\mathbb{R}^n. A quotient group Rn/L\mathbb{R}^n/L of this form corresponds to a fundamental domain of LL. A fundamental domain is a region in Rn\mathbb{R}^n that contains exactly one representative from each coset just like Z/5Z\mathbb{Z}/5\mathbb{Z}. Similar to how Z/5Z\mathbb{Z}/5\mathbb{Z} encompasses the set of integers Z\mathbb{Z} using five cosets, the fundamental domain encompasses all the elements of Rn\mathbb{R}^n by having a representative for each coset.

Formally, a coset of LL in Rn\mathbb{R}^n is a set of the form m+L={m+λλL}m + L = \lbrace m + \lambda | \lambda \in L \rbrace where mm is a vector in Rn\mathbb{R}^n. If m1,m2Rnm_1, m_2 \in \mathbb{R}^n, then m1+Lm_1 + L and m2+Lm_2 + L are either the same set or disjoint. The set of all such cosets forms the quotient group Rn/L\mathbb{R}^n/L.

For example, given a lattice L={[5,2,1],[2,1,3],[4,5,1],[7,2,1],[10,7,7]}L = \lbrace[5, 2, 1], [2, 1, 3], [4, 5, 1], [7, 2, 1], [10, 7, 7]\rbrace and m1=[1.5,2,3.3]m_1 = [1.5, 2, 3.3], m2=[1,5.4,1.1]m_2 = [1, 5.4, 1.1] and m3=[1/2,2.5,3]m_3 = [1/2, 2.5, 3], we can form the following cosets:

  • m1=m1+L=[1.5,2,3.3]+L={[6.5,4,4.3],[3.5,3,6.3],[5.5,7,4.3],[8.5,4,4.3],[11.5,9,10.3]}\underline{m_1} = m_1 + L = [1.5, 2, 3.3] + L = \lbrace[6.5, 4, 4.3], [3.5, 3, 6.3], [5.5, 7, 4.3], [8.5, 4, 4.3], [11.5, 9, 10.3]\rbrace
  • m2=m2+L=[1,5.4,1.1]+L={[6,7.4,2.1],[3,6.4,4.1],[5,10.4,2.1],[8,7.4,2.1],[11,12.4,8.1]}\underline{m_2} = m_2 + L = [1, 5.4, 1.1] + L = \lbrace[6, 7.4, 2.1], [3, 6.4, 4.1], [5, 10.4, 2.1], [8, 7.4, 2.1], [11, 12.4, 8.1]\rbrace
  • m3=m3+L=[1/2,2.5,3]+L={[5.5,4.5,4],[2.5,3.5,6],[4.5,7.5,4],[7.5,4.5,4],[10.5,9.5,10]}\underline{m_3} = m_3 + L = [1/2, 2.5, 3] + L = \lbrace[5.5, 4.5, 4], [2.5, 3.5, 6], [4.5, 7.5, 4], [7.5, 4.5, 4], [10.5, 9.5, 10]\rbrace

An example of a fundamental domain is the set generated by F={t1v1+t2v2++tnvn :0ti<1}F = \lbrace t_1v_1 + t_2v_2 + … + t_nv_n\ : 0 \leq t_i \lt 1 \rbrace where v1,v2,,vnv_1, v_2, …, v_n is the basis of the a lattice and tit_i is a real number R\mathbb{R} not an integer Z\mathbb{Z}. This fundamental domain is called a fundamental parallelepiped.

We are saying that is for any vector sRns \in \mathbb{R}^n, we would be able to find its representative in the fundamental parallelepipeds.

Let’s look at an example using basis v1=[2,1]v_1 = [2, 1] and v2=[1,3]v_2 = [1, 3].

First, the diagram below shows the lattice generate by this basis.

png

Next, let’s create the fundamental parallelepiped and show it.

As stated above, the fundamental parallelepiped would be generated using F={t1v1+t2v2:0ti<1}F = \lbrace t_1v_1 + t_2v_2 : 0 \leq t_i \lt 1 \rbrace. There are infinitely many real numbers in the interval 0ti<10 \leq t_i \lt 1 so we will show generate a few and show more in the diagram.

  • t1=0,t2=0t_1 = 0, t_2 = 0, then t1v1+t2v2=0[2,1]+0[1,3]=[0,0]t_1v_1 + t_2v_2 = 0 * [2, 1] + 0 * [1, 3] = [0, 0]
  • t1=0,t2=0.1t_1 = 0, t_2 = 0.1, then t1v1+t2v2=0[2,1]+0.1[1,3]=[0.1,0.3]t_1v_1 + t_2v_2 = 0 * [2, 1] + 0.1 * [1, 3] = [0.1, 0.3]
  • t1=0.1,t2=0.1t_1 = 0.1, t_2 = 0.1, then t1v1+t2v2=0.1[2,1]+0.1[1,3]=[0.2,0.1]+[0.1,0.3]=[0.3,0.4]t_1v_1 + t_2v_2 = 0.1 * [2, 1] + 0.1 * [1, 3] = [0.2, 0.1] + [0.1, 0.3] = [0.3, 0.4]
  • t1=0.9,t2=0.9t_1 = 0.9, t_2 = 0.9, then t1v1+t2v2=0.9[2,1]+0.9[1,3]=[1.8,0.9]+[0.9,2.7]=[2.7,3.6]t_1v_1 + t_2v_2 = 0.9 * [2, 1] + 0.9 * [1, 3] = [1.8, 0.9] + [0.9, 2.7] = [2.7, 3.6]

That is, the fundamental parallelepiped F={[0,0],[0.1,0.3],[0.3,0.4],,[2.7,3.6]}F = \lbrace[0, 0], [0.1, 0.3], [0.3, 0.4], …, [2.7, 3.6]\rbrace.

Below is the what it looks like on a graph.

png

Notice how it looks like a scaled down and compressed version of the lattice.

Now, let’s verify our claim that we can find a representative of any vector mRnm \in \mathbb{R}^n in the fundamental domain. We will pick s=[5.2,6.3]s = [5.2, 6.3].

This means that there exists t1t_1 and t2t_2 such that t1[2,1]+t2[1,3]=[5.2,6.3]t_1 * [2, 1] + t_2 * [1, 3] = [5.2, 6.3] and we want to find them. Recall that to create an element of an fundamental parallelepiped in R2\mathbb{R}^2 we compute t1v1+t2v2=st_1v_1 + t_2v_2 = s. Here, we know ss, we know v1v_1 and v2v_2(the basis) but we don’t know t1t_1 and t2t_2 hence we are finding them.

Expanding the expression, we have that 2t1+t2=5.22t_1 + t_2 = 5.2 and t1+3t2=6.3t_1 + 3t_2 = 6.3. Solving this we have that t1=1.86t_1 = 1.86 and t2=1.48t_2 = 1.48(i.e using any of the methods for solving simultaneous equations like gaussian elimination).

Recall that t1t_1 and t2t_2 are supposed to be in the interval 0ti<10 \leq t_i \lt 1. We would have to wrap t1t_1 and t2t_2 around this interval. In other words, we would have to compute t1t_1 % 1 and t2t_2 % 1. Doing that we have that t1=0.86t_1 = 0.86 and t2=0.48t_2 = 0.48.

To get to representative rr of ss in the fundamental parallelepiped, we compute r=t1v1+t2v2=0.86[2,1]+0.48[1,3]=[1.72,0.86]+[0.48,1.44]=[2.2,2.3]r = t_1v_1 + t_2v_2 = 0.86 * [2, 1] + 0.48 * [1, 3] = [1.72, 0.86] + [0.48, 1.44] = [2.2, 2.3]. Therefore, r=[2.2,2.3]r = [2.2, 2.3] is the representative of s=[5.2,6.3]s = [5.2, 6.3] in the fundamental parallelepiped.

We are not done yet.

Do you see any similarity between rr and mm? You would notice they both end in the same decimals .2.2 and .3.3. That means their difference is an integer vector. That is, sr=[5.2,6.3][2.2,2.3]=[3,4]s - r = [5.2, 6.3] - [2.2, 2.3] = [3, 4].

Using our basis v1=[2,1]v_1 = [2, 1] and v2=[1,3]v_2 = [1, 3], we can generate the lattice: L={[2,1],[1,3],[211],[3,4],[11,13],[9,7],[1,8],[4,7],[5,10],[8,9]}L = \lbrace[2, 1], [1, 3], [-2 -11], [3, 4], [-11, -13], [9, 7], [1, 8], [4, 7], [-5, -10], [8, 9]\rbrace Recall that, a coset of LL in Rn\mathbb{R}^n is a set of the form m+L={m+λλL}m + L = \lbrace m + \lambda | \lambda \in L \rbrace. Setting r=mr = m, we have that: r+L=[2.2,2.3]+L={[4.2,3.3],[3.2,5.3],[0.2,8.7],[5.2,6.3],[8.8,10.7],[11.2,9.3],[3.2,10.3],[6.2,9.3],[2.8,7.7],[10.2,11.3]}r + L = [2.2, 2.3] + L = \lbrace[4.2, 3.3],[3.2, 5.3], [0.2, -8.7], [5.2, 6.3], [-8.8, -10.7], [11.2, 9.3], [3.2, 10.3], [6.2, 9.3], [-2.8, -7.7], [10.2, 11.3]\rbrace Notice how [3,4][3, 4] is part of the lattice LL and [5.2,6.3][5.2, 6.3] is part of the coset r+Lr + L.

This shows that every vector in this coset has the representative [2.2,2.3][2.2, 2.3] in the fundamental parallelepiped and this is their equivalence relation.

Lastly, note that a fundamental domain is not a lattice.


The goal of this material was to introduce these concepts independently; appreciating their beauty without drawing parallels to their applications in lattice-based cryptography; we will do that in the other posts in this series.

In the next post, we will be looking into Hard Problems in Lattice-Based Cryptography. See you there!