Title:

Faster constant-time evaluation of the Kronecker symbol

 

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. 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, where no efficient addition chain is known for the conventional approach by exponentiation to (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 exponentiation approach, and around 25.7% faster than the previous state of the art. We illustrate the performance of the algorithm with an application for sampling points and hashing to elliptic curves.

 

Speaker:

Prof. Diego Aranha

Department of Computer Science
Aarhus University