Welcome to the resource topic for 2020/1461
Title:
Lower bounds for the depth of modular squaring
Authors: Benjamin Wesolowski, 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.
ePrint: https://eprint.iacr.org/2020/1461
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .