In the quantum era, the advent of quantum computers poses significant threats to the security of current cryptosystems. Therefore, designing quantum-resistant cryptoschemes becomes important to guarantee information security. This work concentrates on the development of the post-quantum public key encryption (PKE) scheme. Non-commutative cryptography (NCC) has entered the field of post-quantum cryptography. We utilize the TSPEM problem with asymmetric structures (which serve as a potential candiate for resisting quantum attacks) to construct two PKE schemes which are demonstrated to be CPA security under the DTSPEM assumption. By representing the plaintext as a matrix, these schemes can effectively encrypt a significant amount of information in a single operation. Assuming an equal amount of messages for encryption, the proposed schemes acheive superior efficiency compared to existing PKE schemes. Structurally, our systems exhibit a level of synchronization and coexistence due to the distinct public keys $ (P) $ and ciphertexts $ (C_{1}) $. The efficiency analysis is conducted by comparing known schemes from the aspect of specific cryptographic indicators. Generally, the proposed ones offer several advantages including provable security, high efficiency, potential quantum-resistant, and relative ease of implementation; along with synchronization and coexistence. Our investigation has established the feasibility of constructing PKE schemes based on the TSPEM problem, specifically for asymmetric communication scenarios. The preliminary results pave the way for further exploration of the TSPEM problem$ ' $s potential in developing other cryptosystems suitable for quantum computing environments.
Citation: Limin Zhou, Qiuyang Wang. Simple PKE schemes from the TSPEM problem[J]. AIMS Mathematics, 2024, 9(8): 22197-22212. doi: 10.3934/math.20241079
In the quantum era, the advent of quantum computers poses significant threats to the security of current cryptosystems. Therefore, designing quantum-resistant cryptoschemes becomes important to guarantee information security. This work concentrates on the development of the post-quantum public key encryption (PKE) scheme. Non-commutative cryptography (NCC) has entered the field of post-quantum cryptography. We utilize the TSPEM problem with asymmetric structures (which serve as a potential candiate for resisting quantum attacks) to construct two PKE schemes which are demonstrated to be CPA security under the DTSPEM assumption. By representing the plaintext as a matrix, these schemes can effectively encrypt a significant amount of information in a single operation. Assuming an equal amount of messages for encryption, the proposed schemes acheive superior efficiency compared to existing PKE schemes. Structurally, our systems exhibit a level of synchronization and coexistence due to the distinct public keys $ (P) $ and ciphertexts $ (C_{1}) $. The efficiency analysis is conducted by comparing known schemes from the aspect of specific cryptographic indicators. Generally, the proposed ones offer several advantages including provable security, high efficiency, potential quantum-resistant, and relative ease of implementation; along with synchronization and coexistence. Our investigation has established the feasibility of constructing PKE schemes based on the TSPEM problem, specifically for asymmetric communication scenarios. The preliminary results pave the way for further exploration of the TSPEM problem$ ' $s potential in developing other cryptosystems suitable for quantum computing environments.
| [1] | L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ACM, (1996), 212–219. https://doi.org/10.1145/237814.237866 |
| [2] | P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, (1999), 303–332. https://doi.org/10.1137/S0036144598347011 |
| [3] | O. Regev, On lattices, learning with errors, random linear codes and cryptography, Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, May, (2005), 84–93. https://doi.org/10.1145/1060590.1060603 |
| [4] |
H. Z. Wang, H. G. Zhang, Z. Y. Wang, M. Tang, Extended multivariate public key cryptosystems with secure encryption function, Sci. China Inform. Sci., 54 (2011), 1161–1171. https://doi.org/10.1007/s11432-011-4262-3 doi: 10.1007/s11432-011-4262-3
|
| [5] |
M. Eftekhari, A diffie-hellman key exchange protocol using matrices over non-commutative rings, Groups Complex. Crypt., 4 (2012), 167–176. https://doi.org/10.1515/gcc-2012-0001 doi: 10.1515/gcc-2012-0001
|
| [6] | A. G. Myasnikov, V. Shpilrain, A. Ushakov, Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, No. 177. Providence, RI, USA: American Mathematical Society, (2011), 41–111. Available from: https://dl.acm.org/doi/abs/10.5555/2161874 |
| [7] | Z. F. Chao, New Directions of Modern Cryptography, CRC Press, (2012), 233–322. Available from: https://dl.acm.org/doi/abs/10.5555/2490637 |
| [8] |
D. J. Bernstein, T. Lange, Post-quantum cryptography, Nature, 549 (2017), 188–194. https://doi.org/10.1038/nature23461 doi: 10.1038/nature23461
|
| [9] | R. A. Perlner, D. A. Cooper, Quantum resistant public key cryptography: A survey, Proceed ings of the 8th Symposium on Identity and Trust on the Internet, ACM, (2009), 85–93. https://doi.org/10.1145/1527017.1527028 |
| [10] | T. Okamoto, K. Tanaka, S. Uchiyama, Quantum public-key cryptosystems, Advances in Cryptology-CRYPTO 2000, Springer Berlin Heidelberg, (2000), 147–165. https://doi.org/10.1007/3-540-44598-6 |
| [11] | S. W. Mao, H. G. Zhang, W. Q. Wu, H. Z. Wang, An asymmetric-computing key exchange protocol, Advances in Cryptology 2014, ChinaCrypt, (2014), 135–149. |
| [12] | Q. H. Wu, Y. Mu, W. Susilo, B. Qin, D. F. Josep, Asymmetric group key agreement, In: Eurocrypt 2009, LNCS, Berlin: Springer-Verlag, 5479 (2009), 153–170. https://doi.org/10.1007/978-3-642-01001-9 |
| [13] |
Z. Yu, C. Gu, Z. Jing, Q. Cai, Y. Luo, Y. Wang, Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem: revisited, Multimed. Tools Appl., 77 (2018), 11307–11320. https://doi.org/10.1007/s11042-017-5535-7 doi: 10.1007/s11042-017-5535-7
|
| [14] | H. Wang, J. Wen, J. Liu, H. Zhang, ACKE: Asymmetric computing key exchange protocol for IoT environments, In: IEEE Internet Things, 10 (2023), 18273–18281. http://doi.org/10.1109/JIOT.2023.3279283 |
| [15] |
S. W. Mao, H. G. Zhang, W. Wu, J. Liu, S. Li, H. Wang, A resistant quantum key exchange protocol and its corresponding encryption scheme, China Commun., 11 (2014), 124–134. http://doi.org/10.1109/CC.2014.6969777 doi: 10.1109/CC.2014.6969777
|
| [16] |
A. Mihalkovich, E. Sakalauskas, K. Luksy, Key exchange protocol defined over a non-commuting group based on an NP-complete decisional problem, Symmetry, 12 (2020), 1–16. https://doi.org/10.3390/sym12091389 doi: 10.3390/sym12091389
|
| [17] | D. Boucher, P. Gaborit, W. Geiselmann, Key exchange and encryption schemes based on non-commutative skew polynomials, International Workshop on Post-Quantum cryptography, Berlin, Heidelberg: Springer Berlin Heidelberg, Lecture Notes in Computer Science, (2010), 126–141. https://doi.org/10.1007/978-3-642-12929-2 |
| [18] |
K. Dudziski, S. Walukiewicz, Exact methods for the knapsack problem and its generalizations, Eur. J. Oper. Res., 28 (1987), 3–21. https://doi.org/10.1016/0377-2217(87)90165-2 doi: 10.1016/0377-2217(87)90165-2
|
| [19] |
J. Li, D. Wan, On the subset sum problem over finite fields, Finite Fields Th. App., 14 (2008), 911–929. https://doi.org/10.1016/j.ffa.2008.05.003 doi: 10.1016/j.ffa.2008.05.003
|
| [20] | C. J. Hillar, L. H. Lim, Most tensor problem are NP-hard, J. ACM (JACM), September, 60 (2013), 1–39. https://doi.org/10.1145/2512329 |
| [21] | S. H. Pei, Y. Z. Zhao, H. W. Zhao, Construct public key encryption scheme using ergodic matrices over GF(2), International Conference on Theory and Applications of Models of Computation, Springer Berlin Heidelberg, (2007), 181–188. https://doi.org/10.1007/978-3-540-72504-6 |
| [22] | J. Katz, Y. Lindell, Introduction to Modern Cryptography: Principles and Protocols, CRC Press, (2007), 336–337. https://doi.org/10.1201/9781420010756 |
| [23] | J. J. Zheng, P. J. Guo, S. G. Chun, A novel public key cryptosystem based on ergodic matrix over GF(2), 2012 International Conference on Computer Science and Service System, IEEE, (2012), 845–848. https://doi.org/10.1109/CSSS.2012.216 |
Limin Zhou, Qiuyang Wang. Simple PKE schemes from the TSPEM problem[J]. AIMS Mathematics, 2024, 9(8): 22197-22212. doi: 10.3934/math.20241079
DownLoad: