Decoding One Out of Many - Post-Quantum Cryptography - page 51

Decoding One Out of Many

Nicolas Sendrier

INRIA Paris-Rocquencourt, Project-Team SECRET
[e-mail]

Abstract. Generic decoding of linear codes is the best known attack
against most code-based cryptosystems. Understanding and measuring
the complexity of the best decoding techniques is thus necessary to select
secure parameters. We consider here the possibility that an attacker has
access to many cryptograms and is satisfied by decrypting (i.e. decoding)
only one of them. We show that, for the parameter range corresponding
to the McEliece encryption scheme, a variant of Stern's collision decoding
can be adapted to gain a factor almost √ N when N instances are given.
If the attacker has access to an unlimited number of instances, we show
that the attack complexity is significantly lower, in fact the number of
security bits is divided by a number slightly smaller than 3 / 2 (but larger
than 1). Finally we give indications on how to counter those attacks.

1 Introduction

Code-based cryptography has attracted a lot of interest in the past few years,
accompanying the rise of post-quantum cryptography. It allows public-key en-
cryption scheme [21,22], zero-knowledge protocols [28,29,16], digital signature
[11], hash functions [1,7], stream ciphers [15,17] to mention only the most classi-
cal primitives. The common point of all code-based cryptographic primitives is
the fact that they rely on the hardness of decoding a linear code with no appar-
ent algebraic structure. This problem is NP-hard [4], and in fact, the parameter
selection for those systems is based on the best knows decoding techniques, usu-
ally the collision decoding [27] and its variants, and sometimes the generalized
birthday algorithm (GBA) [8,30].
In this work, we consider the case where the attacker is given many instances
of the decoding problem for the same linear code and wishes to solve only one
of them. Bleichenbacher's attack against [11] (unpublished but described for

instance in [23]) is a variant of GBA which offers a theoretical speedup of √ N
when the attacker tries to sign one out of N messages. The cost of the attack

will drop from T initially to max(T/ T/ √ N,N ) whose minimal value is T 2 / 3 (when
N = T 2 / 3 ). A variant of ISD for multiple instances has been proposed [18], but
its cost analysis does not allow an easy measure of the gain.
We consider in this paper a modification of ISD (similar to [18]) with a com-
plete cost analysis. We will show that, when the number of errors to decode is
smaller than the Gilbert-Varshamov distance 1 (corresponding to McEliece's or
1 The (binary) Gilbert-Varshamov distance is the largest integer d 0 such that d 0 ≤ 2 r .