When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness

Jesko Dujmovic; Angelos Pelecanos; Stefano Tessaro

Paper 2025/2282

When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness

Jesko Dujmovic

, Northeastern University

Angelos Pelecanos

, University of California, Berkeley

Stefano Tessaro

, University of Washington

Abstract

Over the past two decades, several works have used (almost) $k$-wise independence as a proxy for pseudorandomness in 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$.

Note: 43 pages, comments welcome. v2: added remark about round locality.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in EUROCRYPT 2026
Keywords: block ciphers information theory
Contact author(s): mail @ ind-jesko net
apelecan @ berkeley edu
tessaro @ cs washington edu
History: 2026-02-24: revised; 2025-12-18: received; See all versions
Short URL: https://ia.cr/2025/2282
License: CC BY

BibTeX

@misc{cryptoeprint:2025/2282,
      author = {Jesko Dujmovic and Angelos Pelecanos and Stefano Tessaro},
      title = {When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2282},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2282}
}