Paper 2020/1461

Lower bounds for the depth of modular squaring

Benjamin Wesolowski and Ryan Williams


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)
Publication info
Preprint. MINOR revision.
Verifiable delay functioncircuitmodular squaringRSA
Contact author(s)
benjamin wesolowski @ math u-bordeaux fr
2020-11-19: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.