Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
secret sharing schemes; matroids; matroid ports
secret sharing schemes; matroids; matroid ports
Summary:
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\geq 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})$.
References:
[1] Applebaum, B., Beimel, A., Farràs, O., Nir, O., Peter, N.: Secret-Sharing Schemes for General and Uniform Access Structures. In: Advances in Cryptology - EUROCRYPT 2019, Lect. Notes Comput. Sci. 11478 (2019), Springer, pp. 441-471. DOI 10.1007/978-3-030-17659-4_15 | MR 3964688
[2] Babai, L., Gál, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19 (1999), 301-319. DOI 10.1007/s004930050058 | MR 1723251
[3] Bansal, N., Pendavingh, R. A., Pol, J. G. van der: On the number of matroids. Combinatorica 49 (2013), 675-694. DOI 10.1007/s00493-014-3029-z | MR 3186782
[4] Beimel, A.: Secret-sharing schemes: A survey. In: IWCC 2011, Lect. Notes Comput. Sci. 6639 (2019), Springer, pp. 11-46. DOI 10.1007/978-3-642-20901-7_2 | MR 2834691
[5] Beimel, A., Ben-Efraim, A., Padró, C., Tyomkin, I.: Multi-linear secret-sharing schemes. In: TCC, Lect. Notes Comput. Sci. 8349 (2019), Springer, pp. 394-418. DOI 10.1007/978-3-642-20901-7_2 | MR 3183548
[6] Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. Inform. Theory 40 (1994), 3, 786-794. DOI 10.1109/18.335890 | MR 1295314
[7] Beimel, A., Livne, N.: On matroids and nonideal secret sharing. IEEE Trans. Inform. Theory 54 (2008), 6, 2626-2643. DOI 10.1109/tit.2008.921708 | MR 2449268
[8] Beimel, A., Livne, N., Padró, C.: Matroids can be far from ideal secret sharing. In: TCC 2008, Lect. Notes Comput. Sci. 4948 (2008), Springer, pp. 194-212. DOI 10.1007/978-3-540-78524-8_12 | MR 2494143
[9] Ben-Efraim, A.: Secret-sharing matroids need not be algebraic. Discrete Math. 339 (2016), 8, 2136-2145. DOI 10.1016/j.disc.2016.02.012 | MR 3500143
[10] Benaloh, J. C., Leichter, J.: Generalized secret sharing and monotone functions. In: CRYPTO'88, Lect. Notes Comput. Sci. 403 (1988), Springer, pp. 27-35. DOI 10.1007/0-387-34799-2_3 | MR 1046379
[11] Blakley, G. R.: Safeguarding cryptographic keys. In: AFIPS Conference Proc. 48 (1979), pp. 313-317. DOI 10.1109/mark.1979.8817296
[12] Blundo, C., Santis, A. De, Stinson, D. R., Vaccaro, U.: Graph decomposition and secret sharing schemes. J. of Cryptology 8 (1995), 1, 39-64. DOI 10.1007/bf00204801 | MR 1319955
[13] Brickell, E. F., Davenport, D. M.: On the classification of ideal secret sharing schemes. J. of Cryptology 4 (1991), 73, 123-134. DOI 10.1007/bf00196772 | MR 1062240
[14] Csirmaz, L.: The size of a share must be large. J. Cryptology 1 (1997), 4, 223-231. DOI 10.1007/s001459900029 | MR 1476611
[15] Csirmaz, L., Ligeti, P., Tardos, G.: Erdös-Pyber theorem for hypergraphs and secret sharing. Graphs Combinator. 31 (2015), 5, 1335-1346. DOI 10.1007/s00373-014-1448-7 | MR 3386012
[16] Erdös, P., Pyber, L.: Covering a graph by complete bipartite graphs. Discrete Math. 170 (1997), 1-3, 249-251. DOI 10.1016/s0012-365x(96)00124-0 | MR 1452952
[17] Farràs, O., Kaced, T., Martín, S., Padró, C.: Improving the linear programming technique in the search for lower bounds in secret sharing. In: Advances in Cryptology - Eurocrypt 2018, volume 10820 Lecture Notes in Comput. Sci. 10820 (2018), Springer, pp. 597-621. DOI 10.1007/978-3-319-78381-9_22 | MR 3794799
[18] Farràs, O., Martí-Farré, J., Padró, C.: Ideal multipartite secret sharing schemes. J. Cryptology 25 (2012), 434-463. DOI 10.1007/s00145-011-9101-6 | MR 2900407
[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.: Lower bounds for constant weight codes. IEEE Trans. Inform. Theory 26 (1980), 1, 37-43. DOI 10.1109/tit.1980.1056141 | MR 0560390
[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. MR 0278974
[22] Jackson, W.-A., Martin, K. M.: Geometric secret sharing schemes and their duals. Codes Cryptography 4 (1994), 1, 83-95. DOI 10.1007/bf01388562 | MR 1260371
[23] Korshunov, A. D.: Monotone Boolean functions. Russ. Math. Surv. 58 (2003), 5, 929-1001. DOI 10.1070/rm2003v058n05abeh000667 | MR 2035720
[24] Knuth, D. E.: The asymptotic number of geometries. J. Combinator. Theory, Ser. A 16 (1974), 3, 398-400. DOI 10.1016/0097-3165(74)90063-6 | MR 0335312
[25] Liu, T., Vaikuntanathan, V.: Breaking the circuit-size barrier in secret sharing. In: 50th STOC 2018, pp. 699-708. MR 3826287
[26] Martí-Farré, J., Padró, C.: Secret sharing schemes on sparse homogeneous access structures with rank three. Electr. J. Comb. 11 (2004), 1. DOI | MR 2097338
[27] Martí-Farré, J., Padró, C.: Ideal secret sharing schemes whose minimal qualified subsets have at most three participants. Des. Codes Cryptography 52 (2009), 1, 1-14. DOI 10.1007/s10623-008-9264-9 | MR 2496243
[28] Martí-Farré, J., Padró, C.: On secret sharing schemes, matroids and polymatroids. J. Math. Cryptology 4 (2010), 2, 95-120. DOI 10.1007/s10623-008-9264-9 | MR 2729351
[29] Matúš, F.: Probabilistic conditional independence structures and matroid theory: Background. Int. J. Gen. Syst. 22 (1994), 185-196. DOI 10.1080/03081079308935205
[30] Matúš, F.: Matroid representations by partitions. Discrete Math. 203 (1999), 169-194. DOI 10.1016/s0012-365x(99)00004-7 | MR 1696241
[31] Matúš, F.: Adhesivity of polymatroids. Discrete Math. 307 (2007), 2464-2477. DOI 10.1016/j.disc.2006.11.013 | MR 2359593
[32] Mayhew, D., Newman, M., Welsh, D., Whittle, G.: On the asymptotic proportion of connected matroids. Eur. J. Comb. 32 (2011), 6, 882-890. DOI 10.1016/j.ejc.2011.01.016 | MR 2821559
[33] Oxley, J. G.: Matroid Theory. Second Edition. Oxford Graduate Texts in Mathematics 21, The Clarendon Press, Oxford 2011. MR 2849819
[34] Padró, C.: Lecture notes in secret sharing. Cryptology ePrint Archive, Report 2012/674 (2912).
[35] Seymour, P. D.: A forbidden minor characterization of matroid ports. Quart. J. Math. Oxford Ser. 27 (1976), 407-413. DOI 10.1093/qmath/27.4.407 | MR 0429611
[36] Shamir, A.: How to share a secret. Comm. ACM 22 (1979), 612-613. DOI 10.1145/359168.359176 | MR 0549252
[37] Simonis, J., Ashikhmin, A.: Almost affine codes. Designs Codes Cryptogr. 14 (1998), 2, 179-197. DOI 10.1023/a:1008244215660 | MR 1614357
[38] Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, 1987. MR 0905473 | Zbl 0623.94018
Search
Partner of
