Faster Constant-time Evaluation of the Kronecker Symbol with Application to Elliptic Curve Hashing

We generalize the Bernstein-Yang (BY) algorithm [11] for constant-time modular inversion to compute the Kronecker symbol, of which the Jacobi and Legendre symbols are special cases. We first develop a basic and easy-to-implement algorithm, defined with full-precision division steps. We then describe an optimized version due to Hamburg [21] over word-sized inputs, and formally verify its correctness. Along the way, we introduce a number of optimizations for implementing both versions in constant time. The resulting algorithms are particularly suitable for computing the Legendre symbol with dense prime p, where no efficient addition chain is known for exponentiating to p-1 over 2, as it is often the case in pairing-friendly elliptic curves. Our high-speed implementation for a range of parameters shows that the new algorithm is up to 40 times faster than exponentiation, and up to 25.7% faster than the previous state of the art. We illustrate our techniques with hashing to elliptic curves using the SwiftEC algorithm [17], with savings of 14.7%-48.1%, and to accelerating the CTIDH isogeny-based key exchange [7], with savings of 3.5-13.5%.