International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Prime-Order Group with Complete Formulas from Even-Order Elliptic Curves

Authors:
Thomas Pornin , NCC Group
Download:
DOI: 10.62056/akmp-4c2h
URL: https://cic.iacr.org//p/1/1/10
Search ePrint
Search Google
Abstract:

This paper describes a generic methodology for obtaining unified, and then complete formulas for a prime-order group abstraction homomorphic to a subgroup of an elliptic curve with even order. The method is applicable to any curve with even order, in finite fields of both even and odd characteristic; it is most efficient on curves with order equal to 2 modulo 4, dubbed "double-odd curves". In large characteristic fields, we obtain doubling formulas with cost as low as 1M + 5S, and the resulting group allows building schemes such as signatures that outperform existing fast solutions, e.g. Ed25519. In binary fields, the obtained formulas are not only complete but also faster than previously known incomplete formulas; we can sign and verify in as low as 18k and 27k cycles on x86 CPUs, respectively.

BibTeX
@article{cic-2024-34104,
  title={A Prime-Order Group with Complete Formulas from Even-Order Elliptic Curves},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 1},
  url={https://cic.iacr.org//p/1/1/10},
  doi={10.62056/akmp-4c2h},
  author={Thomas Pornin},
  year=2024
}