YACL Talk | Nov 7 | Jesko Dujmovic, Northwestern University - When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness

[Aviv Yaish]

Do join our next exciting talk by Jesko Dujmovic!

• Jesko Dujmovic, Northeastern University and Boston University - When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness

• Abstract: Over the past two decades, several works have used (almost) $k$-wise independence as a proxy property for block ciphers, since it guarantees resistance against broad classes of statistical attacks. For example, even the case $k = 2$ already implies security against differential and linear cryptanalysis. Hoory, Magen, Myers, and Rackoff (ICALP ’04; TCS ’05) formulated an appealing conjecture: if the sequential composition of $T$ independent local randomized permutations is (close to) four-wise independent, then it should also be a pseudorandom permutation. Here, ``local'' means that each output bit depends on only a constant number of input bits. This conjecture offers a potential strong justification for analyses of block ciphers that establish (almost) $k$-wise independence of this type of constructions. In this work, we disprove the conjecture in full generality by presenting an explicit local randomized permutation whose sequential composition is four-wise independent, but not a pseudorandom permutation. Our counterexample in fact extends to $k$-wise independence for any constant~$k$
• Bio: Jesko Dujmovic is a PostDoc at Northeastern University and Boston University with Daniel Wichs and Ran Canetti. He did his PhD with Nico Döttling at CISPA. He conducts research in cryptography and has published on SNARGs, Registration-Based Encryption, Space-Hard cryptography, Timelock-Puzzles, and 2PC.
• Livestream: https://yale.zoom.us/j/95371310133?pwd=OgRvZlwwt80On26WFAvNWnb8BRCndF.1
• More: For additional details about the talk, see our website: https://yacl.cs.yale.edu

[Aviv Yaish]

Do join tomorrow's very interesting talk by Jesko!