Cryptography Reference
In-Depth Information
Niederreiter's encryption schemes), collision decoding can be adapted to save a
factor
N
0
.
5
−c
(for some small positive
c
) when decoding one out of
N
instances.
Also, if the number of instances is unlimited, we show that the cost of the decod-
ing is raised to the power 2
/
3+
c
(for some small positive
c
). In other words,
the number of security bits (i.e. the log in base 2 of the cost of the best attack)
is divided by some number close (but smaller to) 1
.
5.
We will first analyze an abstract variant of ISD, similar to the one of [14]. We
will then show how this algorithm and its analysis can be extended to the case
of many instances and provide some estimates of what this modified algorithm
can gain. This new attack constitutes a threat which must be considered. We
briefly explain in the conclusion how to completely avoid it. The countermeasures
are simple but it is a new feature to consider when implementing code-based
cryptography.
Notation:
-
S
n
(
0
,w
) denotes the sphere of radius
w
centered in
0
in the Hamming space
{
}
n
, more generally
0
,
1
S
n
(
x, w
) denotes the same sphere centered in
x
.
-
|X|
denotes the cardinality of the set
X
.
2 The Decoding Problem in Cryptology
The security of code-based cryptography heavily relies on the hardness of de-
coding in a random linear code. The computational syndrome decoding problem
is NP-hard and is conjectured dicult in the average case.
Problem 1 (Computational Syndrome Decoding -
CSD
).
Given a matrix
H ∈{
}
r×n
,aword
s ∈{
}
r
, and an integer
w>
0
, find
e ∈{
}
n
of
0
,
1
0
,
1
0
,
1
≤ w
such that
eH
T
=
s
.
Hamming weight
We will denote CSD(
H,s,w
) the above problem and the set of its solutions.
Decoding is one of the prominent algorithmic problems in coding theory for more
than fifty years. So far, no subexponential algorithm is known which correct a
constant proportion of errors in a linear code. Code-based cryptography has been
developed on that ground and for many code-based cryptosystems, public-key
encryption [21,22] and digital signature [11], zero-knowledge protocols based on
codes [28,29,16], hash-function [1], PRNG and stream ciphers [15,17] and many
others, decoding is the most threatening attack and therefore is a key point in
the parameter selection.
2.1 Generic Decoding Algorithms
The most ancient technique for addressing CSD in cryptology is Information
Set Decoding (ISD). It can be traced back to Prange [25]. The variants useful
today in cryptology all derive more or less from Stern's algorithm [27], which we
