Abstract
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 Nasr Esfahani et al. (IEEE Trans Inf Theory 64:3136–3143, 2018) 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bose R.C., Shrikhande S.S., Parker E.T.: Further results on the construction of mutually orthogonal latin squares and the falsity of Euler’s conjecture. Can. J. Math. 12, 189–203 (1960).
D’Arco P., Nasr Esfahani N., Stinson D.R.: All or nothing at all. Electron. J. Combin. 23(4), paper P4.10 (2016).
Great Internet Mersenne Prime Search. https://www.mersenne.org. Accessed 8 April 2018.
Huffman W.C., Pless V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003).
Nasr Esfahani N., Stinson D.R.: Computational results on invertible matrices with the maximum number of invertible \(2\)-by-\(2\) submatrices. Aust. J. Comb. 69, 130–144 (2017).
Nasr Esfahani N., Goldberg I., Stinson D.R.: Some results on the existence of t-all-or-nothing transforms over arbitrary alphabets. IEEE Trans. Inf. Theory 64, 3136–3143 (2018).
Rivest R.L.: All-or-nothing encryption and the package transform. Fast Software Encryption (Lecture Notes in Computer Science) 1267, 210–218 (1997).
Stinson D.R.: Something about all or nothing (transforms). Des. Codes Cryptogr. 22, 133–138 (2001).
Zhang Y., Zhang T., Wang X., Ge G.: Invertible binary matrices with maximum number of \(2\)-by-\(2\) inverible submatrices. Discret. Math. 340, 201–208 (2017).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by J. Bierbrauer.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Xin Wang was supported by the National Natural Science Foundation of China (Grant No. 11801392), the Natural Science Foundation of Jiangsu Province (Grant No. BK20180833) and the Post-Doctoral Science Foundation of China (Grant No. 2018M632356). Lijun Ji was supported by the National Natural Science Foundation of China (Grant No. 11871363 and 11431003).
Rights and permissions
About this article
Cite this article
Wang, X., Cui, J. & Ji, L. Linear (2, p, p)-AONTs exist for all primes p. Des. Codes Cryptogr. 87, 2185–2197 (2019). https://doi.org/10.1007/s10623-019-00612-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-019-00612-1