On dealer-free dynamic threshold schemes

Mehrdad Nojoumian; Douglas R. Stinson

doi:10.3934/amc.2013.7.39

Article Contents

2013, Volume 7, Issue 1: 39-56. Doi: 10.3934/amc.2013.7.39

This issue Previous Article Another look at security definitions Next Article Self-dual $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes with an automorphism of prime order

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
2.
David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1

Received: April 2012

Published: February 2013

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A60.

Citation:

Related Papers

Cited by

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-633.doi: 10.1109/TIT.2004.840857.
[2]	D. Beaver, Multiparty protocols tolerating half faulty processors, in "9th Annual International Cryptology Conference, CRYPTO,'' Springer, (1989), 560-572.
[3]	M. Ben-Or, S. Goldwasser and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in "20th Annual ACM Symposium on Theory of Computing, STOC,'' (1988), 1-10.
[4]	B. Blakley, G. R. Blakley, A. H. Chan and J. L. Massey, Threshold schemes with disenrollment, in "CRYPTO,'' (1992), 540-548.
[5]	G. R. Blakley, Safeguarding cryptographic keys, in "National Computer Conference,'' AFIPS Press, (1979), 313-317.
[6]	C. Blundo, A. Cresti, A. De Santis and U. Vaccaro, Fully dynamic secret sharing schemes, Theoret. Comp. Sci., 165 (1996), 407-440.
[7]	B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults, in "26th Annual IEEE Symposium on Foundations of Computer Science, FOCS,'' (1985), 383-395.
[8]	P. D'Arco and D. R. Stinson, On unconditionally secure robust distributed key distribution centers, in "8th Int. Conf. on the Theory and Application of Cryptology and Info. Security, ASIACRYPT,'' Springer, (2002), 346-363.
[9]	Y. Desmedt and S. Jajodia, Redistributing secret shares to new access structures and its applications, in "Technical Report ISSE TR-97-01,'' George Mason Univ., 1997.
[10]	R. Gennaro, Y. Ishai, E. Kushilevitz and T. Rabin, The round complexity of verifiable secret sharing and secure multicast, in "33th Annual ACM Symposium on Theory of Computing, STOC,'' (2001), 580-589.
[11]	R. Gennaro, M. O. Rabin and T. Rabin, Simplified vss and fast-track multiparty computations with applications to threshold cryptography, in "17th annual ACM symposium on Principles of Distributed Computing, PODC,'' (1998), 101-111.
[12]	A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, Proactive secret sharing or: How to cope with perpetual leakage, in "15th Annual International Cryptology Conference, CRYPTO,'' Springer, (1995), 339-352.
[13]	I. Ingemarsson and G. J. Simmons, A protocol to set up shared secret schemes without the assistance of a mutualy trusted party, in "EUROCRYPT'' (I. Damgård), Springer, (1990), 266-282.
[14]	W.-A. Jackson, K. M. Martin and C. M. O'Keefe, Mutually trusted authority-free secret sharing schemes, J. Cryptology, 10 (1997), 261-289.doi: 10.1007/s001459900031.
[15]	A. Maeda, A. Miyaji and M. Tada, Efficient and unconditionally secure verifiable threshold changeable scheme, in "6th Australasian Conference Information Security and Privacy, ACISP,'' Springer, (2001), 403-416.
[16]	K. Martin, Dynamic access policies for unconditionally secure secret sharing schemes, in "Proceedings of IEEE Information Theory Workshop (ITW 2005),'' IEEE, (2005), 61-66.
[17]	K. M. Martin, J. Pieprzyk, R. Safavi-Naini and H. X. Wang, Changing thresholds in the absence of secure channels, in "4th Australasian Conference Information Security and Privacy, ACISP,'' Springer, (1999), 177-191.
[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-649.
[19]	V. Nikov and S. Nikova, On proactive secret sharing schemes, in "11th International Workshop on Selected Areas in Cryptography, SAC,'' Springer, (2004), 308-325.
[20]	M. Nojoumian, D. R. Stinson and M. Grainger, Unconditionally secure social secret sharing scheme, IET Inform. Secur., 4 (2010), 202-211.doi: 10.1049/iet-ifs.2009.0098.
[21]	T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, in "21st Annual ACM Symposium on Theory of Computing, STOC,'' (1989), 73-85.
[22]	A. Shamir, How to share a secret, Commun. ACM, 22 (1979), 612-613.doi: 10.1145/359168.359176.
[23]	R. Steinfeld, H. X. Wang and J. Pieprzyk, Lattice-based threshold-changeability for standard shamir secret-sharing schemes, in "10th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT,'' Springer, (2004), 170-186.
[24]	D. R. Stinson and R. Z. Wei, Unconditionally secure proactive secret sharing scheme with combinatorial structures, in "6th Annual Int. Workshop on Selected Areas in Cryptography, SAC,'' Springer, (1999), 200-214.
[25]	C. Tartary and H. X. Wang, Dynamic threshold and cheater resistance for shamir secret sharing scheme, in "2nd SKLOIS Conference on Information Security and Cryptology, Inscrypt,'' Springer, (2006), 103-117.doi: 10.1007/11937807_9.