A new semiring and its cryptographic applications

1.   Introduction

Research on the theory of semiring algebra began in the early twentieth century when Vandiver ^[1] introduced the concept of semiring in 1934. Semirings encompass all properties of rings except for additive inverses and have extensive applications in combinatorics, functional analysis, topology, automata, computer science theory, and cryptography. Over the past two decades, various algebraic structures have been employed to enhance existing public-key cryptosystems. In 1998, Yamamura ^[2,3] employed modulo groups to construct cryptosystems; however, in 2001, Steinwandt ^[4] demonstrated their vulnerability to ciphertext-only attacks. In 2013, Kahrobaei et al. ^[5] employed the $3 \times 3$ matrix over $F_7\left[S_5\right]$ to develop a key exchange protocol and cryptosystem, which Eftekhari ^[6] later successfully cracked. Literature ^[7,8,9] proposed cryptosystems based on braid groups, but Hofheinz and Steinwandt ^[10] demonstrated their insecurity.

Brazilian mathematician Imre Simon ^[11] introduced the concept of tropical semirings, where addition represents the comparative size of a number, and multiplication corresponds to ordinary addition. Recently, researchers have actively explored the application of tropical semirings in various cryptographic schemes. Shpilrain and Grigoriev ^[12,13] developed a key exchange protocol utilizing tropical matrix semirings.

However, Kotov and Ushakov ^[14] identified patterns in higher powers of tropical matrices, resulting in an attack on the protocol proposed by Shpilrain and Grigoriev ^[12]. Rudy and Monico ^[15] exploited the monotonically decreasing nature of the first part of the sequence $\{(M, H)^m\}$ to propose a fairly effective attack on ^[13]. Isaac and Kahrobaei ^[16] utilized the almost linear periodicity of the first part of the sequence $\{(M, H)^m\}$ to propose an attack on ^[13] and demonstrated that the second protocol cannot be implemented. Muanalifah and Sergeev ^[17] proposed three types of key exchange protocols using the Jones matrix and Line de la Puente matrix, along with introducing a generalized Kotov-Ushakov attack.

Cryptographic schemes generally rely on the hardness of certain mathematical problems. If such a problem is non-deterministic polynomial-time (NP) complete or NP hard, the corresponding cryptographic scheme is considered to be resistant to quantum attacks. The main types of post-quantum cryptography currently include lattice-based cryptography ^[18], code-based cryptography ^[19], and multivariate cryptography ^[20]. Their security relies on the shortest vector problem of lattice, the closest vector problem of lattice, the problem of decoding random linear codes, and the problem of solving systems of multivariate quadratic equations over finite fields. Lattice-based cryptographic schemes are considered highly secure against quantum attacks. In recent years, this field of research has developed rapidly. For example, Nassr, Anwar, and Bahig ^[21] proposed a new lattice-based cryptosystem, which offers significant improvements in security and efficiency. The system's security is comparable to that of the number theory research unit (NTRU) and remains robust against attacks by quantum computers.

The 3-satisfiability (3-SAT) problem is a well-known NP-complete problem in the computational complexity theory. It involves determining if there exists an assignment of variables that satisfies a given Boolean formula expressed in conjunctive normal form (CNF) with exactly three literals per clause. Introduced in the early 1970s, the 3-SAT problem is a cornerstone in theoretical computer science, serving as a benchmark for many computational problems and algorithms ^[22,23].

In the literature ^[24,25], several quantum-resistant cryptosystems have been proposed. These cryptosystems utilize the multiple exponential power problem of tropical matrices and the tropical circulant matrix action problem, respectively. Other researchers have proposed cryptosystems based on different types of semirings. For instance, Thiruveni ^[26] devised an Elgamal-type cryptographic system using regular semirings, while Nivetha ^[27] extended the Diffie-Hellman key exchange protocol by incorporating exponential semirings within its multiplicative left ideal.

This paper introduces a new semiring called the digital semiring and proposes a key exchange protocol based on the matrix semiring over it. Its security relies on the difficulty of solving quadratic polynomial systems over it. We show that the 3-SAT problem can be polynomial-time reduced to it. The scheme presented in this article introduces a new paradigm for post-quantum cryptography.

2.   A new semiring and its matrix semiring

Definition 2.1. ^[1] A semiring is a nonempty set $S$ on which the operations of + and $\cdot$ are defined to satisfy the following conditions:

(1) $(S, +)$ is a commutative monoid with identity element 0;

(2) $\left(S, \cdot\right)$ is a monoid with identity element $1_s$;

(3) Multiplication distributes over addition from either side;

(4) $s \cdot 0 = 0 \cdot s = 0$, for all $s \in S$;

(5) $0 \neq 1_s$.

The semiring satisfies all properties of the ring except the additive inverse. If $(S, \cdot)$ is commutative, then $S$ is referred to as a commutative semiring. For example, the set $N$ of natural numbers, including 0, forms a commutative semiring under addition and multiplication.

Let $W = N \cup\{\infty\}$, where $N$ is the set of natural numbers. We define the symbol "()" as follows:

where $b$ is the sum of all digits of $a$. For example, $(123) = 1+2+3 = 6, (3456) = 3+4+5+6 = 18$.

Definition 2.2. Define two operations $\oplus$ and $\otimes$ over $W = N \cup\{\infty\}$ as follows:

Theorem 2.3. $(W, \oplus, \otimes)$ is a semiring.

Proof. (1) First, we prove that $W$ forms a commutative monoid with respect to the operation $\oplus$. Let $a, b, c \in W$.

(A) Since the result of $a \oplus b$ is either $a$ or $b$, it follows that the operation $\oplus$ satisfies closure property.

(B) The operation $\oplus$ satisfies the associative property. Table 1 shows that the associative law of $\oplus$ when $(a)$, $(b)$, and $(c)$ are pairwise distinct. Table 2 shows that the associative law of $\oplus$ when two of $(a)$, $(b)$, and $(c)$ are equal.

When $(a) = (b) = (c)$, we have $a \oplus(b \oplus c) = \max (a, b, c) = (a \oplus b) \oplus c$.

(C) $\forall a \in W$, and we have $a \oplus 0 = 0 \oplus a = a$. Thus, 0 is the identity element (zero element) for the operation $\oplus$.

(D) $\forall a, b \in W$, and we have $a \oplus b = b \oplus a$. Therefore, $\oplus$ satisfies the commutative property.

(E) Let $a, b \in W$. If $a \neq 0$, then $a \oplus b \neq 0$. Hence, apart from 0, none of the other elements have additive inverses.

In summary, $W$ forms a commutative monoid with respect to the operation $\oplus$.

(2) Next, we prove that $W$ forms a monoid with respect to the operation $\otimes$.

(A) Since the result of $a \otimes b$ is either $a$ or $b$, the operation $\otimes$ is closed.

(B) The operation $\otimes$ satisfies the associative property. Table 3 describes the associative law of $\otimes$ when $(a)$, $(b)$, and $(c)$ are pairwise distinct. Table 4 describes the associative law of $\otimes$ when two of $(a)$, $(b)$, and $(c)$ are equal.

When $(a) = (b) = (c)$, we have $a \otimes(b \otimes c) = \min (a, b, c) = (a \otimes b) \otimes c$.

(C) $\forall a \in W$, $a \otimes \infty = \infty \otimes a = a$. Therefore, the identity element for $\otimes$ is $\infty$.

In conclusion, $W$ forms a monoid with respect to the operation $\otimes$.

(3) Next, we prove that the operation $\otimes$ distributes over $\oplus$. Table 5 shows that $\otimes$ satisfies the distributive law over $\oplus$ when $(a)$, $(b)$, and $(c)$ are pairwise distinct. Table 6 shows that $\otimes$ satisfies the distributive law over $\oplus$ when two of $(a)$, $(b)$, and $(c)$ are equal.

When $(a) = (b) = (c)$, we have

