Open Access Open Access  Restricted Access Subscription Access

CHEATING DETECTION AND CHEATER IDENTIFICATION IN CRT-BASED SECRET SHARING SCHEMES

Daniel Pasailă, Vlad Alexa, Sorin Iftene

Abstract


In this paper we analyze the cheating detection and cheater identification problems for the secret sharing schemes based on the Chinese remainder theorem (CRT), more exactly for Mignotte [1] and Asmuth-Bloom [2] schemes. We prove that the majority of the solutions for Shamir’s scheme [3] can be translated to these schemes and, moreover, there are some interesting specific solutions.

Keywords


Secret sharing; Chinese remainder theorem; cheater detection; cheater identification.

Full Text:

PDF

References


M. Mignotte. How to share a secret, in Cryptography-Proceedings of the Workshop on Cryptography, Burg Feuerstein, 1982, ser. Lecture Notes in Computer Science, T. Beth, Ed., vol. 149. Springer-Verlag, 1983, pp. 371–375.

C. A. Asmuth, J. Bloom. A modular approach to key safeguarding, IEEE Transactions on Information Theory, vol. IT-29, 1983, no. 2, pp. 208–210.

A. Shamir. How to share a secret, Communications of the ACM, 1979, vol. 22, no. 11, pp. 612–613.

G. R. Blakley. Safeguarding cryptographic keys, in National Computer Conference, 1979, ser. American Federation of Information Processing Societies Proceedings, vol. 48, 1979, pp. 313–317.

B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults, in Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science. IEEE Press, 1985, pp. 383–395.

R. J. McEliece and D. V. Sarwate. On sharing secrets and Reed-Solomon codes, Communications of ACM, 1981, vol. 24, no. 9, pp. 583–584.

M. Tompa and H. Woll. How to share a secret with cheaters, Journal of Cryptology, vol. 1, no. 2, pp. 133–138, 1988, (a preliminary version of this paper appeared in “Advances in Cryptology – CRYPTO ’86”, A. M. Odlyzko, ed., Lecture Notes in Computer Science 263 (1987), 261-265).

K. Kaya and A. Selcuk. Threshold cryptography based on Asmuth-Bloom secret sharing, Information Sciences, vol. 177, no. 19, pp. 4148–4160, 2007, (a preliminary version of this paper has been presented at ISCIS 2006).

S. Iftene and M. Grindei. Weighted threshold RSA based on the Chinese remainder theorem, in Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007. IEEE Computer Society Press, 2007, pp. 175–181.

K. Kaya and A. Selcuk. Robust threshold schemes based on the Chinese remainder theorem, in Progress in Cryptology – AFRICACRYPT 2008, ser. Lecture Notes in Computer Science, S. Vaudenay, Ed., vol. 5023. Springer-Verlag, 2008, pp. 94–108.

S. Iftene. General secret sharing based on the Chinese remainder theorem with applications in E-voting, Electronic Notes in Theoretical Computer Science, 2007, vol. 186, pp. 67–84 (Proceedings of ICS 2006).

S. Iftene and D. Pasaila. A CRT-based solution to Yao’s millionaires’ problem, in Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008. IEEE Computer Society Press, 2008, pp. 189–192.

H. Cohen. A Course in Computational Algebraic Number Theory, 4th ed., ser. Graduate Texts in Mathematics. Springer-Verlag, 2000.

O. Ore. The general Chinese remainder theorem, American Mathematical Monthly, 1952, vol. 59, pp. 365–370.

A. S. Fraenkel. New proof of the generalized Chinese remainder theorem, Proceedings of American Mathematical Society, 1963, vol. 14, pp. 790–791.

H. Garner. The residue number system, IRE Transactions on Electronic Computers, 1959, vol. EC-8, pp. 140–147.

C. Ding, D. Pei, and A. Salomaa. Chinese remainder theorem: applications in computing, coding, cryptography. World Scientific Publishing Co., Inc., 1996.

S. Iftene. Secret Sharing Schemes with Applications in Security Protocols. “Al.I.Cuza” University of Iasi, Faculty of Computer Science, Tech. Rep. TR 07-01, 2007, URL:http://www.infoiasi.ro/ tr/tr.pl.cgi.

E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.

S. Iftene. A generalization of Mignotte’s secret sharing scheme, in Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, September 2004, T. Jebelean, V. Negru, D. Petcu, and D. Zaharie, Eds. Mirton Publishing House, 2004, pp. 196–201.

O. Goldreich, D. Ron, and M. Sudan. Chinese remaindering with errors, IEEE Transactions on Information Theory, 2000, vol. IT-46, no. 4, pp. 1330–1338, (a preliminary version of this paper appeared in Proceedings of the thirty-first annual ACM symposium on Theory of computing (1999), 225-234).

M. Quisquater, B. Preneel, and J. Vandewalle. On the security of the threshold scheme based on the Chinese remainder theorem, in Public Key Cryptography, 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, ser. Lecture Notes in Computer Science, D. Naccache and P. Paillier, Eds., vol. 2274. Springer-Verlag, 2002, pp. 199–210.

M. Carpentieri, A. D. Santis, and U. Vaccaro. Size of shares and probability of cheating in threshold schemes, in Advances in Cryptology – EUROCRYPT ’93, ser. Lecture Notes in Computer Science, T. Helleseth, Ed., vol. 765. Springer-Verlag, 1994, pp. 118–125.

W. Ogata, K. Kurosawa, and D. Stinson. Optimum secret sharing scheme secure against cheating, SIAM Journal on Discrete Mathematics, 2006, vol. 20, no. 1, pp. 79–95.

B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting, in Advances in Cryptology – CRYPTO ’99, ser. Lecture Notes in Computer Science, M. Wiener, Ed., vol. 1666. Springer-Verlag, 1999, pp. 148–164.

K. Kaya and A. Selcuk. A verifiable secret sharing scheme based on the Chinese remainder theorem, in Progress in Cryptology – INDOCRYPT 2008, ser. Lecture Notes in Computer Science, D. Chowdhury, V. Rijmen, and A. Das, Eds., vol. 5365. Springer-Verlag, 2008, pp. 414–425.

H. Ghodosi and J. Pieprzyk. Cheating prevention in secret sharing, in Information Security and Privacy, 5th Australasian Conference, ACISP 2000, ser. Lecture Notes in Computer Science, E. Dawson, A. Clark, and C. Boyd, Eds., vol. 1841. Springer-Verlag, 2000, pp. 328–341.

L. Harn and C. Lin. Detection and identification of cheaters in (t,n) secret sharing scheme. Designs, Codes and Cryptography, 2009, vol. 52, no. 1, pp. 15–24, http://dx.doi.org/10.1007/s10623-008-9265-8.


Refbacks

  • There are currently no refbacks.