Paper 2021/1292

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

Kavya Sreedhar, Mark Horowitz, and Christopher Torng

Abstract

The extended GCD (XGCD) calculation, which computes B\'ezout 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 demonstrate this fact by performing a large-integer XGCD accelerator design space exploration to quantify the tradeoffs between 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 87ns (31X faster than state-of-the-art software). We believe our chip is the first high-performance ASIC for the XGCD computation that is also capable of constant-time evaluation.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Extended GCDASICVerifiable delay functionClass groupsSquaring binary quadratic formsConstant-timeModular inversionCurve25519
Contact author(s)
skavya @ stanford edu
horowitz @ ee stanford edu
ctorng @ stanford edu
History
2022-05-10: last of 3 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},
      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.