The algorithm is based on the hardness of decoding a general linear code (which is known to be NP-hard). For a description of the private key, an error-correcting code is selected for which an efficient decoding algorithm is known, and which is able to correct formula_1 errors. The original algorithm uses binary Goppa codes (subfield codes of geometric Goppa codes of a genus-0 curve over finite fields of characteristic 2); these codes can be efficiently decoded, thanks to an algorithm due to Patterson. The public key is derived from the private key by disguising the selected code as a general linear code. For this, the code's generator matrix formula_2 is perturbated by two randomly selected invertible matrices formula_3 and formula_4 (see below).