Cryptography Reference
In-Depth Information
may obtain any known variant, including the recent ball-collision decoding [6].
Of course the Algorithm 1 is an abstraction. An effective algorithm, not to speak
of its implementation must include a description of how the parameters
p
and
are chosen (something we will do) and how the sets
W
1
and
W
2
are selected
(something we will not do completely). Our main purpose in this work is to es-
timate the impact of having multiple instances. This requires some flexibility in
thechoiceofthesizesof
W
1
and
W
2
which is relatively natural in our abstract
model, but not straightforward, though probably possible, in the above men-
tioned variants. We believe that the evolution of the complexity given in (10)
and (11) between the single and multiple instances scenarios can be obtained for
most variants of collision decoding after proper adjustments.
4 Cost Estimation
We will neglect all control instructions and assume that counting only the in-
structions in blocks (isd
i
) will give an accurate estimation of the algorithm
cost. For
i
=0
,
1
,
2
,
3 we will denote
K
i
the average cost in elementary opera-
tions (whatever that means) for executing the block of instructions (isd
i
).
We are given all the algorithm parameters
n
,
r
,
w
,
p
,
,
W
1
,and
W
2
.For
computing probabilities (and thus cost estimates) we will make the usual ran-
dom coding assumption (pseudo-randomness of syndromes) and also assume
that Algorithm 1 runs on instances which have a solution (this makes sense for
a cryptanalysis). We also admit the following.
Assumptions and approximations:
1.
K
0
,
K
1
,
K
2
,and
K
3
are independent of
p
,
,
W
1
and
W
2
.
2. All sums
e
1
+
e
2
for (
e
1
,e
2
)
|W
1
||W
2
|≤
k
+
p
.
∈ W
1
× W
2
are distinct and
3. Up to a (small) constant factor we have for any
x
1 and any integer
N
− x
)
N
≈
−
min(1
,xN
)
1
(1
Those assumptions and approximations will not cost more than a small constant
factor on the cost estimations we will compute later in this paper.
All the formulas we will give in the rest of the paper will depend of one
fundamental quantity denoted
ε
(
p,
). It is equal to the probability for some
e
∈S
k
+
(
0
,p
) to be a valid output of a particular execution of isd loop. The
following estimates helps to understand how it varies with
p
and
min
2
r
,
w
.
r−
w−p
ε
(
p,
)
≈
(2)
Proof.
(of equation (2), sketch) We consider one particular execution of isd loop
and use all the notations of the algorithm. Given
H
and
H
, for any
e
∈
S
k
+
(
0
,p
) we count how many
s
=(
s
,s
)aresuchthat
e
is a valid output
of isd loop(
H
,H
,s
). We must have
s
=
e
H
T
and
s
∈S
r−
(
e
H
T
,w− p
),
