Cryptography Reference
In-Depth Information
{Multiply the secret plaintext by the row-reduced H, obtaining a public
ciphertext inF
n
q
.
{As a verication step, use the secret key to legitimately decrypt the cipher-
text, and then check that the result matches the original plaintext.
{Throw away all the secret information, leaving only the ciphertext and the
public key.
We wrote a script in the Sage computer-algebra system [23] to do all this, relying
on Sage's random-number generator to produce all secrets; the Sage documen-
tation indicates that the random-number generator is cryptographic. This script
appears on our web page. The script was designed mainly as a reference imple-
mentation, easy to understand and easy to verify; it was not designed for speed.
However, we did incorporate a few standard speedups (such as a balanced prod-
uct tree inside interpolation in generalized Reed{Solomon decryption) to reduce
the time spent generating challenges.
We formatted each challenge as a text file containing cryptosystem parame-
ters, a ciphertext, and a public key. For example, here is our 20kB \wild McEliece
incognito" challenge for q = 13, except that in the actual le there are various
additional numbers in place of the dots:
kilobytes=19.9869819590563
q=13
m=3
n=472
s=7
t=3
u=43
k=343
w=23
ciphertext=[7,4,12,7,7,...,2,8,10,5,0]
recovered_plaintext_using_secret_key=True
pubkeycol129=[9,11,0,4,9,...,4,12,8,1,3]
pubkeycol130=[5,4,12,7,2,...,6,12,5,11,12]
...
pubkeycol471=[0,1,11,3,6,...,11,12,4,11,3]
In this example there are approximately 2
1644
possible sets fa
1
;:::;a
472
g, and
approximately 2
107
possible pairs (f;g). This challenge has wildness percentage
84% because deg(g
q1
) = 36 accounts for 84% of u = deg(fg
q1
) = 43. The
ciphertext is a column vector containing n k = 129 elements ofF
13
. This
column vector is a sum of nonzero coecients times w = 23 columns chosen
secretly from the 472 columns of the row-reduced H; these 472 columns consist
of k = 343 public-key columns shown in the challenge file, and 129 extra columns
containing an identity matrix.
The public key in this challenge has 343 129 log(13)= log 2 163733 bits
of information, slightly below the advertised \20kB" (163840 bits). A standard
radix-13 integer encoding of the matrix would fit into 163734 bits but would
