An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Lattice Based Cryptography

When you use your credit card, you expect that the information that is transmitted is protected so others can't use your card. Similarly, when you create a password for your computer or other devices, you do so with the intention that it will be difficult for others to decipher.

Cryptology is the study of methods to maintain secure communication in the presence of other parties (cryptography), along with the study of breaking codes (cryptanalysis). In essence, cryptology is the art of keeping and breaking secrets. The creation of secure codes (cryptography) can provide confidentiality (ensure that information is available only to the intended recipients), data integrity (prevent data from being altered between the sender and recipient), and authentication (making sure that the information is from the correct source).

Modern cryptology uses mathematical theory that can be implemented with computer hardware and algorithms. The security of public key systems is largely based on mathematical problems that are very difficult to solve. For example, the security of the RSA system relies on the fact that it is computationally difficult to find prime factors of very large numbers, and elliptic curve cryptography relies on the difficulty of the discrete logarithm problem for elliptic curves. However, the continual increase in the power of computers threatens the security of these systems, and so cryptographic systems have to keep adapting to the newest technology. For example, Shor's Algorithm (which could run on a quantum computer) can solve the public key cryptographic systems that rely on the integer factorization problem or the discrete logarithm problem. So if a working quantum computer was ever developed, it would threaten the existing cryptographic systems. Lattice-based cryptography is a potential source of systems that may be secure even in such an environment. The security of these systems is dependent on the fact that the average case of the difficulty of certain problems in lattice theory is higher than the worst case problems that underpin current cryptosystems. As we will see later in this section, lattices are built on bases for subspace of \(\R^n\text{.}\)

Subsection Introduction

A basis provides a system in which we can uniquely represent every vector in the space we are considering. More specifically, every vector in the space can be expressed as a linear combination of the vectors in the basis in a unique way. In order to be able to cover every point in the space, the basis has to span the space. In order to be able to provide a unique coordinate for each point, there should not be any extra vectors in the basis, which is achieved by linear independence of the vectors. For practical reasons, a basis simplifies many problems because we only need to solve the problem for each of the basis vectors. Solutions of the other cases usually follow because every vector in the space can be expressed as a unique linear combination of the basis vectors.

Recall that a basis for a subspace \(W\) of \(\R^n\) is a set of vectors which are linearly independent and which span \(W\text{.}\)

Subsection The Dimension of a Subspace of \(\R^n\)

In Preview Activity 15.1 we saw that a subspace of \(\R^n\) can have more than one basis. This prompts the question of how, if at all, are any two bases for a given space related. More specifically, is it possible to have two bases for a given subspace of \(\R^n\) that contain different numbers of vectors? As we will see the answer is no, which will lead us to the concept of dimension.

Let \(W\) be a subspace of \(\R^n\) that has a basis \(\B = \{\vv_1, \vv_2, \ldots, \vv_k\}\) of \(k\) vectors. Since we have been calling bases minimal spanning sets, we should expect that any two bases for the same subspace have the same number of elements (otherwise one of the two bases would not be minimal). Our goal in this section is to prove that result — that any other basis of \(W\) contains exactly \(k\) vectors. The approach will be the same as was used in Preview Activity 15.1. We will let \(U = \{\vu_1, \vu_2, \ldots, \vu_m\}\) be a set of vectors in \(W\) with \(m > k\) and demonstrate that \(U\) is a linearly dependent set. To argue linear dependence, let \(x_1\text{,}\) \(x_2\text{,}\) \(\ldots\text{,}\) \(x_m\) be scalars so that

For each \(i\) there exist scalars \(a_{ij}\) so that

Substituting into (15.6) yields

