Cryptography Reference
In-Depth Information
such as the optimized Koetter{Vardy weights; but the user is required to
trace the desired weights (after scaling and rounding to integers) through a
thicket of degree computations.
It seems that every implementation of code-based cryptography avoids list de-
coding, even though [
11
, Section 7] pointed out years ago that list decoding im-
proves the tradeoff between key size and security level against all known attacks.
One can blame the non-use of list decoding on the lack of simple high-speed high-
distance decoding algorithms. Some list-decoding papers try to compensate by
adding generality, for example studying higher-genus algebraic-geometry codes,
but if list decoding is not usable even for the most basic constructions of alter-
nant codes then obviously it will also not be usable for higher-genus codes!
This paper presents a list-decoding algorithm that is simultaneously (1) fast,
(2) effective, and (3) simple. The algorithm continues to work for arbitrarily
large values of w, although its speed degrades as w approaches and passes the
F
q
Johnson bound. Specically, in the typical case that n=t, q, and lg q
m
are all
in (lg n)
O(1)
, the algorithm uses
n(lg n)
O(1)
bit operations for w n
0
p
n
0
(n
0
t
1) n=(lg n)
O(1)
;
O(n
4:5
) bit operations for w n
0
p
n
0
(n
0
t
1) + o((lg n)= lg lg n); and
n
O(1)
bit operations for w n
0
p
n
0
(n
0
t 1) + O((lg n)= lg lg n).
Note that the n(lg n)
O(1)
bound does not imply competitive speed with other
n(lg n)
O(1)
algorithms; it merely implies that the speed ratio is bounded by
(lg n)
O(1)
. However, the O(n
4:5
) bound allows easy comparison
s to, e.g., the
n
7+o(1)
achieved in [
4
, Corollary 5.8] for w slightly belo
w n
0
p
n
0
(n
0
t 1),
or the n
6+o(1)
achieved in [
6
] for w slightly below in
p
n(nt 1).
The word \simplied" in the title might suggest that I obtained this algo-
rithm by starting from an existing acceleration of the Koetter{Vardy algorithm
and simplifying it. I actually obtained the algorithm in a completely different
way. I started with a very simple algorithm by Howgrave-Graham that was pub-
lished in 1997 and that was subsequently understood to have the same decoding
capability as the Guruswami{Sudan algorithm. I then tweaked the Howgrave-
Graham algorithm to match the Koetter{Vardy results. The Howgrave-Graham
algorithm does not seem to be widely known among coding theorists, includ-
ing those working on code-based cryptography; see Section 3 and [
9
] for further
discussion of the history.
2
Review of Fast Arithmetic
This section reviews several standard subroutines for fast multiplication, fast
lattice-basis reduction, etc.
All of the algorithms here are F
q
m
-algebraic algorithms, i.e., sequences of
additions, subtractions, multiplications, divisions, and comparisons of elements
of F
q
m
. For a formal definition of this model of computation see, e.g., [
18
]. Cost
here refers to total algebraic complexity over F
q
m
, i.e., the number of arithmetic
operations performed in F
q
m
.