In conclusion, the distributive property of $\otimes$ over $\oplus$ holds.

Finally, let's prove the last two conditions.

(4) $\forall a \in W,$ and we have $a \otimes 0 = 0 \otimes a = 0$.

(5) $0 \neq \infty$.

In conclusion, $(W, \oplus, \otimes)$ forms a semiring and is also a commutative semiring.

For convenience, we refer to it as "digital semiring". It has the following properties:

(1) $(W, \oplus)$ is a commutative monoid with identity element 0;

(2) $(W, \otimes)$ is a monoid with identity element $\infty$;

(3) $a \oplus a = a, a \otimes a = a$, for all $a \in W$.

The security of the cryptographic scheme proposed in this paper relies on the problem of solving quadratic polynomial systems over the new semiring. If this problem is NP-hard, then cryptographic schemes based on it will be resistant to quantum attacks. If we can prove that the 3-SAT problem can be polynomial-time reduced to the problem of solving quadratic polynomial systems over the new semiring, then the problem of solving quadratic polynomial systems over the new semiring is NP-hard.

The Boolean satisfiability problem is NP complete. If all expressions are written in the form of a conjunction normal form with 3 variables per clause (3-CNF), then it is still an NP complete problem and called the 3-SAT problem. The theorem below asserts that the problem of solving quadratic polynomial systems over this semiring is usually NP hard.

Theorem 2.4. 3-SAT problem can be polynomial-time reduced to the problem of solving quadratic polynomial systems over this semiring.

Proof: Suppose we have a 3-CNF. We can construct a system of nonlinear equations on a digital semiring. And this system of equations has a solution if and only if there is a solution for the 3-CNF. Let the variable in the 3-CNF be $u_i$, corresponding to two variables $x_i$ and $y_i$, where $u_i = x_i$ and $\neg u_i = y_i$.

Suppose a clause in a 3-CNF expression: $u_i \vee \neg u_j \vee u_k$. The corresponding system of polynomial equations can be constructed as follows:

Suppose $u_i \vee \neg u_j \vee u_k$ is TURE, i.e., $u_i = 1$, $u_j = 0$, or $u_k = 1$.

(1) If $u_i = 1$, then $x_i = 1, y_i = 0$, and the system of equations ($\nabla$) is satisfied;

(2) if $u_j = 0$, then $x_j = 0, y_j = 1$, and the equation ($\nabla$) is satisfied;

(3) if $u_k = 1$, then $x_k = 1, y_k = 0$, and the equation ($\nabla$) is satisfied.

So, when $u_i \vee \neg u_j \vee u_k$ is TURE, there is a solution to equation ($\nabla$).

Conversely, when there is a solution to equation ($\nabla$), i.e., $x_i = 1$, $y_j = 1$, or $x_k = 1$.

(1) If $x_i = 1$, then $u_i = 1$, and $u_i \vee \neg u_j \vee u_k$ is TURE;

(2) if $y_j = 1$, then $\neg u_j = 1$, and $u_i \vee \neg u_j \vee u_k$ is TURE;

(3) if $x_k = 1$, then $u_k = 1$, and $u_i \vee \neg u_j \vee u_k$ is TURE.

Thus, for each clause in the given 3-CNF, we can construct a system of quadratic polynomial equations on a digital semiring. Finally, we obtain the corresponding system of equations over the whole 3-CNF that has a solution if, and only if, the given 3-CNF expression is satisfied. Thus, the 3-CNF satisfiability problem can be effectively reduced to solving a system of quadratic polynomial equations over the digital semiring.

Next, we define the matrix semiring for digital semiring.

Definition 2.5. Let $M_n(W)$ be the set of all $n \times n$ matrices over $W$. We can define $\oplus$ and $\otimes$ as follows:

Then, $\left(M_n(W), \oplus, \otimes\right)$ is also a semiring with respect to the above operation, which is called a digital matrix semiring.

The identities under $\oplus$ and $\otimes$ on $\left(M_n(W), \oplus, \otimes\right)$ are:

