Lower bounds for the depth of modular squaring
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| hal.structure.identifier | Centre National de la Recherche Scientifique [CNRS] | |
| hal.structure.identifier | Analyse cryptographique et arithmétique [CANARI] | |
| dc.contributor.author | WESOLOWSKI, Benjamin | |
| hal.structure.identifier | Computer Science and Artificial Intelligence Laboratory [Cambridge] [CSAIL] | |
| dc.contributor.author | WILLIAMS, Ryan | |
| dc.date.accessioned | 2024-04-04T02:48:38Z | |
| dc.date.available | 2024-04-04T02:48:38Z | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191756 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | Verifiable delay function | |
| dc.subject.en | Circuit | |
| dc.subject.en | Modular squaring | |
| dc.subject.en | RSA | |
| dc.title.en | Lower bounds for the depth of modular squaring | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Informatique [cs]/Cryptographie et sécurité [cs.CR] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-03038044 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03038044v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=WESOLOWSKI,%20Benjamin&WILLIAMS,%20Ryan&rft.genre=preprint |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||