Intro To Cryptography - Chapter 7

Problem 7.2

Use the algorithm described in Proposition 7.5 to solve each of the following subset-sum problems. If the "solution" that you get is not correct, explain what went wrong.

(a) $M = (3, 7, 19, 43, 89, 195), \quad S = 260$.

1. $260 \ge 195 ;\implies; x_6 := 1, S := 65$
2. $65 < 89 \implies x_5 := 0$
3. $65 \ge 43 \implies x_4 := 1, S := 22$
4. $22 \ge 19 \implies x_3 := 1, S := 3$
5. $3 < 7 \implies x_2 := 0$
6. $3 \ge 3 \implies x_1 := 1, S := 0$

Thus $\textbf{x} = (1, 0, 1, 1, 0, 1)$ is a solution to to $\textbf{x}\cdot M = S$.

(b) $M = (5, 11, 25, 61, 125, 261), \quad S = 408.$

1. $408 \ge 261 \implies x_6 := 1, S := 147$
2. $147 \ge 125 \implies x_5 := 1, S := 22$
3. $22 < 61 \implies x_4 := 0$
4. $22 < 25 \implies x_3 := 0$
5. $22 \ge 11 \implies x_2 := 1, S := 11$
6. $11 \ge 5 \implies x_1 := 1, S := 6$

We are left with $S := 6$ rather than zero; this algorithm is guaranteed to give a solution if one exists. Therefore there is no solution to this subset-sum problem.

(c) $M = (2, 5, 12, 28, 60, 131, 257), \quad S = 334$

1. $334 \ge 257 \implies x_7 := 1, S := 77$
2. $77 < 131 \implies x_6 := 0$
3. $77 \ge 60 \implies x_5 := 1, S := 17$
4. $17 < 28 \implies x_4 := 0$
5. $17 \ge 12 \implies x_3 := 1, S := 5$
6. $5 \ge 5 \implies x_2 := 1, S := 0$
7. $0 < 2 \implies x_1 := 0$

Thus $\textbf{x} = (0, 1, 1, 0, 1, 0, 1)$ is a solution to to $\textbf{x}\cdot M = S$. (Notice that $M$ is actually not a superincreasing sequence, so the algorithm was not guaranteed to work here, but it still found us a solution.)

(d) $M = (4, 12, 15, 36, 75, 162), \quad S = 214$

1. $214 \ge 162 \implies x_6 := 1, S := 52$
2. $52 < 75 \implies x_5 := 0$
3. $52 \ge 36 \implies x_4 := 1, S := 16$
4. $16 \ge 15 \implies x_3 := 1, S := 1$
5. $1 < 12 \implies x_2 := 0$
6. $1 < 4 \implies x_1 := 0$

We have a leftover $S := 1$, and failed to find a solution. In this case, a quick inspection shows that we could have found a solution here if we had $(x_1, x_2, x_3) = (1, 1, 0)$ rather than the $(0, 0, 1)$ result of the algorithm. The reason the algorithm failed is that $M$ is not a superincreasing sequence (notice $2m_2 = 2\cdot12 = 24 > 15 = m_3$).

Problem 7.5

(a) Let

$$ \mathcal{B} = \{(1,3,2), (2, -1, 3), (1, 0, 2)\}, $$

$$ \mathcal{B}' = \{(-1,0,2), (3, 1, -1), (1, 0, 1)\}. $$

Each of the sets $\mathcal{B}$ and $\mathcal{B}'$ is a basis for $\mathbb{R}^3$. Find the change of basis matrix that transforms $\mathcal{B'}$ into $\mathcal{B}$.

Solution: For each $w \in \mathcal{B}'$, we need to find $a, b, c \in \mathbb{R}$ such that

$$ w = av_1 + bv_2 +cv_3 $$

First let's solve these equations in a more general sense.

$$ \begin{pmatrix}w_1 \\ w_2 \\ w_3\end{pmatrix} = a \begin{pmatrix}1 \\ 3 \\ 2\end{pmatrix} + b \begin{pmatrix}2 \\ -1 \\ 3\end{pmatrix} + c \begin{pmatrix}1 \\ 0 \\ 2\end{pmatrix} $$

$$ \implies \begin{align*} w_1 &= a + 2b + c \\ w_2 &= 3a -b \\ w_3 &= 2a + 3b +2c \end{align*} $$

$$ \implies \begin{align*} w_1 + 2w_2 &= 7a + c \\ w_3 + 3w_2 &= 11a + 2c\end{align*} $$

$$ \implies \begin{align*} w_3 -2w_1 - w_2 &= -3a \end{align*} $$