Definition 2.6. ^[28] If a matrix $A$ has the following form,

then it is called a circulant matrix and it is denoted $A = \left[a_1, a_2, \cdots, a_n\right]$. It can be easily verified that if $A, B$ are circulant, then $A \otimes B = B \otimes A$. For example,

3.   Key exchange protocol based on digital semiring

3.1.   Protocol

Alice and Bob agree to exchange keys over the digital semiring $W$ and randomly select a matrix $M \in M_n(W)$ and a prime $p$ as public keys. To obtain the shared secret, Alice and Bob perform the following steps:

(1) Alice chooses two circulant matrices $A_1, A_2 \in M_n(W)$ as her private keys. She computes her public key $U = A_1 \otimes M \otimes A_2$ and sends it to Bob;

(2) Bob chooses two circulant matrices $B_1, B_2 \in M_n(W)$ as his private keys. He computes his public key $V = B_1 \otimes M \otimes B_2$ and sends it to Alice;

(3) Alice computes: $K_{a b} = A_1 \otimes V \otimes A_2 = A_1 \otimes B_1 \otimes M \otimes B_2 \otimes A_2$. Bob computes: $K_{b a} = B_1 \otimes U \otimes B_2 = B_1 \otimes A_1 \otimes M \otimes A_2 \otimes B_2$. By the commutability of the circulant matrix, $K_{a b} = K_{b a}$.

(4) Alice and Bob compute the shared key:

An example with small parameter.

Alice and Bob choose $p = 199$ and the public matrix $M$,

(1) Alice chooses two circulant matrices $A_1, A_2 \in M_5(W)$ and computes $U$;

(2) Bob chooses two circulant matrices $B_1, B_2 \in M_5(W)$ and computes $V$;

(3) Alice and Bob's shared matrix is

(4) Alice and Bob's shared key is

Table 7 shows the size of the private and public key matrices under different parameters, as well as the time of key generation, where the elements of the matrix are randomly selected in $\left[0, 10^6\right]$ and $p = 199$.

4.   Security analysis

In this section, we evaluate the security of the proposed key exchange protocol.

Definition 4.1. Let $A_1, A_2 \in M_n(W)$ be circulant matrices and $M \in M_n(W)$ be an arbitrary matrix. Suppose that $A_1 \otimes M \otimes A_2 = U$. The two-side digital circulant matrix action problem (MAP) is to find two circulant matrices $A_1, A_2 \in M_n(W)$ such that $A_1 \otimes M \otimes A_2 = U$, given the matrices $M, U$.

Definition 4.2. Let $A_1, A_2, B_1, B_2 \in M_n(W)$ be circulant matrices and $M \in M_n(W)$ be an arbitrary matrix. Suppose that $A_1 \otimes M \otimes A_2 = U$ and $B_1 \otimes M \otimes B_2 = V$. The computational two-side digital circulant matrix action problem (CMAP) is to find a matrix $K_{a b} \in M_n(W)$ such that $A_1 \otimes B_1 \otimes M \otimes B_2 \otimes A_2 = K_{a b}$, given the matrices $M, U,$ and $V$.

Proposition 4.3. An algorithm that solves MAP can be used to solve CMAP.

Proof. Suppose there is an algorithm $\mathcal{A}$ of solving MAP. Then, for $M, U, V$ in definition 4.2, $\mathcal{A}(M, U) = (A_1, A_2)$ such that $A_1M A_2 = U$.

So, we have

Proposition 4.4. Solving CMAP is equivalent to finding the matrix $K_{a b}$ from the public information of the protocol.

Proof. Suppose there is an algorithm $\mathcal{A}$ of solving CMAP. Let the public information in the protocol be public matrix $M$, Alice's public key $U$, and Bob's public key $V$. Then,

Conversely, suppose there is an algorithm $\mathcal{B}$ which can compute the matrix $K_{a b}$ when the input is the public information in the protocol. Let the instance of CMAP be $(M, U, V)$. Then we can take $M$ as the public matrix, $U$ as Alice's public key, and $V$ as Bob's public key. So, $\mathcal{B}(M, U, V) = K_{a b}$. According to Definition 4.2, this solves the problem of CMAP.

