McEliece type PKC based on algebraic geometry code over hyperelliptic curve

Abstract

McEliece introduced a public-key cryptosystem based on Algebraic codes, specially binary classical Goppa codes which have a good decoding algorithm and vast number of inequivalent codes with given parameters. In [19], they present new attack based on probalilistic algorithm to find minimum weight codeword, so for a sufficient security level(work factor roughly ＞ $2^{100}$), much larger parameter size [2048,1608,81] is required. Then the big size of public key make McEliece PKC more inefficient. So to think about alternative code is neccessary. Many authors have tried to improve parameters , as a result, five AG-code has been proposed from now on as a code instead of binary Goppa and other method to hide generating matrix. But it also has been shown that those PKC are not secure by another papers(In Main Section). We will propose New Type PKC using Hyperelliptic code [400, 312], t≤38 over $F_{491}$ which has not been concretly suggested yet, so that with smaller parameter(about 1/3) than [2048,1608,81] but still work factor as high as that (especially w.r.t decoding attack) can be maintained.