doi: 10.3934/amc.2021068
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Rectangular, range, and restricted AONTs: Three generalizations of all-or-nothing transforms

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

* D.R. Stinson's research is supported by NSERC discovery grant RGPIN-03882

Received  November 2021 Early access January 2022

All-or-nothing transforms (AONTs) were originally defined by Rivest [14] as bijections from $ s $ input blocks to $ s $ output blocks such that no information can be obtained about any input block in the absence of any output block. Numerous generalizations and extensions of all-or-nothing transforms have been discussed in recent years, many of which are motivated by diverse applications in cryptography, information security, secure distributed storage, etc. In particular, $ t $-AONTs, in which no information can be obtained about any $ t $ input blocks in the absence of any $ t $ output blocks, have received considerable study.

In this paper, we study three generalizations of AONTs that are motivated by applications due to Pham et al. [13] and Oliveira et al. [12]. We term these generalizations rectangular, range, and restricted AONTs. Briefly, in a rectangular AONT, the number of outputs is greater than the number of inputs. A range AONT satisfies the $ t $-AONT property for a range of consecutive values of $ t $. Finally, in a restricted AONT, the unknown outputs are assumed to occur within a specified set of "secure" output blocks. We study existence and non-existence and provide examples and constructions for these generalizations. We also demonstrate interesting connections with combinatorial structures such as orthogonal arrays, split orthogonal arrays, MDS codes and difference matrices.

Citation: Navid Nasr Esfahani, Douglas R. Stinson. Rectangular, range, and restricted AONTs: Three generalizations of all-or-nothing transforms. Advances in Mathematics of Communications, doi: 10.3934/amc.2021068
References:
[1]

C. J. Colbourn and J. H. Dinitz, eds, The CRC Handbook of Combinatorial Designs, Second Edition, CRC Press, 1996. doi: 10.1201/9781420049954.

[2]

P. D'Arco, N. Nasr Esfahani and D. R. Stinson, All or nothing at all, Electronic Journal of Combinatorics, 23 (2016), paper 4.10, 24 pp. doi: 10.37236/6370.

[3]

D. A. Drake, Partial λ-geometries and generalized Hadamard matrices over groups, Canadian Journal of Mathematics, 31 (1979), 617-727.  doi: 10.4153/CJM-1979-062-1.

[4]

N. N. Esfahani, Generalizations of All-or-nothing Transforms and Their Application in Secure Distributed Storage, PhD thesis, University of Waterloo, 2021.

[5]

N. N. EsfahaniI. Goldberg and D. R. Stinson, Some results on the existence of t-all-or-nothing transforms over arbitrary alphabets, IEEE Transactions on Information Theory, 64 (2018), 3136-3143.  doi: 10.1109/TIT.2017.2780233.

[6]

N. N. Esfahani and D. R. Stinson, Computational results on invertible matrices with the maximum number of invertible 2 × 2 submatrices, Australasian Journal of Combinatorics, 69 (2017), 130-144. 

[7]

N. N. Esfahani and D. R. Stinson, On security properties of all-or-nothing transforms, Designs, Codes and Cryptography, 91 (2021), 2857-2867.  doi: 10.1007/s10623-021-00958-5.

[8]

N. N. Esfahani and D. R. Stinson, Asymmetric all-or-nothing transforms, To appear in Mathematical Cryptology.

[9]

G. O. KarameC. SorienteK. Lichota and S. Capkun, Securing cloud data under key exposure, IEEE Transactions on Cloud Computing, 7 (2019), 838-849.  doi: 10.1109/TCC.2017.2670559.

[10]

V. I. Levenshtein, Split orthogonal arrays and maximum independent resilient systems of functions, Designs, Codes and Cryptography, 12 (1997), 131-160.  doi: 10.1023/A:1008207230165.

[11]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[12]

P. F. OliveiraL. LimaT. T. VinhozaJ. Barros and M. Médard, Coding for trusted storage in untrusted networks, IEEE Transactions on Information Forensics and Security, 7 (2012), 1890-1899.  doi: 10.1109/TIFS.2012.2217331.

[13]

