Cryptography Reference
In-Depth Information
where
U
is a non-singular
r × r
matrix. We have
e ∈
CSD(
H,s,w
)ifandonly
if
eP
T
∈
CSD(
H
0
,s
0
,w
). Let (
P,e
) be the output of the algorithm and
e
=
s
+
e
H
T
the word
e
=(
e
,e
)isinCSD(
H,s,w
).
Definition 1.
For any fixed value of
n
,
r
and
w
,wedenote
WF
ISD
(
n,r,w
)
the minimal work factor (average cost in elementary operations) of Algorithm 1
to produce a solution to
CSD
(provided there is a solution), for any choices of
parameters
,
p
,
W
1
and
W
2
.
In the literature, elementary operations are often binary instructions. Our pur-
pose here is to obtain a quantity allowing us to compare algorithms and to mea-
sure the impact of decoding one out of many. Any reasonably fixed polynomial
time (in
n
) “elementary operation” will serve that purpose.
3.1 A Preview of the Analysis
When there is a single solution to CSD (“small”
w
, corresponding to encryption)
we can provide some intuition on the significance of the parameters.
Significance of
W
1
and
W
2
.
Given
p
and
, we would like
W
1
+
W
2
=
{e
1
+
e
2
|
S
k
+
(
0
,p
)as
possible, but no (or not too many) duplicate sums
3
. Typically the elements of
W
1
and those of
W
2
are chosen with distinct supports, for instance in [12]
W
1
=
(
e,
0)
(
e
1
,e
2
)
∈ W
1
× W
2
}
to contain as many distinct elements of
(
0
,
2
)
and
W
2
=
(0
,e
)
(
0
,
2
)
| e ∈S
k
+
2
| e ∈S
k
+
2
(assuming
p
and
k
+
are even). A proper choice of
W
1
and
W
2
will allow us to
find most solutions
e
∈
CSD(
H
,s
,p
) (see (1) for the notations) for a relatively
moderate cost (exploring
W
1
× W
2
uses the birthday paradox and essentially
consists in exploring
W
1
then
W
2
).
Significance of
p
and
.
The optimal size of
W
1
and
W
2
depends on
p
and
.
Given
p
,thebestvaluefor
keeps a balance between the costs of the various
steps of the algorithm and it is best to choose 2
≈|W
1
|
. There is no easy
interpretation of the optimal
p
, but an easy analysis shows that the extremal
cases
p
=0or
w
(either
H
or
H
vanishes in (1)) are not optimal. So there has
to be an optimal value for
p
between 0 and
w
.
=
|W
2
|
3.2 Links With the Other Variants of Collision Decoding
Information set decoding is an old decoding technique [25], the variants of in-
terest today for cryptanalysis derive from Stern's collision decoding [27]. The
algorithm we present here is closer to the “Punctured Split Syndrome Decod-
ing” of Dumer [12,3]. Depending on how the sets
W
1
and
W
2
are chosen, we
3
That is (
e
1
,e
2
)
=(
e
1
,e
2
)in
W
1
× W
2
such that
e
1
+
e
2
=
e
1
+
e
2
.
