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

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

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

3 Citationer (Scopus)

Abstract

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 expo-nentiating to P −1/ 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%.

OriginalsprogEngelsk
TitelCCS'23 : Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
Antal sider11
UdgivelsesstedNew York
ForlagAssociation for Computing Machinery
Publikationsdato15 nov. 2023
Sider3228-3238
ISBN (Trykt)979-8-4007-0050-7
DOI
StatusUdgivet - 15 nov. 2023
Begivenhed30th ACM Conference on Computer and Communications Security - Tivoli Congress Center, Copenhagen, Danmark
Varighed: 26 nov. 202330 nov. 2023
https://www.sigsac.org/ccs/CCS2023/index.html

Konference

Konference30th ACM Conference on Computer and Communications Security
LokationTivoli Congress Center
Land/OmrådeDanmark
ByCopenhagen
Periode26/11/202330/11/2023
Internetadresse

Fingeraftryk

Dyk ned i forskningsemnerne om 'Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing'. Sammen danner de et unikt fingeraftryk.

Citationsformater