American Institute of Mathematical Sciences

doi: 10.3934/amc.2021017
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.

On ideal and weakly-ideal access structures

 Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran

* Corresponding author

Received  October 2020 Revised  April 2021 Early access June 2021

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.

Citation: Reza Kaboli, Shahram Khazaei, Maghsoud Parviz. On ideal and weakly-ideal access structures. Advances in Mathematics of Communications, doi: 10.3934/amc.2021017
References:
 [1] M. Bamiloshin, A. Ben-Efraim, O. Farràs and C. Padró, Common information, matroid representation, and secret sharing for matroid ports, CoRR, (2020), abs/2002.08108. doi: 10.1007/s10623-020-00811-1. [2] A. Beimel, Secret-sharing schemes: A survey, in International Conference on Coding and Cryptology, Springer, 2011, 11–46. doi: 10.1007/978-3-642-20901-7_2. [3] A. Beimel, A. Ben-Efraim, C. Padró and I. Tyomkin, Multi-linear secret-sharing schemes, in Theory of Cryptography Conference, Springer, 2014,394–418. doi: 10.1007/978-3-642-54242-8_17. [4] A. Beimel and B. Chor, Universally ideal secret-sharing schemes, IEEE Transactions on Information Theory, 40 (1994), 786-794.  doi: 10.1109/18.335890. [5] A. Beimel and Y. Ishai, On the power of nonlinear secret-sharing, in Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, 2001,188–202. [6] A. Beimel and N. Livne, On matroids and nonideal secret sharing, IEEE Trans. Information Theory, 54 (2008), 2626–2643. doi: 10.1109/TIT.2008.921708. [7] A. Beimel and N. Livne, On matroids and nonideal secret sharing, IEEE Transactions on Information Theory, 54 (2008), 2626-2643.  doi: 10.1109/TIT.2008.921708. [8] M. Bertilsson and I. Ingemarsson, A construction of practical secret sharing schemes using linear block codes, in Advances in Cryptology - AUSCRYPT '92, Workshop on the Theory and Application of Cryptographic Techniques, Gold Coast, Queensland, Australia, December 13-16, 1992, Proceedings, 1992, 67–79. [9] G. R. Blakley, Safeguarding cryptographic keys, Proc. of the National Computer Conference 1979, 48 (1979), 313-317. [10] E. F. Brickell and D. M. Davenport, On the classification of ideal secret sharing schemes, J. Cryptology, 4 (1991), 123-134.  doi: 10.1007/0-387-34805-0_25. [11] H.-L. Chan and R. W. Yeung, A combinatorial approach to information inequalities, in 1999 Information Theory and Networking Workshop (Cat. No. 99EX371), IEEE, 1999, 63. [12] T. Chan and A. J. Grant, Dualities between entropy functions and network codes, IEEE Trans. Information Theory, 54 (2008), 4470–4487. doi: 10.1109/TIT.2008.928963. [13] T. H. Chan, A. Grant and T. Britz, Properties of quasi-uniform codes, in 2010 IEEE International Symposium on Information Theory, IEEE, 2010, 1153–1157. [14] T. H. Chan and R. W. Yeung, On a relation between information inequalities and group theory, IEEE Trans. Information Theory, 48 (2002), 1992–1995. doi: 10.1109/TIT.2002.1013138. [15] L. Csirmaz, Secret sharing and duality, CoRR, abs/1909.13663, 2019. doi: 10.1515/jmc-2019-0045. [16] P. Gács and J. Körner, Common information is far less than mutual information, Problems of Control and Information Theory, 2 (1973), 149-162. [17] J. Gallian, Contemporary Abstract Algebra, Nelson Education, 2012. [18] L. Guille, T. Chan and A. J. Grant, The minimal set of ingleton inequalities, IEEE Trans. Information Theory, 57 (2011), 1849–1864. doi: 10.1109/TIT.2011.2111890. [19] P. Hall, Complemented groups, Journal of the London Mathematical Society, 1 (1937), 201-204.  doi: 10.1112/jlms/s1-12.2.201. [20] M. Ito, A. Saito and T. Nishizeki, Secret sharing scheme realizing general access structure, Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 72 (1989), 56-64.  doi: 10.1002/ecjc.4430720906. [21] A. Jafari and S. Khazaei, On abelian and homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/575, 2019. [22] A. Jafari and S. Khazaei, Partial secret sharing schemes, Cryptology ePrint Archive, Report 2020/448, 2020. [23] R. Kaboli, S. Khazaei and M. Parviz, On group-characterizability of homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/576, 2019. [24] T. Kaced, Almost-perfect secret sharing, in 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011, St. Petersburg, Russia, July 31 - August 5, 2011, 2011, 1603–1607. [25] T. Kaced, Secret Sharing and Algorithmic Information Theory. (Partage de Secret et The'orie Algorithmique de L'information), Ph.D thesis, Montpellier 2 University, France, 2012. [26] M. Karchmer and A. Wigderson, On span programs, in Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, 1993,102–111. doi: 10.1109/SCT.1993.336536. [27] E. Karnin, J. Greene and M. Hellman, On secret sharing systems, IEEE Transactions on Information Theory, 29 (1983), 35–41, 1983. doi: 10.1109/TIT.1983.1056621. [28] A. D. Keedwell and J. Dénes, Latin Squares and their Applications, Elsevier, 2015. [29] F. Matúš, Algebraic matroids are almost entropic, Proceedings of the AMS, to appear. [30] F. Matúš, Matroid representations by partitions, Discrete Mathematics, 203 (1999), 169-194.  doi: 10.1016/S0012-365X(99)00004-7. [31] F. Matús, Classes of matroids closed under minors and principal extensions, Combinatorica, 38 (2018), 935-954.  doi: 10.1007/s00493-017-3534-y. [32] B. D. McKay and I. M. Wanless, On the number of latin squares, Annals of Combinatorics, 9 (2005), 335-344.  doi: 10.1007/s00026-005-0261-7. [33] C. Mejia and J. A. Montoya, On the information rates of homomorphic secret sharing schemes, Journal of Information and Optimization Sciences, 39 (2018), 1463-1482.  doi: 10.1080/02522667.2017.1367513. [34] J. G. Oxley, Matroid theory, 3, Oxford University Press, USA, 2006. doi: 10.1093/acprof:oso/9780198566946.001.0001. [35] C. Padró, Lecture notes in secret sharing, IACR Cryptology ePrint Archive, 674 (2012). [36] P. D. Seymour, On secret-sharing matroids, J. Comb. Theory, Ser. B, 56 (1992), 69–73. doi: 10.1016/0095-8956(92)90007-K. [37] A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176. [38] J. Simonis and A. E. Ashikhmin, Almost affine codes, Des. Codes Cryptogr., 14 (1998), 179-197.  doi: 10.1023/A:1008244215660. [39] F. Wei, M. Langberg and M. Effros, Towards an operational definition of group network codes, CoRR, abs/2002.00781, 2020. [40] Z. Zhang and R. W. Yeung, On characterization of entropy function via information inequalities, IEEE Trans. Information Theory, 44 (1998), 1440–1452. doi: 10.1109/18.681320.

show all references

References:
 [1] M. Bamiloshin, A. Ben-Efraim, O. Farràs and C. Padró, Common information, matroid representation, and secret sharing for matroid ports, CoRR, (2020), abs/2002.08108. doi: 10.1007/s10623-020-00811-1. [2] A. Beimel, Secret-sharing schemes: A survey, in International Conference on Coding and Cryptology, Springer, 2011, 11–46. doi: 10.1007/978-3-642-20901-7_2. [3] A. Beimel, A. Ben-Efraim, C. Padró and I. Tyomkin, Multi-linear secret-sharing schemes, in Theory of Cryptography Conference, Springer, 2014,394–418. doi: 10.1007/978-3-642-54242-8_17. [4] A. Beimel and B. Chor, Universally ideal secret-sharing schemes, IEEE Transactions on Information Theory, 40 (1994), 786-794.  doi: 10.1109/18.335890. [5] A. Beimel and Y. Ishai, On the power of nonlinear secret-sharing, in Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, 2001,188–202. [6] A. Beimel and N. Livne, On matroids and nonideal secret sharing, IEEE Trans. Information Theory, 54 (2008), 2626–2643. doi: 10.1109/TIT.2008.921708. [7] A. Beimel and N. Livne, On matroids and nonideal secret sharing, IEEE Transactions on Information Theory, 54 (2008), 2626-2643.  doi: 10.1109/TIT.2008.921708. [8] M. Bertilsson and I. Ingemarsson, A construction of practical secret sharing schemes using linear block codes, in Advances in Cryptology - AUSCRYPT '92, Workshop on the Theory and Application of Cryptographic Techniques, Gold Coast, Queensland, Australia, December 13-16, 1992, Proceedings, 1992, 67–79. [9] G. R. Blakley, Safeguarding cryptographic keys, Proc. of the National Computer Conference 1979, 48 (1979), 313-317. [10] E. F. Brickell and D. M. Davenport, On the classification of ideal secret sharing schemes, J. Cryptology, 4 (1991), 123-134.  doi: 10.1007/0-387-34805-0_25. [11] H.-L. Chan and R. W. Yeung, A combinatorial approach to information inequalities, in 1999 Information Theory and Networking Workshop (Cat. No. 99EX371), IEEE, 1999, 63. [12] T. Chan and A. J. Grant, Dualities between entropy functions and network codes, IEEE Trans. Information Theory, 54 (2008), 4470–4487. doi: 10.1109/TIT.2008.928963. [13] T. H. Chan, A. Grant and T. Britz, Properties of quasi-uniform codes, in 2010 IEEE International Symposium on Information Theory, IEEE, 2010, 1153–1157. [14] T. H. Chan and R. W. Yeung, On a relation between information inequalities and group theory, IEEE Trans. Information Theory, 48 (2002), 1992–1995. doi: 10.1109/TIT.2002.1013138. [15] L. Csirmaz, Secret sharing and duality, CoRR, abs/1909.13663, 2019. doi: 10.1515/jmc-2019-0045. [16] P. Gács and J. Körner, Common information is far less than mutual information, Problems of Control and Information Theory, 2 (1973), 149-162. [17] J. Gallian, Contemporary Abstract Algebra, Nelson Education, 2012. [18] L. Guille, T. Chan and A. J. Grant, The minimal set of ingleton inequalities, IEEE Trans. Information Theory, 57 (2011), 1849–1864. doi: 10.1109/TIT.2011.2111890. [19] P. Hall, Complemented groups, Journal of the London Mathematical Society, 1 (1937), 201-204.  doi: 10.1112/jlms/s1-12.2.201. [20] M. Ito, A. Saito and T. Nishizeki, Secret sharing scheme realizing general access structure, Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 72 (1989), 56-64.  doi: 10.1002/ecjc.4430720906. [21] A. Jafari and S. Khazaei, On abelian and homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/575, 2019. [22] A. Jafari and S. Khazaei, Partial secret sharing schemes, Cryptology ePrint Archive, Report 2020/448, 2020. [23] R. Kaboli, S. Khazaei and M. Parviz, On group-characterizability of homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/576, 2019. [24] T. Kaced, Almost-perfect secret sharing, in 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011, St. Petersburg, Russia, July 31 - August 5, 2011, 2011, 1603–1607. [25] T. Kaced, Secret Sharing and Algorithmic Information Theory. (Partage de Secret et The'orie Algorithmique de L'information), Ph.D thesis, Montpellier 2 University, France, 2012. [26] M. Karchmer and A. Wigderson, On span programs, in Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, 1993,102–111. doi: 10.1109/SCT.1993.336536. [27] E. Karnin, J. Greene and M. Hellman, On secret sharing systems, IEEE Transactions on Information Theory, 29 (1983), 35–41, 1983. doi: 10.1109/TIT.1983.1056621. [28] A. D. Keedwell and J. Dénes, Latin Squares and their Applications, Elsevier, 2015. [29] F. Matúš, Algebraic matroids are almost entropic, Proceedings of the AMS, to appear. [30] F. Matúš, Matroid representations by partitions, Discrete Mathematics, 203 (1999), 169-194.  doi: 10.1016/S0012-365X(99)00004-7. [31] F. Matús, Classes of matroids closed under minors and principal extensions, Combinatorica, 38 (2018), 935-954.  doi: 10.1007/s00493-017-3534-y. [32] B. D. McKay and I. M. Wanless, On the number of latin squares, Annals of Combinatorics, 9 (2005), 335-344.  doi: 10.1007/s00026-005-0261-7. [33] C. Mejia and J. A. Montoya, On the information rates of homomorphic secret sharing schemes, Journal of Information and Optimization Sciences, 39 (2018), 1463-1482.  doi: 10.1080/02522667.2017.1367513. [34] J. G. Oxley, Matroid theory, 3, Oxford University Press, USA, 2006. doi: 10.1093/acprof:oso/9780198566946.001.0001. [35] C. Padró, Lecture notes in secret sharing, IACR Cryptology ePrint Archive, 674 (2012). [36] P. D. Seymour, On secret-sharing matroids, J. Comb. Theory, Ser. B, 56 (1992), 69–73. doi: 10.1016/0095-8956(92)90007-K. [37] A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176. [38] J. Simonis and A. E. Ashikhmin, Almost affine codes, Des. Codes Cryptogr., 14 (1998), 179-197.  doi: 10.1023/A:1008244215660. [39] F. Wei, M. Langberg and M. Effros, Towards an operational definition of group network codes, CoRR, abs/2002.00781, 2020. [40] Z. Zhang and R. W. Yeung, On characterization of entropy function via information inequalities, IEEE Trans. Information Theory, 44 (1998), 1440–1452. doi: 10.1109/18.681320.
