Cryptography Reference
In-Depth Information
One can take ` in O(n
2
) for any w smaller than the big-field Johnson bound.
My main interest is in the case ` 2 (lg n)
O(1)
, achievable when there is a notice-
able gap between w and the big-field Johnson bound. Further notes on param-
eter selection appear below. The total cost of the algorithm will turn out to be
bounded by
n(lg n)
O(1)
if ` 2 (lg n)
O(1)
and lg q
m
2 (lg n)
O(1)
; and by
n
+2+o(1)
if ` 2 O(n) and lg q
m
2 O(n
); and by
n
2+3+o(1)
if ` 2 O(n
2
) and lg q
m
2 O(n
21
); and by
n
O(1)
if ` 2 O(n
2
) and lg q
m
2 n
O(1)
.
For example, Step 2 below costs `
3
n(lg `n)
1+o(1)
, which is visibly within each of
these bounds. I will state the cost of each step as a function of `, n, and (when
relevant) q
m
.
Input and output. The algorithm input is a vector v 2 F
q
. The algorithm
output is the set of c 2 C of Hamming distance at most w from v.
Step 1: initial interpolation. Compute the polynomial A = (x
1
)(x
2
)(x
n
) 2 F
q
m
[x]. Also compute 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
. This costs n(lg n)
2+o(1)
.
Step 2: lattice-basis construction. Define X = x
nt1
and F = XyV 2
F
q
m
[x;y]. Compute the ` polynomials
M
0
= A
k
;
M
1
= A
k1
F = A
k1
XyA
k1
V ;
M
2
= A
k2
F
2
= A
k2
X
2
y
2
2A
k2
XV y + A
k2
V
2
;
.
M
k1
= AF
k1
= AX
k1
y
k1
;
M
k
= F
k
= X
k
y
k
;
M
k+1
= F
k+1
= X
k+1
y
k+1
;
.
M
`1
= F
`1
= X
`1
y
`1
in F
q
m
[x;y]. If ` = k then M
`1
is defined as AF
k1
, not F
`1
. (One can save
time by replacing F
k
;F
k+1
;:::;F
`1
with F
k
;XyF
k
;:::; (Xy)
`1k
F
k
, but the
speedup is not visible at the level of detail of the analysis below.)
The coecients of powers of y here form an `` triangular matrix. There are
several straightforward ways to compute all of the matrix entries with a total
of O(`
2
) multiplications in F
q
m
[x], each multiplication involving polynomials of
degree O(`n). The total cost is just `
3
n(lg `n)
1+o(1)
.
