Simple permutations mix well

DOI10.1016/J.TCS.2005.09.016MaRDI QIDQ2581269zbMATH OpenOpenAlexFDO

Authors Shlomo Hoory, Avner Magen, Steven Myers, Charles W. Rackoff

Publication date 9 January 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.09.016

zbMATH Keywords

\(k\)-wise independencefast mixingpermutationsrandom walk

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Data encryption (aspects in computer science) (68P25) Combinatorics in computer science (68R05) Cryptography (94A60)

Recommendations

• Automata, Languages and Programming
• Simple permutations mix even better
• scientific article; zbMATH DE number 1943960
• Permutations
• Simple permutations and pattern restricted permutations
• Permutads
• A survey of simple permutations
• Prolific permutations

Cites work

• An Almost m-wise Independent Random Permutation of the Cube
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Complexity Theoretic Issues Concerning Block Ciphers Related to D.E.S.
• Generators for Certain Alternating Groups with Applications to Cryptography
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 1440880 (Why is no real title available?)
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Simple permutations mix even better
• Stratified random walks on then-cube
• Theory of Cryptography

Cited in

(21)

• Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers
• The \(t\)-wise independence of substitution-permutation networks
• Random permutations using switching networks
• Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions
• Fast pseudorandom functions based on expander graphs
• Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
• Simple permutations mix even better
• scientific article; zbMATH DE number 5542483 (Why is no real title available?)
• An Almost m-wise Independent Random Permutation of the Cube
• The Complexity of Public-Key Cryptography
• Local random quantum circuits are approximate polynomial-designs
• Automata, Languages and Programming
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Layout graphs, random walks and the t-wise independence of SPN block ciphers
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Pseudorandomness properties of random reversible circuits
• Towards general-purpose program obfuscation via local mixing
• Dynamics of pseudoentanglement
• When simple permutations mix poorly. Limited independence does not imply pseudorandomness
• Efficient quantum pseudorandomness from Hamiltonian phase states
• Almost pairwise independence and resilience to deep learning attacks

This page was built for publication: Simple permutations mix well

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581269)