Lattices and Cryptography

Prev: Elliptic Curves and Cryptography Next: Additional Topics in Cryptography

Exercises

Section 7.1. A Congruential Public Key Cryptosystem

7.1

Alice uses the congruential cryptosystem with $q=918293817$ and private key $(f,g)=(19928,18643)$.

(a) What is Alice’s public key $h$?

(b) Alice receives the ciphertext $e=619168806$ from Bob. What is the plaintext?

(c) Bob sends Alice a second message by encrypting the plaintext $m=10220$ using the random element $r=19564$. What is the ciphertext that Bob sends to Alice?

Section 7.2. Subset-Sum Problems and Knapsack Cryptosystems

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)$, $S=260$.

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

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

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

7.3

Alice’s public key for a knapsack cryptosystem is

$$M=(5186,2779,5955,2307,6599,6771,6296,7306,4115,637).$$

Eve intercepts the encrypted message $S=4398$. She also breaks into Alice’s computer and steals Alice’s secret multiplier $A=4392$ and secret modulus $B=8387$. Use this information to find Alice’s superincreasing private sequence $r$ and then decrypt the message.

7.4

Proposition 7.3 gives an algorithm that solves an $n$-dimensional knapsack problem in $O(2^{n/2})$ steps, but it requires $O(2^{n/2})$ storage. Devise an algorithm, similar to Pollard’s rho algorithm (Sect. 5.5), that takes $O(2^{n/2})$ steps, but requires only $O(1)$ storage.

Section 7.3. A Brief Review of Vector Spaces

7.5

(a) Let

$$B=\{(1,3,2),(2,-1,3),(1,0,2)\},B^{\prime }=\{(-1,0,2),(3,1,-1),(1,0,1)\}.$$

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

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

7.6

Use the Gram-Schmidt algorithm (Theorem 7.13) to find an orthogonal basis from the given basis.

(a) $v_1=(1,3,2)$, $v_2=(4,1,-2)$, $v_3=(-2,1,3)$.

(b) $v_1=(4,1,3,-1)$, $v_2=(2,1,-3,4)$, $v_3=(1,0,-2,7)$.

Section 7.4. Lattices: Basic Definitions and Properties

7.7

Let $L$ be the lattice generated by $\{(1,3,-2),(2,1,0),(-1,2,5)\}$. Draw a picture of a fundamental domain for $L$ and find its volume.

7.8

Let $L\subset {\mathbb{R}}^m$ be an additive subgroup with the property that there is a positive constant $ϵ>0$ such that

$$L\cap \{w\in {\mathbb{R}}^m:\Vert w\Vert <ϵ\}=\{0\}.$$

Prove that $L$ is discrete, and hence is a lattice. In other words, show that in the definition of discrete subgroup, it suffices to check that (7.8) is true for the single vector $v=0$.

7.9

Prove that a subset of ${\mathbb{R}}^m$ is a lattice if and only if it is a discrete additive subgroup.

7.10

Let $A$ be an $n$-by-$n$ matrix with entries $a_{ij}$, and for each pair of indices $i$ and $j$, let $A_{ij}$ denote the $(n-1)$-by-$(n-1)$ matrix obtained by deleting the $i$th row of $A$ and the $j$th column of $A$. Define a new matrix $B$ whose $ij$th entry $b_{ij}$ is given by

$$b_{ij}=(-1{)}^{i+j}\det (A_{ji}).$$

The matrix $B$ is called the adjoint of $A$.

(a) Prove that $AB=BA=\det (A)I_n$, where $I_n$ is the $n$-by-$n$ identity matrix.

(b) Deduce that if $\det (A)\ne 0$, then

$$A^{-1}=\frac{1}{\det (A)}B.$$

(c) Suppose that $A$ has integer entries. Prove that $A^{-1}$ exists and has integer entries if and only if $\det (A)=\pm 1$.

(d) For those who know ring theory from Sect. 2.10 or from some other source, suppose that $A$ has entries in a ring $R$. Prove that $A^{-1}$ exists and has entries in $R$ if and only if $\det (A)$ is a unit in $R$.

7.11

Recall from Remark 7.16 that the general linear group ${\mathrm{GL}}_n(\mathbb{Z})$ is the group of $n$-by-$n$ matrices with integer coefficients and determinant $\pm 1$. Let $A$ and $B$ be matrices in ${\mathrm{GL}}_n(\mathbb{Z})$.

(a) Prove that $AB\in {\mathrm{GL}}_n(\mathbb{Z})$.

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

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

(d) Prove that ${\mathrm{GL}}_n(\mathbb{Z})$ is a group.

(e) Is ${\mathrm{GL}}_n(\mathbb{Z})$ a commutative group?

7.12

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

$$A_1=\left(\begin{array}{cc}3& 1\\ 2& 2\end{array}\right),A_2=\left(\begin{array}{cc}3& -2\\ 2& -1\end{array}\right),$$ $$A_3=\left(\begin{array}{ccc}3& 2& 2\\ 2& 1& 2\\ -1& 3& 1\end{array}\right),A_4=\left(\begin{array}{ccc}-3& -1& 2\\ 1& -3& -1\\ 3& 0& -2\end{array}\right).$$

