American Institute of Mathematical Sciences

Advanced
November  2019, 13(4): 601-612. doi: 10.3934/amc.2019037

A network reliability approach to the analysis of combinatorial repairable threshold schemes

Bailey Kacsmar and  Douglas R. Stinson ,

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

* Corresponding author: Douglas R. Stinson

Received  November 2018 Revised  January 2019 Published  June 2019

Fund Project: The second author is supported by NSERC discovery grant RGPIN-03882.

A repairable threshold scheme (which we abbreviate to RTS) is a $ (\tau,n) $-threshold scheme in which a subset of players can "repair" another player's share in the event that their share has been lost or corrupted. This will take place without the participation of the dealer who set up the scheme. The repairing protocol should not compromise the (unconditional) security of the threshold scheme. Combinatorial repairable threshold schemes (or combinatorial RTS) were recently introduced by Stinson and Wei [8]. In these schemes, "multiple shares" are distributed to each player, as defined by a suitable combinatorial design called the distribution design. In this paper, we study the reliability of these combinatorial repairable threshold schemes in a setting where players may not be available to take part in a repair of a given player's share. Using techniques from network reliability theory, we consider the probability of existence of an available repair set, as well as the expected number of available repair sets, for various types of distribution designs.

Keywords: Threshold scheme, combinatorial repairability, reliability.
Mathematics Subject Classification: Primary: 94A62; Secondary: 05B05, 90B25.
Citation: Bailey Kacsmar, Douglas R. Stinson. A network reliability approach to the analysis of combinatorial repairable threshold schemes. Advances in Mathematics of Communications, 2019, 13 (4) : 601-612. doi: 10.3934/amc.2019037
References:
[1]

