On key exchange protocol based on Two-side multiplication action

Otero Sanchez, Alvaro · 2025

Read On key exchange protocol based on Two-side multiplication action by Otero Sanchez, Alvaro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15880.txt.

Introduction

Alvaro Otero Sanchez breaks a key exchange protocol in a 2025 paper on cryptography. The protocol builds shared secrets from a two sided multiplication action over a digital semiring. Sanchez finds the top solution of a linear system over that semiring. Matrix traits of a special circulant form then expose the flaw. The attack rebuilds the shared secret from public data for any case, in polynomial time, so the protocol falls in practice.

Catalog record

CREATOROtero Sanchez, Alvaro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15880

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On key exchange protocol based on Two-side multiplication action Otero Sanchez, Alvaro Abstract We present a cryptanalysis of a two key exchange protocol based on two-side multiplication action. For this purpose, we use the properties of the algebraic structures to obtain a linear system whose solution enable to provide an efficient attack that recovers the shared secret key from publicly exchanged information for any instance of the digital semiring and twisted group ring in polynomial time. The modern cryptosystems appears with the fundational work of Diffie-Hellman [ 13 ] , with foundations upon the difficulty of the discrete logarithm problem in cyclic groups, especially over elliptic curves. Nevertheless, advanced in quantum computing threat the secutity of those protocols. In particular, in 1994, Shor introduced a quantum algorithm capable of efficiently solving this problem. This marked the start of the research in post-quantum cryptography, dedicated to constructing cryptographic schemes resilient to quantum attacks. As a possible solution, Maze et al. [ 12 ] proposed a key exchange protocol using semigroup. This papers is the beginning for cryptography based on semiring, as in that paper a finite congruence simple semiring is proposed as a possible algebraic framework. These algorithm can be interpreted as a generalization of classical protocols such as the Diffie-Hellman [ 13 ] and ElGamal [ 14 ] protocols, but instead of a cyclic group, they use abelian semigroups. Their framework has inspired various cryptographic developments. For example, Kahrobaei and Koupparis [ 11 ] explored the use of non-abelian group actions, pushing the original idea into the realm of non-commutative algebra. Similarly, Gnilke and Zumbrägel [ 16 ] connected these concepts with recent progress in isogeny-based cryptography. Another extension can be found in the work of Torrecillas - Olvera - Lopez [ 17 ] , who applied twisted group rings to design new key exchange mechanisms. However, the instance proposed in [ 12 ] has been shown recently to be vulnerable to cryptanalysis [ 15 ] . Here, we present a generalization of the last one and show how to apply it to different algebraic structures. In another line of research, Grigoriev and Shpilrain investigated the use of tropical semirings as a foundation for public key cryptography, including both key exchange protocols [ 4 , 5 ] and digital signature schemes [ 6 ] . Nevertheless, Kotov and Ushakov [ 7 ] introduced a heuristic algorithm known as the Kotov-Ushakov attack which has become a standard method of cryptanalysis in tropical cryptography. However, that algorithm is based on the solution of an minimal set cover problem, which is one of Karp’s 21 prob- lems shown to be NP-complete in 1972. Recently, Otero et all [ 3 ] recently proposed a deterministic alternative that avoids NP-problems and find a solution in polynomial time. Moreover, other schemes based on tropical algebra by Grigoriev and Shpilrain have also been shown to lack security, as demonstrated in several studies [ 10 , 8 , 9 ] . In [ 20 ] , the authors propose the use of a group ring to perform a key exchange protocol. This idea has been generalized in other works, such as in [ 17 ] , where the action is modified to a two-sided action similar to that of [ 12 ] , and the group ring is twisted by a 2-cocycle with the dihedral group. Another example is presented in [ 21 ] , where the subspaces on which the two-sided action is performed and the twist are altered. However, the latter approach was cryptanalyzed recently in [ 22 ] , where the authors reduce the two-sided problem to a system of equations over circulant matrices, using specific equations that arise when the base group is the dihedral group. They provide a probabilistic solution, where the attacker must find an element by random sampling under certain conditions. Nevertheless, the security of this approach in the context of a different group or a new twist remains an open question. In this paper, we introduce a novel approach that allows for a comprehensive cryptanalysis of all such cases. More recently, new directions have emerged leveraging semiring structures for practical cryptographic applications. In particular, Nassr et al. proposed a public-key encryption scheme grounded on the hardness of the two-sided digital circulant matrix action problem over a semiring initially introduced by Huang et al. [ 2 ] . Between the time our preprint was made publicly available and the final publication of our article, a paper was published presenting a cryptanalysis of the protocol based on digital numbers [ 24 ] . However, as the authors of that work acknowledge in their introduction, our results precede the publication of their article. Moreover, the approach by which the solutions are obtained differs significantly from theirs and is both distinct and independent. In addition, we have added the finite ring section to show how our method is different and able to analyze a wide range of cryptosystems In this paper, we will show how a similar method can be applied to cryptoanalyce different protocols based on two side multiplication, providing as example the protocol over digital semiring of [ 2 ] and other over twisted group ring as in [ 17 ] . 1 General attack against two side action Modern example of two side action on cryptogrpahy are base in the original paper [ 12 ] , In that paper, the following general setting is presented Definition 1.1 . Let S be a semiring. A left S -semimodule is a commutative monoid (Mo,+,0_{M}) equipped with a scalar multiplication S\times Mo\to Mo , denoted (s,m)\mapsto sm , such that for all s,t\in S and all m,n\in Mo , the following axioms hold: 1. s(m+n)=sm+sn (left distributivity) 2. (s+t)m=sm+tm (right distributivity) 3. (st)m=s(tm) (associativity) 4. 1_{S}m=m (identity) 5. 0_{S}m=s0_{M}=0_{M} (annihilation) If S is a semiring with multiplicative identity 1_{S} , then 1_{S} acts as the identity on Mo . A right S -semimodule is defined analogously, with scalar multiplication Mo\times S\to Mo . The key exchange protocol prensented is Protocol 1.2 . Let S be a semiring. Alice and Bob agree M\in S and two commutative set T_{1},T_{2}\subset S . 1. Alice chose (A_{1},A_{2})\in T_{1}\times T_{2} and makes public pk_{1}=A_{1}MA_{2} 2. Bob chose (B_{1},B_{2})\in T_{1}\times T_{2} and makes public pk_{1}=B_{1}MB_{2} 3. Alice computes A_{1}pk_{2}A_{2} and Bob computes B_{1}pk_{1}B_{2} The common key is A_{1}pk_{2}A_{2}=A_{1}B_{1}MB_{2}A_{2}=B_{1}A_{1}MA_{2}B_{2}=B_{1}pk_{1}B_{2} Those key exchange protocol are so called two-side action key exchange. In some papers, as in [ 12 ] , T_{i}=C[M_{i}]=\{\sum_{j=0}^{m}r_{j}M_{i}^{j};r_{j}\in Z(S)\} with Z(S) the center of the semiring S . Other commutative sets are the circulant matrix, as in [ 2 ] . In general, the security of such protocol relies on the following problems Problem 1.3 (SAP) . Let S be a semiring. Let (A_{1},A_{2})\in T_{1}\times T_{2} with T_{1},T_{2} commutative sets of S , and let U=A_{1}MA_{2} for an arbitrary element M\in S . Given U and M , the challenge is to obtain two elements (A_{1}^{\prime},A_{2}^{\prime})\in T_{1}\times T_{2} such that U=A_{1}^{\prime}MA_{2}^{\prime}. Problem 1.4 (Diffie-hellman Problem over semiring) . Let S be a semiring. Let (A_{1},A_{2}),(B_{1},B_{2})\in T_{1}\times T_{2} be elements with T_{1},T_{2} commutative sets of S , and U=A_{1}MA_{2} , and V=B_{1}MB_{2} for an arbitrary element M\in S .

Read the complete text