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

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

Available format(s)
Category
Implementation
Publication info
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
See all versions
Short URL
https://ia.cr/2021/1292

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.