The system will be going down for regular maintenance. Please save your work and logout.
Lower bounds for the depth of modular squaring
WESOLOWSKI, Benjamin
Lithe and fast algorithmic number theory [LFANT]
Centre National de la Recherche Scientifique [CNRS]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
Centre National de la Recherche Scientifique [CNRS]
Analyse cryptographique et arithmétique [CANARI]
WESOLOWSKI, Benjamin
Lithe and fast algorithmic number theory [LFANT]
Centre National de la Recherche Scientifique [CNRS]
Analyse cryptographique et arithmétique [CANARI]
< Reduce
Lithe and fast algorithmic number theory [LFANT]
Centre National de la Recherche Scientifique [CNRS]
Analyse cryptographique et arithmétique [CANARI]
Language
en
Document de travail - Pré-publication
English 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 ...Read more >
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.Read less <
English Keywords
Verifiable delay function
Circuit
Modular squaring
RSA
Origin
Hal imported