THE GENERAL CHINESE REMAINDER THEOREM
DOI:
https://doi.org/10.47839/ijc.6.1.423Keywords:
The Chinese remainder theorem, secret sharing, threshold cryptographyAbstract
The Chinese remainder theorem deals with systems of modular equations. The classical variant requires the modules to be pairwise coprime. In this paper we discuss the general variant, which does not require this restriction on modules. We have selected and implemented several algorithms for the general Chinese remainder theorem. Moreover, we point out some interesting applications of this variant in secret sharing and threshold cryptography.References
C. Ding, D. Pei, and A. Salomaa. Chinese remainder theorem: applications in computing, coding, cryptography. World Scientific Publishing Co., Inc., 1996.
J.-J. Quisquater and C. Couvreur. Fast decipherment algorithm for the RSA public-key cryptosystem. IEE Electronics Letters 8(21) (1982), pp. 905-907.
S. C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, 24:106–110, 1978.
M. Mignotte. How to share a secret. In T. Beth, editor, Proceedings of the Workshop on Cryptography, Burg Feuerstein, 1982, volume 149 of Lecture Notes in Computer Science, pages 371–375. Springer-Verlag, 1983.
C. A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208–210, 1983.
H. Cohen. A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics. Springer-Verlag, 4th edition, 2000.
F.L. Tiplea, S. Iftene, C. Hritcu, I. Goriac, R.M. Gordan and E. Erbiceanu. MpNT: A Multi-Precision Number Theory Package. Number-Theoretic Algorithms (I). Technical Report TR03-02 (2003), Faculty of Computer Science “Al.I.Cuza” University of Iasi. (http://www.infoiasi.ro/~tr/tr.pl.cgi)
O. Ore. The general Chinese remainder theorem. American Mathematical Monthly, 59:365–370, 1952.
C.F. Gauss, Disquisitiones Arithmeticae, 1801. English translation by Arthur A. Clarke, Springer-Verlag, New York, 1986.
A. S. Fraenkel. New proof of the generalized Chinese remainder theorem. Proceedings of American Mathematical Society, 14:790–791, 1963.
H. Garner. The residue number system. IRE Transactions on Electronic Computers EC-8 (1959), pp. 140-147.
Y. Desmedt. Some recent research aspects of threshold cryptography. In E. Okamoto, G. I. Davida, and M. Mambo, editors, ISW ’97: Proceedings of the First International Workshop on Information Security, volume 1396 of Lecture Notes in Computer Science, pages 158–173. Springer-Verlag, 1998.
R. Cramer, M. K. Franklin, B. Schoenmakers, and M. Yung. Multi-authority secret-ballot elections with linear work. In U. Maurer, editor, Advances in Cryptology - EuroCrypt ’96, volume 1070 of Lecture Notes in Computer Science, pages 72–83. Springer-Verlag, 1996.
A. Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.
G. R. Blakley. Safeguarding cryptographic keys. In National Computer Conference, 1979, volume 48 of American Federation of Information Processing Societies Proceedings, pages 313–317, 1979.
M. Ito, A. Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure. In Proceedings of the IEEE Global Telecommunications Conference, Globecom ’87, pages 99–102. IEEE Press, 1987
J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In S. Goldwasser, editor, Advanced in Cryptology-CRYPTO ’88, volume 403 of Lecture Notes in Computer Science, pages 27–35. Springer-Verlag, 1989
S. Iftene. A generalization of Mignotte’s secret sharing scheme. In T. Jebelean, V. Negru, D. Petcu, and D. Zaharie, editors, Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, September, 2004, pages 196–201, 2004.
Y. Desmedt, G. Di Crescenzo, and M. Burmester. Multiplicative non-abelian sharing schemes and their applications to threshold cryptography. In J. Pieprzyk and R. Safavi-Naini, editors, Advances in Cryptology -Asiacrypt ’94, volume 917 of Lecture Notes in Computer Science, pages 21–32. Springer-Verlag, 1995.
S. Iftene. Threshold RSA Based on the General Chinese Remainder Theorem. Technical Report TR05-05 (2005), Faculty of Computer Science “Al.I.Cuza” University of Iasi. (http://www.infoiasi.ro/~tr/tr.pl.cgi)
R. L. Rivest, A. Shamir and L. M. Adelman. A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Communications of the ACM 2 (21) (1978), pp. 120-126.
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.
