Elligator


Introduction
Papers
Software

Software

We have Sage implementations of Elligator for automated verification, but we don't have serious performance-oriented implementations yet. This page reports preliminary performance estimates.

Here are some figures from the Ed25519 paper and eBATS for a high-security curve (Curve25519) on an Intel Westmere CPU:

  • Full scalar multiplication takes 226872 cycles.
  • Fixed-base-point scalar multiplication takes only 80352 cycles.
  • Standard point decompression takes only 44000 cycles.
The basic bottleneck for Elligator is exactly the same sqrt computation used for standard point decompression. There are also a few chi computations, but libgmp computes chi (mpz_jacobi) in only 9000 cycles for 256-bit inputs despite the overhead of being a general-purpose library. The loop in the protocols in Section 2 of the paper is repeated twice on average, but each iteration takes only 80352 cycles plus one chi computation.
Version: This is version 2013.08.29 of the software.html web page.