Secret sharing schemes for ports of matroids of rank 3

Oriol Farràs

Kybernetika (2020)

  • Volume: 56, Issue: 5, page 903-915
  • ISSN: 0023-5954

Abstract

top
A secret sharing scheme is ideal if the size of each share is equal to the size of the secret. Brickell and Davenport showed that the access structure of an ideal secret sharing scheme is determined by a matroid. Namely, the minimal authorized subsets of an ideal secret sharing scheme are in correspondence with the circuits of a matroid containing a fixed point. In this case, we say that the access structure is a matroid port. It is known that, for an access structure, being a matroid port is not a sufficient condition to admit an ideal secret sharing scheme. In this work we present a linear secret sharing scheme construction for ports of matroids of rank 3 in which the size of each share is at most n times the size of the secret. Using the previously known secret sharing constructions, the size of each share was O ( n 2 / log n ) the size of the secret. Our construction is extended to ports of matroids of any rank k ≥ 2 , obtaining secret sharing schemes in which the size of each share is at most n k - 2 times the size of the secret. This work is complemented by presenting lower bounds: There exist matroid ports that require ( 𝔽 q , ℓ ) -linear secret schemes with total information ratio Ω ( 2 n / 2 / ℓ n 3 / 4 log q ) .

How to cite

top

Farràs, Oriol. "Secret sharing schemes for ports of matroids of rank 3." Kybernetika 56.5 (2020): 903-915. <http://eudml.org/doc/297215>.

@article{Farràs2020,
abstract = {A secret sharing scheme is ideal if the size of each share is equal to the size of the secret. Brickell and Davenport showed that the access structure of an ideal secret sharing scheme is determined by a matroid. Namely, the minimal authorized subsets of an ideal secret sharing scheme are in correspondence with the circuits of a matroid containing a fixed point. In this case, we say that the access structure is a matroid port. It is known that, for an access structure, being a matroid port is not a sufficient condition to admit an ideal secret sharing scheme. In this work we present a linear secret sharing scheme construction for ports of matroids of rank 3 in which the size of each share is at most $n$ times the size of the secret. Using the previously known secret sharing constructions, the size of each share was $O(n^2/\log n)$ the size of the secret. Our construction is extended to ports of matroids of any rank $k\ge 2$, obtaining secret sharing schemes in which the size of each share is at most $n^\{k-2\}$ times the size of the secret. This work is complemented by presenting lower bounds: There exist matroid ports that require $(\mathbb \{F\}_q,\ell )$-linear secret schemes with total information ratio $\Omega (2^\{n/2\}/\ell n^\{3/4\}\sqrt\{\log q\})$.},
author = {Farràs, Oriol},
journal = {Kybernetika},
keywords = {secret sharing schemes; matroids; matroid ports},
language = {eng},
number = {5},
pages = {903-915},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Secret sharing schemes for ports of matroids of rank 3},
url = {http://eudml.org/doc/297215},
volume = {56},
year = {2020},
}

TY - JOUR
AU - Farràs, Oriol
TI - Secret sharing schemes for ports of matroids of rank 3
JO - Kybernetika
PY - 2020
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 5
SP - 903
EP - 915
AB - A secret sharing scheme is ideal if the size of each share is equal to the size of the secret. Brickell and Davenport showed that the access structure of an ideal secret sharing scheme is determined by a matroid. Namely, the minimal authorized subsets of an ideal secret sharing scheme are in correspondence with the circuits of a matroid containing a fixed point. In this case, we say that the access structure is a matroid port. It is known that, for an access structure, being a matroid port is not a sufficient condition to admit an ideal secret sharing scheme. In this work we present a linear secret sharing scheme construction for ports of matroids of rank 3 in which the size of each share is at most $n$ times the size of the secret. Using the previously known secret sharing constructions, the size of each share was $O(n^2/\log n)$ the size of the secret. Our construction is extended to ports of matroids of any rank $k\ge 2$, obtaining secret sharing schemes in which the size of each share is at most $n^{k-2}$ times the size of the secret. This work is complemented by presenting lower bounds: There exist matroid ports that require $(\mathbb {F}_q,\ell )$-linear secret schemes with total information ratio $\Omega (2^{n/2}/\ell n^{3/4}\sqrt{\log q})$.
LA - eng
KW - secret sharing schemes; matroids; matroid ports
UR - http://eudml.org/doc/297215
ER -

