Cryptography Reference
In-Depth Information
and (1w=nk=`)
2
+ (w=n(q 1)j=`)
2
=(q1) + k=`
2
+ (q1)j=`
2
= 1=`;
so w;j;k;` are in the parameter space if 1 (t + 1)=n + 1=2(q 1)n
2
< (1
w=n)
2
+ (w=n)
2
=(q 1), i.e., (q 1)n(nt 1) + 1=2 < (q 1)(nw)
2
+ w
2
.
Both (q1)n(nt1) and (q1)(nw)
2
+ w
2
are integers, so this inequality
holds if and only if (q1)n(nt1) < (q1)
(nw)
2
+w
2
, which is equivalent
to (n
0
w)
2
> n
0
(n
0
t 1), i.e., w < n
0
p
n
0
(n
0
t 1).
These parameters have ` 2 O(n
2
) if q 2 O(1); and ` n
2
(lg n)
O(1)
if q 2
(lg n)
O(1)
; and ` 2 n
O(1)
if q 2 n
O(1)
. If q grows superpolynomially with n then
this algorithm obviously cannot run in polynomial time, except in the special
case j = 0 covered in the previous section. Such a large q would also force the
F
q
Johnson bound to be extremely close to the big-field Johnson bound; if there
is an integer w between the two bounds then correcting w errors in polynomial
time is, as far as I know, an open problem.
My main interest is in small q and, as in the previous section, small `. It seems
reasonable, although not always exactly optimal, to choose k as b(1 w=n)`c
and j as b(w=n)`=(q 1)c. Then 0 j k since (w=n)=(q1) 1w=n, and
` (q 1)j + k. These choices also guarantee that (1 w=nk=`)
2
< 1=`
2
,
that k=`
2
(1w=n)=`, that (w=n(q1)j=`)
2
=(q1) < (q1)=`
2
, and that
(q1)j=`
2
(w=n)=`, so w;j;k;` are in the parameter space if (1(t+1)=n)(1
1=`) (1w=n)
2
+ (w=n)
2
=(q1)1=`q=`
2
; i.e., 1(t+ 1)=n+ (t+ 1)=n`
(1 w=n)
2
+ (w=n)
2
=(q 1) q=`
2
; i.e., (1 J
0
=n)
2
+ (J
0
=n)
2
=(q 1) + (t +
1)=n` + q=`
2
(1 w=n)
2
+ (w=n)
2
=(q 1); i.e.,
J
0
w
(t + 1)=` + qn=`
2
2 (w + J
0
)=n
0
:
Assume from now on that q 2 (lg n)
O(1)
. Then t n=m (n lg q)= lg n 2
O((n lg lg n)= lg n), so w and J
0
are both bounded by O((n lg lg n)= lg n), so 2
(w + J
0
)=n
0
is bounded below by 1 for all suciently large n. If the gap J
0
w
is at least 1 then one can
pus
h (t + 1)=` + qn=`
2
below J
0
w by taking ` larger
than both 2(t + 1) and
p
2qn; this is achievable with ` 2 O(n). If the gap J
0
w
is at least n=(lg n)
O(1)
then one can take ` 2 (lg n)
O(1)
.
5
Correcting More Errors
One can trivially build a w-error-correcting algorithm from a (w 1)-error-
correcting algorithm as follows: guess an error position (probability w=n); guess
the error value (probability 1=(q1)); correct the error; apply the (w1)-error-
correcting algorithm. If the guess does not nd the desired c 2 C, try again.
This procedure takes (q 1)n=w repetitions on average. With more repeti-
tions one can condently listall c 2 C at distance w; but I will focus on the
eort required to nd aparticularc 2 C at distance w. Note that in the pre-
vious sections there was no reason to distinguish between these problems: the
algorithms in the previous sections find all answers at almost exactly the same
cost as finding the first answer.
