Cryptology ePrint Archive: Report 2014/274

A note on the construction of pairing-friendly elliptic curves for composite order protocols

Sorina Ionica and Malika Izabachène

Abstract: In pairing-based cryptography, the security of protocols using composite order groups relies on the difficulty of factoring a composite number $N$. Boneh~\etal~proposed the Cocks-Pinch method to construct ordinary pairing-friendly elliptic curves having a subgroup of composite order $N$. Displaying such a curve as a public parameter implies revealing a square root $s$ of the complex multiplication discriminant $-D$ modulo $N$. We exploit this information leak and the structure of the endomorphism ring of the curve to factor the RSA modulus, under certain conditions. Our conclusion is that the values of $s$ modulo each prime in the factorization of $N$ should be chosen as high entropy input parameters when running the Cocks-Pinch algorithm.

Category / Keywords: composite order group, integer factorization, elliptic curve, endomorphism, Coppersmith's algorithm

Original Publication (with minor differences): Balkan Cryptsec 2018

Date: received 20 Apr 2014, last revised 11 Aug 2019

Contact author: sorina ionica at m4x org

Available format(s): PDF | BibTeX Citation

Version: 20190811:080729 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]