Since \(\B\) is a basis, the vectors \(\vv_1\text{,}\) \(\vv_2\text{,}\) \(\ldots\text{,}\) \(\vv_k\) are linearly independent. So each coefficient in (15.7) is 0 and \(\vx~=~[x_1 \ x_2 \ \cdots \ x_m]^{\tr}\) is a solution to the homogeneous system \(A \vx = \vzero\text{,}\) where \(A = [a_{ij}]\text{.}\) Now \(A\) is a \(k \times m\) matrix with \(m > k\text{,}\) so not every column of \(A\) is a pivot column. This means that \(A \vx = \vzero\) has a nontrivial solution. It follows that the vector equation (15.6) has a nontrivial solution and so the \(m\) vectors \(\vu_1\text{,}\) \(\vu_2\text{,}\) \(\ldots\text{,}\) \(\vu_m\) are linearly dependent. We summarize this in the following theorem.

One consequence of Theorem 15.1 is that, in addition to being a minimal spanning set, a basis is also a maximal linearly independent set.

The result of Activity 15.2 is summarized in the following theorem. Recall that the trivial space is the single element set \(\{\vzero\}\text{.}\)

This last theorem states that the number of vectors in a basis for a subspace space is a well-defined number. In other words, the number of vectors in a basis is an invariant of the subspace. This important number is given a name.

We denote the dimension of a subspace \(W\) of \(\R^n\) by \(\dim(W)\text{.}\) As we will see later, any two vector spaces of the same dimension are basically the same vector space. So the dimension of a vector space is an important number that essentially tells us all we need to know about the structure of the space.

Subsection Conditions for a Basis of a Subspace of \(\R^n\)

There are two items we need to confirm before we can state that a subset \(\B\) of a subspace \(W\) of \(\R^n\) is a basis for \(W\text{:}\) the set \(\B\) must be linearly independent and span \(W\text{.}\) However, if we have the right number (namely, the dimension) of vectors in our set \(\B\text{,}\) then either one of these conditions will imply the other.

The result of Activity 15.4 is the following important theorem.

Subsection Finding a Basis for a Subspace

Since every vector in a subspace of \(\R^n\) can be written uniquely as a linear combination of vectors in a basis for the subspace, a basis provides us with the most efficient and convenient way to represent vectors in the subspace. Until now we have been given a set of vectors and have been asked to find a basis from that set, so an important question to address is how we can find a basis for a subspace \(W\) of \(\R^n\) starting from scratch. Here is one way. If \(W = \{\vzero\}\text{,}\) then the dimension of \(W\) is 0 and \(W\) has no basis. So suppose \(\dim(W) > 0\text{.}\) Start by choosing any nonzero vector \(\vw_1\) in \(W\text{.}\) Let \(\B_1 = \{\vw_1\}\text{.}\) If \(\B_1\) spans \(W\text{,}\) then \(\B_1\) is a basis for \(W\text{.}\) If not, there is a vector \(\vw_2\) in \(W\) that is not in \(\Span(\B_1)\text{.}\) Then \(\B_2 = \{\vw_1, \vw_2\}\) is a linearly independent set. If \(\Span(\B_2) = W\text{,}\) then \(\B_2\) is a basis for \(W\) and we are done. If not, repeat the process. Since any basis for \(W\) can contain at most \(n=\dim(\R^n)\) vectors, we know the process must stop at some point. This process also allows us to construct a basis for a vector space that contains a given nonzero vector.

Subsection Rank of a Matrix

In this section, we define the rank of a matrix and review conditions to add to our Invertible Matrix Theorem.

As Activity 15.6 illustrates, the number of vectors in a basis for \(\Nul A\) is the number of non-pivot columns in \(A\) and the number of vectors in a basis for \(\Col A\) is the number of pivot columns of \(A\text{.}\) We define the rank of a matrix \(A\) (denoted rank(\(A\))) to be the dimension of \(\Col A\) and the nullity of \(A\) to be dimension of \(\Nul A\text{.}\) The dimension of the null space of \(A\) is also called the nullity of \(A\) (denoted nullity(\(A\))) Using this terminology we have the Rank-Nullity Theorem.

