Cryptology ePrint Archive: Report 2020/1461

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