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. Google Scholar

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

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

[4]

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

[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. Google Scholar

[6]

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

[7]

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

[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. Google Scholar

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. Google Scholar

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

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

[4]

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

[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. Google Scholar

[6]

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

[7]

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

[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. Google Scholar

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 & 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]

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

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

Bastian Laubner, Dierk Schleicher, Vlad Vicol. A combinatorial classification of postsingularly finite complex exponential maps. Discrete & Continuous Dynamical Systems - A, 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 & 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]

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
[12]

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
[13]

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

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
[15]

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

Wenxue Huang, Xiaofeng Li, Yuanyi Pan. Increase statistical reliability without losing predictive power by merging classes and adding variables. Big Data & Information Analytics, 2016, 1 (4) : 341-347. doi: 10.3934/bdia.2016014
[17]

A. Zeblah, Y. Massim, S. Hadjeri, A. Benaissa, H. Hamdaoui. Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony. Journal of Industrial & Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467
[18]

Masoud Ebrahimi, Seyyed Mohammad Taghi Fatemi Ghomi, Behrooz Karimi. Application of the preventive maintenance scheduling to increase the equipment reliability: Case study- bag filters in cement factory. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018146
[19]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[20]

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

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (32)
  • HTML views (101)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences