GLV Design

[jon-chuang]

This design is primarily based on the original GLV paper and Aztec's approach of doing pre-division by n and a second round of approximate division by right shift. We do an analysis to show that the error bound in terms of the short lattice basis lengths does not increase significantly.

Given a modulus n and a cheap endomorphism ϕ with associated scalar λ such that ϕ(P) = λP for all P in the curve, the objective is to compute two vectors in Z X Z, v1 = [a1, b1], v2 = [a2, b2] such that ||vi|| < sqrt(n) and ai - λbi = n*si = 0 mod n. By the construction from the extended euclidean algorithm found in the paper, we see that wlog a1|b2| + a2|b1| = n. We also know v1 linearly independent to v2.

Then, given any scalar k \in Z/nZ, one has that (k, 0) = β1 v1 + β2 v2, where β1, β2 in Q>=0 and by solving the linear equations, we find that

β2 = k/(a1*|b1/b2|*(-1)^{!(sign(b1) == sign(b2))} β1 = -b1/b2*β2.

If b1 has different signs to b2, β1 = |b2|*k/n, β2 = |b1|*k/n, since then k = (a1|b2| + a2|b1|)k/n and b1|b2| + b2|b1|= 0.

Else,

As a matter of fact, we can assume that at most one of b1, b2 are negative.

Choose R > r. Then, one computes g1 = round(R*|b2|/n), g2 = round(R*|b1|/n). Let kb + 1/2 = qn + t, 0 <= t < n. Note that if R*b + (n-1)/2 = g’n + t’, then g’ = R*b/n +1/2 - t’/n +ε. Then, if we take c = g’k/R = k/R(R*b/n +1/2 - t’/n +ε) = k*b/n +k/2R - t’k/nR + ε’. If we round this, we get a distance from k*b/2 by at most ||t/n - 1/2 + k/R(1/2 - t’/n) + ε’||. Notice that this is at most 1.

Let c1 = round(g1*k/R), c2 = round(g2*k/R). So our total error for u = (k, 0) - (c1*v1 + c2*v2) has ||u|| <= ||v1|| + ||v2|| <= 2*max(||v1||, ||v2||) < 2*sqrt(n) by the triangle equality and f(u) = k where f((a, b)) = a + λb. So we set k2 = -(c1b1 + c2b2) and k1 = k - λ*k2 mod n.

Notes:

1. There is some confusion involved in thinking about lattices both as a subset of ZZ X ZZ and also ZZ/nZZ X ZZ/nZZ