Cryptography Reference
In-Depth Information
Step 3: lattice-basis reduction. The determinant of the aforementioned ``
matrix of coecients of M
0
;:::;M
`1
is the product of the diagonal entries
of the matrix (since the matrix is triangular), i.e., the product of the leading
coecients of M
0
;:::;M
`1
, namely
A
k
A
k1
X A
k2
X
2
X
k
X
k+1
X
`1
= A
k(k+1)=2
X
`(`1)=2
;
of degree nk(k + 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 + (nt1)`(`1)=2)=`, and therefore x-degree below k(nw).
This costs `
n`(lg `
2
n)
O(1)
= `
+1
n(lg `n)
O(1)
.
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 yf=X with f 2 F
q
m
[x]. Note that
there are at most ` 1 such factors, since Q has y-degree at most ` 1. This
costs `
2+o(1)
((lg q
m
)
1+o(1)
+ n`(lg `n)
2+o(1)
).
For each polynomial f 2 F
q
m
[x] such that Q(x;f=X) = 0 and deg f < nt:
Compute c = (
1
if
1
);:::;
n
if
n
)) 2 F
q
m
. Output c if c2 F
q
and jcvj w,
where jcvj means the Hamming weight of cv. This costs n(lg n)
2+o(1)
.
Why the algorithm works. Each output c from the algorithm is checked, in
Step 4, to be an element of C with jcvjw.
Conversely, consider any c 2 C with jc vj w. There is a polynomial
if 2 F
q
m
[x] with deg f < nt such that c = (
1
if
1
);:::;
n
if
n
)). The goal
is to show that the algorithm outputs c; equivalently, that f is found in Step 4
of the algorithm.
The hypothesis jcvj w means that there are at least nw indices i for
which ci
i
= v
i
; i.e., for which
i
if
i
) =
i
V (
i
); i.e., for which
i
is a root of
f V . In other words, gcdfA;f Vg has degree at least nw.
Consider the map y 7! f=X from F
q
m
[x;Xy] to F
q
m
[x]. The image of F =
XyV is fV , so the images of M
0
;M
1
;:::;M
`1
are A
k
;A
k1
(fV );:::; (f
V )
k
;:::; (fV )
`
. Each of these polynomials is divisible by gcdfA;f Vg
k
. The
image of Q, namely Q(x;f=X), is therefore also divisible by gcdfA;f Vg
k
.
Write Q as Q
0
+ Q
1
y ++ Q
`1
y
`1
. Then Q(x;f=X) = Q
0
+ Q
1
(f=X) +
+Q
`1
(f=X)
`1
. Each Q
i
has degree below k(nw), and f=X has degree at
most 0, so Q(x;f=X) has degree below k(nw); but Q(x;f=X) is divisible by
gcdfA;f Vg
k
, which has degree at least k(nw). Consequently Q(x;f=X) = 0
as claimed.
Notes on parameter selection. Suitable k;` exist with ` 2 O(nt) whenever
w is smaller than the big-field Johnson bound. For example, the integers k =
(n w)(t + 1) 0 and ` = n(t + 1) > k have (1 (t + 1)=n)(1 1=`) =
1(t + 1)=n1=` + 1=n
2
and (1w=nk=`)
2
+ k=`
2
= (1w=n)=` < 1=`; so
w;k;` are in the parameter space if (1 w=n)
2
1 (t + 1)=n + 1=n
2
, i.e., if
(nw)
2
n(nt1) + 1. Both (nw)
2
and n(nt1) are integers, so this
condition is equivalent to (nw)
2
> n(nt 1), i.e., w < n
p
n(nt 1).
This choice of ` is simpler and smaller than the choice made in [
36
, Lemma
7 and Proposition 9]. Here is an absurdly large numerical example to illustrate