7.13

Let $L$ be the lattice given by the basis

$$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 $B$, i.e., find the change of basis matrix.

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

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

7.14

Let $L\subset {\mathbb{R}}^m$ be a lattice of dimension $n$ and let $v_1,\dots ,v_n$ be a basis for $L$. The Gram matrix of $v_1,\dots ,v_n$ is the matrix

$$\mathrm{Gram}(v_1,\dots ,v_n)=(v_i\cdot v_j{)}_{1\le i,j\le n}.$$

(a) Let $F(v_1,\dots ,v_n)$ be the matrix (7.11) described in Proposition 7.20, except that now $F(v_1,\dots ,v_n)$ is an $n$-by-$m$ matrix, so it need not be square. Prove that

$$\mathrm{Gram}(v_1,\dots ,v_n)=F(v_1,\dots ,v_n)F(v_1,\dots ,v_n{)}^t.$$

(b) Prove that

$$\det (\mathrm{Gram}(v_1,\dots ,v_n))=\det (L{)}^2,\text{\hspace{1em}(7.62)}$$

where $\det (L)$ is the volume of the parallelepiped spanned by any basis for $L$.

(c) Let $L\subset {\mathbb{R}}^4$ be the 3-dimensional lattice with basis

$$v_1=(1,0,1,-1),v_2=(1,2,0,4),v_3=(1,-1,2,1).$$

Compute the Gram matrix of this basis and use it to compute $\det (L)$.

(d) Let $v_1^{\ast },\dots ,v_n^{\ast }$ be the Gram-Schmidt orthogonalized vectors associated to $v_1,\dots ,v_n$. Prove that

$$\det (\mathrm{Gram}(v_1,\dots ,v_n))=\Vert v_1^{\ast }{\Vert }^2\Vert v_2^{\ast }{\Vert }^2\cdots \Vert v_n^{\ast }{\Vert }^2.$$

Section 7.5. The Shortest and Closest Vector Problems

7.15

Let $L$ be a lattice and let $F$ be a fundamental domain for $L$. This exercise sketches a proof that