Proposition 4.5. MAP can be reduced to the problem of solving quadratic polynomial systems over the digital semiring.

Proof. Suppose there is an algorithm $\mathcal{A}$ which can solve the systems of quadratic polynomial equations over this semiring. That is,

where $f_i = f_i(x_1, \cdots, x_n)$ is a quadratic polynomial over this semiring and $a_i\in W$ such that

Suppose that we are given $U, M\in M_n(W)$, where $U = A_1 M A_2$ for some $A_1, A_2\in M_n(W)$. Then we can find $A_1, A_2$ by the algorithm $\mathcal{A}$. Let

and

By $U = A_1 M A_2$, we can obtain a system of quadratic polynomial equations with $2n$ unknowns $x_1, \cdots, x_n, y_1, \cdots, y_n$ and $n^2$ equations as follows,

Now, we can compute its solution by the algorithm $\mathcal{A}$ since $g_1, \cdots, g_{n^2}$ are the quadratic polynomial equations over the semiring.

Proposition 4.6. The computational complexity of solving the CMAP by enumeration is $O\left(\left(n^2+1\right) t^{n^2}\right)$, where $n$ is the order of the matrix and $t$ is the number of distinct elements in $U, V, M$.

Proof. $K_{a b}$ is completely dependent on the matrices $U, V$, and $M$, that is, $K_{a b}$ is a certain combination of different elements in $U, V$, and $M$. If we solve CMAP through an exhaustive attack, we need to enumerate all possible scenarios, which requires $O(t^{n^2})$ operations, where $t$ is the number of different elements in $U, V$, and $M$, and $n$ is the order of the matrix. After each operation, we need to determine whether the possible value is equal to $K_{a b}$, each determination requires $O\left(n^2\right)$ operations, and verifying all possible values requires $O\left(n^2 t^{t^{n^2}}\right)$ operations. Therefore, in the worst case, where all combinations need to be verified, $O\left(\left(n^2+1\right) t^{n^2}\right)$ operations are required. Therefore, the computational complexity of solving CMAP through exhaustive search is $O\left(\left(n^2+1\right) t^{n^2}\right)$.

In summary, it is infeasible for an attacker to obtain the shared secret key using exhaustive search methods. The attacker's only option is to acquire the shared matrix $K_{a b}$ by solving the MAP or CMAP. However, the currently known methods for solving MAP involve addressing quadratic polynomial systems over the digital semiring. Theorem 2.4 demonstrates that solving such systems of equations is typically NP-hard.

In the appendix, we explain why the key exchange protocol based on the digital semiring is resistant to Kotov-Ushakov(KU) attacks.

5.   Conclusions

This paper introduces a novel semiring structure called the digital semiring and proposes a new key exchange protocol based on it. The shared matrix $K_{ab}$ in this protocol is entirely dependent on the matrices $U$, $V$, and $M$, but this does not compromise the security of the protocol. Solving $K_{ab}$ through $U$, $V$, and $M$ is equivalent to solving the CMAP. Proposition 4.6 states that the computational complexity of CMAP is $O((n^2+1)t^{n^2})$. Current methods for solving CMAP involve addressing quadratic polynomial systems over the digital semiring. Theorem 2.4 demonstrates that solving such systems is an NP-hard problem. Additionally, the traditional KU attack cannot be applied within the digital semiring.

This work highlights the application value of the digital semiring in cryptography. This semiring possesses many intriguing properties that are yet to be discovered, presenting ample opportunities for future research. We recommend further exploration of the structure and properties of the digital semiring to uncover its full potential in cryptography and related fields.

The key exchange protocol proposed in this study offers a new primitive for post-quantum cryptography. This not only enriches the theoretical framework of cryptography but also provides new methods for constructing secure encryption systems. Future work could include the following directions:

(1) In-depth analysis of the algebraic properties of the digital semiring: Investigate its behavior under different operations to identify possible optimizations and enhancements.

