McEliece public key cryptosystems using algebraic-geometric codes (Q1923811)

In the McEliece public key cryptosystem, a user \(A\) chooses a \(k\times n\) binary generator matrix \(G_A\) of a \(t\)-error correcting binary linear code and publishes the matrix \(G'_A= SG_AP\), where \(P\) is a randomly generated \(k\times k\) non-singular binary matrix and \(P\) is an \(n\times n\) permutation matrix. For a user to send message \(M\), represented as a binary vector of length \(k\), to user \(A\), it is encrypted as \(M'=MG'_A+Z\) where \(Z\) is a random error vector of length \(n\) and weight \(t\), representing \(t\) errors. McEliece suggested using \(G_A\) to be that of a \((1024,524,101)\) Goppa code. The security of such a system has been considered and the conclusion drawn that the work factor/size trade-off is not suitable for practical implementations. This note generalizes the scheme in three ways: by using nonbinary algebraic-geometric codes, using subfield subcodes of these and by using concatenated \(q^m\)-ary AG codes with good \(q\)-ary codes. It is shown that such schemes are capable of achieving a more desirable work factor/size trade-off.