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. Showthatx2+y2 =q. (Thusanyprime≡1(mod4)canbe written as the sum of two integer squares.)
(b)(3marks)Nowallowq≡1(mod4)orq≡3(mod4). 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
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 − ⌊√n⌋ 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 = ⌊√n⌋. Let L be the lattice with basis v1 = (0,106) and v2 = (2,2k + 1). Show that the
浙大学霸代写 加微信 cstutorcs
ANTHONY HENDERSON
(unknown) lattice vector v = (n − m2)v1 − mv2 ∈ L satisfies
k2 +k √ v− −100, 106 <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 ).
duces the following reduced basis for L:
v1′ = (18, −1375), v2′ = (1448, 500).
We know that x = s1v1′ + s2v2′ for some s1, s2 ∈ R. Determine v′ = ⌊s1⌉v1′ +⌊s2⌉v2′ ∈ 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.)
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 (− 21 , 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) ̸= (0, 0)
⟨(z, w), (z, w)⟩ ≥ ⟨(z1, w1), (z1, w1)⟩.
106 (c) (2 marks) You can take for granted that Gauss’ algorithm pro-
程序代写 CS代考 加微信: cstutorcs