Cryptography Reference
In-Depth Information
will call collision decoding, following [6,24]. It was implemented (with various
improvements) in [9] then in [5] which reports the first successful attack on
the original parameter set. General lower bounds were proposed [14]. The last
published variant is ball-collision decoding [6] which features a better decoding
exponent than collision decoding.
The other main technique is the Generalized Birthday Algorithm (GBA) [30]
(order 2 GBA was previously published in [8]). The first use of GBA for decoding
was proposed in [10] for attacking an early version of FSB [2]. It is sometimes
faster than ISD.
The security of the various code-based cryptographic primitives corresponds
to a wide range of parameters for the CSD problem. To determine which attack
is the most ecient, one should compare the error weight
w
with the Gilbert-
Varshamov distance
d
0
(which is a function of the code length and size).
For a
single instance
, the situation is the following: (1) when
w<d
0
(for encryption
schemes) ISD is always better, (2) when
w ≈ d
0
(for ZK-protocols, digital sig-
nature, stream cipher), the best attack is also ISD, and (3) when
w>d
0
(for
hashing) the best attack is either ISD or GBA (with no easy rule to predict which
is the best). Let us also mention that
w>r/
4 is insecure because Saarinen's
attack [26].
For multiple instances
the situation is not known precisely, but in one case at
least (namely Bleichenbacher's attack against CFS signature scheme) GBA with
multiple instances has become the most ecient attack. This was a motivation
to consider whether a similar improvement was possible with ISD.
2.2 Decoding One Out of Many Instances
In this work we will consider the scenario where the attacker has many instances
(
H,s,w
) at disposal where the parity check matrix
H
and the error weight
w
are identical, but the syndrome
s
runs over some large set.
Problem 2 (Computational Syndrome Decoding - Multi).
Given a ma-
trix
H
}
r×n
,aset
}
r
, and an integer
w>
0
,findaword
∈{
0
,
1
S⊂{
0
,
1
}
n
of Hamming weight
≤ w
such that
eH
T
∈S
e ∈{
0
,
1
.
For convenience, we will also denote CSD(
H,S,w
) this problem and the set of
its solutions. It has been addressed already using GBA by Bleichenbacher (un-
published, reported in [23]) for attacking the digital signature CFS. In practice,
the attacker builds a large number
N
of instances of a decoding problem (cor-
responding to
N
favorable messages) solves one of them with an order 2 GBA
with a speedup of
√
N
compared with the decoding of a single instance with a
birthday attack. This reduces the order of magnitude of the cost for forging a
signature from
O
(2
r/
2
)to
O
(2
r/
3
). A variant of CFS resistant to this attack was
recently published [13].
An attempt at using ISD with multiple instances was already made in [18].
We revisit here that work in a more general setting and with a more thorough
complexity analysis.
