Cryptography Reference
In-Depth Information
Step 1: initial interpolation. Compute the polynomial A = (x
1
)(x
2
)(x
n
) 2 F
q
m
[x]; the unique polynomial V 2 F
q
m
[x] with deg V < n
satisfying V (
1
) = v
1
=
1
, V (
2
) = v
2
=
2
, and so on through V (
n
) = v
n
=
n
;
and the unique polynomial B 2 F
q
m
[x] with deg B < n satisfying B(
1
) =
1=
q
1
, B(
2
) = 1=
q
2
, and so on through B(
n
) = 1=
q
n
.
Step 2: lattice-basis construction. Define X = x
nt1
; F = Xy V 2
F
q
m
[x;y]; and E = F
q
FB. Compute the ` polynomials M
0
;M
1
;:::;M
`1
2
F
q
m
[x;y] shown in Figure 4.1. Observe that each of M
0
;M
1
;:::;M
`1
includes
A, E, and F to a total power of at least k; that each of M
0
;M
1
;:::;M
`1
includes A and E to a total power of at least j; and that Mi
i
has y-degree i.
The simplest strategy is to begin by computing E;E
2
;:::;E
j
; A;A
2
;:::;A
k
;
and F;F
2
;:::;F
maxfkj+q1;`qj1g
. Each M
i
is then a product of three known
polynomials. Overall this procedure uses O(`) polynomial products in F
q
m
[x;y],
each of product degree ` 1 in y and O(`n) in x. Kronecker substitution
x 7!y
`
reduces these products to O(`
2
n)-coecient products in F
q
m
[y], each of
which costs `
2
n(lg `
2
n)
1+o(1)
, for a total cost of `
3
n(lg `n)
1+o(1)
.
Step 3: lattice-basis reduction. The matrix of coecients of M
0
;:::;M
`1
has determinant
A
(kj)(k+j+1)=2+qj(j+1)=2
X
`(`1)=2
= A
k(k+1)=2+(q1)j(j+1)=2
X
`(`1)=2
of degree nk(k+ 1)=2 +n(q1)j(j + 1)=2 + (nt1)`(`1)=2. Inside the lattice
F
q
m
[x]M
0
+ + F
q
m
[x]M
`1
F
q
m
[x;y] nd a nonzero polynomial Q having
x-degree at most (nk(k + 1)=2 + n(q 1)j(j + 1)=2 + (nt 1)`(` 1)=2)=`,
and therefore x-degree below k(nw) + jw.
Step 4: factorization. Compute all f 2 F
q
m
[x] such that Q(x;f=X) = 0; i.e.,
compute all factors of Q having the form y f=X with f 2 F
q
m
[x]. For each
polynomial f 2 F
q
m
[x] such that Q(x;f=X) = 0 and deg f < nt: Compute
c = (
1
f(
1
);:::;
n
f(
n
)) 2 F
q
m
. Output c if c2 F
q
and jcvj w.
Why the algorithm works. Consider any c 2 C with jcvj w. There is a
polynomial f 2 F
q
m
[x] with deg f < nt such that c = (
1
f(
1
);:::;
n
f(
n
)).
The goal, as in the previous section, is to show that the algorithm finds f in
Step 4.
As before consider the map y 7! f=X from F
q
m
[x;Xy] to F
q
m
[x]. This map
takes A;F;E to A;f V; (f V )
q
(f V )B respectively.
There are exactly njcvj indices i for which c
i
= v
i
, i.e., for which f(αi)
i
) =
V (
i
). Each of these indices has x−αi
i
dividing fV , A, and (fV )
q
(fV )B,
so (x
i
)
k
divides the images of M
0
;M
1
;:::;M
`1
.
There are also exactly jc vj indices i for which c
i
6= v
i
, i.e., for which
i
f(
i
) 6=
i
V (
i
). Both
i
f(
i
) and
i
V (
i
) are in F
q
, so the difference
i
f(
i
)
i
V (
i
) is a nonzero element of F
q
; i.e.,
q
i
(f(αi)−
i
)V (
i
))
q1
= 1;
i.e., (f(αi)−
i
)V (
i
))
q1
= B(
i
). Each of these indices has x−αi
i
dividing both
(fV )
q
(fV )B and A, so (x
i
)
j
divides the images of M
0
;M
1
;:::;M
`1
.
The image of Q is thus divisible by
Q
i:ci
i
=v
i
(x
i
)
k
Q
i:ci
i
6=v
i
(x
i
)
j
, which
has degree k(njcvj) + jjcvj = kn (k j)jcvj kn (k j)w =
