Abstract
The work addresses the problem of cheating prevention in secret sharing. Two cheating scenarios are considered. In the first one, the cheaters always submit invalid shares to the combiner. In the second one, the cheaters collectively decide which shares are to be modified so the combiner gets a mixture of valid and invalid shares from the cheaters. The secret scheme is said to be k-cheating immune if any group of k cheaters has no advantage over honest participants. The paper investigates cryptographic properties of the defining function of secret sharing so the scheme is k-cheating immune. Constructions of secret sharing immune against k cheaters are given.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Carpentieri. A perfect threshold secret sharing scheme to identify cheaters. Designs, Codes and Cryptography, 5(3):183–187, 1995.
M. Carpentieri, A. De Santis, and U. Vaccaro. Size of shares and probability of cheating in threshold schemes. In T. Helleseth, editor, Advances in Cryptology-EUROCRYPT’93, LNCS No 765, pages 118–125. Springer-Verlag, 1993.
C. Ding, D. Pei and A Salomaa. Chinese remainder theorem: applications in computing, coding and cryptography. World Scientific, Singapore, 1996
P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 427–437. IEEE, 1987.
F.J. MacWilliams and N.J.A. Sloane. The theory of error-correcting codes. North-Holland, Amsterdam, 1977.
K. Nyberg. On the construction of highly nonlinear permutations. In Advances in Cryptology-EUROCRYPT’92, LNCS No 658, pages 92–98. Springer-Verlag, 1993.
K. Nyberg and L. R. Knudsen. Provable security against differential cryptanalysis. In Advances in Cryptology-CRYPTO’92, LNCS No 740, pages 566–574. Springer-Verlag, 1993.
T.P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology-CRYPTO’91, LNCS No 576, pages 129–140. Springer-Verlag, 1992.
J. Pieprzyk and X. M. Zhang. Cheating prevention in secret sharing over GF(p t). to appear in Indocrypt 2001.
B. Preneel, W. V. Leekwijck, L. V. Linden, R. Govaerts, and J. Vandewalle. Propagation characteristics of boolean functions. In Advances in Cryptology-EUROCRYPT’90, LNCS No 437, pages 155–165. Springer-Verlag, 1991.
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of 21st ACM Symposium on Theory of Computing, pages 73–85, 1989.
O. S. Rothaus. On “bent” functions. Journal of Combinatorial Theory (A), 20:300–305, 1976.
B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In M. Wiener, editor, Advances in Cryptology-CRYPTO’99, LNCS No 1666, pages 148–164. Springer-Verlag, 1999.
J. Seberry, X. M. Zhang, and Y. Zheng. On constructions and nonlinearity of correlation immune functions. In Advances in Cryptology-EUROCRYPT’93, LNCS No 765, pages 181–199. Springer-Verlag, 1994.
J. Seberry, X. M. Zhang, and Y. Zheng. Nonlinearity and propagation characteristics of balanced boolean functions. Information and Computation, 119(1):1–13, 1995.
T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory, IT-30 No. 5:776–779, 1984.
M. Stadler. Publicly verifiable secret sharing. In U. Maurer, editor, Advances in Cryptology-EUROCRYPT’96, LNCS No 1070, pages 190–199. Springer-Verlag, 1996.
D.R. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.
A. F. Webster and S. E. Tavares. On the design of S-boxes. In Advances in Cryptology-CRYPTO’85, LNCS No 219, pages 523–534. Springer-Verlag, 1986.
Martin Tompa and Heather Woll. How to share a secret with cheaters. In A.M. Odlyzko, editor, Advances in Cryptology-CRYPTO’86, LNCS No 263, pages 261–265. Springer-Verlag, 1987.
X. M. Zhang and J. Pieprzyk, Cheating immune secret sharing. to appear in The Third International Conference on Information and Communication Security (ICICS) 2001.
X. M. Zhang and Y. Zheng. Cryptographically resilient functions. IEEE Transactions on Information Theory, 43(5):1740–1747, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pieprzyk, J., Xian-Mo, Z. (2002). Constructions of Cheating Immune Secret Sharing. In: Kim, K. (eds) Information Security and Cryptology — ICISC 2001. ICISC 2001. Lecture Notes in Computer Science, vol 2288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45861-1_18
Download citation
DOI: https://doi.org/10.1007/3-540-45861-1_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43319-4
Online ISBN: 978-3-540-45861-6
eBook Packages: Springer Book Archive