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$.
Category / Keywords: applications / Verifiable delay function, circuit, modular squaring, RSA Date: received 19 Nov 2020 Contact author: benjamin wesolowski at math u-bordeaux fr Available format(s): PDF | BibTeX Citation Version: 20201119:132453 (All versions of this report) Short URL: ia.cr/2020/1461