CHEATING DETECTION AND CHEATER IDENTIFICATION IN CRT-BASED SECRET SHARING SCHEMES
DOI:
https://doi.org/10.47839/ijc.9.2.702Keywords:
Secret sharing, Chinese remainder theorem, cheater detection, cheater identification.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.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.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
