Article Contents
Article Contents

# Optimal information ratio of secret sharing schemes on Dutch windmill graphs

• * Corresponding author: Bagher Bagherpour
• One of the basic problems in secret sharing is to determine the exact values of the information ratio of the access structures. This task is important from the practical point of view, since the security of any system degrades as the amount of secret information increases.

A Dutch windmill graph consists of the edge-disjoint cycles such that all of them meet in one vertex. In this paper, we determine the exact information ratio of secret sharing schemes on the Dutch windmill graphs. Furthermore, we determine the exact ratio of some related graph families.

Mathematics Subject Classification: Primary: 94A60, 94A62.

 Citation:

• Figure 1.  The Dutch windmill graph $D_4^{(k)}$ with predefined labelling

Figure 2.  The friendship graph $F_k$ with predefined labelling

Table 1.  Subgraphs of the graph $C(\mathcal{F}_k)$

 $G$ $V$ $S_1(V)$ $\{v_c, v^{1}_2, v^{1}_{n_1}, \ldots, v^{k}_{2}, v^{k}_{n_k}\}$ $\Pi_1 =\{(2k-1) \times S_{1}(V)\}$ $S^{i}_{1}(V)$$i\in \{1, \ldots, k\} \{v_c, v^{i}_2, v^{i}_{3}\} \Pi_2 =\{1 \times S^{i}_1(V): i\in \{1, \ldots, k\}\} S^{i}_{2}(V)$$i\in \{1, \ldots, k\}$ $\{v_c, v^{i}_{n_i}, v^{i}_{n_i-1}\}$ $\Pi_3 =\{1 \times S^{i}_{2}(V): i\in \{1, \ldots, k\}\}$ $P^{i}_1(V)$$i\in \{1, \ldots, k\} \{v^{i}_2, v^{i}_3, \ldots, v^{i}_{n_i}\} \Pi_4 =\{(2k-1) \times P^{i}_1(V): i \in \{1, \ldots, k\}\} P^{i}_2(V)$$i\in \{1, \ldots, k\}$ $\{v^{i}_3, v^{i}_{4}, \ldots, v^{i}_{n_i-1}\}$ $\Pi_5 =\{1 \times P^{i}_2(V): i \in \{1, \ldots, k\}\}$

Table 2.  Subgraphs of the graph $C'(\mathcal{F}_k)$

 $G$ $V$ $S_1(V)$ $\{v_c, v', v^{1}_2, v^{1}_{n_1}, \ldots, v^{k}_{2}, v^{k}_{n_k}\}$ $\Pi_1 =\{(2k) \times S_{1}(V)\}$ $S^{i}_{1}(V)$$i\in \{1, \ldots, k\} \{v_c, v^{i}_2, v^{i}_{3}\} \Pi_2 =\{1 \times S^{i}_1(V): i\in \{1, \ldots, k\}\} S^{i}_{2}(V)$$i\in \{1, \ldots, k\}$ $\{v_c, v^{i}_{n_i}, v^{i}_{n_i-1}\}$ $\Pi_3 =\{1 \times S^{i}_{2}(V): i\in \{1, \ldots, k\}\}$ $S'(V)$ $\{v_c, v' \}$ $\Pi_4 =\{1 \times S'(V) \}$ $P^{i}_1(V)$$i\in \{1, \ldots, k\} \{v^{i}_2, v^{i}_3, \ldots, v^{i}_{n_i}\} \Pi_5 =\{2k \times P^{i}_1(V): i \in \{1, \ldots, k\}\} P^{i}_2(V)$$i\in \{1, \ldots, k\}$ $\{v^{i}_3, v^{i}_{4}, \ldots, v^{i}_{n_i-1}\}$ $\Pi_6 =\{1 \times P^{i}_2(V): i \in \{1, \ldots, k\}\}$

Table 3.  Subgraphs of the graph $D^{(k)}_{4}$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v_c, v_1, v_3, \ldots, v_{3k-2}, v_{3k}\}$ $\{v_c v_j , v_c v_{j+2}:$ $j \in \{1, 4, \ldots, 3k-2 \}\}$ $G_{1+(i+2)/3}$$i\in \{1, 4, \ldots 3k-2 \} \{v_c, v_i, v_{i+1}, v_{i+2}\} \{ v_c v_i, v_c v_{i+2}, v_i v_{i+1}, v_{i+1} v_{i+2}\} G_{k+1+(i+2)/3}$$i\in \{1, 4, \ldots, 3k-2 \}$ $\{v_i, v_{i+1}, v_{i+2}\}$ $\{ v_i v_{i+1}, v_{i+1} v_{i+2}\}$

Table 4.  Subgraphs of the graph $D'^{(k)}_{4}$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v_c, v_1, v_3, \ldots, v_{3k-2}, v_{3k},$ $v'\}$ $\{v_c v_j , v_c v_{j+2}, v_c v': j\in\{1, 4,$ $\ldots, 3k-2\}\}$ $G_{1+(i+2)/3}$$i\in \{1, 4, \ldots 3k-2 \} \{v_c, v_i, v_{i+1}, v_{i+2}\} \{ v_c v_i, v_c v_{i+2}, v_i v_{i+1}, v_{i+1} v_{i+2}\} G_{k+2} \{v_c, v' \} \{v_c v' \} G_{k+2+(i+2)/3}$$i\in \{1, 4, \ldots, 3k-2 \}$ $\{v_i, v_{i+1}, v_{i+2}\}$ $\{ v_i v_{i+1}, v_{i+1} v_{i+2}\}$

Table 5.  Subgraphs of the graph $v\nabla \mathcal{F}_k$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v, V(H_1), V(H_2),$ $\ldots, V(H_k)\}$ $\{v w: w \in \{ V(H_1), \ldots, V(H_k)\}\}$ $G_{1+i}$$i\in \{1, \ldots, k\} \{v, V(H_i)\} \{ E(H_i), v w:w \in V(H_i) \} G_{k+1+i}$$i\in \{1, \cdots, k \}$ $V(H_i)$ $E(H_i)$