(2) Expanding the application scope of the digital semiring: Explore its potential use in other cryptographic problems, such as signature algorithms and zero-knowledge proofs.

(3) Improving efficiency and security of the protocol: Enhance the performance and resistance to attacks by refining algorithms and incorporating new mathematical tools.

(4) Experimental validation and practical implementation: Test the protocol's performance and security in real-world applications to facilitate its practical adoption.

In conclusion, the digital semiring offers new perspectives and tools for cryptographic research, and we anticipate that future studies will further explore its potential, contributing new insights and advancements to the field of cryptography.

Author contributions

Huawei Huang: Methodology, supervision, writing-review & editing; Xin Jiang: writing-original draft, software, validation; Changwen Peng: Writing-review & editing, investigation; Geyang Pan: Software, validation. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by the Science and Technology Foundation of Guizhou Province (QIANKEHEJICHU-ZK [2021] Ordinary313), the National Key Research and Development Program of China (No.2022YFB2701401), the National Natural Science Foundation of China (No. 62272124, 61462016, U1836205).

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Appendix.   Resist KU attack

The tropical semiring $\left(a \oplus_1 b = \min (a, b), a \otimes_1 b = a+b\right)$ has higher computational efficiency, which has attracted many cryptologists' research in recent years. However, there are also many attacks. In particular, the KU attack has a significant impact on two-side tropical matrix action. Next, we will describe the KU attack and explain how our scheme can resist this attack.

KU attack ^[14]:

Assuming matrices $A, B$, and $U\left( = p_1(A) \otimes_1 p_2(B)\right)$ are known, find $X$ and $Y$ such that $U = X \otimes_1 Y$.

(1) suppose $X = \underset{i = 0}{\stackrel{D}{\oplus}} x_i \otimes_1 A^i, Y = \underset{j = 0}{\stackrel{D}{\oplus}} y_j \otimes_1 B^j$;

(2)

where $V^{i j} = A^i \otimes_{1} B^j$;

(3) From the properties of tropical semiring operations, we can obtain:

where $T^{i j} = A^i \otimes_1 B^j-U$;

(4) Compute $m_{i j} = \min _{i, j}\left(T_{r s}^{i j}\right), P_{i j} = \left\{(r, s) \mid T_{r s}^{i j} = m_{i j}\right\}$;

(5) Among all minimal covers of Cartesian product $[1, 2, \cdots, n] \times[1, 2, \cdots, n]$ by $P_{i j}$, that is, all minimal subsets $\tau \subseteq[0, 1, \cdots, D] \times[0, 1, \cdots, D]$ such that

find a cover for which the system $\left\{\begin{array}{l}x_i+y_j = -m_{i j}, (i, j) \in \tau \\ x_i+y_j \geq-m_{i j}, (i, j) \notin \tau\end{array}\right.$ is solvable.

We can find that from step (2) to step (3):

Now, regarding the new semiring in this article, we analyze whether similar methods are feasible. Since any circulant matrix can be linearly represented by a basic circulant matrix, that is,

where

0 is the additive identity element, and $\infty$ is the multiplicative identity element.

In our protocol,

(a) let $A_1 = \bigoplus_{i = 0}^{n-1} a_i \otimes P^i, A_2 = \bigoplus_{j = 0}^{n-1} b_j \otimes P^j$, such that $U = A_1 \otimes M \otimes A_2$;

(b) $U = A_1 \otimes M \otimes A_2 = \bigoplus_{i = 0, j = 0}^{n-1} (a_i \otimes b_j) \otimes P^i \otimes M \otimes P^j = \bigoplus_{i = 0, j = 0}^{n-1} (a_i \otimes b_j) \otimes V^{i j}$ where $V^{i j} = P^i \otimes M \otimes P^j$.

However, due to the difference of operation between digital semiring and tropical semirings, the implication relationship similar to $(\diamond)$ cannot be established on the digital semiring. Therefore, our protocol can resist the KU attack.