Title

McEliece public key cryptosystems (PKCs) have been receiving increasing attention recently as alternatives to the other PKCs because of several advantages. They are now seen to be quite practical because of exponential growth in the computing power. Furthermore, in a post-quantum computing world they are expected to remain secure, as opposed to the insecurity of RSA and other similar systems.

Using AG codes, we had proposed two public key cryptosystems (PKCs): Type I based on the subfield subcodes of AG codes, and Type II based on AG Goppa codes (MRI-Report-94, ISIT-95, DCC-97). Our Type I PKCs are still secure and our Type II PKCs have been recently shown to have some weak keys.

After massive worldwide collaborative computing efforts, the ensemble of original McEliece PKC based on binary irreducible classical Goppa codes with parameters [1024, 524,101] has been shown to be insecure recently. The original McEliece PKCs have key lengths that grow exponentially, and thus are not easily scalable. Alternatives, such as shortening or list-decoding of binary classical irreducible Goppa codes based PKCs are being proposed. However, we demonstrate how our Type I based PKCs provide better alternatives with superior parameters to those being proposed.

We will also present some results that will show why our PKCs have similar characteristics as those of McEliece PKCs (and hence should remain secure), but with superior parameters.

Our Type II class of PKCs have some weak keys (already we had excluded genus 0 case (i.e., those corresponding the generalized RS codes))– as they were known to be insecure by Sidelnikov-Shestakov type attack. A refinement of Sidelnikov-Shestakov type attacks have recently demonstrate that under some assumptions, our genus Type II PKCs based on genus 1 and 2 curves are also insecure. It might be possible to extend this attack to hyper elliptic curves of genus 3. For our Type II PKCs that are not based on hyper-elliptic curves, not much seem to be known. We will discuss why this attack might not be feasible for non-hyperelliptic curves based systems, or those based on hype-elliptic curves of genus larger than 2. We show why these are the weak keys and discuss how to avoid other potentially weak keys, and how to choose stronger ones.

We will also present a general framework of public/private key ensembles for Algebraic Geometric based PKCs, and discuss their practicality and cryptanalysis. Thus we propose a Type III PKCs based on AG codes. We present results on feasibility, practicality, and security of these systems.

We also outline several deep algebraic geometric problems that our three classes of PKCs based on AG codes lead to (for moduli space of curves, bounds on exponential sums over curves, existence of curves with many rational points, existence of certain divisors, etc.). We will give some partial results and suggest some open problems. These algebraic geometric problems have also applications to several other areas in mathematics, computer science, and communication sciences (for example in construction of Ramanujan graphs, expander graphs, ECC, random number generators, APN functions, hash functions, and sequence designs).