A Fast Large-Integer Extended GCD ... - Cryptology EPrint Archive

Cryptology ePrint Archive

• Papers
  Updates from the last:
  • 7 days
  • 31 days
  • 6 months
  • 365 days
  • Listing by year
  • All papers
  • Compact view
  • Subscribe
  • How to cite
  • Harvesting metadata
• Submissions
  • Submit a paper
  • Revise or withdraw a paper
  • Acceptance and publishing conditions
• About
  • Goals and history
  • News
  • Statistics
  • Contact

Search Advanced search

Paper 2021/1292

A Fast Large-Integer Extended GCD Algorithm and Hardware Design for Verifiable Delay Functions and Modular Inversion

Kavya Sreedhar, Stanford University Mark Horowitz, Stanford University Christopher Torng, Stanford University

Abstract

The extended GCD (XGCD) calculation, which computes Bézout coefficients b_a, b_b such that b_a ∗ a_0 + b_b ∗ b_0 = GCD(a_0, b_0), is a critical operation in many cryptographic applications. In particular, large-integer XGCD is computationally dominant for two applications of increasing interest: verifiable delay functions that square binary quadratic forms within a class group and constant-time modular inversion for elliptic curve cryptography. Most prior work has focused on fast software implementations. The few works investigating hardware acceleration build on variants of Euclid’s division-based algorithm, following the approach used in optimized software. We show that adopting variants of Stein’s subtraction-based algorithm instead leads to significantly faster hardware. We quantify this advantage by performing a large-integer XGCD accelerator design space exploration comparing Euclid- and Stein-based algorithms for various application requirements. This exploration leads us to an XGCD hardware accelerator that is flexible and efficient, supports fast average and constant-time evaluation, and is easily extensible for polynomial GCD. Our 16nm ASIC design calculates 1024-bit XGCD in 294ns (8x faster than the state-of-the-art ASIC) and constant-time 255-bit XGCD for inverses in the field of integers modulo the prime 2^255−19 in 85ns (31× faster than state-of-the-art software). We believe our design is the first high-performance ASIC for the XGCD computation that is also capable of constant-time evaluation. Our work is publicly available at https://github.com/kavyasreedhar/sreedhar-xgcd-hardware-ches2022.

Metadata

Available format(s) PDF Category Implementation Publication info Published by the IACR in TCHES 2022 DOI 10.46586/tches.v2022.i4.163-187 Keywords Extended GCD ASIC Verifiable delay function Class groups Squaring binary quadratic forms Constant-time Modular inversion Curve25519 Contact author(s) skavya @ stanford eduhorowitz @ ee stanford eductorng @ stanford edu History 2022-09-16: last of 5 revisions 2021-09-27: received See all versions Short URL https://ia.cr/2021/1292 License CC BY

BibTeX Copy to clipboard

@misc{cryptoeprint:2021/1292, author = {Kavya Sreedhar and Mark Horowitz and Christopher Torng}, title = {A Fast Large-Integer Extended {GCD} Algorithm and Hardware Design for Verifiable Delay Functions and Modular Inversion}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1292}, year = {2021}, doi = {10.46586/tches.v2022.i4.163-187}, url = {https://eprint.iacr.org/2021/1292} } Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.