H. PhamR. Steinwandt and A. Suárez Corona, Integrating classical preprocessing into an optical encryption scheme, Entropy, 21 (2019), 872.  doi: 10.3390/e21090872.

[14]

R. L. Rivest, All-or-nothing encryption and the package transform, Lecture Notes in Computer Science, (Fast Software Encryption 1997), 1267 (1997), 210–218. doi: 10.1007/BFb0052348.

[15]

D. R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer-Verlag, New York, 2004.

[16]

D. R. Stinson, Something about all or nothing (transforms), Designs, Codes and Cryptography, 22 (2001), 133-138.  doi: 10.1023/A:1008304703074.

[17]

X. WangJ. Cui and L. Ji, Linear (2, p, p)-AONTs exist for all primes p, Designs, Codes and Cryptography, 87 (2019), 2185-2197.  doi: 10.1007/s10623-019-00612-1.

[18]

Y. Zhang, T. Zhang, X. Wang and G. Ge, Invertible binary matrices with maximum number of 2-by-2 invertible submatrices, Discrete Mathematics, 340 (2017) 201–208. doi: 10.1016/j.disc.2016.08.016.

show all references

References:
[1]

C. J. Colbourn and J. H. Dinitz, eds, The CRC Handbook of Combinatorial Designs, Second Edition, CRC Press, 1996. doi: 10.1201/9781420049954.

[2]

P. D'Arco, N. Nasr Esfahani and D. R. Stinson, All or nothing at all, Electronic Journal of Combinatorics, 23 (2016), paper 4.10, 24 pp. doi: 10.37236/6370.

[3]

D. A. Drake, Partial λ-geometries and generalized Hadamard matrices over groups, Canadian Journal of Mathematics, 31 (1979), 617-727.  doi: 10.4153/CJM-1979-062-1.

[4]

N. N. Esfahani, Generalizations of All-or-nothing Transforms and Their Application in Secure Distributed Storage, PhD thesis, University of Waterloo, 2021.

[5]

N. N. EsfahaniI. Goldberg and D. R. Stinson, Some results on the existence of t-all-or-nothing transforms over arbitrary alphabets, IEEE Transactions on Information Theory, 64 (2018), 3136-3143.  doi: 10.1109/TIT.2017.2780233.

[6]

N. N. Esfahani and D. R. Stinson, Computational results on invertible matrices with the maximum number of invertible 2 × 2 submatrices, Australasian Journal of Combinatorics, 69 (2017), 130-144. 

[7]

N. N. Esfahani and D. R. Stinson, On security properties of all-or-nothing transforms, Designs, Codes and Cryptography, 91 (2021), 2857-2867.  doi: 10.1007/s10623-021-00958-5.

[8]

N. N. Esfahani and D. R. Stinson, Asymmetric all-or-nothing transforms, To appear in Mathematical Cryptology.

[9]

G. O. KarameC. SorienteK. Lichota and S. Capkun, Securing cloud data under key exposure, IEEE Transactions on Cloud Computing, 7 (2019), 838-849.  doi: 10.1109/TCC.2017.2670559.

[10]

V. I. Levenshtein, Split orthogonal arrays and maximum independent resilient systems of functions, Designs, Codes and Cryptography, 12 (1997), 131-160.  doi: 10.1023/A:1008207230165.

[11]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[12]

P. F. OliveiraL. LimaT. T. VinhozaJ. Barros and M. Médard, Coding for trusted storage in untrusted networks, IEEE Transactions on Information Forensics and Security, 7 (2012), 1890-1899.  doi: 10.1109/TIFS.2012.2217331.

[13]

H. PhamR. Steinwandt and A. Suárez Corona, Integrating classical preprocessing into an optical encryption scheme, Entropy, 21 (2019), 872.  doi: 10.3390/e21090872.

[14]

R. L. Rivest, All-or-nothing encryption and the package transform, Lecture Notes in Computer Science, (Fast Software Encryption 1997), 1267 (1997), 210–218. doi: 10.1007/BFb0052348.

[15]

D. R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer-Verlag, New York, 2004.

[16]

D. R. Stinson, Something about all or nothing (transforms), Designs, Codes and Cryptography, 22 (2001), 133-138.  doi: 10.1023/A:1008304703074.

[17]

