Article Contents

2023, Volume 17, Issue 3: 697-713. Doi: 10.3934/amc.2021017

This issue Previous Article Delegating signing rights in a multivariate proxy signature scheme Next Article The conorm code of an AG-code

On ideal and weakly-ideal access structures

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

^* Corresponding author
^* Corresponding author

Received: October 2020

Revised: April 2021

Early access: June 2021

Published: June 2023

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Ideal secret sharing scheme,
linear and group-characterizable random variable,
ideal access structure,
matroid,
Latin square.

Mathematics Subject Classification: Primary: 94A62, 05B35; Secondary: 05B15.

Citation:

Full Text(HTML)

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} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.