$$\underset{R\to \infty }{\lim }\frac{\#(B_R(0)\cap L)}{\mathrm{Vol}(B_R(0))}=\frac{1}{\mathrm{Vol}(F)}.\text{\hspace{1em}(7.63)}$$

(a) Consider the translations of $F$ that are entirely contained within $B_R(0)$, and also those that have nontrivial intersection with $B_R(0)$. Prove the inclusion of sets

$$\bigcup _{\begin{array}{c}v\in L\\ F+v\subset B_R(0)\end{array}}(F+v)\subset B_R(0)\subset \bigcup _{\begin{array}{c}v\in L\\ (F+v)\cap B_R(0)\ne \varnothing \end{array}}(F+v).$$

(b) Take volumes in (a) and prove the corresponding upper and lower bounds involving $\mathrm{Vol}(F)$.

(c) Prove that the number of translates $F+v$ that intersect $B_R(0)$ without being entirely contained within $B_R(0)$ is comparatively small compared to the number of translates that are entirely contained within $B_R(0)$.

(d) Use (b) and (c) to prove (7.63).

7.16

A lattice $L$ of dimension $n=251$ has determinant $\det (L)\approx 2^{2251.58}$. With no further information, approximately how large would you expect the shortest nonzero vector to be?

Section 7.6. Babai’s Algorithm and Solving CVP with a Good Basis

7.17

Let $L\subset {\mathbb{R}}^2$ be the lattice given by 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 $\Vert v-w\Vert$.

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

(c) Show that the vectors $v_1^{\prime }=(2937,-1555)$ and $v_2^{\prime }=(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 $\pm 1$.

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

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

Section 7.8. The GGH Public Key Cryptosystem

7.18

Alice uses the GGH cryptosystem with private basis

$$v_1=(4,13),v_2=(-57,-45),$$

and public basis

$$w_1=(25453,9091),w_2=(-16096,-5749).$$

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

(b) Bob sends Alice the encrypted message $e=(155340,55483)$. Use Alice’s private basis to decrypt the message and recover the plaintext. Also determine Bob’s random perturbation $r$.

(c) Try to decrypt Bob’s message using Babai’s algorithm with the public basis $\{w_1,w_2\}$. Is the output equal to the plaintext?

7.19

Alice uses the GGH cryptosystem with private basis

$$\begin{array}{rl}{v}_1& =(58,53,-68),\\ v_2& =(-110,-112,35),\\ v_3& =(-10,-119,123),\end{array}$$

and public basis

$$\begin{array}{rl}{w}_1& =(324850,-1625176,2734951),\\ w_2& =(165782,-829409,1395775),\\ w_3& =(485054,-2426708,4083804).\end{array}$$

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

(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$.

(c) Try to decrypt Bob’s message using Babai’s algorithm with the public basis $\{w_1,w_2,w_3\}$. Is the output equal to the plaintext?

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^{\prime }$. Explain what sort of information Eve can deduce from the ciphertexts $e=mW+r$ and $e^{\prime }=mW+r^{\prime }$.

(b) For example, suppose that $n=5$ and that random perturbations 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}^{\prime }=(-6,-26,-51,20,47)$$

having the same plaintext. With this information, how many possibilities are there for $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^{\prime }=m^{\prime }W+r$.

7.21

The previous exercise shows the danger of using GGH to send a single message $m$ twice using different values of $r$.

(a) In order to guard against this danger, suppose that Bob generates $r$ by applying a publicly available hash function $\mathrm{Hash}$ to $m$, i.e., Bob’s encrypted message is

$$e=mW+\mathrm{Hash}(m).$$

If Eve guesses that Bob’s message might be $m^{\prime }$, explain why she can check whether her guess is correct.

(b) Explain why the following algorithm eliminates both the problem with repeated messages and the problem described in (a), while still allowing Alice to decrypt Bob’s message. Bob chooses a message $m_0$ and a random string $r_0$. He then computes

$$m=(m_0\mathrm{xor}{r}_0)\Vert r_0,r=\mathrm{Hash}(m),e=mW+r.$$

(c) In (b), the advantage of constructing $m$ from $(m_0\mathrm{xor}{r}_0)$ is that none of the bits of the actual plaintext $m_0$ appear unaltered in $m$. In practice, people replace $(m_0\mathrm{xor}{r}_0)\Vert r_0$ with more complicated mixing functions $M(m_0,r_0)$ having the following two properties: (1) $M$ is easily invertible. (2) If even one bit of either $m_0$ or $r_0$ changes, then the value of every bit of $M(m_0,r_0)$ changes in an unpredictable manner. Try to construct a mixing function $M$ having these properties.

Section 7.9. Convolution Polynomial Rings

7.22

Compute by hand the polynomial convolution product $c=a\star b$ using the given value of $N$.

(a) $N=3$, $a(x)=-1+4x+5x^2$, $b(x)=-1-3x-2x^2$.

(b) $N=5$, $a(x)=2-x+3x^3-3x^4$, $b(x)=1-3x^2-3x^3-x^4$.

(c) $N=6$, $a(x)=x+x^2+x^3$, $b(x)=1+x+x^5$.

(d) $N=10$, $a(x)=x+x^2+x^3+x^4+x^6+x^7+x^9$, $b(x)=x^2+x^3+x^6+x^8$.

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$, $b(x)=-5+4x+2x^2$.

(b) $N=5$, $q=4$, $a(x)=2+2x-2x^2+x^3-2x^4$, $b(x)=-1+3x-3x^2-3x^3-3x^4$.

(c) $N=7$, $q=3$, $a(x)=x+x^3$, $b(x)=x+x^2+x^4+x^6$.

(d) $N=10$, $q=2$, $a(x)=x^2+x^5+x^7+x^8+x^9$, $b(x)=1+x+x^3+x^4+x^5+x^7+x^8+x^9$.

7.24

Let $a(x)\in (\mathbb{Z}/q\mathbb{Z})[x]$, where $q$ is a prime.

(a) Prove that

$$a(1)\equiv 0(\mathrm{mod}q)\text{if and only if}(x-1)\mid a(x)\text{ in }(\mathbb{Z}/q\mathbb{Z})[x].$$

(b) Suppose that $a(1)\equiv 0(\mathrm{mod}q)$. Prove that $a(x)$ is not invertible in $R_q$.

7.25

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

$$a(x)=1+x^2+x^3\in R_3,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 does not exist.

7.26

For each of the following values of $N$, $q$, and $a(x)$, either find $a(x{)}^{-1}$ in $R_q$ or show that the inverse does not exist.

(a) $N=5$, $q=11$, and $a(x)=x^4+8x+3$.

(b) $N=5$, $q=13$, and $a(x)=x^3+2x-3$.

(c) $N=7$, $q=23$, and $a(x)=20x^6+8x^5+4x^4+15x^3+19x^2+x+8$.

7.27

This exercise illustrates how to find inverses in

$$R_m=\frac{(\mathbb{Z}/m\mathbb{Z})[x]}{(x^N-1)}$$

when $m$ is a prime power $p^e$.

(a) Let $f(x)\in \mathbb{Z}[x]/(x^N-1)$ be a polynomial, and suppose that we have already found a polynomial $F(x)$ such that

$$f(x)\star F(x)\equiv 1(\mathrm{mod}{p}^i)$$

for some $i\ge 1$. Prove that the polynomial

$$G(x)=F(x)\star (2-f(x)\star F(x))$$

satisfies

$$f(x)\star G(x)\equiv 1(\mathrm{mod}{p}^{2i}).$$

(b) Suppose that we know an inverse of $f(x)$ modulo $p$. Using (a) repeatedly, how many convolution multiplications does it take to compute the inverse of $f(x)$ modulo $p^e$?

(c) Use the method in (a) to compute the following inverses modulo $m=p^e$, where to ease your task, we have given you the inverse modulo $p$.

(i) $N=5$, $m=2^4$, $f(x)=7+3x+x^2$, $f(x{)}^{-1}\equiv 1+x^2+x^3(\mathrm{mod}2)$.

(ii) $N=5$, $m=2^7$, $f(x)=22+11x+5x^2+7x^3$, $f(x{)}^{-1}\equiv 1+x^2+x^3(\mathrm{mod}2)$.

(iii) $N=7$, $m=5^5$, $f(x)=112+34x+239x^2+234x^3+105x^4+180x^5+137x^6$, $f(x{)}^{-1}\equiv 1+3x^2+2x^4(\mathrm{mod}5)$.

7.28

Let $a\in R_N$ be a fixed vector.

(a) Suppose that $b$ is an $N$-dimensional vector whose coefficients are chosen randomly from the set $\{-1,0,1\}$. Prove that the expected values of $\Vert b{\Vert }^2$ and $\Vert a\star b{\Vert }^2$ are given by

$$E(\Vert b{\Vert }^2)=\frac{2N}{3},E(\Vert a\star b{\Vert }^2)=\Vert a{\Vert }^{2}E(\Vert b{\Vert }^2).$$

(b) More generally, suppose that the coefficients of $b$ are chosen at random from the set of integers $\{-T,-T+1,\dots ,T-1,T\}$. Compute the expected values of $\Vert b{\Vert }^2$ and $\Vert a\star b{\Vert }^2$ as in (a).

(c) Suppose now that the coefficients of $b$ are real numbers that are chosen uniformly and independently in the interval from $-R$ to $R$. Prove that

$$E(\Vert b{\Vert }^2)=\frac{R^{2}N}{3},E(\Vert a\star b{\Vert }^2)=\Vert a{\Vert }^{2}E(\Vert b{\Vert }^2).$$

(d) For each of the scenarios described in (a), (b), and (c), prove that

$$E(\Vert a+b{\Vert }^2)=\Vert a{\Vert }^2+E(\Vert b{\Vert }^2).$$

Section 7.10. The NTRU Public Key Cryptosystem

7.29

Alice and Bob agree to communicate using NTRUEncrypt with $(N,p,q)=(7,3,37)$. Alice’s private key is

$$f(x)=-1+X-X^3+X^4+X^5,$$ $$F_3(x)=1+X-X^2+X^4+X^5+X^6.$$

Alice receives the ciphertext

$$e(x)=2+8X^2-16X^3-9X^4-18X^5-3X^6$$

from Bob. Decipher the message and find the plaintext.

7.30

Alice and Bob decide to communicate using NTRUEncrypt with parameters $(N,p,q)=(7,3,29)$. Alice’s public key is

$$h(x)=3+14X-4X^2+13X^3-6X^4+2X^5+7X^6.$$

Bob sends Alice the plaintext message $m(x)=1+X-X^2-X^3-X^6$ using the random element $r(x)=-1+X^2-X^5+X^6$.

(a) What ciphertext does Bob send to Alice?

(b) Alice’s private key is $f(x)=-1+X-X^2+X^4+X^6$ and $F_3(x)=1+X+X^2+X^4+X^5-X^6$. Check your answer in (a) by using $f$ and $F_3$ to decrypt the message.

7.31

What is the message expansion of NTRUEncrypt in terms of $N$, $p$, and $q$?

7.32

The guidelines for choosing NTRUEncrypt public parameters $(N,p,q,d)$ require that $\gcd (p,q)=1$. Prove that if $p\mid q$, then it is very easy for Eve to decrypt the message without knowing the private key. Hint: First do the case that $p=q$.

7.33

The guidelines for choosing NTRUEncrypt public parameters $(N,p,q,d)$ include the assumption that $\gcd (N,q)=1$. Suppose instead that Alice takes $q=N$, where as always, $N$ is an odd prime.

(a) Make a change of variables $x=y+1$ in the ring $\mathbb{Z}[x]/(x^N-1)$, and show that the NTRU lattice takes a simpler form.

(b) Can you find an efficient way to break NTRU in the case that $q=N$ that does involve lattice reduction? This appears to be an open problem.

7.34

Alice uses NTRUEncrypt with $p=3$ to send messages to Bob.

(a) Suppose that Alice uses the same random element $r(x)$ to encrypt two different plaintexts $m_1(x)$ and $m_2(x)$. Explain how Eve can use the two ciphertexts $e_1(x)$ and $e_2(x)$ to determine approximately $\frac{2}{9}$ of the coefficients of $m_1(x)$. See Exercise 7.38 for a way to exploit this information.

(b) For example, suppose that $N=8$, so there are $3^8$ possibilities for $m_1(x)$. Suppose that Eve intercepts two ciphertexts

$$\begin{array}{rl}{e}_1(x)& =32+21x-9x^2-20x^3-29x^4-29x^5-19x^6+38x^7,\\ e_2(x)& =33+21x-7x^2-19x^3-31x^4-27x^5-19x^6+38x^7,\end{array}$$

that were encrypted using the same random element $r(x)$. How many coefficients of $m_1(x)$ can she determine exactly? How many possibilities are there for $m_1(x)$?

(c) Formulate a similar attack if Alice uses two different random elements $r_1(x)$ and $r_2(x)$ to encrypt the same plaintext $m(x)$. Hint: Do it first assuming that $h(x)$ has an inverse in $R_q$. The problem is harder without this assumption.

7.35

This exercise describes a variant of NTRUEncrypt that eliminates a step in the decryption algorithm at the cost of requiring slightly larger parameters. Suppose that the NTRUEncrypt private key polynomials $f(x)$ and $g(x)$ are chosen to satisfy

$$f(x)=1+p{f}_0(x)\equiv 1(\mathrm{mod}p),g(x)=p{g}_0(x)\equiv 0(\mathrm{mod}p),$$

and that NTRU encryption is changed to

$$e(x)\equiv h(x)\star r(x)+m(x)(\mathrm{mod}q).$$

(a) Prove that if $q$ is sufficiently large, then the following algorithm correctly decrypts the message:

• Compute $a(x)\equiv f(x)\star e(x)(\mathrm{mod}q)$ and center-lift to an element of $R$.
• Compute $a(x)(\mathrm{mod}p)$. The result is $m(x)$.

Note that this eliminates the necessity to multiply $a(x)$ by $f(x{)}^{-1}(\mathrm{mod}p)$.

(b) Suppose that we choose $f_0,g_0\in T(d,d)$, and that we also assume that $m$ is ternary. Prove that decryption works provided $q>8dp+2$. Hint: Mimic the proof of Proposition 7.48.

Section 7.11. NTRU as a Lattice Cryptosystem

7.36

This exercise explains how to formulate NTRU message recovery as a closest vector problem. Let $h(x)$ be an NTRU public key and let

$$e(x)\equiv pr(x)\star h(x)+m(x)(\mathrm{mod}q)$$

be a message encrypted using $h(x)$.

(a) Prove that the vector $(pr,e-m)$ is in $L_h^{\mathrm{NTRU}}$.

(b) Prove that the lattice vector in (a) is almost certainly the closest lattice vector to the known vector $(0,e)$. Hence solving CVP reveals the plaintext $m$. For simplicity, you may assume that $d\approx N/3$ and $q\approx 2N$, as we did in Proposition 7.61.

(c) Show how one can reduce the lattice-to-target distance, without affecting the determinant, by using instead a modified NTRU lattice of the form

$$\left(\begin{array}{cc}1& ph\\ 0& q\end{array}\right).$$

7.37

The guidelines for choosing NTRUEncrypt public parameters $(N,p,q,d)$ include the requirement that $N$ be prime. To see why, suppose that $N$ is even. Explain how Eve can recover the private key by solving a lattice problem in dimension $N$, rather than in dimension $2N$. Hint: Use the natural map

$$\mathbb{Z}[x]/(x^N-1)\to \mathbb{Z}[x]/(x^{N/2}-1).$$

7.38

Suppose that Bob and Alice are using NTRUEncrypt to exchange messages and that Eve intercepts a ciphertext $e(x)$ for which she already knows part of the plaintext $m(x)$. More precisely, suppose that Eve knows $t$ of the coefficients of $m(x)$. Explain how to set up a CVP to find $m(x)$ using a lattice of dimension $2N-2t$.

Section 7.12. Lattice-Based Digital Signature Schemes

7.39

Samantha uses the GGH digital signature scheme with private and public bases

$$\begin{array}{rlrl}{v}_1& =(-20,-8,1),& w_1& =(-248100,220074,332172),\\ v_2& =(14,11,23),& w_2& =(-112192,99518,150209),\\ v_3& =(-18,1,-12),& w_3& =(-216150,191737,289401).\end{array}$$

What is her signature on the document $d=(834928,123894,7812738)$?

7.40

Samantha uses the GGH digital signature scheme with public basis

$$\begin{array}{rl}{w}_1& =(3712318934,-14591032252,11433651072),\\ w_2& =(-1586446650,6235427140,-4886131219),\\ w_3& =(305711854,-1201580900,941568527).\end{array}$$

She publishes the signature $(6987814629,14496863295,-9625064603)$ on the document $d=(5269775,7294466,1875937)$. If the maximum allowed distance from the signature to the document is 60, verify that Samantha’s signature is valid.

7.41

Samantha uses the GGH digital signature scheme with public basis

$$\begin{array}{rl}{w}_1& =(-1612927239,1853012542,1451467045),\\ w_2& =(-2137446623,2455606985,1923480029),\\ w_3& =(2762180674,-3173333120,-2485675809).\end{array}$$

Use LLL or some other lattice reduction algorithm to find a good basis for Samantha’s lattice, and then use the good basis to help Eve forge a signature on the document $d=(87398273893,763829184,118237397273)$. What is the distance from your forged signature lattice vector to the target vector? You should be able to get a distance smaller than 100.

7.42

This exercise gives further details of the NTRUMLS signature scheme. We fix parameters $(N,p,q)$ and set

$$B=\frac{p^{2}N}{4},A=\frac{q}{2p}-\frac{1}{2}.$$

We choose private key polynomials $f$ and $g$ as follows. For $f$ we first choose a polynomial $F$ whose coefficients are randomly selected from the set $\{-1,0,1\}$ and then let $f=pF$. For $g$ we choose a polynomial whose coefficients are randomly selected to lie between $-p/2$ and $p/2$. We further assume that both $F$ and $g$ are invertible modulo $p$ and that $f$ is invertible modulo $q$, otherwise we discard them and choose new polynomials.

(a) If $a$ and $b$ are polynomials whose coefficients lie between $-p/2$ and $p/2$, prove that $\Vert a\star b{\Vert }_{\infty }\le B$.

(b) Prove that the following algorithm outputs a pair of polynomials $(s,t)$ satisfying

$$t\equiv h\star s(\mathrm{mod}q),s\equiv s_p(\mathrm{mod}p),t\equiv t_p(\mathrm{mod}p).$$

0: Input polynomials s_p and t_p with coefficients between -p/2 and p/2.
1: Choose a random polynomial r with coefficients between -A and A.
2: Set s_0 = s_p + pr.
3: Set t_0 = h*s_0 mod q with ||t_0||_infty <= q/2.
4: Set a = g^{-1}*(t_p - t_0) mod p with ||a||_infty <= p/2.
5: Set s = s_0 + a*f and t = t_0 + a*g.

(c) Prove that the output from the algorithm in (b) satisfies

$$\Vert s{\Vert }_{\infty }\le \frac{q}{2}+B\text{and}\Vert t{\Vert }_{\infty }\le \frac{q}{2}+B.$$

(d) Make the simplifying assumption that the output produces polynomials whose coefficients are uniformly and independently distributed between $-\frac{1}{2}q-B$ and $\frac{1}{2}q+B$. Assume further that $k:=q/NB$ is not too large, say $2\le k\le 50$. Prove that the probability that the algorithm in (b) produces a valid signature is approximately $e^{-8/k}$.

Section 7.13. Lattice Reduction Algorithms

7.43

Let $b_1$ and $b_2$ be vectors, and set

$$t=\frac{b_1\cdot b_2}{\Vert b_1{\Vert }^2}\text{and}{b}_2^{\ast }=b_2-t{b}_1.$$

Prove that $b_2^{\ast }\cdot b_1=0$ and that $b_2^{\ast }$ is the projection of $b_2$ onto the orthogonal complement of $b_1$.

7.44

Let $a$ and $b$ be nonzero vectors in ${\mathbb{R}}^n$.

(a) What value of $t\in \mathbb{R}$ minimizes the distance $\Vert a-tb\Vert$?

(b) What is the minimum distance in (a)?

(c) If $t$ is chosen as in (a), show that $a-tb$ is the projection of $a$ onto the orthogonal complement of $b$.

(d) If the angle between $a$ and $b$ is $\theta$, use your answer in (b) to show that the minimum distance is $\Vert a\Vert \sin \theta$. Draw a picture illustrating this result.

7.45

Apply Gauss’s lattice reduction algorithm (Proposition 7.66) to solve SVP for the following two dimensional lattices having the indicated basis vectors. How many steps does the algorithm take?

(a) $v_1=(120670,110521)$ and $v_2=(323572,296358)$.

(b) $v_1=(174748650,45604569)$ and $v_2=(35462559,9254748)$.

(c) $v_1=(725734520,613807887)$ and $v_2=(3433061338,2903596381)$.

7.46

Let $V$ be a vector space, let $W\subset V$ be a vector subspace of $V$, and let $W^{\perp }$ be the orthogonal complement of $W$ in $V$.

(a) Prove that $W^{\perp }$ is also a vector subspace of $V$.

(b) Prove that every vector $v\in V$ can be written as a sum $v=w+w^{\prime }$ for unique vectors $w\in W$ and $w^{\prime }\in W^{\perp }$.

(c) Let $w\in W$ and $w^{\prime }\in W^{\perp }$ and let $v=aw+b{w}^{\prime }$. Prove that

$$\Vert v{\Vert }^2=a^2\Vert w{\Vert }^2+b^2\Vert w^{\prime }{\Vert }^2.$$

7.47

Let $L$ be a lattice with basis vectors $v_1=(161,120)$ and $v_2=(104,77)$.

(a) Is $(0,1)$ in the lattice?

(b) Find an LLL reduced basis.

(c) Use the reduced basis to find the closest lattice vector to $(-\frac{9}{2},11)$.

7.48

Use the LLL algorithm to reduce the lattice with basis

$$v_1=(20,16,3),v_2=(15,0,10),v_3=(0,18,9).$$

You should do this exercise by hand, writing out each step.

7.49

Let $L$ be the lattice generated by the rows of the matrix

$$M=\left(\begin{array}{cccccc}20& 51& 35& 59& 73& 73\\ 14& 48& 33& 61& 47& 83\\ 95& 41& 48& 84& 30& 45\\ 0& 42& 74& 79& 20& 21\\ 6& 41& 49& 11& 70& 67\\ 23& 36& 6& 1& 46& 4\end{array}\right).$$

Implement the LLL algorithm (Fig. 7.8) on a computer and use your program to answer the following questions.

(a) Compute $\det (L)$ and $H(M)$. What is the shortest basis vector?

(b) Apply LLL to $M$. How many swaps are required? What is the value of $H(M^{\mathrm{LLL}})$? What is the shortest basis vector in the LLL reduced basis? How does it compare with the Gaussian expected shortest length?

(c) Reverse the order of the rows of $M$ and apply LLL to the new matrix. How many swaps are required? What is the value of $H(M^{\mathrm{LLL}})$ and what is the shortest basis vector?

(d) Apply LLL to the original matrix $M$, but in the Lovasz condition, use $0.99$ instead of $\frac{3}{4}$. How many swaps are required? What is the value of $H(M^{\mathrm{LLL}})$ and what is the shortest basis vector?

7.50

A more efficient way to implement the LLL algorithm is described in Fig. 7.9, with Reduce and Swap subroutines given in Fig. 7.10.

(a) Prove that the algorithm described in Figs. 7.9 and 7.10 returns an LLL reduced basis.

(b) For any given $N$ and $q$, let $L_{N,q}$ be the $N$-dimensional lattice with basis $v_1,\dots ,v_N$ described by the formulas

$$v_i=(r_{i1},r_{i2},\dots ,r_{iN}),r_{ij}\equiv (i+N{)}^j(\mathrm{mod}q),0\le r_{ij}<q.$$

Implement the LLL algorithm and use it to LLL reduce $L_{N,q}$ for each of the following values of $N$ and $q$:

(i) $(N,q)=(10,541)$.

(ii) $(N,q)=(20,863)$.

(iii) $(N,q)=(30,1223)$.

(iv) $(N,q)=(40,3571)$.

In each case, compare the Hadamard ratio of the original basis to the Hadamard ratio of the LLL reduced basis, and compare the length of the shortest vector found by LLL to the Gaussian expected shortest length.

LLL main routine and subroutines:

[1]  Input a basis {v_1,...,v_n} for a lattice L.
[2]  Set k = 2, kmax = 1, v_1^* = v_1, and B_1 = ||v_1^*||^2.
[3]  If k <= kmax go to Step [9].
[4]  Set kmax = k and v_k^* = v_k.
[5]  Loop j = 1,...,k-1:
[6]      Set mu_{k,j} = v_k dot v_j^*/B_j and v_k^* = v_k^* - mu_{k,j}v_j^*.
[7]  End loop.
[8]  Set B_k = ||v_k^*||^2.
[9]  Execute RED(k,k-1).
[10] If B_k < (3/4 - mu_{k,k-1}^2)B_{k-1}, execute SWAP(k), set k=max(2,k-1), and go to [9].
[11] Else execute RED(k,l) for l=k-2,k-3,...,1, then set k=k+1.
[12] If k <= n go to [3].
[13] Return the LLL reduced basis.
 
RED(k,l):
  If |mu_{k,l}| <= 1/2, return.
  Set m = round(mu_{k,l}), v_k = v_k - m v_l, and mu_{k,l}=mu_{k,l}-m.
  For i=1,...,l-1 set mu_{k,i}=mu_{k,i}-m mu_{l,i}.
 
SWAP(k):
  Exchange v_{k-1} and v_k.
  Update the Gram-Schmidt coefficients as in Fig. 7.10.

7.51

Let $\frac{1}{4}<\alpha <1$ and suppose that we replace the Lovasz condition with the condition

$$\Vert v_i^{\ast }{\Vert }^2\ge (\alpha -{\mu }_{i,i-1}^2)\Vert v_{i-1}^{\ast }{\Vert }^2\text{for all }1<i\le n.\text{\hspace{1em}(7.64)}$$

(a) Prove a version of Theorem 7.69 assuming the alternative Lovasz condition (7.64). What quantity, depending on $\alpha$, replaces the 2 that appears in the estimates (7.54)-(7.56)?

(b) Prove a version of Theorem 7.71 assuming the alternative Lovasz condition (7.64). In particular, how does the upper bound for the number of swap steps depend on $\alpha$? What happens as $\alpha \to 1$?

7.52

Let $v_1,\dots ,v_n$ be an LLL reduced basis for a lattice $L$.

(a) Prove that there are constants $C_1>1>C_2>0$ such that for all $y_1,\dots ,y_n\in \mathbb{R}$ we have

$$C_1^n\sum _{i=1}^n{y}_i^2\Vert v_i{\Vert }^2\ge {\Vert \sum _{i=1}^n{y}_i{v}_i\Vert }^2\ge C_2^n\sum _{i=1}^n{y}_i^2\Vert v_i{\Vert }^2.\text{\hspace{1em}(7.65)}$$

(b) Prove that there is a constant $C$ such that for any target vector $w\in {\mathbb{R}}^n$, Babai’s algorithm (Theorem 7.34) finds a lattice vector $v\in L$ satisfying

$$\Vert w-v\Vert \le C^n\underset{u\in L}{\min }\Vert w-u\Vert .$$

Thus Babai’s algorithm applied with an LLL reduced basis solves apprCVP to within a factor of $C^n$. This is Theorem 7.76.

(c) Find explicit values for the constants $C_1$, $C_2$, and $C$ in (a) and (b).

7.53

Babai’s Closest Plane Algorithm is an alternative rounding method that uses a given basis to solve apprCVP. Implement both of Babai’s algorithms (Theorem 7.34 and Fig. 7.11) and use them to solve apprCVP for each of the following lattices and target vectors. Which one gives the better result?

Closest plane algorithm:

Input a basis v_1,...,v_n of a lattice L and a target vector t.
Compute Gram-Schmidt orthogonalized vectors v_1^*,...,v_n^*.
Set w = t.
Loop i = n,n-1,...,1:
    Set w = w - (w dot v_i^*/||v_i^*||^2)v_i.
End loop.
Return the lattice vector t - w.

(a) $L$ is generated by the rows of the LLL reduced matrix

$$\left(\begin{array}{cccccc}-5& 16& 25& 25& 13& 8\\ 26& -3& -11& 14& 5& -26\\ 15& -28& 16& -7& -21& -4\\ 32& -3& 7& -30& -6& 26\\ 15& -32& -17& 32& -3& 11\\ 5& 24& 0& -13& -46& 15\end{array}\right)$$

and the target vector is $t=(-178,117,-407,419,-4,252)$.

(b) $L$ is generated by the rows of the matrix

$$\left(\begin{array}{cccccc}-33& -15& 22& -34& -32& 41\\ 10& 9& 45& 10& -6& -3\\ -32& -17& 43& 37& 29& -30\\ 26& 13& -35& -41& 42& -15\\ -50& 32& 18& 35& 48& 45\\ 2& -5& -2& -38& 38& 41\end{array}\right)$$

and the target vector is $t=(-126,-377,-196,455,-200,-234)$. Notice that the matrix is not LLL reduced.

(c) Apply LLL reduction to the basis in (b), and then use both of Babai’s methods to solve apprCVP. Do you get better solutions?

7.54

We proved that the LLL algorithm terminates and has polynomial running time under the assumption that $L\subset {\mathbb{Z}}^n$; see Theorem 7.71. Show that this assumption is not necessary by proving that LLL terminates in polynomial time for any lattice $L\subset {\mathbb{R}}^n$. You may assume that your computer can do exact computations in $\mathbb{R}$, although in practice one does need to worry about round-off errors. Hint: Use Hermite’s theorem to derive a lower bound, depending on the length of the shortest vector in $L$, for the quantity $D$ that appears in the proof of Theorem 7.71.

Section 7.14. Applications of LLL to Cryptanalysis

7.55

You have been spying on George for some time and overhear him receiving a ciphertext $e=83493429501$ that has been encrypted using the congruential cryptosystem described in Sect. 7.1. You also know that George’s public key is $h=24201896593$ and the public modulus is $q=148059109201$. Use Gaussian lattice reduction to recover George’s private key $(f,g)$ and the message $m$.

7.56

Let

$$M=(81946,80956,58407,51650,38136,17032,39658,67468,49203,9546)$$

and let $S=168296$. Use the LLL algorithm to solve the subset-sum problem for $M$ and $S$, i.e., find a subset of the elements of $M$ whose sum is $S$.

7.57

Alice and Bob communicate using the GGH cryptosystem. Alice’s public key is the lattice generated by the rows of the matrix

$$\left(\begin{array}{ccccc}10305608& -597165& 45361210& 39600006& 12036060\\ -71672908& 4156981& -315467761& -275401230& -83709146\\ -46304904& 2685749& -203811282& -177925680& -54081387\\ -68449642& 3969419& -301282167& -263017213& -79944525\\ -46169690& 2677840& -203215644& -177405867& -53923216\end{array}\right).$$

Bob sends her the encrypted message

$$e=(388120266,-22516188,1708295783,1491331246,453299858).$$

Use LLL to find a reduced basis for Alice’s lattice, and then use Babai’s algorithm to decrypt Bob’s message.

7.58

Alice and Bob communicate using NTRUEncrypt with public parameters $(N,p,q,d)=(11,3,67,3)$. Alice’s public key is

$$h=39+9x+33x^2+52x^3+58x^4+11x^5+38x^6+6x^7+x^8+48x^9+41x^{10}.$$

Apply the LLL algorithm to the associated NTRU lattice to find an NTRU private key $(f,g)$ for $h$. Check your answer by verifying that $g\equiv f\star h(\mathrm{mod}q)$. Use the private key to decrypt the ciphertext

$$e=52+50x+50x^2+61x^3+61x^4+7x^5+53x^6+46x^7+24x^8+17x^9+50x^{10}.$$

7.59

(a) Suppose that $k$ is a 10 digit integer, and suppose that when $\sqrt{k}$ is computed, the first 15 digits after the decimal place are 418400286617716. Find the number $k$. Hint: Reformulate it as a lattice problem.

(b) More generally, suppose that you know the first $d$ digits after the decimal place of $\sqrt{K}$. Explain how to set up a lattice problem to find $K$.

See Exercise 1.49 for a cryptosystem associated to this problem.