×

Fully dynamic secret sharing schemes. (English) Zbl 0872.68034

Summary: We consider secret sharing schemes in which the dealer is able (after a preprocessing stage) to activate a particular access structure out of a given set and/or to allow the participants to reconstruct different secrets (in different time instants) by sending them the same broadcast message. We establish a formal setting to study secret sharing schemes of this kind. The security of the schemes presented is unconditional, since they are not based on any computational assumption. We give bounds on the size of the shares held by participants, on the size of the broadcast message, and on the randomness needed in such schemes.

MSC:

68P25 Data encryption (aspects in computer science)
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blakley, G. R., Safeguarding cryptographic keys, (Proc. AFIPS 1979 National Computer Conf. (June 1979)), 313-317
[2] Blakley, B.; Blakley, G. R.; Chan, A. H.; Massey, J., Threshold Schemes with Disenrollment, (Brickell, E., Advances in Cryptology — CRYPTO ’92. Advances in Cryptology — CRYPTO ’92, Lecture Notes in Computer Science, Vol. 740 (1993), Springer: Springer Berlin), 546-554 · Zbl 0809.94016
[3] Blundo, C., A Note on Dynamic Threshold Schemes, Inform. Process. Lett., 55, 189-193 (1995) · Zbl 0875.68380
[4] C. Blundo, A. De Santis, R. De Simone and U. Vaccaro, Tight bounds on the information rate of secret sharing schemes, Design Codes Cryptography, to appear.; C. Blundo, A. De Santis, R. De Simone and U. Vaccaro, Tight bounds on the information rate of secret sharing schemes, Design Codes Cryptography, to appear. · Zbl 0878.94050
[5] Blundo, C.; De Santis, A.; Gargano, L.; Vaccaro, U., Advances in Cryptology, CRYPTO ’92, (Lecture Notes in Computer Science, Vol. 740 (1993), Springer: Springer Berlin), 149-169, a preliminary version appeared in · Zbl 0803.00037
[6] Blundo, C.; De Santis, A.; Stinson, D. R.; Vaccaro, U., Advances in Cryptology — Eurocrypt ’92, (Rueppel, R., Lecture Notes in Computer Science, Vol. 658 (1993), Springer: Springer Berlin), 1-24, A preliminary version appeared in: · Zbl 0789.94005
[7] Blundo, C.; De Santis, A.; Vaccaro, U., Randomness in distribution protocols, (Abiteboul, Serge; Shamir, Eli, 21st Internat. Colloq. on Automata, Languages and Programming (ICALP ’94). 21st Internat. Colloq. on Automata, Languages and Programming (ICALP ’94), Lecture Notes in Computer Science, Vol. 820 (1994), Springer: Springer Berlin), 568-579 · Zbl 1418.68079
[8] Blundo, C.; De Santis, A.; Vaccaro, U., On secret sharing schemes, (Technical Report (1995), University di Salerno) · Zbl 0949.94506
[9] Blundo, C.; Gaggia, A. Giorgio; Stinson, D. R., On the dealer’s randomness required in secret sharing schemes, (De Santis, A., Advances in Cryptology — Eurocrypt ’94. Advances in Cryptology — Eurocrypt ’94, Lecture Notes in Computer Science, Vol. 950 (1995), Springer: Springer Berlin), 35-46 · Zbl 0885.94018
[10] Brickell, E. F.; Davenport, D. M., On the classification of ideal secret sharing schemes, J. Cryptology, 4, 2, 123-134 (1991) · Zbl 0747.94010
[11] Brickell, E. F.; Stinson, D. R., Some improved bounds on the information rate of perfect secret sharing schemes, J. Cryptology, 5, 3, 153-166 (1992) · Zbl 0763.94008
[12] Capocelli, R. M.; De Santis, A.; Gargano, L.; Vaccaro, U., On the size of shares for secret sharing schemes, J. Cryptology, 6, 3, 157-169 (1993) · Zbl 0786.68030
[13] Csimarz, L., The size of a share must be large, (De Santis, A., Advances in Cryptology — EUROCRYPT ’94. Advances in Cryptology — EUROCRYPT ’94, Lecture Notes in Computer Science, Vol. 950 (1995), Springer: Springer Berlin), 13-22 · Zbl 0885.94020
[14] Csiszár, I.; Körner, J., Information Theory. Coding Theorems for Discrete Memoryless Systems (1981), Academic Press: Academic Press New York · Zbl 0568.94012
[15] De Santis, A.; Gaggia, A. Giorgio, An Analysis of Shares in Secret Sharing Schemes, (Technical Report (1995), University di Salerno) · Zbl 1006.94538
[16] Gallager, R. G., Information Theory and Reliable Communications (1968), Wiley: Wiley New York · Zbl 0198.52201
[17] Goldreich, O.; Micali, S.; Wigderson, A., How to play any mental game, (Proc. 19th Annual ACM Symp. on Theory of Computing (1987)), 218-229
[18] Harn, L.; Hwang, T.; Laih, C.; Lee, J., Dynamic threshold scheme based on the definition of crossproduct in a N-dimensional linear space, (Brassard, J., Advances in Cryptology — Eurocrypt ’89. Advances in Cryptology — Eurocrypt ’89, Lecture Notes in Computer Science, Vol. 435 (1990), Springer: Springer Berlin), 286-298
[19] Impagliazzo, R.; Zuckerman, D., How to recycle random bits, (Proc. 30th Annual Symp. of Computer Science (1989)), 248-255
[20] Karnin, E. D.; Greene, J. W.; Hellman, M. E., On secret sharing systems, IEEE Trans. Inform. Theory, IT-29, 1, 35-41 (1983) · Zbl 0503.94018
[21] Knuth, D. E.; Yao, A. C., The complexity of nonuniform random number generation, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York), 357-428 · Zbl 0395.65004
[22] Kothari, S. C., Generalized linear threshold schemes, (Blakley, G. R.; Chaum, D., Advances in Cryptology — CRYPTO ’84. Advances in Cryptology — CRYPTO ’84, Lecture Notes in Computer Science, Vol. 196 (1985), Springer: Springer Berlin), 231-241 · Zbl 0571.94016
[23] Krizanc, D.; Peleg, D.; Upfal, E., A time-randomness tradeoff for oblivious routing, (Proc. 20th Annual ACM Symp. on Theory of Computing (1988)), 93-102
[24] Martin, K. M., Discrete structures in the theory of secret sharing, (Ph.D. Thesis (1991), University of London)
[25] Martin, K. M., Untrustworthy participants in perfect secret sharing schemes, (Proc. 3rd IMA Conf. on Coding and Cryptology (1991)), Cirencester · Zbl 0814.94015
[26] Shamir, A., How to share a secret, Comm. ACM, 22, 11, 612-613 (1979) · Zbl 0414.94021
[27] Simmons, G. J., How to (really) share a secret, (Goldwasser, S., Advances in Cryptology — CRYPTO, 88. Advances in Cryptology — CRYPTO, 88, Lecture Notes in Computer Science, Vol. 403 (1989), Springer: Springer Berlin), 390-448 · Zbl 0951.94541
[28] Simmons, G. J., An introduction to shared secret and/or shared control schemes and their application, (Simmons, G. J., Contemporary Cryptology (1991), IEEE Press: IEEE Press New York), 441-497
[29] Simmons, G. J.; Jackson, W.; Martin, K. M., The geometry of shared secret schemes, Bulle. ICA, 1, 71-88 (1991) · Zbl 0826.94018
[30] Stinson, D. R., An explication of secret sharing schemes, Design Codes Cryptography, 2, 357-390 (1992) · Zbl 0793.68111
[31] Stinson, D. R., New general lower bounds on the information rate of secret sharing schemes, (Brockell, E., Advances in Cryptology — CRYPTO ’92. Advances in Cryptology — CRYPTO ’92, Lecture Notes in Computer Science, Vol. 740 (1993), Springer: Springer Berlin), 170-184 · Zbl 0809.94010
[32] Stinson, D. R., Decomposition constructions for secret sharing schemes, IEEE Trans. Inform. Theory, IT-40, 118-125 (1994) · Zbl 0803.94017
[33] Sun, H.-U.; Shieh, S.-P., On dynamic threshold schemes, Inform. Process. Lett., 52, 201-206 (1994) · Zbl 0808.94021
[34] van Dijk, M., On the information rate of perfect secret sharing schemes, Design, Codes, Cryptography, 2, 143-169 (1995) · Zbl 0829.94006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.