Welcome to the resource topic for 2023/1261
Title:
Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing
Authors: Diego F. Aranha, Benjamin Salling Hvass, Bas Spitters, Mehdi Tibouchi
Abstract: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%.
ePrint: https://eprint.iacr.org/2023/1261
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .