Properties of Multiple-Valued Partition Functions

We focus on a set of r-valued n-variable functions that are defined by a partition P on the set of rn input vectors. Specifically, each block of P specifies input vectors, all of which map to the same function value. For example, a symmetric function is defined by a partition where input vectors in the same block are permutations of each other. Given the partition P and the set S of functions associated with P, we analyze the set S' of functions that are a maximal distance from S. Such functions hold promise for use in crypto-systems.In this paper, we characterize functions in S'. From this, we compute the distance to their corresponding partition functions. We show that, when r and n increase without bound, this distance approaches the maximum possible, rn. Bent functions achieve only half the maximum possible distance when n is large. We show that functions a maximal distance from partition functions tend to have a uniform distribution across the r possible function values. Such functions tend to be immune to statistics-based attacks. Finally, we show that, if the set S' of functions is maximally distant from a set S of partition functions, then the converse is true; that is, S is maximally distant from S'.