EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Guillermo Sosa-Gómez

Cryptography · 26.06.2026 · 10 (4) · 43

DOI: 10.3390/cryptography10040043 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Cryptography, online erschienen am 26.06.2026. Verfasst von Guillermo Sosa-Gómez. Die Arbeit nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Sosa-Gómez, G. (2026). Near-Bent Boolean Functions Are Insufficient for Correlation-Robust Hashing: A Spectral Obstruction and an Information-Theoretic Frontier. Cryptography, 10(4), 43. https://doi.org/10.3390/cryptography10040043

Vancouver

Sosa-Gómez G. Near-Bent Boolean Functions Are Insufficient for Correlation-Robust Hashing: A Spectral Obstruction and an Information-Theoretic Frontier. Cryptography. 2026;10(4):43. doi:10.3390/cryptography10040043

BibTeX
@article{SosaGmez2026,
  author = {Sosa-Gómez, Guillermo},
  title = {Near-Bent Boolean Functions Are Insufficient for Correlation-Robust Hashing: A Spectral Obstruction and an Information-Theoretic Frontier},
  journal = {Cryptography},
  year = {2026},
  volume = {10},
  number = {4},
  pages = {43},
  doi = {10.3390/cryptography10040043}
}
Kostenlos starten →