Low-latency ASIC algorithms of modular squaring of large integers for VDF evaluation

Mert, Ahmet Can and Öztürk, Erdinç and Savaş, Erkay (2022) Low-latency ASIC algorithms of modular squaring of large integers for VDF evaluation. IEEE Transactions on Computers, 71 (1). pp. 107-120. ISSN 0018-9340 (Print) 1557-9956 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)


This article is an attempt in quest of the fastest hardware algorithms for the computation of the evaluation component of verifiable delay functions (VDFs), a {2 T} \bmod Na2TN, proposed for use in various distributed protocols, in which no party is assumed to compute it significantly faster than other participants. To this end, we propose a class of modular squaring algorithms suitable for low-latency ASIC implementations. The proposed algorithms aim to achieve highest levels of parallelization that have not been explored in previous works in the literature, which usually pursue more balanced optimization of speed and area. For this, we utilize redundant representations of integers and introduce three modular squaring algorithms that work with integers in redundant forms: i) Montgomery algorithm, ii) memory-based algorithm and iii) direct reduction algorithm for fixed moduli. All algorithms enable O(\log k)O(logk) depth circuit implementations, where kk is the bit-size of the modulus NN in the VDF function. We analyze and compare gate level-circuits of the proposed algorithms and provide estimates for their critical path delay and gate count.
Item Type: Article
Uncontrolled Keywords: modular squaring; montgomery; reduction; redundant representation; Verifiable delay functions
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Ahmet Can Mert
Date Deposited: 31 Aug 2022 17:41
Last Modified: 31 Aug 2022 17:41
URI: https://research.sabanciuniv.edu/id/eprint/43589

Available Versions of this Item

Actions (login required)

View Item
View Item