Otimizing Elligator 1 on Curve1174
In the context of the Advanced Systems Lab, my group and I created an optimized implementation of Bernstein’s Elligator 1 mapping. Some of our major optimizations, including exponentiation with constant exponents close to a power of two, can be applied to other problems: they are often useful in modular inversion with prime modulus or finding the quadratic residue. Furthermore, we provide conceptual implementations of Elligator 1 in C, Python, and Sage. The C implementation features a custom Big Integer library, which we optimized for Elligator 1.
The paper is a concise summary of our optimizations and benchmarking results.
We implement and optimize Elligator 1 on Curve1174 using standard optimization techniques as well as sophisticated algorithmic specializations taking advantage of the curve prime and special structure in the mapping. Elligator is a bijective mapping of a subset of points on an elliptic curve to uniformly random bit-strings and back that was proposed by Bernstein et al. We find that this problem is heavily compute-bound. We optimize Elligator 1 for Intel Haswell i7-4980HQ 2.8 GHz and achieve a maximal speedup of 49.6x for the mappings and up to 83.8x for arithmetic operations on Curve1174. We compare the runtime on Intel’s Haswell, Intel’s Kaby Lake, AMD’s Zen 2, and Apple’s M1 platform.
Our code is available on GitHub. It provides three optimization steps (naive, standard optimizations, vector instructions) for the C implementation of Elligator 1.
⚠️ As this course solely focussed on optimization techniques, we did not consider practical security concerns such as timing side-channels. This implementations should thus not be deployed in any production environment.