There is also a row space of a matrix \(A\text{,}\) which we define to be the span of the rows of \(A\text{.}\) We can find the row space of \(A\) by finding the column space of \(A^{\tr}\text{,}\) so the row space is really nothing new. As it turns out, the dimension of the row space of \(A\) is always equal to the dimension of the column space of \(A\text{,}\) and justification for this statement is in the exercises.

The Rank-Nullity Theorem allows us to add extra conditions to the Invertible Matrix Theorem.

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

The key idea in this section is the dimension of a vector space.

• Any two bases for a vector space must contain the same number of vectors. Therefore, we can define the dimension of a vector space \(W\) to be the number of vectors in any basis for \(W\text{.}\)

• If \(W\) is a subspace of \(\R^n\) with dimension \(k\) and \(S\) is any linearly independent subset of \(W\) with \(k\) vectors, then \(S\) is a basis for \(W\text{.}\)

• If \(W\) is a subspace of \(\R^n\) with dimension \(k\) and \(S\) is any subset of \(W\) with \(k\) vectors that spans \(W\text{,}\) then \(S\) is a basis for \(W\text{.}\)

• The rank of a matrix is the dimension of its column space.

• The Rank-Nullity Theorem states that if \(A\) is an \(m \times n\) matrix, then \(\rank(A) + \nullity(A) = n\text{.}\)

Subsection Project: The GGH Cryptosystem

A cryptographic system (or cryptosystem) allows for secure communication between two or more parties. These systems take messages (called plaintext) and encrypt them in some way to produce what is called ciphertext. This is the scrambled information that is transmitted to the receiver, from which it should not be possible for someone who does not have the proper key to recover the original message. When the message is received by the intended recipient, it must be unscrambled or decrypted. Decryption is the process of converting ciphertext back to plaintext.

The Goldreich-Goldwasser-Halevi (GGH) public key cryptosystem³⁰ uses lattices to encrypt plaintext. The security of the system depends on the fact that the Closest Vector Problem (CVP) is, in general, a very hard problem. To begin to understand these cryptosystems, we begin with lattices.

Lattices are closely related to spans of sets of vectors in \(\R^n\text{.}\) If we start with a linearly independent set \(S = \{\vb_1, \vb_2, \ldots, \vb_m\}\) in \(\R^n\text{,}\) we can create the span of \(S\) — the set of all linear combinations

where \(c_1\text{,}\) \(c_2\text{,}\) \(\ldots\text{,}\) \(c_m\) are real numbers. This span creates a subspace of \(\R^n\text{.}\) If we restrict the set from which we choose the coefficients, we can create different types of structures. An important one is a lattice. The lattice \(\mathcal{L}(S)\) defined by the linearly independent set \(S = \{\vb_1, \vb_2, \ldots, \vb_m\}\) is the set of linear combinations

where \(c_1\text{,}\) \(c_2\text{,}\) \(\ldots\text{,}\) \(c_m\) are integers. If the vectors in \(S\) have integer components, then every point in \(\mathcal{L}(S)\) will have integer entries. In these cases, \(\mathcal{L}(S)\) is a subset of \(\Z^n\text{,}\) as illustrated in Figure 15.9. Also, if \(m = n\) we say that the lattice \(\mathcal{L}(S)\) is full-rank. We will restrict ourselves to full-rank lattices in this project. A basis for a lattice is any set of linearly independent vectors that generates the lattice. There is a little special notation that is often used with lattices. If \(\CB = \{\vb_1, \vb_2, \ldots, \vb_n\}\) is a basis for \(\R^n\text{,}\) we associate to \(\CB\) the matrix \(B = [\vb_1 \ \vb_2 \ \vb_3 \ \cdots \ \vb_n]\text{.}\) We then use the notation \(\mathcal{L}(B)\) to also refer to the lattice defined by \(\CB\text{.}\)

Project Activity 15.7.

We explore lattices in more detail in this activity.

(a)

Let \(S_1 = \{[1 \ 1]^{\tr}, [-1 \ 1]^{\tr}\}\text{.}\)

(i)

Find five distinct vectors in \(\mathcal{L}(S_1)\text{.}\)

