High-degree compression functions on alternative models of elliptic curves and their applications
share
This paper presents method for obtaining high-degree compression functions using natural symmetries in a given model of an elliptic curve. Such symmetries may be found using symmetry of involution [-1] and symmetry of translation morphism τ_T=P+T, where T is the n-torsion point which naturally belongs to the E(𝕂) for a given elliptic curve model. We will study alternative models of elliptic curves with points of order 2 and 4, and specifically Huff's curves and the Hessian family of elliptic curves (like Hessian, twisted Hessian and generalized Hessian curves) with a point of order 3. We bring up some known compression functions on those models and present new ones as well. For (almost) every presented compression function, differential addition and point doubling formulas are shown. As in the case of high-degree compression functions manual investigation of differential addition and doubling formulas is very difficult, we came up with a Magma program which relies on the Gröbner basis. We prove that if for a model E of an elliptic curve exists an isomorphism ϕ:E → E_M, where E_M is the Montgomery curve and for any P ∈ E(𝕂) holds that ϕ(P)=(ϕ_x(P), ϕ_y(P)), then for a model E one may find compression function of degree 2. Moreover, one may find, defined for this compression function, differential addition and doubling formulas of the same efficiency as Montgomery's. However, it seems that for the family of elliptic curves having a natural point of order 3, compression functions of the same efficiency do not exist.
READ FULL TEXT