Cryptography Reference
In-Depth Information
4Challenges
We have created a spectrum of cryptanalytic challenges as a way to measure and
focus progress in attacking our proposals. Each challenge consists of a public key
and a ciphertext; we challenge the readers to find a matching plaintext or even
to find the secret keys. Our challenges are online at
http://pqcrypto.org/
wild-challenges.html
. We intend to keep this web page up to date to show
{any solutions (plaintexts) sent to us | with credit to the rst solver of each
challenge, and with as much detail as the solver is willing to provide regarding
how the challenge was cryptanalyzed;
{any secret keys sent to us | again with credit to the rst solver of each
challenge;
{cryptanalytic benchmarks | measurements of the speed of publicly available
cryptanalytic software for the smaller challenges, as a way for the community
to verify and demonstrate improvements in attack algorithms;
{predictions | estimates of how dicult the larger challenges will be to break.
Our challenges, like the RSA Factoring Challenge (see [19] and [26]) and the
Certicom ECC Challenges (see [8]), cover a wide range of levels of diculty. The
smallest challenges require only a small amount of computer time; the larger
challenges increase rapidly in diculty. However, we did not imitate (e.g.) the
1000 increase in diculty between the ECC2K-108 and ECC2K-130 challenges
in [8]. That increase has kept the list of solved ECC2K challenges static since
2000, not reflecting the impact of more than a decade of advances in computer
technology; we prefer smaller gaps between challenges.
Each of our challenges is labelled by (1) \wild McEliece" for [6], or \wild
Mceliece incognito" for this paper; (2) a eld size q; (3) a key size expressed in
kilobytes. Each challenge also has public parameters m;n;s;t chosen as discussed
below. After choosing these parameters we built the challenge as follows:
{Choose a secret sequence of n distinct elements a
1
;:::;a
n
ofF
q
m
.
{Choose a secret irreducible polynomial g of degree t inF
q
m
[x]. If g has any
of a
1
;:::;a
n
as roots, repeat this step. (This can occur only for t = 1.)
{Choose a secret irreducible polynomial f of degree s inF
q
m
[x]. If f has any
of the a
1
;:::;a
n
as roots, repeat this step. (In principle we should, but we
did not, also check for the rare possibility that s = t and f = g.)
{Write down an (n k) n parity-check matrix H for the Goppa code
q
(a
1
; ;a
n
;fg
q1
), where k = nm(s + (q 1)t).
{Row-reduce H so that it begins with an (nk) (nk) identity matrix
and continues with an (nk)k public key. If this fails (i.e., the rst nk
columns of H are not invertible), go back to the first step.
{Choose a secret plaintext. Here we use the Niederreiter variant [16]: a plain-
text is a random element ofF
n
q
of Hamming weight w, where w =
b(s + (q 1)t)=2c. (This can be made CCA2-secure with negligible loss of
eciency, by techniques analogous to the techniques of [14].) For simplicity
we do not use list decoding here. We also do not use the Berger{Loidreau
defense.