J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, Lecture Notes in Computer Science, 403 (1990), 27-35 (CRYPTO '88 Proceedings). doi: 10.1007/0-387-34799-2_3.

[2] C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, 1987. 
[3]

C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition, Chapman & Hall/CRC, Boca Raton, FL, 2007.

[4]

B. Kacsmar, Designing Efficient Algorithms for Combinatorial Repairable Threshold Schemes, Masters Thesis, University of Waterloo, 2018.

[5]

T. M. Laing and D. R. Stinson, A survey and refinement of repairable threshold schemes, Journal of Mathematical Cryptology, 12 (2018), 57-81.  doi: 10.1515/jmc-2017-0058.

[6]

A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176.

[7]

D. R. Stinson and M. B. Paterson, Cryptography. Theory and Practice, Chapman & Hall/CRC, Boca Raton, 2019.

[8]

D. R. Stinson and R. Wei, Combinatorial repairability for threshold schemes, Designs, Codes and Cryptography, 86 (2018), 195-210.  doi: 10.1007/s10623-017-0336-6.

show all references

References:
[1]

J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, Lecture Notes in Computer Science, 403 (1990), 27-35 (CRYPTO '88 Proceedings). doi: 10.1007/0-387-34799-2_3.

[2] C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, 1987. 
[3]

C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition, Chapman & Hall/CRC, Boca Raton, FL, 2007.

[4]

B. Kacsmar, Designing Efficient Algorithms for Combinatorial Repairable Threshold Schemes, Masters Thesis, University of Waterloo, 2018.

[5]

T. M. Laing and D. R. Stinson, A survey and refinement of repairable threshold schemes, Journal of Mathematical Cryptology, 12 (2018), 57-81.  doi: 10.1515/jmc-2017-0058.

[6]

A. Shamir, How to share a secret, Communications of the ACM, 22 (1979), 612-613.  doi: 10.1145/359168.359176.

[7]

D. R. Stinson and M. B. Paterson, Cryptography. Theory and Practice, Chapman & Hall/CRC, Boca Raton, 2019.

[8]

D. R. Stinson and R. Wei, Combinatorial repairability for threshold schemes, Designs, Codes and Cryptography, 86 (2018), 195-210.  doi: 10.1007/s10623-017-0336-6.

Table 1.  Expected number of repair sets for $ {\mathtt{SQS}}(v) $
size type expected number
2 $ 3(r_2-1)^2 p^2 $
3 pair-pair-pair $ 4(r_2-1)^3 p^3 $
3 pair-pair-point $ 12(r_2-1)^2(r_1-3r_2+2) p^3 $
3 pair-point-point $ 6(r_2-1)(r_1-3r_2+2)^2 p^3 $
4 $ (r_1-3r_2+2)^4 p^4 $
Table Options

Download as excel

size type expected number
2 $ 3(r_2-1)^2 p^2 $
3 pair-pair-pair $ 4(r_2-1)^3 p^3 $
3 pair-pair-point $ 12(r_2-1)^2(r_1-3r_2+2) p^3 $
3 pair-point-point $ 6(r_2-1)(r_1-3r_2+2)^2 p^3 $
4 $ (r_1-3r_2+2)^4 p^4 $
[1]

Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial and Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141
[2]

M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13
[3]

JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003
[4]

Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder. Combinatorial batch codes and transversal matroids. Advances in Mathematics of Communications, 2010, 4 (3) : 419-431. doi: 10.3934/amc.2010.4.419
[5]

Yuebo Shen, Dongdong Jia, Gengsheng Zhang. The results on optimal values of some combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (4) : 681-690. doi: 10.3934/amc.2018040
[6]

Joshua L. Mike, Vasileios Maroulas. Combinatorial Hodge theory for equitable kidney paired donation. Foundations of Data Science, 2019, 1 (1) : 87-101. doi: 10.3934/fods.2019004
[7]

Bastian Laubner, Dierk Schleicher, Vlad Vicol. A combinatorial classification of postsingularly finite complex exponential maps. Discrete and Continuous Dynamical Systems, 2008, 22 (3) : 663-682. doi: 10.3934/dcds.2008.22.663
[8]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial and Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515
[9]

Cuiling Fan, Koji Momihara. Unified combinatorial constructions of optimal optical orthogonal codes. Advances in Mathematics of Communications, 2014, 8 (1) : 53-66. doi: 10.3934/amc.2014.8.53
[10]

Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165
[11]

Jiaoyan Wang, Jianzhong Su, Humberto Perez Gonzalez, Jonathan Rubin. A reliability study of square wave bursting $\beta$-cells with noise. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 569-588. doi: 10.3934/dcdsb.2011.16.569
[12]

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial and Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211
[13]

Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021142
[14]

Tak Kuen Siu, Howell Tong, Hailiang Yang. Option pricing under threshold autoregressive models by threshold Esscher transform. Journal of Industrial and Management Optimization, 2006, 2 (2) : 177-197. doi: 10.3934/jimo.2006.2.177
[15]

Xinli Hu. Threshold dynamics for a Tuberculosis model with seasonality. Mathematical Biosciences & Engineering, 2012, 9 (1) : 111-122. doi: 10.3934/mbe.2012.9.111
[16]

M. P. Moschen, A. Pugliese. The threshold for persistence of parasites with multiple infections. Communications on Pure and Applied Analysis, 2008, 7 (6) : 1483-1496. doi: 10.3934/cpaa.2008.7.1483
[17]

Erisa Hasani, Kanishka Perera. On the compactness threshold in the critical Kirchhoff equation. Discrete and Continuous Dynamical Systems, 2022, 42 (1) : 1-19. doi: 10.3934/dcds.2021106
[18]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

[19]

Jon Fickenscher. A combinatorial proof of the Kontsevich-Zorich-Boissy classification of Rauzy classes. Discrete and Continuous Dynamical Systems, 2016, 36 (4) : 1983-2025. doi: 10.3934/dcds.2016.36.1983
[20]

Pradeep Kumar Mishra, Vassil Dimitrov. A combinatorial interpretation of double base number system and some consequences. Advances in Mathematics of Communications, 2008, 2 (2) : 159-173. doi: 10.3934/amc.2008.2.159

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (280)
  • HTML views (340)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy