A cryptosystem "à la" ElGamal on an elliptic curve over Fp[ϵ]

Abstract

This paper introduces a new public key cryptosystem which is a variant of the ElGamal cryptosystem on an elliptic curve. To this end, we study the equations of type y2 = x3 + ax + b with a and b in Fq[ϵ] where ϵ2 = 0. When 4a3 + 27b2 is invertible in Fq[ϵ], they allow us to define new groups which seem to be good candidates for the ElGamal public key cryptosystem. The variant we introduce has the advantage to present no plaintext encoding problem. Moreover, it reaches security levels which are similar to the ElGamal cryptosystem on an elliptic curve.