Near-Bent Boolean Functions Are Insufficient for Correlation-Robust Hashing: A Spectral Obstruction and an Information-Theoretic Frontier

Oblivious Transfer (OT) extension, in particular, the construction of Ishai, Kilian, Nissim, and Petrank (CRYPTO 2003) requires a hash function H that is correlation-robust(CR). All practical instantiations model H as a random oracle or an ideal cipher, leaving CR with no quantifiable reduction to a structural property of the deployed hash. It is natural to ask whether the most nonlinear balanced Boolean functions available on an odd number of variables, the near-bent functions of the Maiorana–McFarland (MM) class, furnish an algebraic, standard-model CR candidate. We prove that they do not, and we identify precisely why. First, we keep a correct spectral fact: a balanced H:{0,1}n→{0,1} is ε-CR if and only if maxΔ≠0|Af(Δ)|≤4ε·2n, reducing CR to an autocorrelation bound. Against this criterion we establish three obstructions: (i) The MM-doubling family NBk on n=2k+1 variables has autocorrelation supported only on the directions (a,0,1), where it equals 2k+1Wa with ∑a≠0Wa2=22k; hence ε≥14(2k−1)−1/2, a factor ≥2k/2 above the value one would need, and an exhaustive search over all balanced members for k≤2 returns the maximal ε=14 in every case. (ii) Near-bentness controls the Walsh maximum (nonlinearity), not autocorrelation: every near-bent function satisfies ∑Δ≠0Af(Δ)2=22n, so maxΔ≠0|Af(Δ)|≥2n(2n−1)−1/2 and no near-bent function is even approximately CR. (iii) A deterministic H:{0,1}κ→{0,1}ℓ admits the support bound SD(H(x),H(x⊕Δ)),(Uℓ,Uℓ)≥1−2κ−2ℓ, so statistical multi-output CR is impossible for ℓ>κ/2 and in particular at the IKNP regime ℓ≈κ. Together, these results close the near-bent route to standard-model CR and clarify which design objective (low absolute indicator, not high nonlinearity) and which parameter regime (ℓ≤κ/2) a viable algebraic candidate would have to target.