X. WangJ. Cui and L. Ji, Linear (2, p, p)-AONTs exist for all primes p, Designs, Codes and Cryptography, 87 (2019), 2185-2197.  doi: 10.1007/s10623-019-00612-1.

[18]

Y. Zhang, T. Zhang, X. Wang and G. Ge, Invertible binary matrices with maximum number of 2-by-2 invertible submatrices, Discrete Mathematics, 340 (2017) 201–208. doi: 10.1016/j.disc.2016.08.016.

[1]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024

[2]

Ruijing Liu, Junling Zhou. Optimal data placements for triple replication in distributed storage systems. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022037

[3]

Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028

[4]

Shiqiu Liu, Frédérique Oggier. On applications of orbit codes to storage. Advances in Mathematics of Communications, 2016, 10 (1) : 113-130. doi: 10.3934/amc.2016.10.113

[5]

Bingsheng Shen, Yang Yang, Ruibin Ren. Three constructions of Golay complementary array sets. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022019

[6]

Leonid Berlyand, Giuseppe Cardone, Yuliya Gorb, Gregory Panasenko. Asymptotic analysis of an array of closely spaced absolutely conductive inclusions. Networks and Heterogeneous Media, 2006, 1 (3) : 353-377. doi: 10.3934/nhm.2006.1.353

[7]

Masayuki Sato, Naoki Fujita, A. J. Sievers. Logic operations demonstrated with localized vibrations in a micromechanical cantilever array. Discrete and Continuous Dynamical Systems - S, 2011, 4 (5) : 1287-1298. doi: 10.3934/dcdss.2011.4.1287

[8]

Samuel T. Blake, Andrew Z. Tirkel. A multi-dimensional block-circulant perfect array construction. Advances in Mathematics of Communications, 2017, 11 (2) : 367-371. doi: 10.3934/amc.2017030

[9]

Fuhito Kojima. Finding all stable matchings with couples. Journal of Dynamics and Games, 2015, 2 (3&4) : 321-330. doi: 10.3934/jdg.2015008

[10]

Guangzhou Chen, Xiaotong Zhang. Constructions of irredundant orthogonal arrays. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021051

[11]

Tomáš Roubíček, Giuseppe Tomassetti. Thermomechanics of hydrogen storage in metallic hydrides: Modeling and analysis. Discrete and Continuous Dynamical Systems - B, 2014, 19 (7) : 2313-2333. doi: 10.3934/dcdsb.2014.19.2313

[12]

Phil Howlett, Julia Piantadosi, Paraskevi Thomas. Management of water storage in two connected dams. Journal of Industrial and Management Optimization, 2007, 3 (2) : 279-292. doi: 10.3934/jimo.2007.3.279

[13]

Lei Deng, Jingjie Zhao, Ruimei Wang. Modelling and performance analysis of shuttle-based compact storage systems under different storage policies. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022080

[14]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026

[15]

Palle E. T. Jorgensen and Steen Pedersen. Orthogonal harmonic analysis of fractal measures. Electronic Research Announcements, 1998, 4: 35-42.

[16]

Piotr Oprocha. Double minimality, entropy and disjointness with all minimal systems. Discrete and Continuous Dynamical Systems, 2019, 39 (1) : 263-275. doi: 10.3934/dcds.2019011

[17]

Julian Newman. Synchronisation of almost all trajectories of a random dynamical system. Discrete and Continuous Dynamical Systems, 2020, 40 (7) : 4163-4177. doi: 10.3934/dcds.2020176

[18]

Robert W. Ghrist. Flows on $S^3$ supporting all links as orbits. Electronic Research Announcements, 1995, 1: 91-97.

[19]

Yang Cao, Song Shao. Topological mild mixing of all orders along polynomials. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1163-1184. doi: 10.3934/dcds.2021150

[20]

Sze-Bi Hsu, Junping Shi, Feng-Bin Wang. Further studies of a reaction-diffusion system for an unstirred chemostat with internal storage. Discrete and Continuous Dynamical Systems - B, 2014, 19 (10) : 3169-3189. doi: 10.3934/dcdsb.2014.19.3169

2021 Impact Factor: 1.015

Article outline

[Back to Top]