×

Conjugacy systems based on nonabelian factorization problems and their applications in cryptography. (English) Zbl 1442.94037

Summary: To resist known quantum algorithm attacks, several nonabelian algebraic structures mounted upon the stage of modern cryptography. Recently, S. Baba, S. Kotyada and R. Teja [“A non-abelian factorization problem and an associated cryptosystem”, Cryptology EPrint Archive Report 2011/048 (2011)] proposed an important analogy from the integer factorization problem to the factorization problem over nonabelian groups. In this paper, we propose several conjugated problems related to the factorization problem over nonabelian groups and then present three constructions of cryptographic primitives based on these newly introduced conjugacy systems: encryption, signature, and signcryption. Sample implementations of our proposal as well as the related performance analysis are also presented.

MSC:

94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Merkle, R. C., Secure communications over insecure channels, Communications of the ACM, 21, 4, 294-299 (1978) · Zbl 1342.94085
[2] Diffie, W.; Hellman, M. E., New directions in cryptography, IEEE Transactions on Information Theory, 22, 6, 644-654 (1976) · Zbl 0435.94018
[3] Rivest, R. L.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Communications of the Association for Computing Machinery, 21, 2, 120-126 (1978) · Zbl 0368.94005
[4] ElGamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 31, 4, 469-472 (1985) · Zbl 0571.94014
[5] Miller, V. S., Use of elliptic curves in cryptography, Advances in Cryptology (CRYPTO ’85). Advances in Cryptology (CRYPTO ’85), Lecture Notes in Computer Science, 218, 417-426 (1986), Berlin, Germany: Springer, Berlin, Germany
[6] Koblitz, N., Elliptic curve cryptosystems, Mathematics of Computation, 48, 177, 203-209 (1987) · Zbl 0622.94015
[7] Dent, A.; Zheng, Y., Practical Signcryption. Practical Signcryption, Information Security and Cryptography (2010), Berlin, Germany: Springer, Berlin, Germany · Zbl 1203.68005
[8] Zheng, Y., Digital signcryption or how to achieve Cost(Signature & Encryption) ≪ Cost(Signature) + Cost(Encryption), Advances in Cryptology—Crypto ’97. Advances in Cryptology—Crypto ’97, Lecture Notes in Computer Science, 1294, 165-179 (1997), Berlin, Germany: Springer, Berlin, Germany · Zbl 1058.94524
[9] Gu, L.; Pan, Y.; Dong, M.; Ota, K., Noncommutative lightweight signcryption for wireless sensor networks, International Journal of Distributed Sensor Networks, 2013 (2013)
[10] Steinfeld, R.; Zheng, Y., A signcryption scheme based on integer factorization, Information Security Workshop—ISW ’00. Information Security Workshop—ISW ’00, Lecture Notes in Computer Science, 1975, 308-322 (2000), Berlin, Germany: Springer, Berlin, Germany · Zbl 1044.68619
[11] Malone-Lee, J.; Mao, W., Two birds one stone: signcryption using RSA, Cryptographers’ Track at the RSA Conference—CT-RSA ’03. Cryptographers’ Track at the RSA Conference—CT-RSA ’03, Lecture Notes in Computer Science, 2612, 211-225 (2003), Berlin, Germany: Springer, Berlin, Germany · Zbl 1039.94529
[12] Zheng, Y.; Imai, H., How to construct efficient signcryption schemes on elliptic curves, Information Processing Letters, 68, 5, 227-233 (1998) · Zbl 1339.94072
[13] Toorani, M.; Shirazi, A. A. B., A directly public verifiable signcryption scheme based on elliptic curves, Proceedings of the IEEE Symposium on Computers and Communications (ISCC ’09)
[14] Zhang, L.; Mo, T., A signcryption scheme for WEP in WLAN based on bilinear pairings, Proceedings of the International Conference on Computer Application and System Modeling (ICCASM ’10), IEEE Computer Society
[15] Zhang, J.; Yang, Y.; Niu, X., A novel identity-based multi-signcryption scheme, International Journal of Distributed Sensor Networks, 1, 5, 28-28 (2009)
[16] Shor, P. W., Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS ’94), IEEE Computer Society
[17] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26, 5, 1484-1509 (1997) · Zbl 1005.11065
[18] Proos, J.; Zalka, C., Shor’s discrete logarithm quantum algorithm for elliptic curves, Quantum Information & Computation, 3, 4, 317-344 (2003) · Zbl 1152.81800
[19] Li, F.; Muhaya, F.; Khan, M.; Takagi, T., Lattice-based signcryption, Concurrency and Computation: Practice and Experience, 25, 14, 2112-2122 (2013)
[20] Wang, F.; Hu, Y.; Wang, C., Post-quantum secure hybrid signcryption from lattice assumption, Applied Mathematics & Information Sciences, 6, 1, 23-28 (2012) · Zbl 1320.94085
[21] Myasnikov, A.; Shpilrain, V.; Ushakov, A., Non-Commutative Cryptography and Complexity of Group-Theoretic Problems. Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, Mathematical Surveys and Monographs, 177 (2011), Providence, RI, USA: American Mathematical Society, Providence, RI, USA · Zbl 1248.94006
[22] Anshel, I.; Anshel, M.; Goldfeld, D., An algebraic method for public-key cryptography, Mathematical Research Letters, 6, 3-4, 287-291 (1999) · Zbl 0944.94012
[23] Ko, K. H.; Lee, S. J.; Cheon, J. H.; Han, J. W.; Kang, J.-s.; Park, C.; Bellare, M., New public-key cryptosystem using braid groups, Advances in Cryptology (CRYPTO ’00). Advances in Cryptology (CRYPTO ’00), Lecture Notes in Computer Science, 1880, 166-183 (2000), Berlin, Germany: Springer, Berlin, Germany · Zbl 0995.94531
[24] Paeng, S. H.; Ha, K. C.; Kim, J. H.; Chee, S.; Park, C., New public key cryptosystem using finite nonabelian groups, Advances in Cryptology (CRYPTO ’01). Advances in Cryptology (CRYPTO ’01), Lecture Notes in Computer Science, 2139, 470-485 (2001), Berlin, Germany: Springer, Berlin, Germany · Zbl 1003.94525
[25] Mahalanobis, A., A simple generalization of the ElGamal cryptosystem to non-abelian groups, Communications in Algebra, 36, 10, 3878-3889 (2008) · Zbl 1163.94006
[26] Shpilrain, V.; Ushakov, A., Thompson’s group and public key cryptography, Applied Cryptography and Network Security (ACNS ’05). Applied Cryptography and Network Security (ACNS ’05), Lecture Notes in Computer Science, 3531, 151-163 (2005), Berlin, Germany: Springer, Berlin, Germany · Zbl 1126.68416
[27] Baumslag, G.; Fine, B.; Xu, X., A proposed public key cryptosystem using the modular group, Combinatorial Group Theory, Discrete Groups, and Number Theory. Combinatorial Group Theory, Discrete Groups, and Number Theory, Contemporary Mathematics, 421, 35-44 (2006), Providence, RI, USA: American Mathematical Society, Providence, RI, USA · Zbl 1122.94028
[28] Baumslag, G.; Fine, B.; Xu, X., Cryptosystems using linear groups, Applicable Algebra in Engineering, Communication and Computing, 17, 3-4, 205-217 (2006) · Zbl 1104.94017
[29] Magliveras, S. S.; Stinson, D. R.; van Trung, T., New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups, Journal of Cryptology, 15, 4, 285-297 (2002) · Zbl 1020.94010
[30] Baba, S.; Kotyada, S.; Teja, R., A non-abelian factorization problem and an associated cryptosystem, Cryptology EPrint Archive Report, 2011/048 (2011)
[31] Gu, L.; Wang, L.; Ota, K.; Dong, M.; Cao, Z.; Yang, Y., New public key cryptosystems based on non-abelian factorization problems, Security and Communication Networks, 6, 7, 912-922 (2013)
[32] Wang, L.; Wang, L.; Cao, Z.; Okamoto, E.; Shao, J., New constructions of public-key encryption schemes from conjugacy search problems, Information Security and Cryptology (Inscrypt ’10). Information Security and Cryptology (Inscrypt ’10), Lecture Notes in Computer Science, 6584, 1-17 (2011), Berlin, Germany: Springer, Berlin, Germany · Zbl 1295.94148
[33] Maurer, U.; Smart, N. P., Abstract models of computation in cryptography, Cryptography and Coding. Cryptography and Coding, Lecture Notes in Computer Science, 3796, 1-12 (2005), Heidelberg, Germany: Springer, Heidelberg, Germany · Zbl 1122.94040
[34] Fujisaki, E.; Okamoto, T., How to enhance the security of public key encryption at minimum cost, Public Key Cryptography (PKC ’99). Public Key Cryptography (PKC ’99), Lecture Notes in Computer Science, 1560, 53-68 (1999), Berlin, Germany: Springer, Berlin, Germany · Zbl 0964.94020
[35] Kahrobaei, D.; Koupparis, C., Non-commutative digital signatures, Groups Complexity Cryptology, 4, 2, 377-384 (2012) · Zbl 1293.94080
[36] Wang, L.; Wang, L.; Cao, Z.; Yang, Y.; Niu, X., Conjugate adjoining problem in braid groups and new design of braid-based signatures, Science China—Information Sciences, 53, 3, 524-536 (2010)
[37] Maffre, S., A weak key test for braid based cryptography, Designs, Codes and Cryptography, 39, 3, 347-373 (2006) · Zbl 1159.94366
[38] Menezes, A. J.; Wu, Y.-H., The discrete logarithm problem in GLn,q, Ars Combinatoria, 47, 23-32 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.