Paper 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Balkan Cryptsec 2018
Keywords
composite order groupinteger factorizationelliptic curveendomorphismCoppersmith's algorithm
Contact author(s)
sorina ionica @ m4x org
History
2019-08-11: last of 4 revisions
2014-04-21: received
See all versions
Short URL
https://ia.cr/2014/274
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/274,
      author = {Sorina Ionica and Malika Izabachène},
      title = {A note on the construction of pairing-friendly elliptic curves for composite order protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2014/274},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/274}},
      url = {https://eprint.iacr.org/2014/274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.