**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$.

**Category / Keywords: **applications / Verifiable delay function, circuit, modular squaring, RSA

**Date: **received 19 Nov 2020

**Contact author: **benjamin wesolowski at math u-bordeaux fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20201119:132453 (All versions of this report)

**Short URL: **ia.cr/2020/1461

[ Cryptology ePrint archive ]