Cryptography Reference
In-Depth Information
Non-binary codes.
Obviously there is a non binary version of the KKS scheme
which would deal with codes defined over larger alphabets. The benefits of the
generalized scheme are questionable. The attack presented here generalizes easily
to higher order fields. What is more, moving to non-binary fields seems to be a
poor idea in terms of security. For instance, whereas a message/signature pair
reveals only half the positions of
J
in the binary case, in the
q
-ary case we expect
to obtain roughly a fraction
q−
1
q
of positions of
J
, which is significantly larger.
Decoding one out of many.
Another approach could have been used for
attacking the scheme. Let us denote by
s
1
,
···
,
s
k
the columns of
F
.These
vectors can be considered as
k
syndromes of codewords of
C
hidden
with respect
to the parity-check matrix
H
. If we want to obtain one message/pair we can
i
try to find an error
s
i
.
This suggests to use “the decoding one out of many” approach [Sen11], that is
we have
k
words to decode and we want to decode at least one of them. This
problem can be solved more eciently than just decoding one instance. We can
even refine this approach by considering all possible syndromes obtained by all
e
i
of weight in the range [
t
1
···
t
2
] such that
He
=
possible (non-zero) combinations
i
α
i
s
i
. In this case, we would have to solve
“a decoding one out of many” problem with 2
k
1 instances. However a naive
use of the results of [Sen11] would be far from indicating that all the parameters
of [KKS97, KKS05, BMJ11] are easily broken by this approach.
−
References
[BF02] Barg, A., Forney, G.D.: Random codes: Minimum distances and error expo-
nents. IEEE Transactions on Information Theory 48(9), 2568-2573 (2002)
[BLP11] Bernstein, D.J., Lange, T., Peters, C.: Smaller Decoding Exponents: Ball-
Collision Decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841,
pp. 743-760. Springer, Heidelberg (2011)
[BMJ11] Barreto, P.S.L.M., Misoczki, R., Simplicio Jr., M.A.: One-time signature
scheme from syndrome decoding over generic error-correcting codes. Journal
of Systems and Software 84(2), 198 (2011)
[CFS01] Courtois, N.T., Finiasz, M., Sendrier, N.: How to Achieve a McEliece-Based
Digital Signature Scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS,
vol. 2248, pp. 157-174. Springer, Heidelberg (2001)
[Com74] Comtet, L.: Advanced Combinatorics. Reidel, Dordrecht (1974)
[COV07] Cayrel, P.-L., Otmani, A., Vergnaud, D.: On Kabatianskii-Krouk-Smeets
Signatures. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547,
pp. 237-251. Springer, Heidelberg (2007)
[dC97] de Caen, D.: A lower bound on the probability of a union. Discrete Math-
ematics 169, 217-220 (1997)
[Dum91] Dumer, I.: On minimum distance decoding of linear codes. In: Proc. 5th
Joint Soviet-Swedish Int. Workshop Inform. Theory, Moscow, pp. 50-52
(1991)
[Dum96] Dumer, I.: Suboptimal decoding of linear codes: partition techniques. IEEE
Transactions on Information Theory 42(6), 1971-1986 (1996)
[FGO
+
10] Faugere, J.-C., Gauthier, V., Otmani, A., Perret, L., Tillich, J.-P.: A distin-
guisher for high rate McEliece cryptosystems. Cryptology ePrint Archive,
Report 2010/331 (2010),
http://eprint.iacr.org/