References

top
  1. Applebaum, B., Beimel, A., Farràs, O., Nir, O., Peter, N., 10.1007/978-3-030-17659-4_15, In: Advances in Cryptology - EUROCRYPT 2019, Lect. Notes Comput. Sci. 11478 (2019), Springer, pp. 441-471. MR3964688DOI10.1007/978-3-030-17659-4_15
  2. Babai, L., Gál, A., Wigderson, A., 10.1007/s004930050058, Combinatorica 19 (1999), 301-319. MR1723251DOI10.1007/s004930050058
  3. Bansal, N., Pendavingh, R. A., Pol, J. G. van der, 10.1007/s00493-014-3029-z, Combinatorica 49 (2013), 675-694. MR3186782DOI10.1007/s00493-014-3029-z
  4. Beimel, A., 10.1007/978-3-642-20901-7_2, In: IWCC 2011, Lect. Notes Comput. Sci. 6639 (2019), Springer, pp. 11-46. MR2834691DOI10.1007/978-3-642-20901-7_2
  5. Beimel, A., Ben-Efraim, A., Padró, C., Tyomkin, I., 10.1007/978-3-642-20901-7_2, In: TCC, Lect. Notes Comput. Sci. 8349 (2019), Springer, pp. 394-418. MR3183548DOI10.1007/978-3-642-20901-7_2
  6. Beimel, A., Chor, B., 10.1109/18.335890, IEEE Trans. Inform. Theory 40 (1994), 3, 786-794. MR1295314DOI10.1109/18.335890
  7. Beimel, A., Livne, N., 10.1109/tit.2008.921708, IEEE Trans. Inform. Theory 54 (2008), 6, 2626-2643. MR2449268DOI10.1109/tit.2008.921708
  8. Beimel, A., Livne, N., Padró, C., 10.1007/978-3-540-78524-8_12, In: TCC 2008, Lect. Notes Comput. Sci. 4948 (2008), Springer, pp. 194-212. MR2494143DOI10.1007/978-3-540-78524-8_12
  9. Ben-Efraim, A., 10.1016/j.disc.2016.02.012, Discrete Math. 339 (2016), 8, 2136-2145. MR3500143DOI10.1016/j.disc.2016.02.012
  10. Benaloh, J. C., Leichter, J., 10.1007/0-387-34799-2_3, In: CRYPTO'88, Lect. Notes Comput. Sci. 403 (1988), Springer, pp. 27-35. MR1046379DOI10.1007/0-387-34799-2_3
  11. Blakley, G. R., 10.1109/mark.1979.8817296, In: AFIPS Conference Proc. 48 (1979), pp. 313-317. DOI10.1109/mark.1979.8817296
  12. Blundo, C., Santis, A. De, Stinson, D. R., Vaccaro, U., 10.1007/bf00204801, J. of Cryptology 8 (1995), 1, 39-64. MR1319955DOI10.1007/bf00204801
  13. Brickell, E. F., Davenport, D. M., 10.1007/bf00196772, J. of Cryptology 4 (1991), 73, 123-134. MR1062240DOI10.1007/bf00196772
  14. Csirmaz, L., 10.1007/s001459900029, J. Cryptology 1 (1997), 4, 223-231. MR1476611DOI10.1007/s001459900029
  15. Csirmaz, L., Ligeti, P., Tardos, G., 10.1007/s00373-014-1448-7, Graphs Combinator. 31 (2015), 5, 1335-1346. MR3386012DOI10.1007/s00373-014-1448-7
  16. Erdös, P., Pyber, L., 10.1016/s0012-365x(96)00124-0, Discrete Math. 170 (1997), 1-3, 249-251. MR1452952DOI10.1016/s0012-365x(96)00124-0
  17. Farràs, O., Kaced, T., Martín, S., Padró, C., 10.1007/978-3-319-78381-9_22, In: Advances in Cryptology - Eurocrypt 2018, volume 10820 Lecture Notes in Comput. Sci. 10820 (2018), Springer, pp. 597-621. MR3794799DOI10.1007/978-3-319-78381-9_22
  18. Farràs, O., Martí-Farré, J., Padró, C., 10.1007/s00145-011-9101-6, J. Cryptology 25 (2012), 434-463. MR2900407DOI10.1007/s00145-011-9101-6
  19. Gürpinar, E., Romashchenko, A., How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma., In: 2019 IEEE International Symposium on Information Theory (ISIT), pp. 1377-1381. 
  20. Graham, R. L., Sloane, N. J. A., 10.1109/tit.1980.1056141, IEEE Trans. Inform. Theory 26 (1980), 1, 37-43. MR0560390DOI10.1109/tit.1980.1056141
  21. Ingleton, A. W., Representation of matroids., In: Combinatorial Mathematics and its Applications, (D. J. A. Welsh, ed.), Academic Press, London 1971, pp. 149-167. MR0278974
  22. Jackson, W.-A., Martin, K. M., 10.1007/bf01388562, Codes Cryptography 4 (1994), 1, 83-95. MR1260371DOI10.1007/bf01388562
  23. Korshunov, A. D., 10.1070/rm2003v058n05abeh000667, Russ. Math. Surv. 58 (2003), 5, 929-1001. MR2035720DOI10.1070/rm2003v058n05abeh000667
  24. Knuth, D. E., 10.1016/0097-3165(74)90063-6, J. Combinator. Theory, Ser. A 16 (1974), 3, 398-400. MR0335312DOI10.1016/0097-3165(74)90063-6
  25. Liu, T., Vaikuntanathan, V., Breaking the circuit-size barrier in secret sharing., In: 50th STOC 2018, pp. 699-708. MR3826287
  26. Martí-Farré, J., Padró, C., , Electr. J. Comb. 11 (2004), 1. MR2097338DOI
  27. Martí-Farré, J., Padró, C., 10.1007/s10623-008-9264-9, Des. Codes Cryptography 52 (2009), 1, 1-14. MR2496243DOI10.1007/s10623-008-9264-9
  28. Martí-Farré, J., Padró, C., 10.1007/s10623-008-9264-9, J. Math. Cryptology 4 (2010), 2, 95-120. MR2729351DOI10.1007/s10623-008-9264-9
  29. Matúš, F., 10.1080/03081079308935205, Int. J. Gen. Syst. 22 (1994), 185-196. DOI10.1080/03081079308935205
  30. Matúš, F., 10.1016/s0012-365x(99)00004-7, Discrete Math. 203 (1999), 169-194. MR1696241DOI10.1016/s0012-365x(99)00004-7
  31. Matúš, F., 10.1016/j.disc.2006.11.013, Discrete Math. 307 (2007), 2464-2477. MR2359593DOI10.1016/j.disc.2006.11.013
  32. Mayhew, D., Newman, M., Welsh, D., Whittle, G., 10.1016/j.ejc.2011.01.016, Eur. J. Comb. 32 (2011), 6, 882-890. MR2821559DOI10.1016/j.ejc.2011.01.016
  33. Oxley, J. G., Matroid Theory. Second Edition., Oxford Graduate Texts in Mathematics 21, The Clarendon Press, Oxford 2011. MR2849819
  34. Padró, C., Lecture notes in secret sharing., Cryptology ePrint Archive, Report 2012/674 (2912). 
  35. Seymour, P. D., 10.1093/qmath/27.4.407, Quart. J. Math. Oxford Ser. 27 (1976), 407-413. MR0429611DOI10.1093/qmath/27.4.407
  36. Shamir, A., 10.1145/359168.359176, Comm. ACM 22 (1979), 612-613. MR0549252DOI10.1145/359168.359176
  37. Simonis, J., Ashikhmin, A., 10.1023/a:1008244215660, Designs Codes Cryptogr. 14 (1998), 2, 179-197. MR1614357DOI10.1023/a:1008244215660
  38. Wegener, I., The Complexity of Boolean Functions., Wiley-Teubner, 1987. Zbl0623.94018MR0905473

NotesEmbed ?

top

You must be logged in to post comments.