Near-Bent Boolean Functions Are Insufficient for Correlation-Robust Hashing: A Spectral Obstruction and an Information-Theoretic Frontier
Journal
Cryptography
ISSN
2410387X
Publisher
MDPI AG
Date Issued
2026-06-26
Author(s)
Type
Article
Abstract
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 (Formula presented.) is (Formula presented.) -CR if and only if (Formula presented.), reducing CR to an autocorrelation bound. Against this criterion we establish three obstructions: (i) The MM-doubling family (Formula presented.) on (Formula presented.) variables has autocorrelation supported only on the directions (Formula presented.), where it equals (Formula presented.) with (Formula presented.) ; hence (Formula presented.), a factor (Formula presented.) above the value one would need, and an exhaustive search over all balanced members for (Formula presented.) returns the maximal (Formula presented.) in every case. (ii) Near-bentness controls the Walsh maximum (nonlinearity), not autocorrelation: every near-bent function satisfies (Formula presented.), so (Formula presented.) and no near-bent function is even approximately CR. (iii) A deterministic (Formula presented.) admits the support bound (Formula presented.), so statistical multi-output CR is impossible for (Formula presented.) and in particular at the IKNP regime (Formula presented.). 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 ( (Formula presented.) ) a viable algebraic candidate would have to target. © 2026 by the author.