(ii)

Is the vector \([1 \ 0]^{\tr}\) in \(\mathcal{L}(S_1)\text{?}\) Justify your answer.

(iii)

We can draw pictures of lattices by plotting the terminal points of the lattice vectors. Draw all of the lattice points in \(\mathcal{L}(S_1)\) on the square with vertices \((-4,-4)\text{,}\) \((4,-4)\text{,}\) \((4,4)\text{,}\) and \((-4,4)\text{.}\)

(b)

Now let \(S_2 = \{[3 \ 5]^{\tr}, [1 \ 2]^{\tr}\}\text{.}\) A picture of \(\mathcal{L}(S_2)\) is shown in Figure 15.9 with the basis vectors highlighted. As we have seen, \(\mathcal{L}(S_1)\) is not the entire space \(\Z^2\text{.}\) Is \(\mathcal{L}(S_2) = \Z^2\text{?}\) Justify your answer.

Project Activity 15.7 shows that even if \(\CB\) is a basis for \(\R^n\text{,}\) it does not follow that \(\mathcal{L}(\CB)\) is all of \(\Z^n\text{.}\) So latices can be complicated, and problems in lattice theory can be very difficult.

The GGH cryptosystem relies on the fact that we can convert “good” bases for lattices into “bad” bases. We will not delve into the details of what separates a “good” basis from a “bad” one, but suffice it to say that a good basis is one in which the basis vectors are close to being perpendicular³¹ and are all short (that is, they have small norms), while any other basis is a bad basis. An example of a good basis is the basis \(S_1\) for \(\R^2\) in Project Activity 15.7, and we will see later that \(\{[-2 \ 8]^{\tr}, [-1 \ 3]^{\tr}\}\) is a bad basis for the same lattice. You should draw a picture of the vectors \([-2 \ 8]^{\tr}\) and \([-1 \ 3]^{\tr}\) to convince yourself that this is a bad basis for its lattice.

