Linear $(2,p,p)$-AONTs do Exist
This addresses theoretical gaps in coding theory and cryptography by advancing the understanding of AONT constructions, though it is incremental in nature.
The paper solves three open problems by proving the existence of linear (2,p,p)-all-or-nothing transforms (AONTs), and introduces an infinite class of linear AONTs for prime power alphabets that outperforms those based on Cauchy matrices.
A $(t,s,v)$-all-or-nothing transform (AONT) is a bijective mapping defined on $s$-tuples over an alphabet of size $v$, which satisfies that if any $s-t$ of the $s$ outputs are given, then the values of any $t$ inputs are completely undetermined. When $t$ and $v$ are fixed, to determine the maximum integer $s$ such that a $(t,s,v)$-AONT exists is the main research objective. In this paper, we solve three open problems proposed in [IEEE Trans. Inform. Theory 64 (2018), 3136-3143.] and show that there do exist linear $(2,p,p)$-AONTs. Then for the size of the alphabet being a prime power, we give the first infinite class of linear AONTs which is better than the linear AONTs defined by Cauchy matrices. Besides, we also present a recursive construction for general AONTs and a new relationship between AONTs and orthogonal arrays.