WESOLOWSKI, Benjamin; WILLIAMS, Ryan

Metadatos

Licencia de uso del documento

WESOLOWSKI, Benjamin
Lithe and fast algorithmic number theory [LFANT]
Centre National de la Recherche Scientifique [CNRS]
Analyse cryptographique et arithmétique [CANARI]

WILLIAMS, Ryan
Computer Science and Artificial Intelligence Laboratory [Cambridge] [CSAIL]

Idioma

Document de travail - Pré-publication

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

Verifiable delay function

Circuit

Modular squaring

RSA

Metadatos

Compartir este ítem

Licencia de uso del documento

Lower bounds for the depth of modular squaring

Idioma

Resumen en inglés

Palabras clave en inglés

URI

Orígen

Centros de investigación