Generating pairing-friendly elliptic curve parameters using sparse families
type: Item
instance of: scholarly article
title: Generating pairing-friendly elliptic curve parameters using sparse families
zbMATH Open document ID: 1496.94043
author: Georgios Fotiadis
author: Elisavet Konstantinou
published in: Journal of Mathematical Cryptology
publication date: 2018-06-14T00:00:00Z
full work available at URL: http://orbilu.uni.lu/handle/10993/39267
review text: Let \(E/\mathbb{F}_q\) be an ordinary elliptic curve with Frobenius trace \(t = q+1 - \# E(\mathbb{F}_q)\) such that \(\# E(\mathbb{F}_q) = hr\) for some large prime \(r\). \(E\) is said to be pairing friendly if \(\log q \approx \log r\) (measured by the \(\rho\) value \(\rho = \log q / \log r\)) and there exists a bilinear pairing \(\hat{e}: G_1 \times G_2 \mapsto G_T\) where \(G_1, G_2 \leq E(\mathbb{F}_q)\), \(G_T \leq \mathbb{F}^\ast_{q^k}\) and \(\# G_1 = \# G_2 = \# G_T = r\) such that the discrete logarithm problem in all three groups is believed to be hard. The integer \(k\), called the embedding degree, should also be sufficiently small that arithmetic in \(G_T\) is efficient. One method to construct pairing-friendly curves involves parameterizing the values of \(q\), \(t\), \(r\) via polynomial families, triples of polynomials \((q(x),t(x),r(x))\) in \(\mathbb{Q}[x].\) Sparse polynomial families are those satisfying \(4 q(x) - t(x)^2 = g(x) y(x)^2\) with \(g(x)\) quadratic with positive leading coefficient; these are attractive because the resulting curves have large CM discriminants, providing some resistance against certain attacks on the discrete logarithm problem. In this paper, the authors propose a novel method for constructing sparse polynomial families that combines methods of \textit{H.-S. Lee} and \textit{C.-M. Park} [Lect. Notes Comput. Sci. 5671, 66--77 (2009; Zbl 1250.14017)] and \textit{R. Dryło} [ibid. 7107, 310--319 (2011; Zbl 1291.94075)]. The construction is used to produce new sparse families with \(\rho \leq 2\) and the same embedding degrees as those appearing in the literature, as well as first examples for several other embedding degrees. These families were used to produce numerical examples of pairing-friendly curves with parameters of cryptographically-relevant size, considering recent progress on the tower number field sieve algorithm for solving the discrete logarithm problem in \(G_T\).
reviewed by: Michael J. Jacobson jun.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 6889364
zbMATH Keywords: pairing-based cryptography
zbMATH Keywords: pairing-friendly elliptic curves
zbMATH Keywords: sparse families
zbMATH Keywords: Pell equation
MaRDI profile type: Publication
OpenAlex ID: W2789331349
cites work: Pairing-Friendly Elliptic Curves of Prime Order
cites work: Elliptic curves suitable for pairing based cryptography
cites work: On Constructing Families of Pairing-Friendly Elliptic Curves with Variable Discriminant
cites work: Building curves with arbitrary small MOV degree over finite prime fields
cites work: Guide to pairing-based cryptography
cites work: On the Efficient Generation of Generalized MNT Elliptic Curves
cites work: Algorithmic Number Theory
cites work: A taxonomy of pairing-friendly elliptic curves
cites work: Ordinary Abelian varieties having small embedding degree
cites work: Constructing Brezing-Weng Pairing-Friendly Elliptic Curves Using Elements in the Cyclotomic Field
cites work: Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case
cites work: Generating Pairing-Friendly Curves with the CM Equation of Degree 1
cites work: CONSTRUCTING PAIRING-FRIENDLY CURVES WITH VARIABLE CM DISCRIMINANT
cites work: Simple continued fraction solutions for Diophantine equations
cites work: Generating more MNT elliptic curves
cites work: Computing Hilbert class polynomials with the Chinese remainder theorem
cites work: Constructing Pairing-Friendly Elliptic Curves Using Factorization of Cyclotomic Polynomials
cites work: A new method of choosing primitive elements for Brezing-Weng families of pairing-friendly elliptic curves
DOI: 10.1515/JMC-2017-0024
description: scientific article; zbMATH DE number 6889364