Search Advanced

AIMS Mathematics

2024, Volume 9, Issue 8: 20677-20691. doi: 10.3934/math.20241005
Previous Article Next Article
Research article Special Issues

A new semiring and its cryptographic applications

  • 1.
    School of Mathematical Sciences, Guizhou Normal University, Guiyang 550025, China
  • 2.
    School of Mathematics and Information Science, Guiyang University, Guiyang 550005, China
  • Received: 07 March 2024 Revised: 28 May 2024 Accepted: 13 June 2024 Published: 26 June 2024

  • MSC : 15A80, 94A60

  • This paper introduced a novel semiring structure involving nonnegative integers, where operations depended on the comparison of the magnitudes of decimal digit sums. Consequently, a corresponding matrix semiring can be established on this commutative semiring. We showed that the 3-satisfiability problem can be polynomial-time reduced to solving systems of quadratic polynomial equations over this semiring. We proposed a key exchange protocol based on this matrix semiring, with its security relying on the two-sided digital circulant matrix action problem over this semiring. This scheme provides a novel cryptographic primitive for post-quantum cryptography.

    Citation: Huawei Huang, Xin Jiang, Changwen Peng, Geyang Pan. A new semiring and its cryptographic applications[J]. AIMS Mathematics, 2024, 9(8): 20677-20691. doi: 10.3934/math.20241005

    Related Papers:

  • This paper introduced a novel semiring structure involving nonnegative integers, where operations depended on the comparison of the magnitudes of decimal digit sums. Consequently, a corresponding matrix semiring can be established on this commutative semiring. We showed that the 3-satisfiability problem can be polynomial-time reduced to solving systems of quadratic polynomial equations over this semiring. We proposed a key exchange protocol based on this matrix semiring, with its security relying on the two-sided digital circulant matrix action problem over this semiring. This scheme provides a novel cryptographic primitive for post-quantum cryptography.


    加载中


    [1] H. S. Vandiver, Note on a simple type of algebra in which the cancellation 1 aw of addition does not hold, Bull. Amer. Math. Soc., 40 (1934), 914–920. https://doi.org/10.1090/S0002-9904-1934-06003-8 doi: 10.1090/S0002-9904-1934-06003-8
    [2] A. Yamamura, A functional cryptosystem using a group action, In: Information Security and Privacy, Berlin: Springer, 1999. https://doi.org/10.1007/3-540-48970-3_26
    [3] A. Yamamura, Public-key cryptosystems using the modular group, In: Public Key Cryptography, Berlin: Springer, 1998. https://doi.org/10.1007/BFb0054026
    [4] R. Steinwandt, Loopholes in two public key cryptosystems using the modular group, In: Public Key Cryptography, Berlin: Springer, 2001. https://doi.org/10.1007/3-540-44586-2_14
    [5] D. Kahrobaei, C. Koupparis, V. Shpilrain, Public key exchange using matrices over group rings, Groups Complex. Crypt., 5 (2013), 97–115. https://doi.org/10.1515/gcc-2013-0007 doi: 10.1515/gcc-2013-0007
    [6] M. Eftekhari, Cryptanalysis of some protocols using matrices over group rings, In: Progress in Cryptology-AFRICACRYPT 2017, Cham: Springer, 2017. https://doi.org/10.1007/978-3-319-57339-7_13
    [7] I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett., 6 (1999), 287–291, https://doi.org/10.4310/MRL.1999.v6.n3.a3 doi: 10.4310/MRL.1999.v6.n3.a3
    [8] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. S. Kang, C. Park, New public-key cryptosystem using Braid groups, In: Advances in Cryptology-CRYPTO 2000, Berlin: Springer, 2000. https://doi.org/10.1007/3-540-44598-6_10
    [9] I. Anshel, M. Anshel, B. Fisher, D. Goldfeld, New key agreement protocols in Braid group cryptography, In: Topics in Cryptology-CT-RSA 2001, Berlin: Springer, 2001. https://doi.org/10.1007/3-540-45353-9_2
    [10] D. Hofheinz, R. Steinwandt, A practical attack on some braid group based cryptographic primitives, In: Public Key Cryptography-PKC 2003, Berlin: Springer, 2003. https://doi.org/10.1007/3-540-36288-6_14
    [11] D. Sypeyer, B. Sturmfels, Tropical mathematics, Math. Mag., 82 (2009), 163–173, https://doi.org/10.1080/0025570X.2009.11953615
    [12] D. Grigoriev, V. Shpilrain, Tropical cryptography, Commun. Algebra, 42 (2014), 2624–2632. https://doi.org/10.1080/00927872.2013.766827
    [13] D. Grigoriev, V. Shpilrain, Tropical cryptography II: Extensions by homomorphisms, Commun. Algebra, 47 (2019), 4224–4229. https://doi.org/10.1080/00927872.2019.1581213 doi: 10.1080/00927872.2019.1581213
    [14] M. Kotov, A. Ushakov, Analysis of a key exchange protocol based on tropical matrix algebra, J. Math. Cryptol., 12 (2018), 137–141. https://doi.org/10.1515/jmc-2016-0064 doi: 10.1515/jmc-2016-0064
    [15] D. Rudy, C. Monico, Remarks on a tropical key exchange system, J. Math. Cryptol., 15 (2021), 280–283. https://doi.org/10.1515/jmc-2019-0061 doi: 10.1515/jmc-2019-0061
    [16] S. Isaac, D. Kahrobaei, A closer look at the tropical cryptography, Int. J. Comput. Math. Co., 6 (2021), 137–142. https://doi.org/10.1080/23799927.2020.1862303 doi: 10.1080/23799927.2020.1862303
    [17] A. Muanalifah, S. Sergeev, Modifying the tropical version of Stickel's key exchange protocol, Appl. Math., 65 (2022), 727–753. https://doi.org/10.21136/AM.2020.0325-19 doi: 10.21136/AM.2020.0325-19
    [18] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56 (2009), 1–40. https://doi.org/10.1145/1568318.1568324
    [19] R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Deep Space Netw. Progr. Rep., 44 (1978), 114–116.
    [20] J. Patarin, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms, In: Advances in Cryptology-EUROCRYPT'96, Berlin: Springer, 1996. https://doi.org/10.1007/3-540-68339-9_4
    [21] D. I. Nassr, M. Anwar, H. M. Bahig, New public key cryptosystem (First version), Cryptology ePrint Archive, 2021.
    [22] D. S. Johnson, M. R. Garey, Computers and intractability: A guide to the theory of NP-completeness, WH Freeman, 1979.
    [23] S. A. Cook, The complexity of theorem-proving procedures, In: Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, 1971,151–158.
    [24] H. Huang, C. Li, Tropical cryptography based on multiple exponentiation problem of matrices, Secur. Commun. Netw., 2022 (2022), 1024161. https://doi.org/10.1155/2022/1024161 doi: 10.1155/2022/1024161
    [25] H. Huang, C. Li, L. Deng, Public-key cryptography based on tropical circular matrices, Appl. Sci., 12 (2022), 7401. https://doi.org/10.3390/app12157401 doi: 10.3390/app12157401
    [26] V. Thiruveni, Elgamal encryption using regular semiring, 2018.
    [27] S. Nivetha, M. Chandramouleeswaran, Action of a semiring to encrypt asymmetric key elgamal, J. New Front. Math. Stat., 2 (2021), 1–10.
    [28] G. Robert, Toeplitz and circulant matrices: A review, Found. Trends Commun., 2 (2006), 155–239. https://doi.org/10.1561/0100000006 doi: 10.1561/0100000006
  • 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搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(515) PDF downloads(44) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(7)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog