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

Diego F. Aranha; Benjamin Salling Hvass; Bas Spitters; Mehdi Tibouchi

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)

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\%.

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

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Minor revision. ACM CCS 2023
DOI: 10.1145/3576915.3616597
Keywords: Kronecker/Jacobi/Legendre Symbol Division step Constant-time software implementation Formal verification.
Contact author(s): dfaranha @ cs au dk
bsh @ cs au dk
spitters @ cs au dk
mehdi tibouchi br @ hco ntt co jp
History: 2024-05-20: last of 8 revisions; 2023-08-21: received; See all versions
Short URL: https://ia.cr/2023/1261
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1261,
      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},
      url = {https://eprint.iacr.org/2023/1261}
}