On circular external difference families
Pith reviewed 2026-05-18 19:07 UTC · model grok-4.3
The pith
Cyclic circular external difference families can be constructed for every odd number of blocks when each block has size two, and for three blocks of even size.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We construct cyclic (v,m,2,1)-CEDFs for every odd m>1. We present two different ways to do so based on arithmetic progressions whose step patterns ensure the circular differences cover every nonzero element exactly once. We also construct cyclic (v,3,ℓ,1)-CEDFs for every even ℓ≥2 by relying on the existence of a suitable tiling of the multiplicative semigroup of Z_v excluding zero.
What carries the argument
Arithmetic progressions with chosen step patterns in the cyclic group Z_v, which generate the required multiset of external differences in a circular sequence of blocks.
If this is right
- Provides constructions for all odd m with ℓ=2, extending beyond the known even m cases.
- Shows that different step patterns yield inequivalent CEDFs.
- Additional families arise from translating subsets within the constructed CEDF.
- For m=3 and even ℓ, existence follows from suitable tilings of the multiplicative semigroup.
- The nonexistence for both odd m and odd ℓ remains as previously known.
Where Pith is reading between the lines
- These constructions might be generalized to other values of m and ℓ by finding appropriate tilings or patterns.
- Applications in cryptography could benefit from the explicit nature of these arithmetic progression based families.
- Further research could seek to prove the existence of the required tilings for all suitable v.
- Similar techniques may apply to other variants of difference families in group theory.
Load-bearing premise
The specific step patterns for the arithmetic progressions must generate differences that exactly cover the multiset of all nonzero group elements without any overlaps or omissions.
What would settle it
A direct computation for a small odd m, such as m=3 and v=13 with ℓ=2, checking whether the constructed blocks produce exactly one occurrence of each nonzero difference in the circular manner.
read the original abstract
Circular external difference families (CEDFs) are a recently-introduced variation of external difference families with applications to non-malleable threshold schemes: a $(v,m,\ell,1)$-CEDF is an $m$-sequence $(A_0, \ldots, 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'$, with $(a,a')\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\}$. 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript constructs cyclic (v,m,2,1)-CEDFs for every odd m>1 via two distinct arithmetic-progression representations whose step patterns are analyzed to verify the external-difference multiset condition; it further constructs cyclic (v,3,ℓ,1)-CEDFs for every even ℓ≥2 by representing blocks as arithmetic progressions whose steps are governed by a tiling of the multiplicative semigroup of ℤ_v∖{0}. The two families for odd m are shown to be inequivalent, and further inequivalent examples are obtained by translating subsets. The work addresses the open case of odd m with even ℓ that was previously resolved only in special instances.
Significance. If the step-pattern verification and the tiling hypothesis are confirmed, the constructions supply explicit, infinite families that close a documented gap in the existence theory of cyclic CEDFs and furnish concrete objects for applications in non-malleable threshold schemes. The arithmetic-progression approach yields parameter-free descriptions once the tiling is granted, which is a methodological strength.
major comments (2)
- [§4] §4 (m=3 constructions): the universal claim that cyclic (v,3,ℓ,1)-CEDFs exist for every even ℓ≥2 is stated as relying on the existence of a suitable tiling of the multiplicative semigroup of ℤ_v∖{0}, yet no existence proof, explicit construction, or verification that the tiling produces a difference multiset covering G∖{0} without overlaps is supplied for arbitrary even ℓ and admissible v. This renders the result conditional on an auxiliary combinatorial statement whose scope is not established in the manuscript.
- [§3.2] §3.2 (step-pattern analysis for odd m): the verification that the external differences exactly partition G∖{0} as a multiset is carried out only for the two base constructions; it is not shown that the additional translated families obtained by moving subsets inside the CEDF preserve the covering property for all admissible translations.
minor comments (2)
- Notation for the cyclic group and the sequence indexing should be made uniform between the abstract and the body (e.g., consistent use of ℤ_v versus ℤ/vℤ).
- Figure captions for the step-pattern diagrams should explicitly label the arithmetic-progression parameters (common difference and length) to facilitate direct comparison with the textual definitions.
Simulated Author's Rebuttal
We thank the referee for their thorough review and valuable comments on our manuscript concerning cyclic external difference families. We address each of the major comments in detail below and outline the revisions we plan to make.
read point-by-point responses
-
Referee: [§4] §4 (m=3 constructions): the universal claim that cyclic (v,3,ℓ,1)-CEDFs exist for every even ℓ≥2 is stated as relying on the existence of a suitable tiling of the multiplicative semigroup of ℤ_v∖{0}, yet no existence proof, explicit construction, or verification that the tiling produces a difference multiset covering G∖{0} without overlaps is supplied for arbitrary even ℓ and admissible v. This renders the result conditional on an auxiliary combinatorial statement whose scope is not established in the manuscript.
Authors: We acknowledge that the manuscript presents the construction for m=3 as depending on the existence of such a tiling without providing a general existence proof or explicit verification for all even ℓ. This is a valid observation. In the revised version, we will include an explicit construction of the tiling of the multiplicative semigroup ℤ_v ∖ {0} for even ℓ, based on partitioning into suitable subsets that correspond to the arithmetic progressions in the blocks. We will verify that this tiling ensures the external differences cover G ∖ {0} exactly once as a multiset, for admissible v (such as when v is odd and sufficiently large). This will remove the conditional aspect and make the result unconditional. revision: yes
-
Referee: [§3.2] §3.2 (step-pattern analysis for odd m): the verification that the external differences exactly partition G∖{0} as a multiset is carried out only for the two base constructions; it is not shown that the additional translated families obtained by moving subsets inside the CEDF preserve the covering property for all admissible translations.
Authors: The step-pattern analysis confirms the property for the two inequivalent base constructions. Regarding the translated families, translating a subset by a fixed element preserves all differences within and between blocks because the difference a - b remains unchanged under simultaneous translation of a and b. However, when translating only certain subsets, care must be taken to maintain the overall structure. We agree that this preservation needs explicit verification. In the revision, we will add a paragraph in §3.2 demonstrating that for admissible translations (those that result in distinct blocks and maintain the arithmetic progression property where applicable), the multiset of external differences remains a partition of G ∖ {0}. This will be shown by noting the invariance of differences under translation. revision: yes
Circularity Check
No circularity: constructions are explicit and independent
full rationale
The paper supplies direct combinatorial constructions of the claimed cyclic CEDFs by representing blocks as arithmetic progressions whose step patterns are chosen to produce the required external difference multiset. For odd m and ℓ=2 the two inequivalent families are built explicitly; for m=3 and even ℓ the argument conditions on the existence of an auxiliary tiling of the multiplicative semigroup but does not define the CEDF or its difference covering in terms of that tiling (or vice versa). No equation reduces to a fitted parameter renamed as prediction, no self-citation is load-bearing for the central claim, and no uniqueness theorem or ansatz is smuggled from prior author work. The derivation chain therefore remains self-contained against external combinatorial verification.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math The additive group G is cyclic of order v and the differences are taken in the usual way.
- ad hoc to paper A suitable tiling of the multiplicative semigroup of Z_v excluding zero exists for the chosen v when m=3.
Reference graph
Works this paper leans on
-
[1]
M. Buratti, L. Gionfriddo, Strong difference families over arbitrary graphs, J. Combin. Des. 16 (2008), 443–461
work page 2008
-
[2]
R. Cramer, Y. Dodis, S. Fehr, C. Padr´ o, D. Wichs, Detection of Al- gebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors. In: N. Smart, (eds) Advances in Cryptology – EURO- CRYPT 2008. Lecture Notes in Computer Science, vol 4965. Springer, Berlin, Heidelberg
work page 2008
-
[3]
S. Huczynska, M.B. Paterson, Decomposing complete graphs into iso- morphic complete multipartite graphs, in New Advances in Designs, Codes and Cryptography , Fields Institute Communications, Eds C.J. Coulbourn and J.H. Dinitz, Springer, 2024
work page 2024
-
[4]
S. Huczynska, C. Jefferson, S. McCartney, Digraph-defined exter- nal difference families and new circular external difference families, http://arxiv.org/abs/2504.20959v1. 14
- [5]
- [6]
-
[7]
M.B. Paterson, D.R. Stinson, Combinatorial characterizations of al- gebraic manipulation detection codes involving generalized difference familes, Discrete Math. 275 (2016), 2891–2906
work page 2016
-
[8]
M.B. Paterson, D.R. Stinson, Circular external difference families, grace- ful labellings and cyclotomy, Discrete Math. 347 (2024), 114103
work page 2024
-
[9]
S. Veitch, D.R. Stinson, Unconditionally secure non-malleable secret sharing, Des. Codes Cryptogr. 92 (2024), 941–956
work page 2024
-
[10]
H. Wu, J. Yang, K. Feng, Circular external difference families: construc- tion and non-existence, Des. Codes Cryptogr. 92 (2024), 3377–3390. 15
work page 2024
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.