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]

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

[17]

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

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

Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057
[20]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks & Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (57)
  • HTML views (232)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences