Cryptography Reference
In-Depth Information
Table 3.
Average number of iterations of Algorithm 1
Article
ρ
n
l p
R
N
UpperBound
t
1
t
2
Iterations Average time of
an attack (in s)
60
1023
≈
8 1
192
[KKS97]
0
.
059 1,023
3000
≈
0
.
064 3,000
111
.
26
352 672
102.34
19.50
60
1023
≈
0
.
059 1,023 14 2
192
3000
≈
0
.
064 3,000
14
.
17
352 672
9.22
1.754
48
255
≈
8 1
273
[KKS05]
0
.
188
255
1200
≈
0
.
228 1,200
26
.
41
48 208
24.32
0.384
48
255
≈
255 14 2
273
0
.
188
1200
≈
0
.
228 1,200
4
.
37
48 208
3.13
0.051
48
180
≈
0
.
267
8 1
335
1100
≈
0
.
305 1,100
6
.
07
[KKS97]
180
96
96
5.58
0.061
48
180
≈
180 15 2
335
0
.
267
1100
≈
0
.
305 1,100
1
.
82
96
96
1.23
0.017
[BMJ11]
1
/
2
320 12 1
1
/
2
11,626
1
.
24
133 187
1.13
6.425
[BMJ11]
1
/
2
448 13 1
1
/
2
16,294
1
.
34
192 256
1.18
18.90
[BMJ11]
1
/
2
512 13 1
1
/
2
18,586
1
.
39
222 290
1.26
32.23
[BMJ11]
1
/
2
768 13 1
1
/
2
27,994
1
.
61
342 426
1.51
119.5
[BMJ11]
1
/
2
1,024 14 1
1
/
2
37,274
1
.
85
464 560
1.73
350.8
7
Concluding Remarks
Design principles.
As explained in Section 3, the parameters of the KKS
scheme were chosen in order to make decoding of
C
known
intractable when the
weight of errors is in the range [
t
1
···
t
2
], where
C
known
denotes the code defined
by the parity-check matrix
C
known
is
of minimum distance greater than 4
n
. Both requirements are clearly insucient
to ensure that the scheme is secure as demonstrated by this paper. We suggest
here to replace all these requirements by choosing the parameters such as to
make our attack impracticable. This algorithm is exponential in nature when
the parameters are well chosen. If we want to avoid that the knowledge of a
message-signature pair allows to recover the secret key, this implies for instance
that the rate
R
of
H
.In[BMJ11],itisfurtherrequiredthat
C
known
should be significantly larger than 2
ρ
,thatistwice
the rate of the secret code
C
hidden
. This would change the parameters of the
scheme significantly and give much larger key sizes than has been proposed
in [KKS97, KKS05, BMJ11]. Choosing these parameters requires however to
analyze properly the complexity of the attack when one message-signature is
known (here we just analyzed the complexity of the attack which does not make
use of any message-signature pair). The analysis we performed in our case can
be carried over to the case when a message-signature pair is known but this is
beyond the scope of this paper and will appear in a full version of this paper.
Relating the security to the problem of decoding a linear code.
The
attack which has been suggested here is nothing but a well known algorithm
for finding low weight codewords or for decoding a generic linear code. It just
happens that this algorithm is much more powerful here than for a random
linear code due to the peculiar nature of the code it is applied to. However as
mentioned above, this attack is exponential in nature and can easily be defeated
by choosing the parameters appropriately. It would be interesting to analyze the
relationship of the problem of breaking the KKS scheme with decoding problems
in more depth, or to prove that the problem which has to be solved is indeed
NP hard.
