Cryptography Reference
In-Depth Information
where
h
−
1
(
x
) is the inverse function defined over [0
,
2
] of the binary entropy
function
h
(
x
)
de
=
−
x
log
2
x
−
(1
−
x
)log
2
(1
−
x
). Recall that we expect to have:
I
|≈
|
(
R
+
αρ
+
λ
)
n,
which implies
ρ
R
when
α
and
λ
are small. Roughly speaking, to avoid such an attack, several
conditions have to be met:
k
ρ
R
+
αρ
+
λ
≈
I
|
≈
|
1.
ρ
has to be significantly smaller than
R
,
2.
n
has to be large enough.
This phenomenon was clearly not taken into account in the parameters suggested
in [KKS97, KKS05, BMJ11] as shown in Table 1. The values of
d
GV
(
I
|
|
,k
)are
extremely low (in the range 1
6). In other words, taking
p
= 1 is already
quite threatening for all these schemes. For the first parameter set, namely
(
k, n, K, N
)=(60
,
1023
,
192
,
3000), this suggests to take
p
= 3. Actually taking
p
= 1 is already enough to break the scheme. The problem with these low val-
ues of
p
comes from the dependency of the complexity in
p
asdetailedinthe
following section. For instance as long as
p
is smaller than 3 the complexity of
one iteration is dominated by the Gaussian elimination Step 2.
Finally, let us observe that when this attack gives a message/signature pair,
it can be used as a bootstrap for an attack that recovers the whole private key
as will be explained in the following subsection.
−
Table 1.
KKS Parameters with the corresponding value of
d
GV
(
n
,k
)
l n
de
=
E
{|I
|}
N d
GV
(
n
,k
)
Article
ρ
n
R
60
1023
≈
0
.
059 1,023
192
3000
≈
0
.
064
[KKS97]
8
89
3,000
6
48
255
≈
0
.
188
273
1200
≈
0
.
228
[KKS05]
255
8
65
1,200
5
48
180
≈
0
.
267
335
1100
≈
0
.
305
[KKS97]
180
8
64
1,100
4
[BMJ11]
1
/
2
320 12
165
1
/
2
11,626
1
[BMJ11]
1
/
2
448 13
230
1
/
2
16,294
1
1
/
2
1
/
2
[BMJ11]
512 13
264
18,586
1
[BMJ11]
1
/
2
768 13
395
1
/
2
27,994
2
[BMJ11]
1
/
2
1,024 14
527
1
/
2
37,274
2
4.4 Exploiting a Signature for Extracting the Private Key
de
=(
σ,
If a signature
σ
of a message
C
sec
which has weight about
n/
2 when restricted to its
N
first positions. This yields
almost half of the positions of
J
. This can be exploited as follows. We perform
the same attack as in the previous subsection, but we avoid choosing positions
x
is known, then
y
x
)isacodewordof
