Characterization and Optimization of Ideal Secret Sharing Schemes via Algebraic Matroid Theory
DOI:
https://doi.org/10.31185/bsj.Vol22.Iss43.1603Keywords:
الكلمات المفتاحية: الماترويدات الجبرية، مخططات مشاركة الأسرار المثالية، تفاضلات كاهلر، امتدادات الحقول، هندسة الخاصية p، الامتدادات غير القابلة للفصل تمامًا، متباينة إنجلتون، فضاءات التحقيق، التشفير التوافقي، معيار جاكوبي.Abstract
This paper establishes a rigorous algebraic characterization of Perfect Secret Sharing Schemes by generalizing the classical linear framework to the domain of Algebraic Matroids defined over field extensions. We demonstrate that the class of access structures admitting an Ideal Scheme with information rate ρ = 1 is canonically isomorphic to the class of matroids representable over a field extension L/K via transcendental and algebraic dependencies. To overcome the geometric limitations imposed by the Ingleton Inequality on linear representations, we introduce a constructive methodology utilizing the module of Kähler differentials. as a linearization functor that transforms algebraic independence into vector space independence. We prove that the security of a scheme is equivalent to the non-vanishing of the Jacobian determinant associated with the unauthorized sets in the realization variety. Furthermore, we explicitly construct ideal schemes for non-linear matroids, specifically the Vámos matroid, by exploiting the properties of purely inseparable extensions and the Frobenius endomorphism in fields of positive characteristic p. These constructions confirm that the capacity of algebraic secret sharing strictly exceeds that of linear schemes, providing a complete structural resolution to the problem of ideal realizability through the geometry of field extensions and algebraic curves.
References
[1] Beimel, A., Farràs, O., & Moya, A. (2025, December). Polynomial secret sharing schemes and algebraic matroids. In Theory of Cryptography Conference (pp. 428-461). Cham: Springer Nature Switzerland. https://doi.org/10.1007/978-3-032-12293-3_14
[2] Boege, T. (2025). The entropy profiles of a definable set over finite fields. arXiv preprint arXiv:2502.20355. https://doi.org/10.48550/arXiv.2502.20355
[3] Matera, G. (2025). Entropy approximations of algebraic matroids over finite fields. arXiv preprint arXiv:2509.15348. https://doi.org/10.48550/arXiv.2509.15348
[4] Matúš, F. (2024). Algebraic matroids are almost entropic. Proceedings of the American Mathematical Society, 152(01), 1-6. https://doi.org/10.1090/proc/13846
[5] Beimel, A., Farràs, O., & Lasri, O. (2023, November). Improved polynomial secret-sharing schemes. In Theory of Cryptography Conference (pp. 374-405). Cham: Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-48618-0_13
[6] Beimel, A., Othman, H., & Peter, N. (2021, August). Quadratic secret sharing and conditional disclosure of secrets. In Annual International Cryptology Conference (pp. 748-778). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-84252-9_25
[7] Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., & Ishai, Y. (2023, August). Arithmetic sketching. In Annual International Cryptology Conference (pp. 171-202). Cham: Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-38557-5_6
[8] Jafari, A., & Khazaei, S. (2023). Partial secret sharing schemes. IEEE Transactions on Information Theory, 69(8), 5364-5385. https://doi.org/10.1109/TIT.2023.3265093
[9] Slavov, K. (2023). Nearly sharp Lang–Weil bounds for a hypersurface. Canadian Mathematical Bulletin, 66(2), 654-664. https://doi.org/10.4153/S0008439522000625
[10] Bollen, G. P., Cartwright, D., & Draisma, J. (2022). Matroids over one-dimensional groups. International Mathematics Research Notices, 2022(3), 2298-2336. https://doi.org/10.1093/imrn/rnaa175
[11] Beimel, A., & Farràs, O. (2020, November). The share size of secret-sharing schemes for almost all access structures and graphs. In Theory of Cryptography Conference (pp. 499-529). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-64381-2_18
[12] Farras, O. (2020). Secret sharing schemes for ports of matroids of rank 3. Kybernetika, 56(5), 903-915. http://dx.doi.org/10.14736/kyb-2020-5-0903
[13] Paskin-Chernivasky, A., & Radune, A. (2019). On polynomial secret sharing schemes. Cryptology ePrint Archive. https://eprint.iacr.org/2019/361
[14] Csirmaz, L. (2020). Secret sharing and duality. Journal of Mathematical Cryptology, 15(1), 157-173. https://doi.org/10.1515/jmc-2019-0045
[15] Kaced, T. (2018). Information inequalities are not closed under polymatroid duality. IEEE Transactions on Information Theory, 64(6), 4379-4381. https://doi.org/10.1109/TIT.2018.2823328
[16] Bollen, G. P., Draisma, J., & Pendavingh, R. (2018). Algebraic matroids and Frobenius flocks. Advances in mathematics, 323, 688-719. https://doi.org/10.1016/j.aim.2017.11.006
[17] Liu, T., & Vaikuntanathan, V. (2018, June). Breaking the circuit-size barrier in secret sharing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 699-708). https://doi.org/10.1145/3188745.3188936
[18] Liu, T., Vaikuntanathan, V., & Wee, H. (2017, July). Conditional disclosure of secrets via non-linear reconstruction. In Annual International Cryptology Conference (pp. 758-790). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-63688-7_25
[19] Ben-Efraim, A. (2016). Secret-sharing matroids need not be algebraic. Discrete Mathematics, 339(8), 2136-2145. https://doi.org/10.1016/j.disc.2016.02.012
[20] Berson, J. (2014). Linearized polynomial maps over finite fields. Journal of Algebra, 399, 389-406. https://doi.org/10.1016/j.jalgebra.2013.10.013
Downloads
Published
Issue
Section
License
Copyright (c) 2026 وليد عادل عبد الحسين

This work is licensed under a Creative Commons Attribution 4.0 International License.