Cryptography Reference
In-Depth Information
Algorithm 2.
Recovering the private key from
t
1signatures.
PARAMETERS:
r
: number of iterations
l
: small integer (
l
40)
p
: very small integer (1
p
4).
INPUT:
ˆ
H
: public matrix as defined in Figure 3
{σ
1
,...,σ
t
}
: list of
t
1 valid signatures
OUTPUT:
···N
] of cardinality
n
1:
J ←∪
i
=1
supp
(
σ
i
)
2:
repeat
3:
S ←
[1
···N
]
\ J
4:
L←
KKSforge
(
r
,
l
,
p
,
S
,
H
)
5:
for all
σ ∈L
do
6:
J ← J ∪
supp
(
σ
)
7:
end for
8:
until
|J|
=
n
9:
return
J ⊂
[1
J
5
Analysis of the Attack
The purpose of this section is to provide a very crude upper-bound on the com-
plexity of the attack. We assume here that the code
C
rand
of length
n
which is
equal to the restriction on
J
of
C
sec
:
C
rand
de
=
(
x
j
)
j∈J
:
∈ C
sec
x
=(
x
1
,...,x
N
+
k
)
behaves like a random code. More precisely we assume that it has been chosen
by picking a random parity-check matrix
H
rand
of size (
n
−
k
)
×
n
(by choosing
its entries uniformly at random among
F
2
). This specifies a code
C
rand
of length
2
T
=0
n
as
. We first give in the following section
some quite helpful lemmas about codes of this kind.
C
rand
=
{
x
∈
F
:
H
rand
x
}
5.1 Preliminaries about Random Codes
We are interested in this section in obtaining a lower bound on the probability
that a certain subset
X
of
2
has a non empty intersection with
C
rand
.Forthis
purpose, we first calculate the two following probabilities. The probabilities are
taken here over the random choices of
F
H
rand
.
2
.Then
Lemma 1.
Let
x
and
y
be two different and nonzero elements of
F
x
∈ C
rand
)=2
k−n
prob
(
(10)
y
∈ C
rand
)=2
2(
k−n
)
prob
(
x
∈ C
rand
,
(11)
