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
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
-
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}, url = {https://eprint.iacr.org/2020/1461} }