Table 6.  Subgraphs of the graph $v\nabla \mathcal{F'}_k$

 $G$ $V(G)$ $E(G)$ $G_1$ $\{v, V(H_1), \ldots, V(H_k), v'\}$ $\{v v', v w: w \in \{ V(H_1), \ldots, V(H_k) \}$ $G_{1+i}$$i\in \{1, \ldots, k\} \{v, V(H_i)\} \{ E(H_i), v w:w \in V(H_i) \} G_{k+2} \{v, v'\} \{v v' \} G_{k+2+i}$$i\in \{1, \cdots, k \}$ $V(H_i)$ $E(H_i)$
•  [1] J. C. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, Advances in Cryptology-Crpto 88 Proceedings, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 403 (1990), 27-35. doi: 10.1007/0-387-34799-2_3. [2] G. R. Blakley, Safeguarding Cryptographic Keys, in AFIPS Conference Proceedings, 48 (1979), 313-317. [3] C. Blundo, A. De Santis, D. R. Stinson and U. Vaccaro, Graph decompositions and secret sharing schemes, Advances in Cryptology-Proceeding of Eurocrypt 92, Lecture Notes in Comput. Sci, 658 (1993), 1-24.  doi: 10.1007/3-540-47555-9_1. [4] C. Blundo, A. De Santis and U. Vaccaro, Tight bounds on the information rate of secret sharing schemes, Designs Codes and Cryptography, 11 (1997), 107-122.  doi: 10.1023/A:1008216403325. [5] C. Blundo, A. De Santis, L. Gargano and U. Vaccaro, On the information rate of secret sharing schemes, Theoretical Computer Science, 154 (1996), 283-306.  doi: 10.1016/0304-3975(95)00065-8. [6] E. F. Brickell and D. M. Davenport, On the classification of ideal secret sharing schemes, Journal of Cryptology, 4 (1993), 157-167. [7] R. M. Capocelli, A. De Santis, L. Gargano and U. Vaccaro, On the size of shares for secret sharing schemes, Journal of Cryptology, 6 (1993), 157-169. [8] T. M. Cover and J.A. Thomas, Elements of Information Theory, 2$^{nd}$ edition, John Wiley and Sons, Inc., Hoboken, New Jersey, 2006. [9] L. Csirmas, The size of a share must be large, Journal of Cryptology, 10 (1997), 223-231.  doi: 10.1007/s001459900029. [10] L. Csirmas, An impossibility result on graph secret sharing, Designs Codes and Cryptography, 53 (2009), 195-209.  doi: 10.1007/s10623-009-9304-0. [11] L. Csirmaz and G. Tardos, Optimal information rate of secret sharing schemes on trees, IEEE Transaction on Information Theory, 59 (2013), 2527-2530.  doi: 10.1109/TIT.2012.2236958. [12] L. Csirmaz and P. Ligeti, On an infinite family of graphs with information ratio $1-\frac{2}{k}$, Computing, 85 (2009), 127-136.  doi: 10.1007/s00607-009-0039-6. [13] P. Erdős, A. Rényi and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar, 1 (1966), 215-235. [14] R. G. Gallager, Information Theory and Reliable Communications, John Wiley, New York, 1986. [15] M. Ito, A. Saito and T. Nishizeki, Secret sharing scheme realizing general access structure, Proc. IEEE Globecorn, Tokyo, 87 (1987), 99-102. [16] M. Ito, A. Saito and T. Nishizeki, Multiple assignment scheme for sharing secret, Journal of Cryptology, 6 (1993), 15-20.  doi: 10.1007/BF02620229. [17] W. Jackson and Keith M. Martin, Perfect secret sharing schemes on five participants, Designs. Codes and Cryptography, 9 (1996), 267-286.  doi: 10.1007/BF00129769. [18] C. Padró and G. Sáez, Secret sharing with bipartite access structure, IEEE Transaction on Information Theory, 46 (2000), 2596-2604.  doi: 10.1109/18.887867. [19] C. Padró and L. Vazquez, Finding lower bounds on the complexity of secret sharing schemes by linear programming, Ninth Latin American Theoretical Informatics Symposium, LATIN 2010, Lecture Notes in Computer Science, 6034 (2010), 344-355.  doi: 10.1007/978-3-642-12200-2_31. [20] A. Shamir, How to share a secret, Communication of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176. [21] D. R. Stinson, Decomposition constructions for secret sharing schemes, IEEE Transaction on Information Theory, 40 (1994), 118-125.  doi: 10.1109/18.272461. [22] D. R. Stinson, An explication of secret sharing schemes, Designs Codes and Cryptography, 2 (1992), 357-390.  doi: 10.1007/BF00125203. [23] H. M. Sun and B. L. Chen, Weighted decomposition construction for perfect secret sharing schemes, Compute Math. Appl., 43 (2002), 877-887.  doi: 10.1016/S0898-1221(01)00328-5. [24] M. Van dijk, On the information rate of perfect secret sharing schemes, Designs, Codes and Cryptography, 6 (1995), 143-169.  doi: 10.1007/BF01398012.

Figures(2)

Tables(6)