Ratio Mathematica Volume 41, 2021, pp. 19-27 Encryption using semigroup action Anooja I* Vinod S† Biju G.S‡ Abstract An enciphering transformation is a function f that converts any plain- text message into a ciphertext message and deciphering transforma- tion is a function f−1, which reverse the process. Such a set-up is called a cryptosystem. In this paper, we extend a generalization of the original Diffie-Hellman key exchange and ElGamal cryptosystem in (Z/pZ)∗ by constructing a semigroup action on a finite dimensional vector space T over F2. Keywords: semigroup action; enciphering; plaintext; ciphertext; cryp- tosystem 2010 AMS subject classifications: 94A60, 08A70, 08A62. 1 *Department of Mathematics, CMS College Kottayam (Autonomous), Kottayam 686 001 Ker- ala, India; anoojai@gmail.com. †Department of Mathematics, Government College for Women, Thiruvananthapuram, Kerala, India; wenod76@gmail.com. ‡Department of Mathematics, College of Engineering, Thiruvananthapuram-695016, Kerala, India; gsbiju@cet.ac.in. 1Received on August 23, 2021. Accepted on December 14, 2021. Published on December 31, 2021. doi: 10.23755/rm.v41i0.649. ISSN: 1592-7415. eISSN: 2282-8214. ©Anooja et al. This paper is published under the CC-BY licence agreement. 19 Anooja I, Vinod S, Biju G.S 1 Introduction Recently there has been a lot of on-going research work to find more secure and efficient public key cryptosystems based on algebraic structures such as non- abelian groups, linear groups, semigroups and power series rings (see Anshel et al. [1999], Baumslag et al. [2006], Maze et al. [2007], Shpilrain and Zapata [2006]), and where the security is based on hard algorithmic problems from combinato- rial group theory. The hard problems from combinatorial group theory include the conjugacy search problem, the decomposition search problem and the sub- group membership search problem. Most common public key cryptosystems and public key exchange protocols presently in use, such as the RSA algorithm, Diffie- Hellman, and elliptic curve methods are number theory based and hence depend on the structure of abelian groups. The idea of using semigroups as platforms for public key cryptosystems has appeared in several papers. Yamamura [1998] has considered a group action of Sl2(Z). Blackburn and Galbraith [1999] have analyzed the system of Yamamura and they have shown that it is insecure. Maze et al. [2007] showed that the discrete logarithm problem over a group can be considered as a special case of an action by a semigroup on a set. They showed that every semigroup action by an abelian semigroup on a set gives rise to a Diffie-Hellman key exchange. By taking the action of the semigroup on itself, a semigroup can then be used as a platform for a public key cryptosystem. Kropholler et al. [2010] studied the potential of the semigroup 〈a, b ; ap = br, aq = bs〉 as platforms for the Diffie-Hellman key exchange protocol. Special instances of semigroup actions appears in Anshel et al. [1999], Shpilrain and Ushakov [2005], Ko et al. [2000] and Slavin [2007]. In this paper, we try to extend a generalization of the original Diffie-Hellman key exchange and ElGamal cryptosystem in (Z/pZ)∗ by constructing a semigroup from a (p, q)-graph G and defining a semigroup action on a finite vector space of dimension q over the field F2. 2 Notations and Basic Results Most of the notations, definitions and results we mentioned here are standard and can be found in Menezes et al. [1996], Koblitz [1998], Lyndon and Schupp [1977], Maze et al. [2007] and Diffie and Hellman [1976]. Most of the public key cryptosystems and public key exchange protocols cur- rently in use, like the Diffie and Hellman [1976] key exchange protocol, the ElGa- mal [1985] public key cryptosystem, the Digital Signature Algorithm (DSA) and the ElGamal’s signature scheme, use the discrete logarithm problem as the basis of their security. 20 Encryption Using Semigroup Action The discrete logarithm problem can be defined as follows. Problem 2.1. (Discrete Logarithm Problem) Let G be a group and a, b ∈ G. Find an integer n ∈ N such that an = b. Problem (2.1) has a solution if and only if b ∈ 〈a〉, the cyclic group generated by a. If b ∈ 〈a〉 then there is a unique integer n satisfying 1 ≤ n ≤ ord(a) such that an = b. This unique integer is called the discrete logarithm of b with base a and denote it by loga b. Discrete Logarithm Problem plays important role in the Diffie-Hellman key agreement and the ElGamal public key cryptosystem, the digital signature algorithm and ElGamal’s signature scheme. Currently the multiplicative group (Z/pZ)∗ of integers modulo n where n is a prime is widely used as the platform group. Protocol 2.1. (Diffie-Hellman Key Exchange Protocol) Let G be a group. 1. Alice and Bob publicly agree on an element g ∈ G. 2. Alice chooses n ∈ N and computes gn . Alice’s private key is n, her public key is gn. 3. Bob chooses m ∈ N and computes gm . Bob’s private key is m, his public key is gm. 4. Their common secret key is then gmn. The ElGamal public key cryptosystem works as follows: Alice chooses n ∈ N, a, b ∈ G where b = an. The private key of Alice is (a, b, n), the public key is (a, b). Bob chooses a random integer r ∈ N and he applies the encryption function ϕ : G → G×G m → (c1, c2) = (ar, mbr) Alice computes m from the ciphertext (c1, c2) by m = c2(cn1) −1. 3 Construction of a semigroup from a (p, q)- graph Let G be a finite (p, q)-graph and H be a subgraph of G. Let xH denote a vector corresponding to H such that xH = (x1, x2, . . . , xq) where xi = { 1 if ei is in H 0 otherwisef 21 Anooja I, Vinod S, Biju G.S Figure 1: Graph G Let S be a set of such vectors. Then S is a semigroup under the operation defined by xH yK = (x1, x2, . . . , xq)(y1, y2, . . . , yq) = (x1y1, x2y2, . . . , xqyq) We shall illustrate this with the following example. Example 3.1. Consider the graph G with p = 6 and q = 10 given in Figure 1. Let us consider seven subgraphs of G, which are displayed in Figure 2. Let xH1 , xH2, . . .,xH7 be the vectors corresponding to the subgraphs H1, H2, . . ., H7 respectively. Let S = {xH1, xH2, . . . , xH7}. Then xH1 = (1, 0, 1, 0, 0, 1, 0, 0, 1, 1) xH2 = (1, 1, 0, 0, 0, 1, 1, 0, 0, 0) xH3 = (1, 1, 1, 0, 0, 0, 0, 0, 1, 0) xH4 = (1, 0, 0, 0, 0, 1, 0, 0, 0, 0) xH5 = (1, 0, 1, 0, 0, 0, 0, 0, 1, 0) xH6 = (1, 1, 0, 0, 0, 0, 0, 0, 0, 0) xH7 = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0) 22 Encryption Using Semigroup Action Figure 2: Subgraphs of the graph G 23 Anooja I, Vinod S, Biju G.S Now, xH1xH2 = xH4, xH1xH3 = xH5, xH1xH4 = xH4, xH1xH5 = xH5, xH1xH6 = xH7, xH1xH7 = xH7, xH2xH3 = xH6, xH2xH4 = xH4, xH2xH5 = xH7, xH2xH6 = xH6, xH2xH7 = xH7, xH3xH4 = xH7, xH3xH5 = xH5, xH3xH6 = xH6, xH3xH7 = xH7, xH4xH5 = xH7, xH4xH6 = xH7, xH4xH7 = xH7, xH5xH6 = xH7, xH5xH7 = xH7, xH6xH7 = xH7 Also, xHi(xHjxHk) = (xHixHj)xHk, i, j, k = 1, 2, . . . , 7. Hence S is a semigroup. 4 Key Exchange using S-action Let T be a q dimensional vector space over F2. Define the left action of S on T , ϕ : S × T → T such that ϕ(x, t) = xt. We call this action as an S-action on the vector space T . The right action is similarly defined. Let G be a (p, q)-graph, S an abelian semigroup associated with the graph G, T be a q dimensional vector space over F2, and an S-action on T as defined above. Diffie-Hellman key exchange using S-action is as follows: 1. Alice and Bob agree on an element t ∈ T . 2. Alice chooses x ∈ S and computes xt. Alice’s private key is x, her public key is xt. 3. Bob chooses y ∈ S and computes yt. Bobss private key is y, his public key is yt. 4. Their common secret key is then x(yt) = (xy)t = (yx)t = y(xt). Example 4.1. Consider the semigroup S in the example 3.1. Let T be a 10 di- mensional vector space over F2. Suppose Alice and Bob want to agree on a key. Suppose they choose t = (0, 1, 1, 0, 1, 0, 1, 1, 0, 0) ∈ T . Then Alice chooses xH1 = (1, 0, 1, 0, 0, 1, 0, 0, 1, 1) ∈ S and computes xH1t = (0, 0, 1, 0, 0, 0, 0, 0, 0, 0). Then send it to Bob. Similarly, Bob chooses xH6 = (1, 1, 0, 0, 0, 1, 0, 0, 1, 1) ∈ S and computes xH6t = (0, 1, 0, 0, 0, 0, 0, 0, 0, 0). Then send it to Alice. Their com- mon key is xH1(xH6t) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0). 24 Encryption Using Semigroup Action S-action Problem Let G be a (p, q)-graph and S be a semigroup associated with the graph G, acting on a q dimensional vector space T over F2. Given elements t ∈ T and y ∈ S, find x ∈ S such that xt = y. 4.1 Diffie-Hellman Problem using S-action Let G be a (p, q)-graph, S be a semigroup associated with the graph G, T be a q dimensional vector space over F2 and ϕ be an S-action on T . Given r, s, t ∈ T with s = xr and t = yr for some x, y ∈ S, find (xy)r ∈ T . 5 Cryptosystem using S-action Let G be a (p, q)-graph, S be a semigroup associated with the graph G, T be a q dimensional vector space over F2, T is an additive abelian group and an action on T as defined above. ElGamal cryptosystem using S-action is as follows: 1. Alice chooses elements t ∈ T and x ∈ S. Alice’s public key is (t, xt). 2. Bob chooses a random element y ∈ S and encrypts a message m using the encryption function (m, y) 7→ (yt, (y(xt)) + m) = (c1, c2). 3. Alice can decrypt the message using m = (y(xt))−1 + (y(xt)) + m = (xc1) −1 + c2 Note: Message m is also represented as vectors. Each letter in the message repre- sents a vector (x1, x2, . . . , xq), q ≥ 26 such that xi = { 1 if the corresponding letter is in ith position of the alphabet 0 otherwise Example 5.1. Let G be any (p, q)-graph with q = 26. Let T be a 26 dimensional vector space over F2, T be an additive abelian group and S be the semigroup associated with the graph G. The action of S on T is as defined earlier. Suppose Alice wants to receive a message. 25 Anooja I, Vinod S, Biju G.S 1. Alice chooses t = (0, 1, 1, 0, 1, 0, 1, 1, 0, . . . , 0) ∈ T . Then chooses x = (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, . . . , 0) ∈ S corresponding to one subgraph H1 of G and compute xt = (0, 0, 1, 0, 1, 0, 1, 0, 0, . . . , 0). Her public key is (t, tx). 2. Bob wishes to send a message m = MEET ME TOMORROW to Alice. He send it letter by letter. So, first he wants to send the letter M = m1(m) = (0, 0, . . . , 0, 0, 1, 0, 0, . . . , 0, 0). For, he chooses y = (0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, . . . , 0, 0) ∈ S that is a vector corresponding to one subgraphH2 of G and compute yt = (0, 0, 1, 0, 1, 0, 0, 1, 0, 0, . . . , 0, 0) = c1 y(xt) = (0, 0, 1, 0, 1, 0, 0, . . . , 0, 0) and y(xt) = (0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, . . . , 0, 0) = c2 Then he sends (c1, c2) to Alice. 3. After receiving this, Alice decrypt the message by computing (xc1)−1 + c2. xc1 = (0, 0, 1, 0, 1, 0, 0, . . . , 0, 0) (xc1) −1 = (0, 0, 1, 0, 1, 0, 0, . . . , 0, 0) (xc1) −1 + c2 = (0, 0, 0, . . . , 0, 0, 1, 0, . . . , 0, 0) = m1(m) = M Similarly, they transfer each letter in the message. References Iris Anshel, Michael Anshel, and Dorian Goldfeld. An algebraic method for pub- lic key cryptography. Mathematical Research Letters, 6(3–4):287–291, 1999. Gilbert Baumslag, Benjamin Fine, and Xiaowei Xu. Cryptosystems using linear groups. Applicable Algebra in Engineering, Communication and Computing, 17(3):205–217, 2006. Simon R Blackburn and Steven Galbraith. Cryptanalysis of two cryptosystems based on group actions. In International Conference on the Theory and Ap- plication of Cryptology and Information Security, volume 3531, pages 52–61. Springer, 1999. 26 Encryption Using Semigroup Action Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE transactions on Information Theory, 22(6):644–654, 1976. Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4):469–472, 1985. Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, and Choonsik Park. New public-key cryptosystem using braid groups. In Annual International Cryptology Conference, pages 166–183. Springer, 2000. Neal Koblitz. Algebraic methods of cryptography. Berlin Heidelberg New York: Springer, 1998. PH Kropholler, SJ Pride, WAM Othman, KB Wong, and PC Wong. Properties of certain semigroups and their potential as platforms for cryptosystems. In Semigroup Forum, volume 81, pages 172–186. Springer, 2010. Roger C Lyndon and Paul E Schupp. Combinatorial group theory. Berlin Heidel- berg New York: Springer, 1977. Gérard Maze, Chris Monico, and Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances of Mathematics of Communications, 1 (4):489–507, 2007. Alfred J Menezes, Paul C Van Oorschot, and Scott A Vanstone. Handbook of Applied Cryptography. Discrete Mathematics and Its Applications. CRC press, New York, 1996. Vladimir Shpilrain and Alexander Ushakov. Thompson’s group and public key cryptography. In International Conference on Applied Cryptography and Net- work Security, pages 151–163. Springer, 2005. Vladimir Shpilrain and Gabriel Zapata. Combinatorial group theory and public key cryptography. Applicable Algebra in Engineering, Communication and Computing, 17(3):291–302, 2006. Keith R Slavin. Public key cryptography using matrices. 2007. US Patent 10260818, http://www.patentstorm.us/patents/7184551-fulltext.html. Akihiro Yamamura. Public-key cryptosystems using the modular group. In In- ternational Workshop on Public Key Cryptography, pages 203–216. Springer, 1998. 27