WCSE

Constructing Weak Curves ECDLP-Equivalent to Ordinary Curves via Elliptic Surfaces

Abstract— The elliptic curve discrete logarithm problem(ECDLP) is the basis for the security of elliptic curve cryptography. Up to now, there is no subexponential algorithm for ECDLP. Only certain classes of weak curves exist whose standard ECDLP can be reduced to sample problems, like supersingular curves, anomalous curves etc. Elliptic surfaces are algebraic surfaces containing a pencil of elliptic curves (also means fibers). In order to reduce ordinary curves to weak curves using connections among these fibers, we define the ECDLP-equivalence of specialized-reduced points in the sense of the same section to elliptic surfaces (hereafter shortened as ECDLP-equivalence). We make a discovery that the ECDLP-equivalence is only related to the order of specialized-reduced points, and present an algorithm for constructing supersingular curves ECDLP-equivalent to ordinary curves via elliptic surfaces. In the end, we illustrate a 256-bit example.

Index Terms— elliptic surfaces, ECDLP-Equivalence, supersingular curves, rank one lifting problem.

Yuhong Zhang, Bo Peng, Maozhi Xu
LMAM, School of Mathematical Sciences, Peking University, No.5 Yiheyuan Rd., Haidian District, CHINA

[Download]

Cite: Yuhong Zhang, Bo Peng, Maozhi Xu, "Constructing Weak Curves ECDLP-Equivalent to Ordinary Curves via Elliptic Surfaces," Proceedings of 2017 the 7th International Workshop on Computer Science and Engineering, pp. 940-944, Beijing, 25-27 June, 2017.