A Cheating Model for Cellular Automata-Based Secret Sharing Schemes

Authors: Borna Jafarpour, Azadeh Nematzadeh, Vahid Kazempour, Babak Sadeghian

Abstract:

Cellular automata have been used for design of cryptosystems. Recently some secret sharing schemes based on linear memory cellular automata have been introduced which are used for both text and image. In this paper, we illustrate that these secret sharing schemes are vulnerable to dishonest participants- collusion. We propose a cheating model for the secret sharing schemes based on linear memory cellular automata. For this purpose we present a novel uniform model for representation of all secret sharing schemes based on cellular automata. Participants can cheat by means of sending bogus shares or bogus transition rules. Cheaters can cooperate to corrupt a shared secret and compute a cheating value added to it. Honest participants are not aware of cheating and suppose the incorrect secret as the valid one. We prove that cheaters can recover valid secret by removing the cheating value form the corrupted secret. We provide methods of calculating the cheating value.

Keywords: Cellular automata, cheating model, secret sharing, threshold scheme.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079262

References:

[1] J. Pieprzyk, T. Hardjono, J. Seberry, "Fundamentals of Computer Security," Springer, 2003.
[2] G. R. Blakley, "Safeguarding cryptographic keys," in Proc. of 1979 AFIPS National Computer Conference, 1979, pp. 313-317.
[3] A. Shamir, "How to Share a Secret," Communications of the ACM, Vol. 22. No. 11., 1979, pp. 612 - 613.
[4] M. Tompa, H. Woll, "How to share a secret with cheaters," Journal of Cryptology, Vol. 1. No. 2. , 1988, pp. 133-138.
[5] H. Ghodosi, J. Pieprzyk, "Cheating prevention in secret sharing," Australasian Conference on Information Security and Privacy, 2000, pp. 328-341.
[6] J. Pieprzyk, X. Zhang, "Cheating Prevention in Linear Secret Sharing," Information Security and Privacy. Lecture Notes in Computer Science, Vol. 2384, 2002, pp. 121-131.
[7] A. Rey , J. P. Mateus, G. R. Sanchez, "A secret sharing scheme based on cellular automata," Applied Mathematics and Computation, Vol. 170, 2005, pp. 1356-1364.
[8] G. A. Maranon, L.H. Encinas, A. M. Rey, "Sharing secret color images using cellular automata with memory," CoRR 0312034, 2003.
[9] G. Alvarez, A.H. Encinas, L.H. Encinas, A. M. Rey, "A secure scheme to share secret color images," Computer and Physics communication, Vol. 173. No. 1-2., 2005, pp. 9-16.
[10] G. A. Maranon, L.H. Encinas, A. M. Rey, "A new secret sharing schemes for images based on additive 2-dimensional cellular automata," Pattern Recognition and Image Analysis. Lecture note in computer science, Vol. 3522, 2005, pp. 411-418.
[11] S. Wolfram, "Cellular Automata, Los Alamos Science," Vol. 9, 1983, pp. 2-21.
[12] R. Alonso-Sanz, M. Mart─▒n, "Elementary cellular automata with memory," Complex Systems, Vol. 14, 2003, pp. 99-126.
[13] R. Alonso-Sanz, M. Mart─▒n, "One-dimensional cellular automata with memory: patterns from a single site seed," Int. J. Bifur. Chaos Application Science Engineering, Vol. 12, 2002, pp. 205-226.
[14] C. Meadows, "A formal framework and evaluation method for network denial of service," in Proc. Of 1999 IEEE Computer Security Foundations Workshop, 1998, pp. 4-13.