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

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

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

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

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

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

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

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

[9]

G. R. Blakley, Safeguarding cryptographic keys, Proc. of the National Computer Conference 1979, 48 (1979), 313-317.   Google Scholar

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

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

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

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

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

[15]

L. Csirmaz, Secret sharing and duality, CoRR, abs/1909.13663, 2019. doi: 10.1515/jmc-2019-0045.  Google Scholar

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

[17]

J. Gallian, Contemporary Abstract Algebra, Nelson Education, 2012. Google Scholar

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

[19]

P. Hall, Complemented groups, Journal of the London Mathematical Society, 1 (1937), 201-204.  doi: 10.1112/jlms/s1-12.2.201.  Google Scholar

[20]

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

[21]

A. Jafari and S. Khazaei, On abelian and homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/575, 2019. Google Scholar

[22]

A. Jafari and S. Khazaei, Partial secret sharing schemes, Cryptology ePrint Archive, Report 2020/448, 2020. Google Scholar

[23]

R. Kaboli, S. Khazaei and M. Parviz, On group-characterizability of homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/576, 2019. Google Scholar

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

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

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

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

[28]

A. D. Keedwell and J. Dénes, Latin Squares and their Applications, Elsevier, 2015.  Google Scholar

[29]

F. Matúš, Algebraic matroids are almost entropic, Proceedings of the AMS, to appear. Google Scholar

[30]

F. Matúš, Matroid representations by partitions, Discrete Mathematics, 203 (1999), 169-194.  doi: 10.1016/S0012-365X(99)00004-7.  Google Scholar

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

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

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

[34]

J. G. Oxley, Matroid theory, 3, Oxford University Press, USA, 2006. doi: 10.1093/acprof:oso/9780198566946.001.0001.  Google Scholar

[35]

C. Padró, Lecture notes in secret sharing, IACR Cryptology ePrint Archive, 674 (2012). Google Scholar

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

[37]

A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176.  Google Scholar

[38]

J. Simonis and A. E. Ashikhmin, Almost affine codes, Des. Codes Cryptogr., 14 (1998), 179-197.  doi: 10.1023/A:1008244215660.  Google Scholar

[39]

F. Wei, M. Langberg and M. Effros, Towards an operational definition of group network codes, CoRR, abs/2002.00781, 2020. Google Scholar

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

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

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

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

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

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

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

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

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

[9]

G. R. Blakley, Safeguarding cryptographic keys, Proc. of the National Computer Conference 1979, 48 (1979), 313-317.   Google Scholar

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

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

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

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

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

[15]

L. Csirmaz, Secret sharing and duality, CoRR, abs/1909.13663, 2019. doi: 10.1515/jmc-2019-0045.  Google Scholar

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

[17]

J. Gallian, Contemporary Abstract Algebra, Nelson Education, 2012. Google Scholar

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

[19]

P. Hall, Complemented groups, Journal of the London Mathematical Society, 1 (1937), 201-204.  doi: 10.1112/jlms/s1-12.2.201.  Google Scholar

[20]

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

[21]

A. Jafari and S. Khazaei, On abelian and homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/575, 2019. Google Scholar

[22]

A. Jafari and S. Khazaei, Partial secret sharing schemes, Cryptology ePrint Archive, Report 2020/448, 2020. Google Scholar

[23]

R. Kaboli, S. Khazaei and M. Parviz, On group-characterizability of homomorphic secret sharing schemes, Cryptology ePrint Archive, Report 2019/576, 2019. Google Scholar

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

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

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

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

[28]

A. D. Keedwell and J. Dénes, Latin Squares and their Applications, Elsevier, 2015.  Google Scholar

[29]

F. Matúš, Algebraic matroids are almost entropic, Proceedings of the AMS, to appear. Google Scholar

[30]

F. Matúš, Matroid representations by partitions, Discrete Mathematics, 203 (1999), 169-194.  doi: 10.1016/S0012-365X(99)00004-7.  Google Scholar

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

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

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

[34]

J. G. Oxley, Matroid theory, 3, Oxford University Press, USA, 2006. doi: 10.1093/acprof:oso/9780198566946.001.0001.  Google Scholar

[35]

C. Padró, Lecture notes in secret sharing, IACR Cryptology ePrint Archive, 674 (2012). Google Scholar

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

[37]

A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176.  Google Scholar

[38]

J. Simonis and A. E. Ashikhmin, Almost affine codes, Des. Codes Cryptogr., 14 (1998), 179-197.  doi: 10.1023/A:1008244215660.  Google Scholar

[39]

F. Wei, M. Langberg and M. Effros, Towards an operational definition of group network codes, CoRR, abs/2002.00781, 2020. Google Scholar

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

Table 1.  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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2021  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 & 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 & 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 & 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 & Continuous Dynamical Systems - S, 2021, 14 (11) : 4035-4067. doi: 10.3934/dcdss.2020458

2020 Impact Factor: 0.935

Article outline

Figures and Tables

[Back to Top]