Research article

Simple PKE schemes from the TSPEM problem

  • Received: 07 March 2024 Revised: 20 June 2024 Accepted: 02 July 2024 Published: 16 July 2024
  • MSC : 06D50

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(451) PDF downloads(37) Cited by(0)

Article outline

Figures and Tables

Tables(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog