Geodesic
Secret sharing schemes for ports of matroids of rank 3
Kybernetika, Tome 56 (2020) no. 5, pp. 903-915
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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})$.
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})$.
DOI : 10.14736/kyb-2020-5-0903
Classification : 05B35, 94A60, 94A62
Keywords: secret sharing schemes; matroids; matroid ports 
@article{10_14736_kyb_2020_5_0903,
     author = {Farr\`as, Oriol},
     title = {Secret sharing schemes for ports of matroids of rank 3},
     journal = {Kybernetika},
     pages = {903--915},
     year = {2020},
     volume = {56},
     number = {5},
     doi = {10.14736/kyb-2020-5-0903},
     mrnumber = {4187779},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0903/}
}
TY  - JOUR
AU  - Farràs, Oriol
TI  - Secret sharing schemes for ports of matroids of rank 3
JO  - Kybernetika
PY  - 2020
SP  - 903
EP  - 915
VL  - 56
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0903/
DO  - 10.14736/kyb-2020-5-0903
LA  - en
ID  - 10_14736_kyb_2020_5_0903
ER  - 
%0 Journal Article
%A Farràs, Oriol
%T Secret sharing schemes for ports of matroids of rank 3
%J Kybernetika
%D 2020
%P 903-915
%V 56
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0903/
%R 10.14736/kyb-2020-5-0903
%G en
%F 10_14736_kyb_2020_5_0903
Farràs, Oriol. Secret sharing schemes for ports of matroids of rank 3. Kybernetika, Tome 56 (2020) no. 5, pp. 903-915. doi: 10.14736/kyb-2020-5-0903

[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 | MR

[2] Babai, L., Gál, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19 (1999), 301-319. | DOI | MR

[3] Bansal, N., Pendavingh, R. A., Pol, J. G. van der: On the number of matroids. Combinatorica 49 (2013), 675-694. | DOI | MR

[4] Beimel, A.: Secret-sharing schemes: A survey. In: IWCC 2011, Lect. Notes Comput. Sci. 6639 (2019), Springer, pp. 11-46. | DOI | MR

[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 | MR

[6] Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. Inform. Theory 40 (1994), 3, 786-794. | DOI | MR

[7] Beimel, A., Livne, N.: On matroids and nonideal secret sharing. IEEE Trans. Inform. Theory 54 (2008), 6, 2626-2643. | DOI | MR

[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 | MR

[9] Ben-Efraim, A.: Secret-sharing matroids need not be algebraic. Discrete Math. 339 (2016), 8, 2136-2145. | DOI | MR

[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 | MR

[11] Blakley, G. R.: Safeguarding cryptographic keys. In: AFIPS Conference Proc. 48 (1979), pp. 313-317. | DOI

[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 | MR

[13] Brickell, E. F., Davenport, D. M.: On the classification of ideal secret sharing schemes. J. of Cryptology 4 (1991), 73, 123-134. | DOI | MR

[14] Csirmaz, L.: The size of a share must be large. J. Cryptology 1 (1997), 4, 223-231. | DOI | MR

[15] Csirmaz, L., Ligeti, P., Tardos, G.: Erdös-Pyber theorem for hypergraphs and secret sharing. Graphs Combinator. 31 (2015), 5, 1335-1346. | DOI | MR

[16] Erdös, P., Pyber, L.: Covering a graph by complete bipartite graphs. Discrete Math. 170 (1997), 1-3, 249-251. | DOI | MR

[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 | MR

[18] Farràs, O., Martí-Farré, J., Padró, C.: Ideal multipartite secret sharing schemes. J. Cryptology 25 (2012), 434-463. | DOI | MR

[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 | MR

[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

[22] Jackson, W.-A., Martin, K. M.: Geometric secret sharing schemes and their duals. Codes Cryptography 4 (1994), 1, 83-95. | DOI | MR

[23] Korshunov, A. D.: Monotone Boolean functions. Russ. Math. Surv. 58 (2003), 5, 929-1001. | DOI | MR

[24] Knuth, D. E.: The asymptotic number of geometries. J. Combinator. Theory, Ser. A 16 (1974), 3, 398-400. | DOI | MR

[25] Liu, T., Vaikuntanathan, V.: Breaking the circuit-size barrier in secret sharing. In: 50th STOC 2018, pp. 699-708. | MR

[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

[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 | MR

[28] Martí-Farré, J., Padró, C.: On secret sharing schemes, matroids and polymatroids. J. Math. Cryptology 4 (2010), 2, 95-120. | DOI | MR

[29] Matúš, F.: Probabilistic conditional independence structures and matroid theory: Background. Int. J. Gen. Syst. 22 (1994), 185-196. | DOI

[30] Matúš, F.: Matroid representations by partitions. Discrete Math. 203 (1999), 169-194. | DOI | MR

[31] Matúš, F.: Adhesivity of polymatroids. Discrete Math. 307 (2007), 2464-2477. | DOI | MR

[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 | MR

[33] Oxley, J. G.: Matroid Theory. Second Edition. Oxford Graduate Texts in Mathematics 21, The Clarendon Press, Oxford 2011. | MR

[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 | MR

[36] Shamir, A.: How to share a secret. Comm. ACM 22 (1979), 612-613. | DOI | MR

[37] Simonis, J., Ashikhmin, A.: Almost affine codes. Designs Codes Cryptogr. 14 (1998), 2, 179-197. | DOI | MR

[38] Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, 1987. | MR | Zbl

Cité par Sources :