Three New Families of Zero-Difference Balanced Functions With Applications

Cunsheng Ding, Qi Wang, Maosheng Xiong

TL;DR

This paper introduces three novel families of Zero-Difference Balanced (ZDB) functions, expanding the toolkit for constructing efficient error-correcting codes and cryptographic primitives. These new ZDB functions offer more flexible parameters and are applied to generate improved optimal constant composition codes and difference systems of sets.

What Problem Does This Paper Address?

The paper tackles the challenge of finding new Zero-Difference Balanced (ZDB) functions with flexible parameters. ZDB functions are crucial in various fields like coding theory, cryptography, and communications engineering. While existing ZDB functions have proven useful, there's a continuous need for new constructions that offer a wider range of parameters to meet specific application requirements. The authors aim to address this by presenting three new families of ZDB functions, two of which are specifically designed to offer more flexible parameter choices than previously known constructions.

Methods

The paper presents three distinct constructions for ZDB functions:

  • First Construction (Abelian Groups): This method builds upon recent work and constructs ZDB functions on generalized abelian groups of the form $GF(q_1) \times \dots \times GF(q_k)$. It utilizes the concept of generalized cyclotomy within these groups, allowing for flexible parameter choices based on the prime powers $q_i$ and a parameter $e$. The construction involves decomposing the group into cosets of cyclic subgroups generated by specific elements.
  • Second and Third Constructions (Cyclic Groups $\mathbb{Z}_n$): These constructions focus on ZDB functions defined on the cyclic group $\mathbb{Z}_n$. They leverage 2-cyclotomic cosets modulo $n$, where $n = 2^m - 1$. The second construction yields ZDB functions with parameters $(2^m-1, \frac{2^m+m-2}{m}, m-1)$, and the third provides functions with parameters $(2^m-1, \frac{2^{m-1}+m-1}{m}, 2^m-1)$. These constructions are specifically designed for $n$ of the form $2^m-1$ and offer new parameter sets.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions of mathematical objects (ZDB functions) and their applications, rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Flexibility in Group Structure: The first construction is particularly noteworthy for its ability to work with non-cyclic abelian groups, broadening the applicability of ZDB functions beyond just cyclic groups.
  • New Parameter Spaces: The constructions based on 2-cyclotomic cosets open up new possibilities for ZDB functions on $\mathbb{Z}_n$ with parameters that were not previously available.
  • Connection to Codes and DSSs: The paper reinforces the strong link between ZDB functions and the construction of optimal constant composition codes (CCCs) and optimal/perfect difference systems of sets (DSSs). The new ZDB functions directly translate into new optimal CCCs and DSSs.
  • Parameter Importance: The authors emphasize that when comparing ZDB functions, it's crucial to consider all parameters ($n$, $\bar{\ell}$, $\lambda$, and the preimage set sizes $\{\tau_i\}$), not just a subset, to truly assess novelty.

Key Results

The paper successfully presents three new families of ZDB functions:

  1. Family 1: ZDB functions on $(GF(q_1) \times \dots \times GF(q_k), +)$ with parameters $(n, \frac{n+e-1}{e}, e-1)$, where $n = q_1 \dots q_k$ and $e | (q_i-1)$ for all $i$.
  2. Family 2: ZDB functions on $(\mathbb{Z}_{2^m-1}, +)$ with parameters $(2^m-1, \frac{2^m+m-2}{m}, m-1)$, where $m$ is a prime. The preimage set sizes are $\{1, m, \dots, m\}$.
  3. Family 3: ZDB functions on $(\mathbb{Z}_{2^m-1}, +)$ with parameters $(2^m-1, \frac{2^{m-1}+m-1}{m}, 2^m-1)$, where $m$ is an odd prime. The preimage set sizes are $\{1, 2m, \dots, 2m\}$.

These constructions lead to new optimal constant composition codes and optimal/perfect difference systems of sets, with their parameters summarized in Tables II and III.

Limitations and Future Work

  • Optimality of DSSs: The paper notes that DSSs constructed from ZDB functions using Lemma 7 are not always optimal unless the condition $\bar{\ell}\lambda \le n$ is met. While Theorems 2 and 3 provide optimal DSSs for all primes $m$ and for $m \ge 11$ respectively, this condition might not hold for all cases.
  • Cyclic Group Restriction for Theorem 1: The ZDB functions from Theorem 1 can only be used to construct DSSs when the group $(GF(p^{m_1}_1) \times \dots \times GF(p^{m_k}_k), +)$ is cyclic, which occurs only when $m_1 = \dots = m_k = 1$.
  • Future Work: The paper implicitly suggests exploring ZDB functions on other algebraic structures and investigating further applications. The emphasis on comprehensive parameter comparison also hints at future work in systematically cataloging and comparing ZDB functions based on all their defining parameters.

Summary updated

Abstract

Zero-difference balanced (ZDB) functions integrate a number of subjects in combinatorics and algebra, and have many applications in coding theory, cryptography, and communications engineering. In this paper, three new families of ZDB functions are presented. The first construction gives ZDB functions defined on the abelian groups (GF( <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q1</sub> )×,...,×GF( <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">qk</sub> ),+) with new and flexible parameters. The other two constructions are based on 2-cyclotomic cosets and yield ZDB functions on \BBZn with new parameters. The parameters of optimal constant composition codes, optimal, and perfect difference systems of sets obtained from these new families of ZDB functions are also summarized.
BibTeX
@article{ding2014three,
  author = {Cunsheng Ding and Qi Wang and Maosheng Xiong},
  title = {{Three New Families of Zero-Difference Balanced Functions With Applications}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  url = {https://openreview.net/forum?id=lIhD7HdPgjH},
}
Figure