On circular external difference families

Abstract

Circular external difference families (CEDFs) are a recently-introduced variation of external difference families (EDFs) with applications to non-malleable threshold schemes: a $(v,m,\ell ,1)$-CEDF is an $m$-sequence $(A_0,\dots ,A_{m-1})$ of $\ell$-subsets of an additive group $G$ of order $v$ such that $G\setminus \{0\}$ equals the multiset of all differences $a-a^{\prime }$, with $(a,a^{\prime })\in A_{i+1}\times A_i$ for some $i\in {\mathbb{Z}}_m$. When $G$ is the cyclic group, we speak of a cyclic CEDF. The existence of cyclic $(v,m,\ell ,1)$-CEDFs is well understood when $m$ is even, while nonexistence is known when both $m$ and $\ell$ are odd. However, the case where $m$ is odd and $\ell$ is even has only been resolved in a few special cases. In this paper, we address this gap by constructing cyclic $(v,m,\ell ,1)$-CEDFs for any odd $m>1$ when $\ell =2$, and for any even $\ell \ge 2$ when $m=3$. Notably, the latter result relies on the existence of a suitable tiling of the multiplicative semigroup of ${\mathbb{Z}}_v\setminus \{0\}$. Moreover, noting that every $(v,3,\ell ,1)$-CEDF produces a $(v,3,\ell ,2)$-EDF, we completely solve the existence problem for $(3{\ell }^2+1,3,\ell ,2)$-EDFs over an abelian group. Our approach is based on representing the blocks as arithmetic progressions and analyzing their step patterns. We present two different ways to construct cyclic $(v,m,2,1)$-CEDFs for every odd $m>1$; their step patterns show that the resulting CEDFs are inequivalent. Many additional inequivalent CEDFs are obtained by translating suitable subsets within the CEDF.

28 pages