Revisiting Cycles of Pairing-Friendly Elliptic Curves

A recent area of interest in cryptography is recursive composition of proof systems. One of the approaches to make recursive composition efficient involves cycles of pairing-friendly elliptic curves of prime order. However, known constructions have very low embedding degrees. This entails large parameter sizes, which makes the overall system inefficient. In this paper, we explore 2-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds. As a consequence, we prove that no 2-cycles can arise from the known families, except for those cycles already known. Additionally, we show some general properties about cycles, and provide a detailed computation on the density of pairing-friendly cycles among all cycles.

1. 1.

   Other works take \(|d |\) as the discriminant.

2. 2.

   Furthermore, numerical experiments easily find many tuples (t, p, q) with low degree and small coefficients satisfying conditions 1–4, but unfortunately not condition 5.

3. 3.

   In [3], the authors define pairing friendliness as having an embedding degree \(k \le (\log q)^2\). We will keep the bound as an unspecified parameter K.

The second author is partially supported by Dusk Network and the Spanish grant PID2019-110224RB-I00.

Authors and Affiliations

1. Dusk Network, Amsterdam, The Netherlands

   Marta Bellés-Muñoz & Javier Silva

2. Pompeu Fabra University, Barcelona, Spain

   Marta Bellés-Muñoz

3. Polytechnic University of Catalonia, Barcelona, Spain

   Jorge Jiménez Urroz

4. Technical University of Madrid, Madrid, Spain

   Jorge Jiménez Urroz

Corresponding author

Correspondence to Javier Silva .

Editors and Affiliations

1. Rambus Inc., San Jose, CA, USA

   Helena Handschuh

2. Brown University, Providence, RI, USA

   Anna Lysyanskaya

A Polynomial Division

In this section, we show that \(p(X)^\ell \bmod {q(X)}\) is an integer-valued polynomial, when \(E \leftrightarrow (t, p, q)\) are either the MNT3 or BN curves. This is completely analogous to the argument in Remark 4.6.

MNT3 Curves. In this case, \(q(X) = 12X^2 - 1\). We proceed by induction on \(\ell \). For \(\ell = 1\), we have that

which is of the form \(6aX + b\), for some \(a, b\in \mathbb {Z}\). We show that, if \(p^\ell \bmod q\) is of this form, then so is \(p^{\ell +1}\bmod {q}\). Then all the remainders will actually be in \(\mathbb {Z}[X]\).

Assume that there exist \(a, b, c, d \in \mathbb {N}\) such that

Then

Since the coefficient of degree 1 is divisible by 6, the induction step works.

BN Curves. In this case, \(q(X) = 36X^4 + 36X^3 + 24X^2 + 6X + 1\). Assume that there exist \(a, b, c, d \in \mathbb {N}\) such that

for some \(a, b, c, d\in \mathbb {Z}\). Then

Since the coefficient of degree 3 is divisible by 36, and the coefficients of degree 2 and 1 are divisible by 6, the induction step works.

B Tables

C SageMath Code

This code is available at [1].

Setup

MNT3() , MNT4() , MNT6() , Freeman() , BN()

These functions return the set of polynomials that define the families of curves MNT3, MNT4, MNT6, Freeman, and BN, respectively.

The expected outputs are:

• t: polynomial \(t(X)\in \mathbb {Q}[X]\) that parameterizes the trace.

• p: polynomial \(p(X)\in \mathbb {Q}[X]\) that parameterizes the order of the curves.

• q: polynomial \(q(X)\in \mathbb {Q}[X]\) that parameterizes the order of the finite field over which the curve is defined.

Code for Proposition 4.1

candidate_embedding_degrees(Family, K_low, K_high)

Given a family of curves, this function computes the possible embedding degrees of curves that may form 2-cycles with a curve of the given family.

The expected inputs are:

• Family: a polynomial parameterization (t(X), p(X), q(X)) of a family of pairing-friendly elliptic curves with prime order.

• K_low, K_high: lower and upper bounds on the embedding degree to look for.

The expected outputs are:

• embedding_degrees: a list of potential embedding degrees k such that \(\texttt {K\_low} \le k \le \texttt {K\_high}\) and a curve from the family might form a cycle with a curve with embedding degree k.

• modular_conditions: conditions on \(x\bmod {k}\) for each of these k.

Auxiliary functions

is_integer_valued(g)

This function checks whether a given polynomial g is integer-valued. It returns True if so, and False otherwise. The test is based on the fact that a polynomial \(g\in \mathbb {Q}[X]\) is integer-valued if and only if \(g(x)\in \mathbb {Z}\) for \(\textrm{deg}\,g + 1\) consecutive \(x\in \mathbb {Z}\) [14, Corollary 2].

find_relevant_root(w, b, side)

This function finds the left-most or right-most root of a polynomial \(b(X)\in \mathbb {Q}[X]\).

The expected inputs are:

• w: positive integer.

• b: polynomial \(b(X)\in \mathbb {Q}[X]\).

• side: this parameter specifies which root to keep. If side = -1, then the function takes the left-most root, and if side = 1, it returns the right-most root.

The expected output is the relevant extremal root.

check_embedding_degree(px, qx, k)

This function determines whether k is the smallest positive integer such that \((\texttt {px}^k - 1) \pmod {\texttt {qx}} = 1\), and outputs \(\texttt {True/False}\).

Code for Table 3

compute_bounds(a, b)

This function computes the bounds \(N_{\textsf{left}}, N_{\textsf{right}}\) of Lemma 4.4. This function has been used to produce the results of tables from Table 3. It uses the auxiliary functions from Appendix C.

The expected inputs are:

• a, b: two integer-valued polynomials in \(\mathbb {Q}[X]\).

The expected outputs are:

• N_left, N_right: integer bounds \(N_{\textsf{left}}, N_{\textsf{right}}\) described in Lemma 4.4.

Code for Corollary 4.8

exhaustive_search(Family, k, N_left, N_right, mod_cond)

This function performs the exhaustive search from Corollary 4.8 within the intervals \([N_{\textsf{left}}, N_{\textsf{right}}]\).

The expected inputs are:

• Family: a polynomial parameterization (t(X), p(X), q(X)) of a family of pairing-friendly elliptic curves with prime order.

• k: an embedding degree.

• N_left, N_right: upper and lower integer bounds.

• mod_cond: conditions on \(x\bmod {\texttt {k}}\) for every x in the interval \([\texttt {N\_left, N\_right}]\).

The expected output is:

• curves: a list of curve descriptions (x, k, t(x), p(x), q(x)) such that \(x\in [\texttt {N\_left, N\_right}]\), and the curve parameterized by (t(x), p(x), q(x)) forms a cycle with a curve with embedding degree k.

1.1 Main function

search_for_cycles(Family, K_low, K_high)

This function looks for 2-cycles formed by a curve belonging to a given parameterized family of curves and a prime-order curve with an embedding degree between two given bounds.

The expected inputs are:

• Family: a polynomial parameterization (t(X), p(X), q(X)) of a family of pairing-friendly elliptic curves with prime order.

• K_low, K_high: integer lower and upper bounds on the embedding degree to look for.

The function prints to a file all 2-cycles involving a curve from the family and a prime-order curve with embedding degree \(\texttt {K\_low} \le k \le \texttt {K\_high}\).

Reprints and permissions

© 2023 International Association for Cryptologic Research

Policies and ethics