Paper 2023/1261

Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing

Diego F. Aranha, Aarhus University
Benjamin Salling Hvass, Aarhus University
Bas Spitters, Aarhus University
Mehdi Tibouchi, NTT (Japan)

We generalize the Bernstein-Yang (BY) algorithm for constant-time modular inversion to compute the Kronecker symbol, of which the Jacobi and Legendre symbols are special cases. We start by developing a basic and easy-to-implement divstep version of the algorithm defined in terms of full-precision division steps. We then describe an optimized version due to Hamburg over word-sized inputs, similar to the jumpdivstep version of the BY algorithm, and formally verify its correctness. Along the way, we introduce a number of optimizations for implementing both versions in constant time and at high-speed. The resulting algorithms are particularly suitable for the special case of computing the Legendre symbol with dense prime $p$, where no efficient addition chain is known for the conventional approach by exponentiation to $\frac{p-1}{2}$. This is often the case for the base field of popular 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 the conventional exponentiation approach, and up to 25.7\% faster than the previous state of the art. We illustrate the performance of the algorithm with an application for hashing to elliptic curves, where the observed savings amount to 14.7\% -- 48.1\% when used for testing quadratic residuosity within the SwiftEC hashing algorithm. We also apply our techniques to the CTIDH isogeny-based key exchange, with savings of 3.5--13.5\%.

Note: Fixed some annoying typos in the algorithms, relaxed restrictions on Algorithms 6 and 7.

Available format(s)
Publication info
Published elsewhere. Minor revision. ACM CCS 2023
Kronecker/Jacobi/Legendre SymbolDivision stepConstant-time software implementationFormal verification.
Contact author(s)
dfaranha @ cs au dk
bsh @ cs au dk
spitters @ cs au dk
mehdi tibouchi br @ hco ntt co jp
2024-05-20: last of 8 revisions
2023-08-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Diego F. Aranha and Benjamin Salling Hvass and Bas Spitters and Mehdi Tibouchi},
      title = {Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1261},
      year = {2023},
      doi = {10.1145/3576915.3616597},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.