Kybernetika 59 no. 2, 198-208, 2023

Access structures for finding characteristic-dependent linear rank inequalities

Victor Peña-MaciasDOI: 10.14736/kyb-2023-2-0198

Abstract:

Determining information ratios of access structures is an important problem in secret sharing. Information inequalities and linear rank inequalities play an important role for proving bounds on these ratios. Characteristic-dependent linear rank inequalities are rank inequalities which are true over vector spaces with specific field characteristic. In this paper, using ideas of secret sharing, we show a theorem that produces characteristic-dependent linear rank inequalities. These inequalities are then used for getting lower bounds on information ratios of some access structures in linear secret sharing.

Keywords:

entropy, matroids, secret sharing, cryptography, access structures, complementary spaces, linear rank inequalities

Classification:

68P30, 94A15

paper.pdf

References:

  1. A. Blasiak, R. Kleinberg and E. Lubetzky: Lexicographic products and the power of non-linear network coding. Ib: IEEE Symposium on Foundations of Computer Science 2011, pp. 609-618.   DOI:10.1109/FOCS.2011.39
  2. E. F. Brickell and D. M. Davenport: On the classification of ideal secret sharing. J. Cryptology (1991), 4, 123-134.   DOI:10.1007/BF00196772
  3. R. Dougherty, C. Freiling and K. Zeger: Achievable Rate regions for network coding. IEEE Trans. Inform. Theory 61 (2015), 5, 2488-2509.   DOI:10.1109/TIT.2015.2403315
  4. O. Farràs, T. Kaced, S. Martín and C. Padró: Improving the linear programming technique in the search for lower bounds in secret sharing. IEEE Transactions on Information Theory 66 (2020), 11, 7088-7100.   DOI:10.1109/TIT.2020.3005706
  5. A. Jafari and S. Khazaei: On Abelian secret sharing: Duality and separation. IACR Cryptol. ePrint Archive (2019), 575.   CrossRef
  6. S. Martín, C. Padró and A. Yang: Secret Sharing, Rank Inequalities, and Information Inequalities. IEEE Trans. Inform. Theory 2 (2016), 1, 599-609.   DOI:10.1109/TIT.2015.2500232
  7. C. Padró: Lecture notes in secret sharing. Cryptology ePrint Archive: Report (2012), 674.   CrossRef
  8. V. Peña-Macias and H. Sarria: Characteristic-dependent linear rank inequalities via complementary vector spaces. J. Inform. Optim. Sci. 42 (2021), 2, 345-369.   DOI:10.1080/02522667.2019.1668157
  9. V. Peña-Macias and H. Sarria: Characteristic-dependent linear rank inequalities in 21 variables. Rev. Acad. Colomb. Cienc. Ex. Fis. Nat. 43 (2019), 169, 76-5-770.   DOI:10.18257/raccefyn.928
  10. A. Shen, D. Hammer, A. E. Romashchenko and N. K. Vereshchagin: Inequalities for Shannon Entropy and Kolmogorov Complexity. J. Computer Systems Sci. 60 (2000), 442-464.   DOI:10.1006/jcss.1999.1677