Cryptography Reference
In-Depth Information
For those parameters typically used today in code-based cryptography, ISD is
much faster than statistical decoding. However, the complexity of ISD increases
significantly with the field size q . To estimate the value of q for which statistical
decoding becomes faster than ISD, we will compare our algorithm with the one
in [14].
In the case of statistical decoding, the largest part of the complexity is due to
the generation of the sample sets H w , so we will restrict our analysis to this. Our
algorithm is not fully optimized; for example, the sets H w are sampled essentially
randomly, instead of using a generalized version of ISD to sample the vectors.
We will therefore estimate the total work factor of statistical decoding by
2 n ( n k )
| H |
WF SD
,
F · P
where H =
B ,and P
is the success probability of decoding. The factor of 2 n ( n k ) reflects the fact
that our sampling algorithm requires n ( n k ) multiplications and additions.
Note that both algorithms estimate the number of q -ary operations (instead
of binary operations), so the results are comparable.
For the (64 , 40) code over
w H w , F is the fraction of codewords c with b
wt( c )
F 3 ,ISDrequires2 13 . 9 operations, compared with
2 20 . 2 for our algorithm. Increasing q , we find that ISD is slower than statistical
decoding for q
1201.
In the case of the (128 , 72) code and q = 3, the number of operations is 2 18 . 3
for ISD and 2 22 . 0 for statistical decoding. Here, q
233 is su cient to make our
algorithm the more ecient one.
5Con lu on
In this paper we have generalized Overbeck's (binary) statistical decoding algo-
rithm [13] to codes over non-binary fields
F q . Our algorithm was able to decode
a large part of the instances successfully. This probability can be increased by
using a larger number of sample vectors
or a larger weight spectrum B b ,
but this increases the overall complexity of the algorithm. The success probabil-
ity showed to be independent of the field size q , making it especially interesting
for short codes over large fields
| H |
F q .
In addition to that, we showed how knowledge about the structure of the
underlying code or about the solution can be used to increase the eciency of
the algorithm.
As further work, we propose to analyze if other types of structure can be
exploited as well. Expecially the code structure seems to be very promising, for
example if the underlying code is a Goppa code.
References
1. Augot, D., Finiasz, M., Sendrier, N.: A Family of Fast Syndrome Based Crypto-
graphic Hash Functions. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS,
vol. 3715, pp. 64-83. Springer, Heidelberg (2005);
Cited on page 223
 
Search WWH ::




Custom Search