Cryptography Reference
In-Depth Information
We can observe that in Table 6, as for formula (10) and Table 5, the behavior
is close to what we expect when encryption is concerned (when w is significantly
smaller than the Gilbert-Varshamov distance). For parameters for code-based
signature schemes there is a gain but not as high as expected. For parameters for
code-based hashing, multiple instances does not seem to provide a big advantage.
The values of p and given in the fifth and sixth columns are real numbers
which minimize the formula for log 2 (WF ( )
ISD ). In an implementation they must
be integers and the real cost will be (marginally) different.
Tabl e 6. Workfactor with unlimited number of instances with the same code param-
eters as in Table 2
log 2 (WF ISD ) log 2 (WF ( )
ISD
) observed expected
( n, r, w )
p
p
=
β
β
(2048 , 352 , 32)
6 30 81 . 0 6 . 01
55 . 2
. 682
. 694
(2048 , 781 , 71)
6 29 100 . 7 8 . 20
69 . 2
. 688
. 696
(4096 , 252 , 21)
10 52 80 . 4 5 . 27
55 . 3
. 688
. 685
(4096 , 540 , 45)
12 60 128 . 4 9 . 00
88 . 0
. 685
. 689
(8192 , 416 , 32)
15 81 128 . 8 8 . 10
89 . 2
. 693
. 683
(2 16 , 144 , 11)
10 75 70 . 2 3 . 69
55 . 1
. 785
. 671
(2 16 , 160 , 12)
11 81 79 . 4 4 . 16
61 . 7
. 777
. 671
(2 18 , 162 , 11)
10 85 78 . 9 3 . 77
63 . 7
. 808
. 671
(2 20 , 180 , 11)
10 94 87 . 8 3 . 83
72 . 3
. 824
. 670
(5 · 2 18 , 640 , 160)
10 91 91 . 8 4 . 45
84 . 8
. 924
. 768
(7 · 2 18 , 896 , 224)
14 126 126 . 6 6 . 12 117 . 6
. 929
. 768
(2 21 , 1024 , 256)
16 144 144 . 0 6 . 96 134 . 0
. 930
. 768
(23 · 2 16 , 1472 , 368) 24 206 205 . 9 10 . 48 191 . 7
. 931
. 768
(31 · 2 16 , 1984 , 496) 32 275 275 . 4 14 . 01 257 . 2
. 934
. 767
6Con lu on
Decoding one out of many with collision decoding provides a significant advan-
tage to an attacker. For the digital signature scheme, the threat is real because
the attacker can create many syndromes by hashing many messages (favorable to
him), however what we gain with ISD is less than what Bleichenbacher obtained
with GBA. Anyway it is possible to completely avoid those attacks by signing
several syndromes (see [13]).
For very large values of w (used for instance in hashing) we have seen that the
attack is not so worrying, moreover the actual FSB [1] or RFSB [7] use regular
words and using ISD threatens an idealized version used for the security proofs.
Decoding regular words is harder, and the question of how to decode one out of
many and how to use it for an attack is still open.
Finally, when w is significantly smaller than the Gilbert-Varshamov distance
(for public-key encryption) there is a gain. If the attacker has access to many
cryptograms and is satisfied by decoding only one of them, the present work must
be taken into account. We consider two scenarios: (1) the encryption scheme is
Search WWH ::




Custom Search