MATH3301/6114 ADD-ON MODULE (ASE/HPO/6114)
POST-QUANTUM CRYPTOGRAPHY ASSIGNMENT 2
DUE FRIDAY 20 OCTOBER AT 6PM
ANTHONY HENDERSON
There are 25 marks in total. Explain your reasoning in sufficient detail
to demonstrate your understanding, unless the question specifies otherwise.
(1) This question relates to the Toy NTRU cryptosystem from Add-on
Lecture 4 (Week 7). Suppose that Alice’s public key consists of
q = 131 and h = 100, so that the relevant lattice L is the one with
basis (1, 100), (0, 131).
(a) (3 marks) Use Gauss’ lattice basis reduction algorithm to find
a reduced basis of L. (You can use a calculator or computer to
do any required calculations, but show all the steps.)
(b) (2 marks) Suppose that Bob sends the encrypted message e =
78. What was his message m before encryption?
(2) This question shows some applications of the upper bound on λ1(L)
proved in Add-on Lecture 6 (Week 9). Let q be an odd prime.
(a) (2 marks) In this part, suppose that q ≡ 1 (mod 4). Recall that
it was shown in the main lectures that there exists an integer
h such that h2 ≡ −1 (mod q). Let L be the lattice with basis
(1, h), (0, q), and let (x, y) be a shortest nonzero vector of L.
Show that x2 + y2 = q. (Thus any prime ≡ 1 (mod 4) can be
written as the sum of two integer squares.)
(b) (3 marks) Now allow q ≡ 1 (mod 4) or q ≡ 3 (mod 4). You
can assume (it is shown by an easy counting argument) that
there exist integers u, v such that u2 + v2 ≡ −1 (mod q). By
considering the 4-dimensional lattice with generating matrix
1 0 u v
0 1 −v u
0 0 q 0
0 0 0 q
 ,
show that q can be written as a sum of four integer squares.
(3) Suppose that we know that there is a positive integer n < 104 such
that
√
n − b√nc has a decimal expansion beginning 0.888812 · · · .
How can we find n (without programming a computer to check all
the possibilities in turn)? Here is a method using lattice theory.
(a) (3 marks) Let k = 888812 and m = b√nc. Let L be the lattice
with basis v1 = (0, 10
6) and v2 = (2, 2k + 1). Show that the
2 ANTHONY HENDERSON
(unknown) lattice vector v = (n−m2)v1 −mv2 ∈ L satisfies∣∣∣∣∣∣∣∣v − (−100, k2 + k106
)∣∣∣∣∣∣∣∣ < 100√2.
(b) (3 marks) Explain why, given the result of (a), we can reason-
ably expect v to be the closest vector in L to x = (−100, k2+k
106
).
(c) (2 marks) You can take for granted that Gauss’ algorithm pro-
duces the following reduced basis for L:
v′1 = (18,−1375), v′2 = (1448, 500).
We know that x = s1v
′
1 + s2v
′
2 for some s1, s2 ∈ R. Determine
v′ = bs1ev′1+bs2ev′2 ∈ L. (You can use a calculator or computer
to do the calculations. Feel free to round the second component
of x to the nearest integer; that won’t change v′.)
(d) (2 marks) Working on the assumption that the unknown v de-
fined in (a) equals the known v′ defined in (c), find n. (You can
use a calculator or computer to do the calculations.)
(4) One way you might attempt to make the Toy NTRU cryptosystem
more secure is to use the Gaussian integers
Z[i] = {a+ bi | a, b ∈ Z} ⊂ C
instead of the integers Z. But this turns out to have the same vul-
nerability, because there is an analogue of Gaussian lattice basis
reduction for Z[i]-lattices in C2. On C2 we use (instead of the dot
product) the complex scalar product 〈−,−〉 defined by
〈(z1, w1), (z2, w2)〉 = z1z2 + w1w2, for z1, w1, z2, w2 ∈ C,
where z is the usual complex conjugate of z. A Z[i]-lattice in C2 is
a subset of the form
{u1(z1, w1) + u2(z2, w2) |u1, u2 ∈ Z[i]}
where (z1, w1), (z2, w2) is a given C-basis of C2. We say that this
basis is Z[i]-reduced if it satisfies the two conditions:
(i) 〈(z1, w1), (z1, w1)〉 ≤ 〈(z2, w2), (z2, w2)〉;
(ii) both the real part and the imaginary part of
〈(z1, w1), (z2, w2)〉
〈(z1, w1), (z1, w1)〉
belong to the interval (−12 , 12 ].
(a) (2 marks) Imitate Gauss’ algorithm to find a Z[i]-reduced basis
for the Z[i]-lattice with basis (1, i), (0, 2 + 3i).
(b) (3 marks) Show that if (z1, w1), (z2, w2) is a Z[i]-reduced basis
for the Z[i]-lattice L, then every (z, w) ∈ L with (z, w) 6= (0, 0)
satisfies
〈(z, w), (z, w)〉 ≥ 〈(z1, w1), (z1, w1)〉.