$$ \implies \begin{align*} a &= \frac{2w_1 + w_2 - w_3}{3} \\ b &= 3a - w_2 = 2w_1 - w_3 \\ c &= w_1 -a - 2b = \frac{-11w_1 - w_2 + 7w_3}{3} \end{align*} $$

Using this formula for each $w \in \mathcal{B}'$ we find

$$\begin{align*} w_1 &= (-4/3)v_1 + (-4)v_2 + (25/3)v_3 \\ w_2 &= (8/3)v_1 + (7)v_2 + (-41/3)v_3 \\ w_3 &= (1/3)v_1 + (1)v_2 + (-4/3)v_3\end{align*}$$

Now we use these component vectors in $\mathcal{B}$ as the columns of the change of basis matrix:

$$ A = \begin{pmatrix}\frac{-4}{3} & \frac{8}{3} & \frac{1}{3} \\ -4 & 7 & 1 \\ \frac{25}{3} & \frac{-41}{3} & \frac{-4}{3}\end{pmatrix}$$

Just as a quick sanity check, let's use this matrix on the vector $v = w_1 + w_2 = (2, 1, 1)$ whose component vector in $\mathcal{B}'$ is $(1, 1, 0)$:

$$ Av = \begin{pmatrix}\frac{-4}{3} & \frac{8}{3} & \frac{1}{3} \\ -4 & 7 & 1 \\ \frac{25}{3} & \frac{-41}{3} & \frac{-4}{3}\end{pmatrix} \begin{pmatrix}1 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix}\frac{4}{3} \\ 3 \\ \frac{-16}{3}\end{pmatrix}$$

$$ (4/3)v_1 + 3v_2 + (-16/3)v_3 = (4/3)\begin{pmatrix}1\\ 3\\ 2\end{pmatrix} + 3\begin{pmatrix}2 \\ -1 \\ 3\end{pmatrix} - (16/3)\begin{pmatrix}1 \\ 0 \\ 2\end{pmatrix} = \begin{pmatrix}2 \\ 1 \\ 1 \end{pmatrix}$$

Voila.

(b) Let $\textbf{v} = (2, 3, 1)$ and $\textbf{w} = (-1, 4, -2)$. Compute the lengths $|\textbf{v}|$ and $|\textbf{w}|$ and the dot product $\textbf{v}\cdot\textbf{w}$. Compute the angle between $\textbf{v}$ and $\textbf{w}$.

Solution:

$$ |\textbf{v}| = \sqrt{4 + 9 + 1} = \sqrt{14} $$

$$ |\textbf{w}| = \sqrt{1 + 16 + 4} = \sqrt{21} $$

$$ \textbf{v}\cdot\textbf{w} = -2 + 12 - 2 = 8 $$

By Proposition 7.12.a we know

$$ \cos(\theta) = \frac{\textbf{v}\cdot\textbf{w}}{|v| |w|} = \frac{8}{\sqrt{14\cdot21}} = \frac{8}{7\sqrt{6}}$$

So $\theta = \arccos(8/7\sqrt{6}) \approx 1.0853 rad \approx 62^\circ$.

Problem 7.6

