On the near prime-order MNT curves

DOI10.1007/S00200-018-0363-1MaRDI QIDQ2631924zbMATH OpenOpenAlexFDO

Authors Duc-Phong Le, Safia Haloui, Chik How Tan, Nadia El Mrabet

Publication date 16 May 2019

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.02536

zbMATH Keywords

near prime-order MNT curvespairing friendly elliptic curvePell's equation

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) Applications to coding theory and cryptography of arithmetic geometry (14G50) Cryptography (94A60)

Abstract: In their seminar paper, Miyaji, Nakabayashi and Takano introduced the first method to construct families of prime-order elliptic curves with small embedding degrees, namely k = 3, 4, and 6. These curves, so-called MNT curves, were then extended by Scott and Barreto, and also Galbraith, McKee and Valenca to near prime-order curves with the same embedding degrees. In this paper, we extend the method of Scott and Barreto to introduce an explicit and simple algorithm that is able to generate all families of MNT curves with any given cofactor. Furthermore, we analyze the number of potential families of these curves that could be obtained for a given embedding degree $k$ and a cofactor h. We then discuss the generalized Pell equations that allow us to construct particular curves. Finally, we provide statistics of the near prime-order MNT curves.

Recommendations

• On near prime-order elliptic curves with small embedding degrees
• On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6
• Generating more MNT elliptic curves
• On the efficient generation of generalized MNT elliptic curves
• Elliptic curves with low embedding degree

Cites work

• A comparison of MNT curves and supersingular curves
• A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
• A taxonomy of pairing-friendly elliptic curves
• Abstract Algebra
• Faster Addition and Doubling on Elliptic Curves
• Faster computation of the Tate pairing
• Generating more MNT elliptic curves
• scientific article; zbMATH DE number 1643939 (Why is no real title available?)
• scientific article; zbMATH DE number 1689862 (Why is no real title available?)
• scientific article; zbMATH DE number 2081084 (Why is no real title available?)
• scientific article; zbMATH DE number 1842494 (Why is no real title available?)
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• scientific article; zbMATH DE number 3065066 (Why is no real title available?)
• Improved Miller’s Algorithm for Computing Pairings on Edwards Curves
• On near prime-order elliptic curves with small embedding degrees
• On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6
• On the efficient generation of generalized MNT elliptic curves
• On the number of isogeny classes of pairing-friendly elliptic curves and statistics of MNT curves
• Ordinary Abelian varieties having small embedding degree
• Reducing elliptic curve logarithms to logarithms in a finite field
• The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm
• Twisted Edwards Curves

Cited in

(7)

• Generating more MNT elliptic curves
• A prime curve is determined by its VF-matrix
• On the efficient generation of generalized MNT elliptic curves
• On near prime-order elliptic curves with small embedding degrees
• On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6
• On Cycles of Pairing-Friendly Elliptic Curves
• Elliptic curves with low embedding degree

This page was built for publication: On the near prime-order MNT curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631924)