The GGH cryptosystem works with two keys — a public key and a private key. The keys are based on lattices. The general process of the GGH cryptosystem is as follows. Begin with a good basis \(\CB = \{\vb_1 \ \vb_2 \ \ldots \ \vb_n\}\) of \(\R^n\) of vectors with integer components. Let \(B = [\vb_1 \ \vb_2 \ \cdots \ \vb_n]\) be the matrix associated with \(\CB\text{.}\) Let \(\CB' = \{\vb'_1, \vb'_2, \ldots, \vb'_n\}\) be a bad basis for which \(\mathcal{L}(\CB') = \mathcal{L}(\CB)\text{.}\) Let \(B' = [\vb'_1 \ \vb'_2 \ \cdots \ \vb'_n]\) be the matrix associated to the basis \(\CB'\text{.}\) The bad basis can be shared with anyone (the public key), but the good basis is kept secret (the private key). Start with a message \(\vm = [m_1 \ m_2 \ \cdots \ m_n]^{\tr}\) with integer entries to send.

First we encrypt the message, which can be done by anyone who has the public key \(\CB'\text{.}\)

• Create the message vector

  \begin{equation*} \vm' = m_1 \vb'_1 + m_2 \vb'_2 + \cdots + m_n \vb'_n = B' \vm \end{equation*}

  that is in the lattice using the bad basis \(\CB'\text{.}\)

• Choose a small error \(\ve\) to add to \(\vm'\) to move \(\vm'\) off the lattice (small enough so that \(\vm'\) does not pass by another lattice point). This is an important step that will make the message difficult to decrypt without the key. Let \(\vc = \vm' + \ve = B'\vm + \ve\text{.}\) The vector \(\vc\) is the ciphertext that is to be transmitted to the receiver.

Only someone who knows the basis \(\CB\) can decode the ciphertext. This is done as follows.

• Find the vector \(\va = a_1 \vb_1 + a_2 \vb_2 + \cdots + a_n \vb_n\) in the good basis \(\CB\) that is closest to \(\vc\text{.}\)

• We interpret the vector \([a_1 \ a_2 \ \ldots \ a_n]^{\tr}\) as being the encoded vector without the error. So to recreate the original message vector we need to undo the encrypting using the bad basis \(\CB'\text{.}\) That is, we need to find the weights \(y_1\text{,}\) \(y_2\text{,}\) \(\ldots\text{,}\) \(y_n\) such that

  \begin{equation*} [a_1 \ a_2 \ \ldots \ a_n]^{\tr} = y_1 \vb'_1 + y_2 \vb'_2 + \cdots + y_n \vb'_n = B' [y_1 \ y_2 \ \cdots \ y_n]^{\tr}\text{.} \end{equation*}

  We can do this by as \([y_1 \ y_2 \ \cdots \ y_n]^{\tr} = B'^{-1} [a_1 \ a_2 \ \ldots \ a_n]^{\tr}\text{.}\)

There are several items to address before we can implement this algorithm. One is how we create a bad basis \(\CB'\) from \(\CB\) that produces the same lattice. Another is how we find the vector in \(\mathcal{\CB}\) closest to a given vector. The latter problem is called the Closest Vector Problem (CVP) and is, in general, a very difficult problem. This is what makes lattice-based cryptosystems secure. We address the first of these items in the next activity, and the second a bit later.

The two bases \(S_1 = \{[1 \ 1]^{\tr}, [-1 \ 1]^{\tr}\}\) and \(S_3 =\{[-2 \ 8]^{\tr}, [-1 \ 3]^{\tr}\}\) from Project Activity 15.8 are shown in Figure 15.10. This figure illustrates how the matrix \(U\) transforms the basis \(S_1\text{,}\) in which the vectors are perpendicular and short, to one in which the vectors are nearly parallel and significantly longer. So the matrix \(U\) converts the “good” basis \(S_1\) into a “bad” basis \(S_2\text{,}\) keeping the lattice intact. This is a key idea in the GGH cryptosystem. What makes this work is the fact that both \(U\) and \(U^{-1}\) have integer entries. The reason for this is that, for a \(2 \times 2\) matrix \(U = \left[ \begin{array}{cc} a\amp b\\c\amp d \end{array} \right]\text{,}\) we know that \(U^{-1} = \frac{1}{ad-bc} \left[ \begin{array}{rr} d\amp -b\\-c\amp a \end{array} \right]\text{.}\) If \(U\) has integer entries and \(ad-bc = \pm 1\text{,}\) then \(U^{-1}\) will also have integer entries. The number \(ad-bc\) is called the determinant of \(U\text{,}\) and matrices with determinant of \(1\) or \(-1\) are called unimodular. That what happened in Project Activity 15.8 happens in the general case is the focus of the next activity.

Project Activity 15.9 is the part we need for our lattice-based cryptosysystem. Although we won't show it here, the converse of the statement in Project Activity 15.9 is also true. That is, if \(\CB\) and \(\CB'\) generate the same lattice, then \(B' = BU\) for some unimodular matrix \(U\) with integer entries.

There is one more item to address before we implement the GGH cryptosystem. That item is how to solve the Closest Vector Problem. There are some algorithms for approximating the closest vector in a basis. One is Babai's Closest Vector algorithm. This algorithm works in the following way. Consider a lattice with basis \(\{\vb_1, \vb_2, \ldots, \vb_n\}\text{.}\) To approximate the closest vector in the lattice to a vector \(\vw\text{,}\) find the weights \(c_1\text{,}\) \(c_2\text{,}\) \(\ldots\text{,}\) \(c_n\) in \(\R\) such that \(\vw = c_1\vb_1 + c_2 \vb_2 + \cdots + c_n \vb_n\text{.}\) Then round the coefficients to the nearest integer. This algorithm works well for a good basis, but is unlikely to return a lattice point that is close to \(\vw\) if the basis is a bad one.

Now we put this all together to illustrate the GGH algorithm.