### Lower bounds for the depth of modular squaring

Benjamin Wesolowski and Ryan Williams

##### Abstract

The modular squaring operation has attracted significant attention due to its potential in constructing cryptographic time-lock puzzles and verifiable delay functions. In such applications, it is important to understand precisely how quickly a modular squaring operation can be computed, even in parallel on dedicated hardware. We use tools from circuit complexity and number theory to prove concrete numerical lower bounds for squaring on a parallel machine, yielding nontrivial results for practical input bitlengths. For example, for $n=2048$, we prove that every logic circuit (over AND, OR, NAND, NOR gates of fan-in two) computing modular squaring on all $n$-bit inputs (and any modulus that is at least $2^{n-1}$) requires depth (critical path length) at least $12$. By a careful analysis of certain exponential Gauss sums related to the low-order bit of modular squaring, we also extend our results to the average case. For example, our results imply that every logic circuit (over any fan-in two basis) computing modular squaring on at least $76\%$ of all $2048$-bit inputs (for any RSA modulus that is at least $2^{n-1}$) requires depth at least $9$.

Available format(s)
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Verifiable delay functioncircuitmodular squaringRSA
Contact author(s)
benjamin wesolowski @ math u-bordeaux fr
History
Short URL
https://ia.cr/2020/1461

CC BY

BibTeX

@misc{cryptoeprint:2020/1461,
author = {Benjamin Wesolowski and Ryan Williams},
title = {Lower bounds for the depth of modular squaring},
howpublished = {Cryptology ePrint Archive, Paper 2020/1461},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1461}},
url = {https://eprint.iacr.org/2020/1461}
}

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