AIMS Mathematics (Jun 2024)

A new semiring and its cryptographic applications

  • Huawei Huang,
  • Xin Jiang ,
  • Changwen Peng,
  • Geyang Pan

DOI
https://doi.org/10.3934/math.20241005
Journal volume & issue
Vol. 9, no. 8
pp. 20677 – 20691

Abstract

Read online

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.

Keywords