Lower bounds for the depth of modular squaring - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Lower bounds for the depth of modular squaring

Résumé

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.
Fichier principal
Vignette du fichier
2020-1461.pdf (556.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03038044 , version 1 (03-12-2020)

Identifiants

  • HAL Id : hal-03038044 , version 1

Citer

Benjamin Wesolowski, Ryan Williams. Lower bounds for the depth of modular squaring. 2020. ⟨hal-03038044⟩

Collections

CNRS INRIA INRIA2
69 Consultations
39 Téléchargements

Partager

Gmail Facebook X LinkedIn More