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

Original language | English |
---|---|

Title of host publication | CCS'23 : Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security |

Number of pages | 11 |

Place of publication | New York |

Publisher | Association for Computing Machinery |

Publication date | Nov 2023 |

Pages | 3228-3238 |

ISBN (Print) | 979-8-4007-0050-7 |

DOIs | |

Publication status | Published - Nov 2023 |

Event | 30th ACM Conference on Computer and Communications Security - Tivoli Congress Center, Copenhagen, Denmark Duration: 26 Nov 2023 → 30 Nov 2023 https://www.sigsac.org/ccs/CCS2023/index.html |

### Conference

Conference | 30th ACM Conference on Computer and Communications Security |
---|---|

Location | Tivoli Congress Center |

Country/Territory | Denmark |

City | Copenhagen |

Period | 26/11/2023 → 30/11/2023 |

Internet address |

## Keywords

- Constant-time software implementation
- Division step
- Formal verification
- Kronecker/Jacobi/Legendre Symbol