Use the Gram-Schmidt algorithm to find an orthogonal basis from the given basis. (Note: Mathjax is broken af; some of the vectors are unbolded below because that's the only way they will display with the proper subscripts.)

(a) $\textbf{v}_1 = (1,3,2), \ \textbf{v}_2 = (4, 1, -2), \ \textbf{v}_3 = (-2, 1, 3)$.

1. $\textbf{v}_1^\ast := \textbf{v}_1 = (1, 3, 2)$

2. Compute

   1. $\mu_{21} := \textbf{v}_2 \cdot \textbf{v}_1^\ast / |{\textbf{v}_1^\ast}|^2 = 3/14$
   2. $v_2^\ast = v_2 - \mu_{21} v_1^\ast = (53/14, 5/14, -17/7)$

3. Compute

   1. $\mu_{31} := \textbf{v}_3 \cdot \textbf{v}_1^\ast / |{\textbf{v}_1^\ast}|^2 = \frac{-2 + 3 + 6}{14} = \frac{1}{2}$
   2. $\mu_{32} := \textbf{v}_3 \cdot \textbf{v}_2^\ast / |{\textbf{v}_2^\ast}|^2 = \frac{-2(53/14) + 1(5/14) - 3(17/7)}{(53/14)^2 + (5/14)^2 + (17/7)^2} = \frac{-29/2}{285/14} = - \frac{203}{285}$
   3. Set

$$ \begin{align*} v_3^\ast &:= v_3 - \mu_{31}v_1^\ast - \mu_{32}v_2^\ast \\ &= (-2, 1, 3) - (1/2)(1,3,2) + (203/285)(53/14, 5/14, -17/7) \\ &= (56/285, -14/57, 77/285) \end{align*} $$

So an orthogonal basis with the same span is

$$\{(1, 3, 2), \ (53/14, 5/14, -17/7), \ (56/285, -14/57, 77/285) \}. $$

Or, just notice that a basis of 3 vectors in $\mathbb{R}^3$ spans the whole space. So we could use the canonical $(1,0,0), (0,1,0), (0,0,1)$ basis instead.

(b) $\textbf{v}_1 = (4, 1, 3, -1), \ \textbf{v}_2 = (2, 1, -3, 4), \ \textbf{v}_3 = (1, 0, -2, 7)$.

1. $\textbf{v}_1^\ast := \textbf{v}_1 = (4, 1, 3, -1)$
2. Compute
   1. $\mu_{21} := \textbf{v}_2 \cdot \textbf{v}_1^\ast / |{\textbf{v}_1^\ast}|^2 = \frac{8 + 1 -9-4}{16 + 1 + 9 + 1} = \frac{-4}{27}$
   2. $v_2^\ast := v_2 - \mu_{21}v_1^\ast = (2, 1, -3, 4) + (4/27)(4, 1, 3, -1) = (70/27, 31/27, -23/9, 104/27)$
3. Compute
   1. $\mu_{31} := \textbf{v}_3 \cdot \textbf{v}_1^\ast / |{\textbf{v}_1^\ast}|^2 = \frac{4 -6 -7}{27} = \frac{-1}{3}$
   2. $\mu_{32} := \textbf{v}_3 \cdot \textbf{v}_2^\ast / |{\textbf{v}_2^\ast}|^2 = \frac{70/27 + 2(23/9) + 7(104/27)}{(70/27)^2 + (31/27)^2 + (23/9)^2 + (104/27)^2} = \frac{104/3}{794/27} = \frac{468}{397}$
   3. Set

$$ \begin{align*} v_3^\ast &:= v_3 - \mu_{31}v_1^\ast - \mu_{32}v_2^\ast \\ &= (1, 0, -2, 7) + (1/3)(4, 1, 3, -1) - (468/397)(70/27, 31/27, -23/9, 104/27) \\ &= (-287/397, -405/397, 799/397, 844/397) \end{align*} $$

So an orthogonal basis with the same span is

$$\{(4, 1, 3, -1), \ (70/27, 31/27, -23/9, 104/27), \ (-287/397, -405/397, 799/397, 844/397) \}. $$

Problem 7.11

Let $A, B \in GL_n\mathbb{Z}$.

(a) Prove that $AB \in GL_n(\mathbb{Z})$.

Proof: We know from basic linear algebra that $AB$ is an $n$-by-$n$ matrix and that $\det(AB) = \det(A)\det(B) = \pm 1$. Consider any arbitrary coefficient of $AB$, for example in row $i$ and col $j$. This entry is the dot product $A_{i, \cdot} \cdot B_{\cdot, j}$ of row $i$ in $A$ and column $j$ in B. Of course, since $A, B$ have integer cofficients, it is clear that their dot product is an integer as well. Therefore $AB \in GL_n(\mathbb{Z})$.

(b) Prove that $A^{-1} \in GL_n(\mathbb{Z})$.

Proof: Since $\det(A)$ is nonzero, we know $A^{-1}$ exists and $\det(A^{-1}) = \frac{1}{\det(A)} = \pm 1$. Furthermore,

$$ A^{-1} = \frac{1}{\det(A)} Adj(A) = \pm 1 \cdot Adj(A) $$

But the adjugate of $A$ is the transpose of the cofactor of $A$, whose entries are $\pm$ values of determinants of minor matrices within $A$. Since all of these minor matrices have integer coefficients, so too do their determinants. Thus, if one was so inclined, it is easy to see an inductive argument that the cofactor indeed has all integer coefficients. This proves that $A^{-1} \in GL_n(\mathbb{Z})$.

(c) Prove that the $n$-by-$n$ identity matrix is in $GL_n(\mathbb{Z})$.

Proof: This is rather immediate, no? We have $\det(I) = 1$ and all of its entries are either $0, 1\in \mathbb{Z}$.

Problem 7.12

Which of the following are in $GL_n(\mathbb{Z})$? Find the inverses of those that are in $GL_n(\mathbb{Z})$.

(a) $A_1 = \begin{pmatrix} 3 & 1 \\ 2 & 2 \end{pmatrix}$

Solution: Since

$$\det(A_1) = 3\cdot2 - 1\cdot2 = 4 \ne \pm 1,$$

we conclude $A_1 \notin GL_2(\mathbb{Z})$.

(b) $A_2 = \begin{pmatrix} 3 & -2 \\ 2 & -1 \end{pmatrix}$

Solution: Since

$$\det(A_2) = 3\cdot(-1) - (-2)\cdot2 = 1,$$

we conclude $A_2 \in GL_2(\mathbb{Z})$ and

$$A_2^{-1} = \frac{1}{\det(A_2)}\begin{pmatrix}d & -b \\ -c & a \end{pmatrix} = \begin{pmatrix}-1 & 2 \\ -2 & 3 \end{pmatrix}. $$

Problem 7.13

Let $L$ be a lattice with basis

$$\mathcal{B} = \{(3, 1, -2), (1, -3, 5), (4, 2, 1)\}.$$

Which of the following sets of vectors are also bases for $L$? For those that are, express the new basis in terms of the basis $\mathcal{B}$.

(a) $\mathcal{B}_1 = \{(5, 13, -13), (0, -4, 2), (-7, -13, 18)\}$.

Solution: As long as we can express the $v \in \mathcal{B}$ as integer multiples of the vectors $w \in \mathcal{B}_1$, then we can conclude that $\mathcal{B}_1$ is a basis for $L$.

$$v_1 = aw_1 + bw_2 + cw_3 \implies \begin{pmatrix} 3 \\ 1 \\ -2 \end{pmatrix} = a\begin{pmatrix}5 \\ 13 \\ -13 \end{pmatrix} + b\begin{pmatrix}0\\ -4 \\ 2\end{pmatrix} + c\begin{pmatrix}-7 \\ -13 \\ 18 \end{pmatrix} $$

Luckily, a quick inspection reveals an answer: $a = 2, b = 3, c = 1$, so $[v_1]_{\mathcal{B}_1} = (2, 3, 1)$. Next for $v_2$:

$$v_2 = aw_1 + bw_2 + cw_3 \implies \begin{pmatrix} 1 \\ -3 \\ 5 \end{pmatrix} = a\begin{pmatrix}5 \\ 13 \\ -13 \end{pmatrix} + b\begin{pmatrix}0\\ -4 \\ 2\end{pmatrix} + c\begin{pmatrix}-7 \\ -13 \\ 18 \end{pmatrix} $$

Again, it is apparent that $[v_2]_{\mathcal{B}_1} = (3, 4, 2)$. Finally:

$$v_3 = aw_1 + bw_2 + cw_3 \implies \begin{pmatrix} 4 \\ 2 \\ 1 \end{pmatrix} = a\begin{pmatrix}5 \\ 13 \\ -13 \end{pmatrix} + b\begin{pmatrix}0\\ -4 \\ 2\end{pmatrix} + c\begin{pmatrix}-7 \\ -13 \\ 18 \end{pmatrix} $$

from which we can deduce $[v_3]_{\mathcal{B}_1} = (5, 6, 3)$. Therefore $\mathcal{B}_1$ is indeed a basis for lattice $L$. Furthermore

$$A = \begin{pmatrix}2 & 3 & 5\\ 3 & 4 & 6\\ 1 & 2 & 3 \end{pmatrix}$$

is the change of basis matrix from $\mathcal{B}$ into $\mathcal{B}_1$. But we are asked to express the new basis in terms of $\mathcal{B}$, which is the inverse of this matrix. So we compute

$$\det(A) = 2(12 - 12) -3(9 - 6) + 5(6 - 4) = -9 + 10 = 1$$

and

$$A^{-1} = \frac{1}{\det(A)}\begin{pmatrix}(12-12) & -(9-6) & (6-4)\\ -(9-10) & (6-5) & -(4-3)\\ (18-20) & -(12-15) & (8-9) \end{pmatrix}^T = \begin{pmatrix}0 & 1 & -2\\ -3 & 1 & 3\\ 2 & -1 & -1 \end{pmatrix}$$

where $A^{-1}$ is the matrix that sends component vectors in $\mathcal{B_1}$ into $\mathcal{B}$. As a quick check,
consider the component vector $[w_1]_{\mathcal{B}_1} = (1, 0, 0)$:

$$\begin{pmatrix}0 & 1 & -2\\ -3 & 1 & 3\\ 2 & -1 & -1 \end{pmatrix} \begin{pmatrix}1 \\ 0 \\ 0\end{pmatrix} = \begin{pmatrix}0\\ -3 \\ 2\end{pmatrix}$$

and

$$ 0v_1 -3v_2 + 2v_3 = (5, 13, -13)$$

as expected.

(b) $\mathcal{B}_2 = \{(4, -2, 3), (6, 6, -6), (-2, -4, 7)\}$.

Solution: If we take the same approach and try to write $v_1$ as a linear combination of the vectors in $\mathcal{B}_2$:

$$v_1 = aw_1 + bw_2 + cw_3 \implies \begin{pmatrix} 3 \\ 1 \\ -2 \end{pmatrix} = a\begin{pmatrix}4 \\ -2 \\ 3 \end{pmatrix} + b\begin{pmatrix}6\\ 6 \\ -6\end{pmatrix} + c\begin{pmatrix}-2 \\ -4 \\ 7 \end{pmatrix} $$

we can see from the first component that $a, b, c$ must satisfy

$$3 = 4a + 6b -2c = 2(2a +3b -c) \implies \frac{3}{2} = 2a + 3b - c$$

but clearly there are no integers that satisfy this equation. Thus, $\mathcal{B}_2$ is not a basis for $L$.

Problem 7.17

Let $L \subset \mathbb{R}^2$ be the lattice given y the basis $v_1 = (213, -437)$ and $v_2 = (312, 105)$, and let $w = (43127, 11349)$.

(a) Use Babai's algorithm to find a vector $v \in L$ that is close to $w$. Compute the distance $|v - w|$.

Solution: First we find an exact linear combination $w = t_1 v_1 + t_2 + v_2$:

$$ \begin{align*} 43127 &= 213t_1 + 312t_2 \\ 11349 &= -437 t_1 + 105 t_2 \\ \implies 43127-\frac{312}{105}\cdot 11349 &= t_1(213 + \frac{312}{105}\cdot 437) \\ \implies t_1 &\approx 6.22 \\ t_2 &\approx 133.98 \end{align*} $$

so

$$ \begin{align*} v &= 6(213, -437) + 134(312, 105) = (43086, 11448) \\ | v - w| &= |(44, -99)| = \sqrt{41^2 + 99^2} \approx 107.15 \end{align*}$$

(b) What is the value of the Hadamard ratio $(\det(L)/|v_1||v_2|)^{1/2}$? Is the basis $\{v_1, v_2\}$ a "good" basis?

Solution: First we compute

$$ \begin{align*} \det(L) &= 213\cdot105 - (-437)\cdot312 = 158709 \\ |v_1| &= \sqrt{213^2 + 437^2} \approx 486.15 \\ |v_2| &= \sqrt{312^2 + 105^2} \approx 329.19 \end{align*}$$

Then

$$\sqrt{\frac{\det(L)}{|v_1||v_2|}} \approx \sqrt{\frac{158709}{486.15\cdot329.19}} \approx 0.996. $$

Since the Hadamard ratio is close to 1, these basis vectors are highly orthogonal, so this is a good basis for Babai's algorithm.

(c) Show that the vectors $v_1' = (2937, -1555)$ and $v_2' = (11223, -5888)$ are also a basis for $L$ by expressing them as linear combinations of $v_1$ and $v_2$ and checking that the change-of-basis matrix has integer coefficients and determinant $\pm1$.

Solution: As directed, first we solve $v_1' = t_1v_1 + t_2v_2$:

$$\begin{align*}2937 &= 213t_1 + 312t_2 \\ -1555 &= -437t_1 +105t_2 \\ \implies -1555 + \frac{437}{213}\cdot 2937 &= t_2(\frac{437}{213}\cdot 312 + 105) \\ \implies t_2 &= 6 \\ \implies t_1 &= \frac{2937 - 6\cdot 312}{213} = 5 \\ \implies v_1' &= 5v_1 + 6v_2 \end{align*}$$

and next solve $v_2' = t_1v_1 + t_2v_2$:

$$\begin{align*}11223 &= 213t_1 + 312t_2 \\ -5888 &= -437t_1 +105t_2 \\ \implies -5888 + \frac{437}{213}\cdot 11223 &= t_2(\frac{437}{213}\cdot 312 + 105) \\ \implies t_2 &= 23 \\ \implies t_1 &= \frac{11223 - 23\cdot 312}{213} = 19 \\ \implies v_2' &= 19v_1 + 23v_2 \end{align*}$$

So the change of basis matrix is

$$B = \begin{pmatrix} 6 & 23 \\ 5 & 19 \end{pmatrix} $$

which has integer coefficients and determinant $6\cdot19 - 5\cdot23 = -1$. So $v_1', v_2'$ indeed form a basis for $L$.

(d) Use Babai's algorithm with the basis $\{v_1', v_2'\}$ to find a vector $v' \in L$. Compute the distance $|v' - w|$ and compare it to your answer from (a).

Solution: Once again we solve $w = t_1 v_1' + t_2 v_2'$ with real numbers first:

$$ \begin{align*} 43127 &= 2937 t_1 + 11223 t_2 \\ 11349 &= -1555 t_1 -5888 t_2 \\ \implies 11349+\frac{1555}{2937}\cdot 43127 &= t_2(-5888 + \frac{1555}{2937}\cdot 11223) \\ \implies t_2 &\approx 632.57 \\ t_1 &\approx -2402.52 \end{align*} $$

so

$$ \begin{align*} v &= -2403(2937, -1555) + 633(11223, -5888) = (46548, 9561) \\ | v - w| &= |(3421, -1788)| = \sqrt{3421^2 + 1788^2} \approx 3860.08 \end{align*}$$

which is much less accurate than the vector found in part (a).

(e) Compute the Hadamard ratio using $v_1'$ and $v_2'$. Is $\{v_1', v_2'\}$ a good basis?

Solution: The Hadamard ratio is

$$\sqrt{\frac{\det(L)}{|v_1'||v_2'|}} \approx \sqrt{\frac{158709}{\sqrt{2937^2 + 1555^2}\sqrt{11223^2 + 5888^2}}} \approx 0.06 $$

which is quite small, meaning that the basis vectors are very unorthogonal, and explains the inaccuracy observed in part (d). So this is not a good basis for Babai's algorithm.

Problem 7.19

Alice uses the GGH cryptosystem with private basis

$$v_1 = (58, 53, -68) \quad v_2 = (-110, -112, 35), \quad v_3 = (-10, -119, 123) $$

and public basis

$$\begin{align*}w_1 &= (324850, -1625176, 2734951) \\ w_2 &= (165782, -829409, 1395775), \\ w_3 &= (485054, -2426708, 4083804). \end{align*}$$

(a) Compute the determinant of Alice's lattice and the Hadamard ratio of the private and public bases.

Solution: First, the determinant of the lattice is:

$$\begin{align*}\det(L) &= \left| 58(-112\cdot123 + 35\cdot119) -53(-110\cdot123 + 35\cdot10) - 68(110\cdot119 - 112\cdot10)) \right| \\ &= 672858. \end{align*}$$

Next, for the private basis:

$$ \begin{align*} | v_1 | &= \sqrt{58^2 + 53^2 + 68^2} \approx 103.91 \\ |v_2 | &= \sqrt{110^2 + 112^2 + 35^2} \approx 160.84 \\ |v_3| &= \sqrt{10^2 + 119^2 + 123^2} \approx 171.44 \end{align*} $$

$$h_{priv} = \left( \frac{\det(L)}{|v_1||v_2||v_3|} \right)^{1/3} \approx 0.617$$

And for the public basis:

$$ \begin{align*} | w_1 | &= \sqrt{324850^2 + 1625176^2 + 2734951^2} \approx 3197918.31 \\ |w_2 | &= \sqrt{165782^2 + 829409^2 + 1395775^2} \approx 1632051.11 \\ |w_3| &= \sqrt{485054^2 + 2426708^2 + 4083804^2} \approx 4775106.72 \end{align*} $$

$$h_{pub} = \left( \frac{\det(L)}{|w_1||w_2||w_3|} \right)^{1/3} \approx 0.00003.$$

(b) Bob sends Alice the encrypted message $e = (8930810, -44681748, 75192665)$. Use Alice's private basis to decrypt the message and recover the plaintext. Also determine Bob's random perturbation $r$.

Solution: To decrypt, we first use Babai's algorithm. Setting $e = t_1v_2 + t_2v_2 + t_3v_3$:

$$\begin{align*}8930810 &= 58t_1 - 110t_2 - 10 t_3 \\ -44681748 &= 53 t_1 - 112 t_2 - 119 t_3 \\ 75192665 &= -68 t_1 + 35 t_2 + 123 t_3 \\ \\ \implies t_1 &\approx 334.865 \\ t_2 &\approx -304373 \\ t_3 &\approx 512804 \\ \\ \implies v &= \lfloor t_1 \rceil v_1 + \lfloor t_2 \rceil v_3 + \lfloor t_3 \rceil v_3 \\ &= (8930820, -44681745, 75192657)\end{align*}$$

Finally we find $m$ by solving $v = m_1 w_1 + m_2 w_2 + m_3 w_3$:

$$\begin{align*}8930820 &= 324850m_1 + 165782m_2 + 485054 m_3 \\ -44681745 &= -1625176m_1 - 829409m_2 - 2426708 m_3 \\ 75192657 &= 2734951m_1 + 1395775 m_2 + 4083804 m_3 \\ \\ \implies m_1 &= -50 \\ m_2 &= -91 \\ m_3 &= 83 \\ \\ \implies m &= (-50, -91, 83) \end{align*}$$

And calculate the random perturbation:

$$\begin{align*}r &= e - mW \\ &= (8930810, -44681748, 75192665) - (-50)w_1 - (-91)w_2 - 83w_3 \\ &= (-10, -3, 8) \end{align*}$$

(c) Try to decrypt Bob's message using Babai's algorithm with the public basis. Is the output equal to the plaintext?

Solution: Setting $e = t_1w_1 + t_2w_2 + t_3w_3$ we find

$$\begin{align*}8930810 &= 324850t_1 + 165782 t_2 + 485054 t_3 \\ -44681748 &= -1625176 t_1 - 829409 t_2 - 2426708 t_3 \\ 75192665 &= 2734951 t_1 + 1395775 t_2 + 4083804 t_3 \\ \\ \implies t_1 &\approx 51.6 \\ t_2 &\approx 416.7 \\ t_3 &\approx -158.6 \\ \\ \implies m' &= \lfloor t_1 \rceil w_1 + \lfloor t_2 \rceil w_3 + \lfloor t_3 \rceil w_3 \\ &= (52, 417, -159)\end{align*}$$

which is not the correct plaintext.

Problem 7.20

Bob uses the GGH cryptosystem to send some messages to Alice.

(a) Suppose that Bob sends the same message $m$ twice, using different random elements $r$ and $r'$. Explain what sort of information Eve can deduce from the ciphertexts $e = mW + r$ and $e' = mW + r'$.

Solution: Because the $r$ are small, Eve might notice that $e$ and $e'$ are similar and suspect that the ciphertexts belong to the same plaintext; this alone is a problem for IND-CPA security. Furthermore, she can compute

$$\ell = e - e' = (mW + r) - (mW +r') = r - r'.$$

to learn the difference between the random perturbations. If the random perturbations are from a finite set, this reveals quite a bit, as seen in part (b). In the more realistic case where each $r_i$ is chosen as a small real number $-\delta < r_i < \delta$, instead of having to search the hypercube

$$ \{(e_1 + \delta_1, \ldots, e_n + \delta_n) : |\delta_i| < \delta \}$$

for a lattice point, now Eve can search the intersection of both hypercubes:

$$ \{(e_1 + \delta_1, \ldots, e_n + \delta_n) : |\delta_i| < \delta \} \cap \{(e_1' + \delta_1, \ldots, e_n' + \delta_n) : |\delta_i| < \delta \}$$

so her CVP has gotten potentially easier.

(b) For example, suppose that $n = 5$ and that random permutations are chosen with coordinates in the set $\{-2, -1, 0, 1, 2\}$. This means that there are $5^5 = 3125$ possibilities for $r$. Suppose further that Eve intercepts two ciphertexts

$$e = (-9, -29, -48, 18, 48) \text{ and } e' = (-6, -26, -51, 20, 47)$$

having the same plaintext. With this information, how many possibilities are there for $r$?

Solution: As we mentioned in part (a), we can take the difference:

$$ r - r' = e - e' = (-3, -3, 3, -2, 1). $$

Taking the first component, we see that $r_1 - r_1' = -3$. The only way that this is possible given the choices for each $r_i$ is if $(r_1, r_1') \in \{(-1, 2), (-2, 1)\}$. Continuing in this fashion, we have:

1. Two possibilities for $(r_1, r_1')$: $\{(-1, 2), (-2, 1)\}$
2. Two possibilities for $(r_2, r_2')$: $\{(-1, 2), (-2, 1)\}$
3. Two possibilities for $(r_3, r_3')$: $\{(1, -2), (2, -1)\}$
4. Three possibilities for $(r_4, r_4')$: $\{(-2, 0), (-1, 1), (0, 2)\}$
5. Four possibilities for $(r_5, r_5')$: $\{(2, 1), (1, 0), (0, -1), (-1, -2) \}$
   and since these are componentwise independent, there are

$$ 2 \cdot 2 \cdot 2 \cdot 3 \cdot 4 = 96 $$

possible values of $r$.

(c) Suppose that Bob is lazy and uses the same perturbation to send two different messages. Explain what sort of information Eve can deduce from the ciphertexts $e = mW +r$ and $e' = m'W + r$.

Solution: Using the same perturbation is quite bad! It removes randomness from the encryption process, again failing IND-CPA security. For example, two identical plaintexts yield two identical ciphertexts. More generally, Eve can compute

$$ (e - e')W^{-1} = \left((mW + r) - (m'W + r)\right)W^{-1} = (m - m')WW^{-1} = m - m'$$

and can see the difference between the two plaintexts.

Problem 7.23

Compute the polynomial convolution product $c = a \star b$ modulo $q$ using the given values of $q$ and $N$.

(a) $N = 3, ; q = 7$,

$$ a(x) = 1 + x,\quad b(x) = -5 + 4x + 2x^2$$

Solution:

$$\begin{align*}a(x) \star b(x) &= -5 + 4x +2x^2 - 5x + 4x^2 + 2x^3 \\ &= -5 -x + 6x^2 + 2 \\ &= -3 -x -x^2 \\ &= -5 -x + 6x^2 + 2 \\ &= -3 -x -x^2. \end{align*}$$

(b) $N = 5, ; q = 4$,

$$a(x) = 2 + 2x - 2x^2 + x^3 - 2x^4,\quad b(x) = -1 + 3x - 3x^2 - 3x^3 - 3x^4$$

Solution: First rewrite

$$a(x) = 2 + 2x + 2x^2 + x^3 + 2x^4,\quad b(x) = -1 -x + x^2 + x^3 + x^4$$

$$\begin{align*}a(x) \star b(x) &= &-2 &-2x &-2x^2 &-x^3 &-2x^4 & & & & \\ & & &-2x &-2x^2 &-2x^3 &-x^4 &-2x^5 \\ & & & &+2x^2 &+2x^3 &+2x^4 &+x^5 &+2x^6 \\ & & & & &+2x^3 &+2x^4 &+2x^5 &+x^6 &+2x^7 \\ & & & & & &+2x^4 &+2x^5 &+2x^6 &+x^7 &+2x^8 \\ &= &-2 & &+2x^2 &+x^3 &+3x^4 &+3x^5 &+x^6 &+3x^7 &+2x^8 \\ &= &1 &+x &+x^2 &+3x^3 &+3x^4 & & & & \end{align*}$$

Problem 7.25

Let $N = 5$ and $q = 3$ and consider the two polynomials

$$a(x) = 1 + x^2 + x^3,\quad b(x) = 1 + x^2 - x^3 ; \in R_3.$$

One of these polynomials has an inverse in $R_3$ and the other does not. Compute the inverse that exists, and explain why the other doesn't exist.

Solution: Let's use the Euclidean algorithm to find the gcd with the modulus $x^5 - 1$. If the gcd is 1, then we can use the intermediary equations to form the inverse. Starting with $a$:

$$\begin{align}1 + x^2 + x^3 &= (0)(x^5 - 1) + (1 + x^2 + x^3) \\ (x^5-1) &= (1 + x ^2 +x^3)(1+2x +x^2) + (x^2 + x + 1) \\ (1 + x^2 + x^3) &= (x^2 + x + 1) (x) + (2x + 1) \\ (x^2 + x + 1) &= (2x + 1)(2x + 1) + 0\end{align}$$

we find that $\gcd(a(x), x^5 - 1) = 2x + 1 \ne 1$ which means $a(x)$ does not have an inverse in $R_3$. Let's try $b(x)$:

$$\begin{align}(1 + x^2 - x^3) &= (0)(x^5 - 1) + (1 + x^2 - x^3) \\ (x^5 - 1) &= (1 + x^2 - x^3)(2x^2 + 2x + 2) + (2x^2 + x) \\ (1+x^2 -x^3) &= (2x^2 +x)(x) + 1.\end{align}$$

So the gcd is 1 and

$$\begin{align*}1 &= (1 + x^2 - x^3) - (x)(2x^2 + x) \\ &= (1 + x^2 - x^3) - \left(x\right)\left( x^5 - 1 - (1 + x^2 -x^3)(2x^2 +2x + 2) \right) \\ &= \left(1+x^2 -x^3\right)\left( 1 + 2x + 2x^2 + 2x^3 \right) +2x(x^5-1).\end{align*}$$

Therefore $(1+x^2-x^3)^{-1} = 1 + 2x + 2x^2 + 2x^3$.