Volume 1,Issue 6
秘密共享中若干信息等式的证明
在秘密共享方案中，复杂度是指参与者某个份额的最大长度与秘密长度的比值，而最优复杂度是指所有能实现某访问结构的方案复杂度的下确界。计算通用访问结构的最优复杂度问题一直悬而未决。现有研究多聚焦于确定最优复杂度的上界与下界。计算下界问题可转化为线性规划求解问题，而随机变量的公共信息属性与该求解问题密切相关，且该属性可拓展衍生出若干信息等式。在本文中，利用信息论及多拟阵的相关知识，证明了这一系列信息等式。这些等式将有助于确定最优复杂度的下界。
[1] Gharahi, M., Khazaei, S.: Optimal Linear Secret Sharing Schemes for Graph Access Structures on Six Participants. Theoret. Comput. Sci. 771, 1-8 (2019).
[2] Gharahi, M., Khazaei, S.: Reduced access structures with four minimal qualified subsets on six participants. Adv. Math. Commun. 12, 199-214 (2018).
[3] Gharahi, M., Dehkordi, M.H.: The complexity of the graph access structures on six participants. Des. Codes Cryptogr. 67, 169-173 (2013).
[4] Reza Kaboli, Shahram Khazaei, and Maghsoud Parviz: On ideal and weaklyideal access structures. Cryptology ePrint Archive, https://eprint.iacr.org/2020/483, (2020).
[5] Gyarmati M., Ligeti P.: On the information ratio of graphs without high-degree neighbors. Discret. Appl.Math. 304(15), 55-62 (2021).
[6] Csirmaz, L.: The size of a share must be large. J. Cryptology 10, 223-231 (1997).
[7] M. Ito, A. Saito, and T. Nishizeki, Secret sharing scheme realizing any access structure, Proc. IEEE Globecom’87 (1987), 99–102.
[8] Padro, C., Vazquez, L., Yang, A.: Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming. Discrete Applied Mathematics. 161, 1072-1084 (2013).
[9] Martı-Farre, J., Padro, C.: On secret sharing schemes, matroids and polymatroids. J. Math. Cryptol. 4, 95-120 (2010).
[10] Beimel, A., Orlov, I.: Secret Sharing and Non-Shannon Information Inequalities. IEEE Trans. Inform. Theory 57, 5634-5649 (2011).
[11] Oriol Farras, Tarik Kaced, Sebastia Mart´ın, Carles Padr´o: Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing. IEEE Trans. Inf. Theory 66(11): 7088-7100 (2022).
[12] S. Fujishige, Polymatroidal Dependence Structure of a Set of Random Variables,Information and Control 39 (1978), 55–72.
[13] Csirmaz L.: Secret sharing and duality. J. Math. Cryptol. 15(1), 157-173 (2021).
[14] Jafari, A., Khazaei, S.: On Abelian Secret Sharing: duality and separation. Cryptology ePrint Archive, https://eprint.iacr.org/2019/575, (2019).
[15] Amir Jafari and Shahram Khazaei: Partial secret sharing schemes. Cryptology ePrint Archive, https://eprint.iacr.org/2020/448, (2020).