Coding Theory and Cryptography

One of the few public-key cryptosystems which does not rely on number theory is the McEliece cryptosystem, whose security depends on coding theory. An attack on the McEliece cryptosystem must determine the coset leader (of known weight) from a user defined error coset. In general it is assumed that the code in question has no known structure, and is treated as a random code.

The best known attacks on the McEliece cryptosystem are a series of probabilistic enumeration-based algorithms.

Standard Attacks

McEliecesAttack(C, v, e): Code, ModTupFldElt, RngIntElt -> ModTupFldElt

MaxTime          : FldReElt                    Default: Infinity()
DirectEnumeration: BoolElt                     Default: true

Perform the original decoding attack described by McEliece when he defined his cryptosystem. Random information sets are tested for being disjoint for the support of the desired error vector. This intrinsic attempts to enumerate a vector of weight \(e\) from the error coset \(v + C\) for the given vector \(v\).

If set to a non-zero positive value, the variable argument MaxTime aborts the computation if it goes to long. The argument DirectEnumeration controls whether or not the coset is enumerated directly, or whether the larger code generated by \(\langle C, v \rangle\) is enumerated.

LeeBrickellsAttack(C, v, e, p): Code, ModTupFldElt, RngIntElt, RngIntElt -> ModTupFldElt

MaxTime          : FldReElt                    Default: Infinity()
DirectEnumeration: BoolElt                     Default: true

Perform the decoding attack described by Lee and Brickell. Random information sets are tested for having weight less than or equal to \(p\). For most sized codes, the optimal input parameter for this attack is \(p=2\). This intrinsic attempts to enumerate a vector of weight \(e\) from the error coset \(v + C\) for the given vector \(v\).

If set to a non-zero positive value, the variable argument MaxTime aborts the computation if it goes to long. The argument DirectEnumeration controls whether or not the coset is enumerated directly, or whether the larger code generated by \(\langle C, v \rangle\) is enumerated.

LeonsAttack(C, v, e, p, l): Code, ModTupFldElt, RngIntElt, RngIntElt, RngIntElt -> ModTupFldElt

MaxTime          : FldReElt                    Default: Infinity()
DirectEnumeration: BoolElt                     Default: true

Perform the decoding attack described by Leon. For random information sets of size \(k\), a punctured code of length \(k+l\) is investigated for codewords of weight less than or equal to \(p\). For small codes (up to length around \(200\)), the optimal input parameter for this attack is \(p=2\) with \(l\) somewhere in the range \(3-6\). For larger code \(p=3\) can sometimes be faster, with values of \(l\) in the range \(7-10\). This intrinsic attempts to enumerate a vector of weight \(e\) from the error coset \(v + C\) for the given vector \(v\).

If set to a non-zero positive value, the variable argument MaxTime aborts the computation if it goes to long. The argument DirectEnumeration controls whether or not the coset is enumerated directly, or whether the larger code generated by \(\langle C, v \rangle\) is enumerated.

SternsAttack(C, v, e, p, l): Code, ModTupFldElt, RngIntElt, RngIntElt, RngIntElt -> ModTupFldElt

MaxTime          : FldReElt                    Default: Infinity()
DirectEnumeration: BoolElt                     Default: true

Perform the decoding attack described by Stern. For random information sets of size \(k\), a punctured code of length \(k+l\) is split into two subspaces. Each subspace is enumerated up to information weight \(p\) and collisions found with zero non-information weight. For small to mid-range codes (up to length around \(500\)), the optimal input parameter for this attack is \(p=2\) with \(l\) somewhere in the range \(9-13\). For larger code \(p=3\) can sometimes be faster, with values of \(l\) from \(20\) to much higher. This intrinsic attempts to enumerate a vector of weight \(e\) from the error coset \(v + C\) for the given vector \(v\).

If set to a non-zero positive value, the variable argument MaxTime aborts the computation if it goes to long. The argument DirectEnumeration controls whether or not the coset is enumerated directly, or whether the larger code generated by \(\langle C, v \rangle\) is enumerated.

CanteautChabaudsAttack(C, v, e, p, l): Code, ModTupFldElt, RngIntElt, RngIntElt, RngIntElt -> ModTupFldElt

MaxTime          : FldReElt                    Default: Infinity()
DirectEnumeration: BoolElt                     Default: true

Perform the decoding attack described by Canteaut and Chabaud. For random information sets of size \(k\), a punctured code of length \(k+l\) is split into two subspaces. Using the enumeration technique identical to that of Stern’s attack, a different linear algebra process steps through information sets more quickly. The price for this is less independent information sets. This intrinsic attempts to enumerate a vector of weight \(e\) from the error coset \(v + C\) for the given vector \(v\).

For most codes (up to length around \(1000\)), the optimal input parameter for this attack is \(p=1\) with \(l\) somewhere in the range \(6-9\). For very large codes \(p=2\) can sometimes be faster, with values of \(l\) from \(20\) to much higher.

If set to a non-zero positive value, the variable argument MaxTime aborts the computation if it goes to long. The argument DirectEnumeration controls whether or not the coset is enumerated directly, or whether the larger code generated by \(\langle C, v \rangle\) is enumerated.

Generalized Attacks

All of the decoding attacks on the McEliece cryptosystem can be put into a uniform framework, consisting of repeated operation of a two stage procedure. Magma allows the user to choose any combination of the implemented methods, which include improvements on the standard attacks.

DecodingAttack(C, v, e): Code, ModTupFldElt, RngIntElt -> ModTupFldElt

Enumeration      : MonStgElt                    Default: "Standard"
MatrixSequence   : MonStgElt                    Default: "Random"
NumSteps         : RngIntElt                    Default: 1
p                : RngIntElt                    Default: 2
l                : RngIntElt                    Default: 
MaxTime          : FldReElt                     Default: Infinity()
DirectEnumeration: BoolElt                      Default: true

Perform a generalized decoding attack by specifying the enumeration and matrix sequence procedures to be used. This intrinsic attempts to enumerate a vector of weight \(e\) from the error coset \(v + C\) for the given vector \(v\).

The parameter Enumeration can take the values "Standard", "Leon" or "HashTable", and correspond to the methods used in Lee and Brickells, Leons and Sterns attacks respectively.

The parameter MatrixSequence can take on the values "Random" or "Stepped", corresponding to either a completely random sequence of information sets or a sequence of sets differing in one place.

The integer valued NumSteps offers a generalization of the stepped matrix process, taking a sequence of sets which differ at the specified number of places.

The parameter p and l describe the enumeration process, and their exact meaning depends on the enumeration process in question. See the earlier descriptions of the standard attacks for a full description of their meanings.

For codes of lengths anywhere between \(500-1000\), the best performance can be obtained using a multiply stepped matrix sequence, using around \(10\) steps at a time. This is in conjunction with the hashtable enumeration technique using \(p=2\) and \(l\) in the range \(15-20\).

If set to a non-zero positive value, the variable parameter MaxTime aborts the computation if it goes to long. The parameter DirectEnumeration controls whether or not the coset is enumerated directly, or whether the larger code generated by \(\langle C, v \rangle\) is enumerated.