American Institute of Mathematical Sciences

Advanced
February  2013, 7(1): 39-56. doi: 10.3934/amc.2013.7.39

On dealer-free dynamic threshold schemes

Mehrdad Nojoumian 1, and  Douglas R. Stinson 2,

1. 

Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, United States
2. 

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

Received  April 2012 Published  January 2013

In a threshold scheme, the sensitivity of the secret as well as the number of players may fluctuate due to various reasons, e.g., mutual trust may vary or the structure of the players' organization might be changed. A possible solution to this problem is to modify the threshold and/or change the secret. Moreover, a common problem with almost all secret sharing schemes is that they are "one-time", meaning that the secret and shares are known to everyone after a public secret recovery process. This problem could be resolved if the dealer shares various secrets at the beginning, but a better solution is to dynamically generate new secrets in the absence of the dealer. These issues are our main motivation to revisit dynamic threshold schemes.
    Therefore, we first provide the first comprehensive study of threshold modification techniques in both the passive and active adversary models. We first review an existing method for threshold modification based on resharing shares of a secret; this method is secure in the setting of a passive adversarial coalition. We then discuss two methods, termed public evaluation (for threshold reduction) and zero addition (for threshold increase) that can be used in both the passive and active adversarial setting. In the case of an active adversary, the techniques make use of verifiable secret sharing schemes, whereas the schemes considered in the passive adversary model are all based on the Shamir scheme. As an application, we discuss how the threshold and the secret can be changed multiple times to arbitrary values after the scheme's initialization.
Keywords: unconditional security, threshold and secret changeability., Secret sharing.
Mathematics Subject Classification: Primary: 94A6.
Citation: Mehrdad Nojoumian, Douglas R. Stinson. On dealer-free dynamic threshold schemes. Advances in Mathematics of Communications, 2013, 7 (1) : 39-56. doi: 10.3934/amc.2013.7.39
References:
[1]

S. G. Barwick, W. A. Jackson and K. M. Martin, Updating the parameters of a threshold scheme by minimal broadcast,, IEEE Trans. Inform. Theory, 51 (2005), 620.  doi: 10.1109/TIT.2004.840857.  Google Scholar

[2]

D. Beaver, Multiparty protocols tolerating half faulty processors,, in, (1989), 560.   Google Scholar

[3]

M. Ben-Or, S. Goldwasser and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation,, in, (1988), 1.   Google Scholar

[4]

B. Blakley, G. R. Blakley, A. H. Chan and J. L. Massey, Threshold schemes with disenrollment,, in, (1992), 540.   Google Scholar

[5]

G. R. Blakley, Safeguarding cryptographic keys,, in, (1979), 313.   Google Scholar

[6]

C. Blundo, A. Cresti, A. De Santis and U. Vaccaro, Fully dynamic secret sharing schemes,, Theoret. Comp. Sci., 165 (1996), 407.   Google Scholar

[7]

B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults,, in, (1985), 383.   Google Scholar

[8]

P. D'Arco and D. R. Stinson, On unconditionally secure robust distributed key distribution centers,, in, (2002), 346.   Google Scholar

[9]

Y. Desmedt and S. Jajodia, Redistributing secret shares to new access structures and its applications,, in, (1997), 97.   Google Scholar

[10]

R. Gennaro, Y. Ishai, E. Kushilevitz and T. Rabin, The round complexity of verifiable secret sharing and secure multicast,, in, (2001), 580.   Google Scholar

[11]

R. Gennaro, M. O. Rabin and T. Rabin, Simplified vss and fast-track multiparty computations with applications to threshold cryptography,, in, (1998), 101.   Google Scholar

[12]

A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, Proactive secret sharing or: How to cope with perpetual leakage,, in, (1995), 339.   Google Scholar

[13]

I. Ingemarsson and G. J. Simmons, A protocol to set up shared secret schemes without the assistance of a mutualy trusted party,, in, (1990), 266.   Google Scholar

[14]

W.-A. Jackson, K. M. Martin and C. M. O'Keefe, Mutually trusted authority-free secret sharing schemes,, J. Cryptology, 10 (1997), 261.  doi: 10.1007/s001459900031.  Google Scholar

[15]

A. Maeda, A. Miyaji and M. Tada, Efficient and unconditionally secure verifiable threshold changeable scheme,, in, (2001), 403.   Google Scholar

[16]

