More Efficient Approximate $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

Lucas Gretta; William He; Angelos Pelecanos

Paper 2024/847

More Efficient Approximate $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

Lucas Gretta, University of California, Berkeley

William He, Carnegie Mellon University

Angelos Pelecanos

, University of California, Berkeley

Abstract

We prove that the permutation computed by a reversible circuit with $\widetilde{O}(nk\cdot \log(1/\epsilon))$ random $3$-bit gates is $\epsilon$-approximately $k$-wise independent. Our bound improves on currently known bounds in the regime when the approximation error $\epsilon$ is not too small. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.

Note: 19 pages

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: information theory block ciphers pseudorandomness
Contact author(s): lucas_gretta @ berkeley edu
wrhe @ cs cmu edu
apelecan @ berkeley edu
History: 2024-05-31: revised; 2024-05-29: received; See all versions
Short URL: https://ia.cr/2024/847
License: CC BY

BibTeX

@misc{cryptoeprint:2024/847,
      author = {Lucas Gretta and William He and Angelos Pelecanos},
      title = {More Efficient Approximate $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities},
      howpublished = {Cryptology ePrint Archive, Paper 2024/847},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/847}},
      url = {https://eprint.iacr.org/2024/847}
}