Paper Info
Title
Properties of Multiple-Valued Partition Functions
Abstract
We focus on a set of r-valued n-variable functions that are defined by a partition P on the set of r <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> 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, r <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> . 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'.
Year
DOI
Venue
2020
10.1109/ISMVL49045.2020.00-25
2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL)
Keywords
DocType
ISSN
Partition functions,partition set,maximally distant functions,maximally asymmetric functions,bent functions,mutually maximally distant functions,set partitions,characterization and count
Conference
0195-623X
ISBN
Citations 
PageRank 
978-1-7281-5407-7
1
0.36
References 
Authors
0
3
Name
Order
Citations
PageRank
Jon T. Butler132142.77
Tsutomu Sasao21083141.62
Shinobu Nagayama321825.30