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

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Verifiable delay functioncircuitmodular squaringRSA
Contact author(s)
benjamin wesolowski @ math u-bordeaux fr
History
2020-11-19: received
Short URL
https://ia.cr/2020/1461
License
Creative Commons Attribution
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.