K. Martin, Dynamic access policies for unconditionally secure secret sharing schemes,, in, (2005), 61.   Google Scholar

[17]

K. M. Martin, J. Pieprzyk, R. Safavi-Naini and H. X. Wang, Changing thresholds in the absence of secure channels,, in, (1999), 177.   Google Scholar

[18]

K. M. Martin, R. Safavi-Naini and H. X. Wang, Bounds and techniques for efficient redistribution of secret shares to new access structures,, Computer J., 42 (1999), 638.   Google Scholar

[19]

V. Nikov and S. Nikova, On proactive secret sharing schemes,, in, (2004), 308.   Google Scholar

[20]

M. Nojoumian, D. R. Stinson and M. Grainger, Unconditionally secure social secret sharing scheme,, IET Inform. Secur., 4 (2010), 202.  doi: 10.1049/iet-ifs.2009.0098.  Google Scholar

[21]

T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority,, in, (1989), 73.   Google Scholar

[22]

A. Shamir, How to share a secret,, Commun. ACM, 22 (1979), 612.  doi: 10.1145/359168.359176.  Google Scholar

[23]

R. Steinfeld, H. X. Wang and J. Pieprzyk, Lattice-based threshold-changeability for standard shamir secret-sharing schemes,, in, (2004), 170.   Google Scholar

[24]

D. R. Stinson and R. Z. Wei, Unconditionally secure proactive secret sharing scheme with combinatorial structures,, in, (1999), 200.   Google Scholar

[25]

C. Tartary and H. X. Wang, Dynamic threshold and cheater resistance for shamir secret sharing scheme,, in, (2006), 103.  doi: 10.1007/11937807_9.  Google Scholar

show all references

References:
[1]

S. G. Barwick, W. A. Jackson and K. M. Martin, Updating the parameters of a threshold scheme by minimal broadcast,, IEEE Trans. Inform. Theory, 51 (2005), 620.  doi: 10.1109/TIT.2004.840857.  Google Scholar

[2]

D. Beaver, Multiparty protocols tolerating half faulty processors,, in, (1989), 560.   Google Scholar

[3]

M. Ben-Or, S. Goldwasser and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation,, in, (1988), 1.   Google Scholar

[4]

B. Blakley, G. R. Blakley, A. H. Chan and J. L. Massey, Threshold schemes with disenrollment,, in, (1992), 540.   Google Scholar

[5]

G. R. Blakley, Safeguarding cryptographic keys,, in, (1979), 313.   Google Scholar

[6]

C. Blundo, A. Cresti, A. De Santis and U. Vaccaro, Fully dynamic secret sharing schemes,, Theoret. Comp. Sci., 165 (1996), 407.   Google Scholar

[7]

B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults,, in, (1985), 383.   Google Scholar

[8]

P. D'Arco and D. R. Stinson, On unconditionally secure robust distributed key distribution centers,, in, (2002), 346.   Google Scholar

[9]

Y. Desmedt and S. Jajodia, Redistributing secret shares to new access structures and its applications,, in, (1997), 97.   Google Scholar

[10]

R. Gennaro, Y. Ishai, E. Kushilevitz and T. Rabin, The round complexity of verifiable secret sharing and secure multicast,, in, (2001), 580.   Google Scholar

[11]

R. Gennaro, M. O. Rabin and T. Rabin, Simplified vss and fast-track multiparty computations with applications to threshold cryptography,, in, (1998), 101.   Google Scholar

[12]

A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, Proactive secret sharing or: How to cope with perpetual leakage,, in, (1995), 339.   Google Scholar

[13]

I. Ingemarsson and G. J. Simmons, A protocol to set up shared secret schemes without the assistance of a mutualy trusted party,, in, (1990), 266.   Google Scholar

[14]

W.-A. Jackson, K. M. Martin and C. M. O'Keefe, Mutually trusted authority-free secret sharing schemes,, J. Cryptology, 10 (1997), 261.  doi: 10.1007/s001459900031.  Google Scholar

[15]

A. Maeda, A. Miyaji and M. Tada, Efficient and unconditionally secure verifiable threshold changeable scheme,, in, (2001), 403.   Google Scholar

[16]

K. Martin, Dynamic access policies for unconditionally secure secret sharing schemes,, in, (2005), 61.   Google Scholar

[17]