Summary of answers to the problem of whether every ideal (resp. weakly-ideal) access structure is realizable by an ideal scheme (resp. weakly-ideal family of schemes) from different classes
 Weakly-ideal Ideal Nearly-ideal Stat.-ideal Almost-ideal Quasi-ideal Multi-linear $\text{Unsolved}$ $\text{No}$ $\text{No}$ $\text{No}$ $\text{No}$ GC with normal secret group $\text{Unsolved}$ $\text{Unsolved}$ $\text{Unsolved}$ GC $\text{Unsolved}$ $\text{Unsolved}$ $\text{Unsolved}$ $\text{Unsolved}$ $\text{Yes}$
 Weakly-ideal Ideal Nearly-ideal Stat.-ideal Almost-ideal Quasi-ideal Multi-linear $\text{Unsolved}$ $\text{No}$ $\text{No}$ $\text{No}$ $\text{No}$ GC with normal secret group $\text{Unsolved}$ $\text{Unsolved}$ $\text{Unsolved}$ GC $\text{Unsolved}$ $\text{Unsolved}$ $\text{Unsolved}$ $\text{Unsolved}$ $\text{Yes}$
 [1] Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003 [2] Simon Castle, Norbert Peyerimhoff, Karl Friedrich Siburg. Billiards in ideal hyperbolic polygons. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 893-908. doi: 10.3934/dcds.2011.29.893 [3] King-Yeung Lam, Daniel Munther. Invading the ideal free distribution. Discrete and Continuous Dynamical Systems - B, 2014, 19 (10) : 3219-3244. doi: 10.3934/dcdsb.2014.19.3219 [4] Rodrigo Abarzúa, Nicolas Thériault, Roberto Avanzi, Ismael Soto, Miguel Alfaro. Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates. Advances in Mathematics of Communications, 2010, 4 (2) : 115-139. doi: 10.3934/amc.2010.4.115 [5] Robert Stephen Cantrell, Chris Cosner, Yuan Lou. Evolution of dispersal and the ideal free distribution. Mathematical Biosciences & Engineering, 2010, 7 (1) : 17-36. doi: 10.3934/mbe.2010.7.17 [6] Bagher Bagherpour, Shahrooz Janbaz, Ali Zaghian. Optimal information ratio of secret sharing schemes on Dutch windmill graphs. Advances in Mathematics of Communications, 2019, 13 (1) : 89-99. doi: 10.3934/amc.2019005 [7] Vladimír Špitalský. Transitive dendrite map with infinite decomposition ideal. Discrete and Continuous Dynamical Systems, 2015, 35 (2) : 771-792. doi: 10.3934/dcds.2015.35.771 [8] John V. Shebalin. Theory and simulation of real and ideal magnetohydrodynamic turbulence. Discrete and Continuous Dynamical Systems - B, 2005, 5 (1) : 153-174. doi: 10.3934/dcdsb.2005.5.153 [9] Chun Liu, Jan-Eric Sulzbach. The Brinkman-Fourier system with ideal gas equilibrium. Discrete and Continuous Dynamical Systems, 2022, 42 (1) : 425-462. doi: 10.3934/dcds.2021123 [10] Ryutaroh Matsumoto. Strongly secure quantum ramp secret sharing constructed from algebraic curves over finite fields. Advances in Mathematics of Communications, 2019, 13 (1) : 1-10. doi: 10.3934/amc.2019001 [11] Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191 [12] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [13] Kalikinkar Mandal, Guang Gong. On ideal $t$-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125 [14] Yong Zhou, Jishan Fan. Local well-posedness for the ideal incompressible density dependent magnetohydrodynamic equations. Communications on Pure and Applied Analysis, 2010, 9 (3) : 813-818. doi: 10.3934/cpaa.2010.9.813 [15] Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237 [16] David Karpuk, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, Emanuele Viterbo. Probability estimates for fading and wiretap channels from ideal class zeta functions. Advances in Mathematics of Communications, 2015, 9 (4) : 391-413. doi: 10.3934/amc.2015.9.391 [17] Shu-Guang Shao, Shu Wang, Wen-Qing Xu, Yu-Li Ge. On the local C1, α solution of ideal magneto-hydrodynamical equations. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 2103-2113. doi: 10.3934/dcds.2017090 [18] Feng Cheng, Chao-Jiang Xu. On the Gevrey regularity of solutions to the 3D ideal MHD equations. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6485-6506. doi: 10.3934/dcds.2019281 [19] Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311 [20] Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete and Continuous Dynamical Systems - S, 2021, 14 (11) : 4035-4067. doi: 10.3934/dcdss.2020458

2020 Impact Factor: 0.935