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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

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

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

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

[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.  Google Scholar

[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.  Google Scholar

[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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Yang Cao, Song Shao. Topological mild mixing of all orders along polynomials. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021150

[15]

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

[16]

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

[17]

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

[18]

Sze-Bi Hsu, Chiu-Ju Lin. Dynamics of two phytoplankton species competing for light and nutrient with internal storage. Discrete & Continuous Dynamical Systems - S, 2014, 7 (6) : 1259-1285. doi: 10.3934/dcdss.2014.7.1259

[19]

Lisa C Flatley, Robert S MacKay, Michael Waterson. Optimal strategies for operating energy storage in an arbitrage or smoothing market. Journal of Dynamics & Games, 2016, 3 (4) : 371-398. doi: 10.3934/jdg.2016020

[20]

Patrice Bertail, Stéphan Clémençon, Jessica Tressou. A storage model with random release rate for modeling exposure to food contaminants. Mathematical Biosciences & Engineering, 2008, 5 (1) : 35-60. doi: 10.3934/mbe.2008.5.35

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (24)
  • HTML views (25)
  • Cited by (0)

Other articles
by authors

[Back to Top]