K. M. Martin, J. Pieprzyk, R. Safavi-Naini and H. X. Wang, Changing thresholds in the absence of secure channels,, in, (1999), 177.   Google Scholar

[18]

K. M. Martin, R. Safavi-Naini and H. X. Wang, Bounds and techniques for efficient redistribution of secret shares to new access structures,, Computer J., 42 (1999), 638.   Google Scholar

[19]

V. Nikov and S. Nikova, On proactive secret sharing schemes,, in, (2004), 308.   Google Scholar

[20]

M. Nojoumian, D. R. Stinson and M. Grainger, Unconditionally secure social secret sharing scheme,, IET Inform. Secur., 4 (2010), 202.  doi: 10.1049/iet-ifs.2009.0098.  Google Scholar

[21]

T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority,, in, (1989), 73.   Google Scholar

[22]

A. Shamir, How to share a secret,, Commun. ACM, 22 (1979), 612.  doi: 10.1145/359168.359176.  Google Scholar

[23]

R. Steinfeld, H. X. Wang and J. Pieprzyk, Lattice-based threshold-changeability for standard shamir secret-sharing schemes,, in, (2004), 170.   Google Scholar

[24]

D. R. Stinson and R. Z. Wei, Unconditionally secure proactive secret sharing scheme with combinatorial structures,, in, (1999), 200.   Google Scholar

[25]

C. Tartary and H. X. Wang, Dynamic threshold and cheater resistance for shamir secret sharing scheme,, in, (2006), 103.  doi: 10.1007/11937807_9.  Google Scholar

[1]

Bagher Bagherpour, Shahrooz Janbaz, Ali Zaghian. Optimal information ratio of secret sharing schemes on Dutch windmill graphs. Advances in Mathematics of Communications, 2019, 13 (1) : 89-99. doi: 10.3934/amc.2019005
[2]

Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191
[3]

Ryutaroh Matsumoto. Strongly secure quantum ramp secret sharing constructed from algebraic curves over finite fields. Advances in Mathematics of Communications, 2019, 13 (1) : 1-10. doi: 10.3934/amc.2019001
[4]

Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 1-38. doi: 10.3934/amc.2013.7.1
[5]

Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413
[6]

Razvan Mosincat, Haewon Yoon. Unconditional uniqueness for the derivative nonlinear Schrödinger equation on the real line. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 47-80. doi: 10.3934/dcds.2020003
[7]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169
[8]

Dan Mangoubi. A gradient estimate for harmonic functions sharing the same zeros. Electronic Research Announcements, 2014, 21: 62-71. doi: 10.3934/era.2014.21.62
[9]

Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007
[10]

Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012
[11]

Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016
[12]

Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020057
[13]

Rafael Bravo De La Parra, Luis Sanz. A discrete model of competing species sharing a parasite. Discrete & Continuous Dynamical Systems - B, 2020, 25 (6) : 2121-2142. doi: 10.3934/dcdsb.2019204
[14]

Luiz Gustavo Farah. Local solutions in Sobolev spaces and unconditional well-posedness for the generalized Boussinesq equation. Communications on Pure & Applied Analysis, 2009, 8 (5) : 1521-1539. doi: 10.3934/cpaa.2009.8.1521
[15]

Jian Su, Yinnian He. The almost unconditional convergence of the Euler implicit/explicit scheme for the three dimensional nonstationary Navier-Stokes equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3421-3438. doi: 10.3934/dcdsb.2017173
[16]

Jian Mao, Qixiao Lin, Jingdong Bian. Application of learning algorithms in smart home IoT system security. Mathematical Foundations of Computing, 2018, 1 (1) : 63-76. doi: 10.3934/mfc.2018004
[17]

Jong Soo Kim, Won Chan Jeong. A model for buyer and supplier coordination and information sharing in order-up-to systems. Journal of Industrial & Management Optimization, 2012, 8 (4) : 987-1015. doi: 10.3934/jimo.2012.8.987
[18]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143
[19]

João Correia-da-Silva, Joana Pinho. The profit-sharing rule that maximizes sustainability of cartel agreements. Journal of Dynamics & Games, 2016, 3 (2) : 143-151. doi: 10.3934/jdg.2016007
[20]

Adriana Navarro-Ramos, William Olvera-Lopez. A solution for discrete cost sharing problems with non rival consumption. Journal of Dynamics & Games, 2018, 5 (1) : 31-39. doi: 10.3934/jdg.2018004

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (73)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences