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 edu
horowitz @ ee stanford edu
ctorng @ 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
Creative Commons Attribution
CC BY

BibTeX

@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},
      note = {\url{https://eprint.iacr.org/2021/1292}},
      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.