Faster Mixing of Higher-Dimensional Random Reversible Circuits
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929711262728192 |
|---|---|
| author | Gay, William He, William Kocurek, Nicholas |
| author_facet | Gay, William He, William Kocurek, Nicholas |
| contents | We continue the study of the approximate $k$-wise independence of random reversible circuits as permutations of $\{\pm1\}^n$. Our main result is the first construction of a natural class of random reversible circuits with a sublinear-in-$n$ dependence on depth. Our construction is motivated by considerations in practical cryptography and is somewhat inspired by the design of practical block ciphers, such as DES and AES. Previous constructions of He and O'Donnell [HO24], which were built with gate architectures on one-dimensional lattices, suffered from an inherent linear-in-$n$ dependence on depth. The main novelty of our circuit model is a gate architecture built on higher-dimensional lattices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14614 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Mixing of Higher-Dimensional Random Reversible Circuits Gay, William He, William Kocurek, Nicholas Computational Complexity Cryptography and Security We continue the study of the approximate $k$-wise independence of random reversible circuits as permutations of $\{\pm1\}^n$. Our main result is the first construction of a natural class of random reversible circuits with a sublinear-in-$n$ dependence on depth. Our construction is motivated by considerations in practical cryptography and is somewhat inspired by the design of practical block ciphers, such as DES and AES. Previous constructions of He and O'Donnell [HO24], which were built with gate architectures on one-dimensional lattices, suffered from an inherent linear-in-$n$ dependence on depth. The main novelty of our circuit model is a gate architecture built on higher-dimensional lattices. |
| title | Faster Mixing of Higher-Dimensional Random Reversible Circuits |
| topic | Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2409.14614 |