Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Lower bounds for the depth of modular squaring

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Benjamin Wesolowski Connect in order to contact the contributor
Submitted on : Thursday, December 3, 2020 - 11:58:54 AM
Last modification on : Wednesday, November 3, 2021 - 5:55:50 AM
Long-term archiving on: : Thursday, March 4, 2021 - 6:59:20 PM


Files produced by the author(s)


  • HAL Id : hal-03038044, version 1




Benjamin Wesolowski, Ryan Williams. Lower bounds for the depth of modular squaring. 2020. ⟨hal-03038044⟩



Record views


Files downloads