all InfoSec News
More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
May 31, 2024, 8:36 a.m. |
IACR News www.iacr.org
ePrint Report: More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Lucas Gretta, William He, Angelos Pelecanos
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.
More from www.iacr.org / IACR News
Jobs in InfoSec / Cybersecurity
Principal Architect - LINUX - Active Top Secret Required
@ General Dynamics Information Technology | USA DC Washington - Customer Proprietary (DCC076)
Expert SOAR (CORTEX)
@ Alter Solutions | PARIS, France
Program Management Analyst
@ Peraton | Arlington, VA, United States
Gestion des menaces et des vulnérabilités
@ Alter Solutions | Paris, France
Senior IAM Security Engineer
@ WEX | Brazil - Remote Office
Senior Information Security Engineer
@ Ameriprise Financial Services | 11071 Ameriprise India - Hyderabad