Cryptography Reference
In-Depth Information
de
=
i
for which
σ
i
= 1. More precisely, if we let
J
σ
supp
(
σ
)=
{
i
:
σ
i
=1
}
,then
we choose
K
+
k
+
l
positions among [1
J
σ
to form
I
. The point of this
choice is that we have more chances to have a smaller size for
I
···
N
]
\
=
I
∩
J
.Let
de
=
n
I
|
|
,wehavenow:
n
−|
J
σ
|
n
|
E
{
J
σ
}
=
(
k
+
K
+
l
)
(8)
N
−|
J
σ
|
n/
2
I
|}
n
|
E
{|
=
E
{
E
{
J
σ
}} ≈
n/
2)
(
k
+
K
+
l
)
.
(9)
(
N
−
The last approximation follows from the fact that the weight
is quite con-
centrated around
n/
2. The same reasoning can be made as before, but the odds
that the algorithm finds other valid signatures are much higher. This comes from
the fact that the expectation
|
σ
|
I
|
is half the expected size of
I
in the previous
|
|
I
|
k
R
ρ
, whereas now
case as given in Equation (3). Previously we had
E
≈
we have:
|
I
|
k
R
2
ρ
.
In other words, in order to avoid the previous attack we had to take
ρ
significantly
smaller than
R
and now, we have to take
ρ
significantly smaller than
R/
2.
For all the parameters proposed in the past, it turns out that
d
GV
(
E
≈
I
|
,k
)is
almost always equal to 1, which makes the attack generally successful in just
one iteration by choosing
p
=1.
Moreover, if another valid signature
σ
is obtained and by taking the union
J
σ
∪
|
J
σ
of the supports, then about 3
/
4ofthepositionsof
J
will be revealed. We
can start again the process of finding other message/signature pairs by choosing
K
+
k
+
l
positions among
J
σ
)toformthesets
I
.This
approach can be iterated as explained in Algorithm 2. This process will quickly
reveal the whole set
J
and from this, the private key is easily extracted as detailed
in [COV07].
Finally, let us focus on the variant proposed in [BMJ11]. In this case, we have
slightly less information than in the original KKS scheme. This can be explained
by the following reasoning. In this case too, we choose
S
again as [1
{
1
,
2
,...,N
}\
(
J
σ
∪
···
N
]
\
J
σ
,
de
=
where as before
J
σ
is defined as
J
σ
{
i
:
σ
i
=1
}
. However this time, by
defining
n
again as
n
de
=
I
|
|
,wehave
J
σ
|
|
n
|
E
{
J
σ
}
(
k
+
K
+
l
)
=
N
−|
J
σ
|
where
J
σ
=
J
J
σ
.
However, this time due to the noise which is added,
\
|
J
σ
|
is expected to be larger
2
+
(
N−n
)
n
than before (namely of order
).
N
