Limited Independence

What t-wise (limited) independence of a distribution does, and does not, imply.

Status	Problem	Tags
	192-Round AES Pairwise Independence Theorem 7 proves the bound for 192-round censored AES – real AES S-boxes and mixing layer, but a subset of the mixing layers removed. The source conjectures the same round count suffices for AES itself, and calls proving it an outstanding open problem. The best proved bound for actual AES is Liu, Tessaro and Vaikuntanathan’s, which needs more than 9000 rounds. 4 open	Block Ciphers Limited Independence Pseudorandom Permutations T Wise Independencetight-bound
	SZK Batch Verification Named by the source as the most pressing open question its work leaves. Its Theorem 1.1 gives the NISZK analogue: communication and CRS length \(\mathrm{poly}(n,\log k)\) for \(k\) up to \(2^{n^{0.01}}\). A \(\mathrm{poly}(n)\) dependence is unavoidable even at \(k=1\) under a sub-exponential hardness assumption, so \(\log k\) is the aggressive part of the bound. The source also offers a weaker fallback target: any sub-linear dependence on \(k\). 5 open	Batch Verification Direct Product Theorems Limited Independence Randomness Extractioncharacterization
	Almost k-Wise Locality Gap Settled up to a \(\log n\) factor at word size 1 and at word size \(\Omega(\log^2 n)\) and above; the source gives no matching construction at all for intermediate word sizes, so the gap is recorded only where both a bound and a construction exist to compare. 4 open	Limited Independence Locally Computable Hashingtight-boundadaptation (ai)
	Logarithmic independence implies PRP Open at independence order \(\log n\). The same implication is refuted at order 4 and at every constant order by an explicit construction; the logarithmic-order form is untouched, and no unconditional proof of it can be expected. 5 open	Limited Independence Pseudorandom Permutationscharacterization
	Randomness Complexity of XOR The source proves an \(\Omega(t^2)\) lower bound, matching Kushilevitz and Mansour’s non-explicit \(O(t^2\log(n/t))\) upper bound up to a logarithmic factor, and up to a constant factor when \(t=\Omega(n)\). It also gives an explicit protocol at \(O(t^2\log^2 n)\). It states it leaves the remaining polylogarithmic gaps open. 4 open	Limited Independence Randomness Complexitytight-bound
	AES t-Wise Independence, t > 2 Named by the source as the first of the two outstanding open problems that come of its work. It proves almost pairwise independence (\(t=2\)) for multi-round AES with independent round keys, and an existential \(t\)-wise result for key-alternating ciphers with most permutations, but nothing for concrete AES beyond \(t=2\). Its Appendix B attacks 4-wise independence in the width-1 case with the same S-box. 4 open	Block Ciphers Limited Independence Pseudorandom Permutations T Wise Independencecharacterizationbarrier (ai)