### Low-Latency ASIC Algorithms of Modular Squaring of Large Integers for VDF Evaluation

Ahmet Can Mert, Erdinc Ozturk, and Erkay Savas

##### Abstract

This study 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 N$, 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)$ depth circuit implementations, where $k$ is the bit-size of the modulus $N$ 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.

##### Metadata
Available format(s)
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Verifiable Delay FunctionsModular SquaringReductionMontgomeryRedundant Representation
Contact author(s)
ahmetcanmert @ sabanciuniv edu
erdinco @ sabanciuniv edu
erkays @ sabanciuniv edu
History
2020-09-18: revised
2020-04-28: received
See all versions
Short URL
https://ia.cr/2020/480
License

CC BY

BibTeX

@misc{cryptoeprint:2020/480,
author = {Ahmet Can Mert and Erdinc Ozturk and Erkay Savas},
title = {Low-Latency ASIC Algorithms of Modular Squaring of Large Integers for VDF Evaluation},
howpublished = {Cryptology ePrint Archive, Paper 2020/480},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/480}},
url = {https://eprint.iacr.org/2020/480}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.