Paper 2026/838

On the Resilience Order of Weightwise Almost Perfectly Balanced Functions

Abstract

The recent development of Fully Homomorphic Encryption (FHE) witnessed the emergence of a new generation of tailored cryptographic primitives designed to meet its specific criteria. Among promising candidates for FHE constructions stands out the FLIP cipher, which employs Boolean functions that are evaluated only on specific subsets of $\mathbb{F}_2^n$. In this article, we study Weightwise Almost Perfectly Balanced (WAPB) functions, which are almost balanced on each of these subsets. While WAPB functions have been of great interest for new constructions recently, some aspects, such as resilience remain poorly understood. As such, we take a first step at characterizing the resilience of WAPB functions, through their properties as correctors. We highlight its close connection with the restricted Walsh transform and uncover an algebraic relation between Krawtchouk matrices and Vandermonde matrices, which reduces the problem of determining the corrector order of a WAPB function to a particular instance of the Prouhet-Tarry-Escott problem. This reduction helps us show that for infinitely many integers $n$, WAPB functions in $n$ variables have corrector order tightly upper bounded by the Hamming weight of $n$ minus one. We conjecture that this observation holds for any positive integer $n$, which is verified for $n$ up to $62$.