Keywords

1 Introduction

A lot of study regarding group factorization theory of abelian group written additively had been conducted over the years. The study of group factorization was first initiated by Hajos in year 1938 [13]. He successfully solved a geometry problem that raised by Minkowski by using group theoretical equivalent [14]. This scenario attracted the attention of studying the factorization of a finite abelian group into not necessary subgroup factors [15]. Many type of algebraic structures were derived from group factorization. One of the algebraic structure is exhaustion number as defined in [6]. In [8], they investigated the exhaustion number of dihedral group of order 2p, where p is an odd prime. Another type of analogous of group factorization, namely complete decomposition is defined as follows: Let G be a finite non-abelian group. Let \(A_1,\cdots , A_k\) be non-empty subsets of G, where \(k \ge 2\) is an integer such that \(A_i\cap A_j = \emptyset \) for integers \(i,j= 1,\cdots , k\) \((i \ne j)\). We say that \((A_1, \cdots , A_k)\) is a complete decomposition of G if the product of subsets \(A_{i_1} \cdots A_{i_k} = \{a_{i_1}...a_{i_k} | a_{i_j}\in A_{i_j}; j=1,\cdots , k\}\) coincides with G where the \(A_{i_j}\) are all distinct and \(\{A_{i_1},\cdots , A_{i_k}\}= \{A_1,\cdots , A_k\}\). The investigation of complete decomposition of some finites groups can be found in [5].

Computational hardness assumptions are essential elements in cryptography. They are building blocks of a cryptographic primitive. Generally, computer scientist relates the hardness of a new problem to a well-known hardness assumption by reduction. Researchers reviewed the proposed hardness problem continuously over the years [4, 11, 24, 25]. There are many hardness problems proposed in the past, such as integer factorization problem, Rivest-Shamir-Adleman (RSA) problem, discrete logarithm problem, knapsack problem etc. In this paper, we proposed some group-based hardness problem. One of the well known group-based hardness problem proposed is the Conjugacy Search Problem (CSP) [20]. The similarity of our proposed hardness problem and CSP is the utilization of non-commutative properties of the underlying group.

Diffie and Hellman [9] first developed the idea of asymmetric key exchange protocol. The security of Diffie-Hellman key exchange protocol depended on the hardness of the discrete logarithm problem (DLP). Two years later, Rivest, Shamir and Aldeman applied the hardness of integer factorization problem (IFP) to propose an encryption scheme which known as RSA encryption scheme [17]. However, Shor [18] proposed an algorithm that can feasibly solve many conventional number theory based problem. Therefore, the security of public-key cryptosystems that relied on some well-studied hardness problem such as DLP and IFP become questionable. Thus, researchers start looking into code-based, lattice-based, hash-based and group-based cryptographic primitives that suspected to remain secure under post-quantum attack [3].

Numerous studies regarding group-based cryptography had been conducted over the years [10]. The idea of constructing some cryptographic primitives based on the non-commutative group has been discussed in [19]. There are some constructions of cryptographic primitives based on the braid group by applying the conjugacy search problem (CSP) [1, 7, 16]. Baba et al. [2] constructed a relevant analogy from the integer factorization problem to the factorization problem over non-abelian groups. Gu and Zheng proposed several conjugated problems related to the factorization problem over non-abelian groups and showed three constructions of cryptographic primitives based on these conjugacy systems [12]. The idea that using the complexity of infinite non-abelian groups in cryptography was first proposed by Wagner and Magyarik [23]. They devised a public-key protocol based on unsolvability of the word problem in 1985. Search problems are the most suggested protocols and they are variants of decision problems of group theory. They are suitable for the general paradigm of a public key protocol. Some of the key exchange protocols related to non-commutative groups were proposed in [21, 22].

Our Contribution. The main contribution of this paper is to propose a new hardness problem called Complete Decomposition Search Problem (CDSP). We construct a key exchange protocol based on CDSP. We choose generalized quaternion group \(Q_{2^n}\) as our platform group. We also provide some constructions of complete decomposition of \(Q_{2^n}\) to show that the CDSP can be practically applied. Besides, we compare the performance of our scheme with the Diffie-Hellman key exchange protocol. Finally, we present some simple security analysis of the proposed scheme.

2 Some Constructions of Complete Decomposition of \(Q_{2^n}\)

The generalized quaternion group \(Q_{2^n}\) is a finite non-abelian group with group presentation \(\langle x,y| x^{2^{n-1}}=1, y^2=x^{2^{n-2}}, yx=x^{2^{n-1}-1}y\rangle \) for integer \(n \ge 3\). In this section, we first introduce some of the multiplication rules for the elements in the generalized quaternion group \(Q_{2^n}\). Then, we provide a construction of complete decomposition of \(Q_{2^n}\).

Lemma 1

Let i, n be some integers such that \(1 \le i \le 2^{n-1}-1\) and \(n \ge 3\). Then the following properties holds:

  1. (i)

    \(x^iy = yx^{2^{n-1}-i}\);

  2. (ii)

    \(\langle x \rangle yx^i= \langle x \rangle y.\)

Proof

Note that \(\langle x \rangle = \{1,x,x^2,\dots ,x^{2^{n-1}-1}\}\) and \(\langle x \rangle y= \{y,xy,\dots ,x^{2^{n-1}-1}y\}\). By employing induction on i, the basic step \(xy=yx^{2^{n-1}-1}\) for \(i=1\) holds. Assume that it is true when \(i=k\) for some positive integers k, then \(x^ky=yx^{2^{n-1}-k}\). Now, we show that the case \(i=k+1\) is true. For \(i=k+1\), we have \(x^{k+1}y=x^kxy = x^kyx^{2^{n-1}-1} =yx^{2^{n-1}-k}x^{2^{n-1}-1} = yx^{2^{n-1}}x^{2^{n-1}-(k+1)}\). Since \(x^{2^{n-1}} = 1\), it follows that \(yx^{2^{n-1}}x^{2^{n-1}-(k+1)}= yx^{2^{n-1}-(k+1)}\) as required. For part (ii), we see that \(\langle x \rangle y x^i = \{1,x,\dots ,x^{2^{n-1}-1}\}x^{2^{n-1}-i}y =\{x^{2^{n-1}-i}y\), \(x^{2^{n-1}}y\), \(\dots ,x^{2^n-i-1}y\}\). Since \(|\{x^{2^{n-1}-i}y,x^{2^{n-1}}y,\dots ,x^{2^n-i-1}y\}|=2^{n-1}\), it follows that \(\{x^{2^{n-1}-i}y,x^{2^{n-1}}y\), \(\dots \), \(x^{2^n-i-1}y\} = \langle x \rangle y\).

2.1 Construction of Complete Decomposition of \(Q_{2^n}\)

Let A, B be the subsets of \(Q_{2^n}\). To show that the complete decomposition of generalized quaternion group \(Q_{2^n}\) is not trivial, we first show an example where (A, B) is not a complete decomposition of \(Q_{2^n}\).

Example 1

Let \(A=\{1,x,\dots ,x^{2^{n-1}-1}\}\) and \(B=\{y,xy,\dots \), \(x^{2^{n-1}-1}y\}\) be the subsets of \(Q_{2^n}\). Clearly, \(A = \langle x \rangle \subseteq Q_{2^n}\) and \(B= \langle x \rangle y \subseteq Q_{2^n}\). Since \(AB \subseteq \langle x \rangle y\), it follows that (A, B) is not a complete decomposition of \(Q_{2^n}\).

Next, we provide a construction of complete decomposition of generalized quaternion group \(Q_{2^n}\) for integer \(n \ge 4\). For practical reason, the selection of subsets A and B are restricted to the condition where \(A\cup B \subsetneq Q_{2^n}\).

Proposition 1

Let \(A=\{1,x,x^2,\dots ,x^{2^{n-1}-3}\}\cup \{x^{2^{n-1}-2}y,x^{2^{n-1}-1}y\}\) and \(B_i=(\{y,xy,\dots ,x^{2^{n-1}-3}y\}\cup \{x^{2^{n-1}-2},x^{2^{n-1}-1}\} )\setminus \{xy,x^3y,\dots ,x^{i}y\}\) be the subsets of \(Q_{2^n}\), where \(i\in \{1,3,\dots \), \(2^{n-1}-5\}\), \(|A|=2^{n-1}\) and \(2^{n-2}+2 \le |B_i| \le 2^{n-1}-1\). Then \((A,B_i)\) is a complete decomposition of \(Q_{2^n}\) for integer \(n \ge 4\).

Proof

To show that \((A,B_i)\) is a complete decomposition, we first consider the case when \(i=2^{n-1}-5\). We have \(B_{2^{n-1}-5}=\{y,x^2y,\dots ,x^{2^{n-1}-6}y, x^{2^{n-1}-4}y\} \cup \{x^{2^{n-1}-3}y\} \cup \{x^{2^{n-1}-2},x^{2^{n-1}-1}\}\) with size \(2^{n-2}+2\). We compute the product of sets \(\{1,x,x^2\), \(\dots \), \(x^{2^{n-1}-3}\}\subseteq A\) and \(\{y,x^2y,\dots ,x^{2^{n-1}-4}y\}\subseteq B_{2^{n-1}-5}\) as follows:

$$\begin{aligned}&\{1,x,x^2,\dots ,x^{2^{n-1}-3}\}\{y,x^2y,x^{2^{n-1}-4}y\}\\&=\langle x \rangle y. \end{aligned}$$

Then, we compute the product of sets \(\{x^{2^{n-1}-2}y,x^{2^{n-1}-1}y\}\subseteq A\) and \(\{y,x^2y\), \(\dots \), \(x^{2^{n-1}-4}y\}\subseteq B_{2^{n-1}-5}\) as follows:

$$\begin{aligned} L_1=&\{x^{2^{n-1}-2}y,x^{2^{n-1}-1}y\}\{y,x^2y,\dots ,x^{2^{n-1}-4}y\}\\ =&\{x^{2^{n-1}+2^{n-2}+2}, x^{2^{n-1}+2^{n-2}+3},\dots ,x^{2^{n-1}+2^{n-2}+2^{n-1}-1}\} \end{aligned}$$

where \(|L_1|=2^{n-1}-2\). Then, we compute the product of sets \(\{x^{2^{n-1}-2}y,x^{2^{n-1}-1}y\}\subseteq A\) and \(\{x^{2^{n-1}-3}y\}\subseteq B_{2^{n-1}-5}\) as follows:

$$\begin{aligned} L_2=\{x^{2^{n-1}-2}y,x^{2^{n-1}-1}y\}\{x^{2^{n-1}-3}y\}=\{x^{2^{n-1}+2^{n-2}+1}, x^{2^{n-1}+2^{n-2}+2}\}. \end{aligned}$$

Observe that \(L_1\cup L_2 = \{x^{2^{n-1}+2^{n-2}+1},x^{2^{n-1}+2^{n-2}+2},\dots ,x^{2^{n-1}+2^{n-2}+2^{n-1}-1}\}\) with the size \(|L_1\cup L_2|=2^{n-1}-1\). We notice that \(\langle x \rangle \setminus (L_1\cup L_2) = \{x^{2^{n-1}+2^{n-2}+2^{n-1}}\}\). Next, we compute the product of sets \(\{1,x,\dots ,x^{2^{n-1}-3}\}\subseteq A\) and \(\{x^{2^{n-1}-2}\), \(x^{2^{n-1}-1}\}\) \(\subseteq B_{2^{n-1}-5}\) as follows:

$$\begin{aligned} L_3=&\{1,x,\dots ,x^{2^{n-1}-3}\}\{x^{2^{n-1}-2},x^{2^{n-1}-1}\}\\ =&\{x^{2^{n-1}-2},x^{2^{n-1}-1},\dots ,x^{2^{n-1}+2^{n-1}-4}\} \end{aligned}$$

where \(|L_3|=2^{n-1}-1\). From here, we see that \(\langle x \rangle \setminus L_3 = \{x^{2^{n-1}+2^{n-1}-3}\}\). To show that \((L_1\cup L_2\cup L_3)=\langle x \rangle y\), we need to show that \(x^{2^{n-1}+2^{n-2}+2^{n-1}}\ne x^{2^{n-1}+2^{n-1}-3}\). Clearly \(2^{n-1}+2^{n-2}+2^{n-1}\ne 2^{n-1}+2^{n-1}-3\) for any integer \(n \ge 4\) which implies \(x^{2^{n-1}+2^{n-2}+2^{n-1}}\ne x^{2^{n-1}+2^{n-1}-3}\). Thus, \((L_1\cup L_2\cup L_3)=\langle x \rangle y\). Therefore, we say that \((A,B_{2^{n-1}-5})\) is a complete decomposition of \(Q_{2^n}\). Since \(B_{2^{n-1}-5} \subseteq B_{2^{n-1}-7} \subseteq \dots \subseteq B_{1}\) and \((A,B_{2^{n-1}-5})\) is a complete decomposition of \(Q_{2^n}\), it follows that \((A,B_i)\) is a complete decomposition of \(Q_{2^n}\) for \(n\ge 4\) and \(i \in \{1,3,\dots ,2^{n-1}-5\}\).

3 Application on Cryptography

In this section, we first propose two problems, namely Decisional Complete Decomposition Search Problem and Computational Complete Decomposition Search Problem for arbitrary finite nonabelian group G. We provide a key exchange protocol based on the hardness problem proposed. Finally, we analyze the performance and security of the proposed scheme.

3.1 Complete Decomposition Search Problem (CDSP)

We define two problems as follows:

Decisional Complete Decomposition Search Problem (DCDSP): Let G be a finite non-abelian group. Given A, B and G. Determine whether B satisfies \(AB=G\), where \(A,B\subseteq G\) and \(A\cap B=\emptyset \).

Computational Complete Decomposition Search Problem (CCDSP): Let G be a finite non-abelian group. Given A and G. Find B such that \(AB=G\), where \(A,B\subseteq G\) and \(A\cap B=\emptyset \).

In this paper, we choose our platform group G as generalized quaternion group \(Q_{2^n}\). We construct an algorithm to solve CCDSP in \(Q_{2^n}\) below for integer \(n \ge 4\). Since \(A\cap B=\emptyset \) and \(|Q_{2^n}|=2^n\), it follows that the total combination of subsets B given |A| is \({{2^n-|A|}\atopwithdelims (){|B|}}\). Let \(\{B_j|j=1,2,\dots ,{{2^n-|A|}\atopwithdelims (){|B|}}\}\) represents all the possible subsets of B. The algorithm computes the products \(AB_1, AB_2,\dots ,AB_{{2^n-|A|}\atopwithdelims (){|B|}}\) and return \(B_j\) if \(AB_j=G\) for integer \(1 \le j \le {{2^n-|A|}\atopwithdelims (){|B|}}\).

figure a

3.2 Our Proposed Scheme

Let \(A,B\subseteq Q_{2^n}\). In this section, we propose a key exchange protocol based on the computational complete decomposition search problem (CCDSP) in \(Q_{2^n}\) between Alice and Bob. Suppose Alice holds a shared key B and wants to share with Bob. They can proceed as follows:

  1. 1.

    Preparation Step A and \(Q_{2^n}\) are selected and published, where \(AB=Q_{2^n}\). Two subsets \(A_1,A_2 \subseteq \langle x \rangle \) are selected and kept secretly. Alice chooses \(a \in A\) and two distinct elements \(b_1,b_2\in A_1\) secretly. Bob chooses \(c \in Q_{2^n}\) and two distinct elements \(d_1,d_2 \in A_2\) secretly.

  2. 2.

    Sharing private key a

    1. (a)

      Alice computes \(b_1ab_2\).

    2. (b)

      Bob computes \(d_1b_1ab_2d_2\).

    3. (c)

      Alice computes \(b_1^{-1}b_1d_1ad_2b_2b_2^{-1}\).

    4. (d)

      Bob computes \(d_1^{-1}d_1ad_2d_2^{-1}=a\).

  3. 3.

    Sharing private key c

    1. (a)

      Bob computes \(d_1cd_2\).

    2. (b)

      Alice computes \(b_1d_1cd_2b_2\).

    3. (c)

      Bob computes \(d_1^{-1}d_1b_1cb_2d_2d_2^{-1}=b_1cb_2\).

    4. (d)

      Alices computes \(b_1^{-1}b_1cb_2b_2^{-1}=c\).

  4. 4.

    Exchange shared key B

    1. (a)

      Alice and Bob compute \(ac=b\).

    2. (b)

      Alice computes \(E=Bb\).

    3. (c)

      Bob computes \(x=(ac)^{-1}=c^{-1}a^{-1}\).

    4. (d)

      Bob computes \(Ex=Bbx=Bacc^{-1}a^{-1}=B\).

Fig. 1.
figure 1

Proposed key exchange protocol

Full size image

3.3 Performance Analysis

For our proposed scheme which constructed using finite non-abelian generalized quaternion group, the steps involved are expected to be longer compare to other group-based key exchange protocol which constructed based on the abelian group. From Fig. 1, we see that sharing private key a and c between Alice and Bob involved 8 mathematical computation in total. For the step involving calculating the shared key B, there is a total of 4 mathematical computations required. The computations involved in our proposed scheme are mainly on multiplication between the group elements, which can be done easily due to the well-studied structure of the generalized quaternion group \(Q_{2^n}\).

Comparing with Diffie-Hellman Key Exchange Protocol in Term of Performance. Now, we compare the performance of our proposed scheme with the pioneer of the key exchange protocol, which is Diffie-Hellman key exchange protocol. The parameters used in Diffie-Hellman key exchange protocol are a prime numbers p and q (generator of p). For computation wise, Diffie-Hellman key exchange protocol involved of 4 steps. Besides, only one communication required between Alice and Bob to obtain the shared key. Clearly our proposed scheme takes more steps in term of computation and communication compare to Diffie-Hellman key exchange protocol, however Diffie-Hellman Problem (DHP) might become vulnerable under the post-quantum attack.

3.4 Security of the Scheme

In Sect. 2.1, we show a construction of (A, B) is a complete decomposition of generalized quaternion group \(Q_{2^n}\), where \(|A|=2^{n-1}\) and \(2^{n-1}-2 \le |B| \le 2^{n-1}-1\) for integer \(n \ge 4\). We first discuss the security of the scheme by using Algorithm 1 proposed in Sect. 3.1 and consider the case where \(|A|=2^{n-1}\) and \(|B|= 2^{n-1}-2\).

Theorem 1

Let A, B be the subsets of \(Q_{2^n}\), where \(|A|=2^{n-1}\) and \(|B|=2^{n-1}-2\) for \(n \ge 4\). Adversary takes at least exponential time E to solve Computational Complete Decomposition Search Problem using subsets A, B in Algorithm 1.

Proof

Note that \(|B| = \frac{|Q_{2^n}|}{|A|}\), \(A\cap B= \emptyset \) and \(|Q_{2^n}|=2^n\). Since \(A\cap B =\emptyset \), we can exclude the elements in subset A and hence left with the remaining \(2^n-|A|\) elements. To search for subset B, one will try for different subset \(B_i\), where the choice of elements for \(B_i\) comes from \(2^n-|A|\) remaining elements. Thus, the worst case for one to obtain such subset B require \({2^n-|A|}\atopwithdelims (){|B|}\) attempts. Next, we show that Algorithm 1 need at least exponential time E to break our scheme. We compare the value between \({2^n-|A|}\atopwithdelims (){|B|}\) and \(2^n\) as follows:

$$\begin{aligned} {{2^n-|A|}\atopwithdelims (){|B|}} =&{{2^{n-1}}\atopwithdelims (){2^{n-1}-2}}\\ =&\frac{2^{n-1}!}{2!(2^{n-1}-2)!}\\ =&\frac{1 \cdot 2 \cdots 2^{n-1}}{2(1\cdot 2 \cdots (2^{n-1}-2))}\\ =&\frac{(2^{n-1}-1)2^{n-1}}{2}\\ =&(2^{n-1}-1)2^{n-2}\\ =&2^{2n-3}-2^{n-2} \ge 2^n \end{aligned}$$

Clearly, \((2^{n-1}-1)2^{n-2} \ge 2^n\) for \(n \ge 4\). Since \({2^n-|A|}\atopwithdelims (){|B|}\) \(\ge 2^n\) for \(n\ge 4\), it follows that Adversary takes at least exponential time E to break our scheme using Algorithm 1.

Table 1. Security of the scheme with the assumption that the adversary knows some information
Full size table

Next, we discuss the security of the scheme by assuming that adversary knows some of the private information related to the scheme. Firstly, suppose adversary knows \(A_1 \subseteq \langle x \rangle \), where \(|A_1|=t\). Then, adversary can guess two distinct elements \(b_1,b_2 \in A_1\) correctly with the probability Pr(Adv guess \(b_1,b_2)=\frac{1}{t}(\frac{1}{t-1})\). From here, adversary is able to compute a from \(b_1ab_2\) by using \(b_1,b_2\). However, adversary has no information about \(c \in Q_{2^n}\). Secondly, suppose adversary knows \(A_2 \subseteq \langle x \rangle \), where \(|A_2|=u\). Then, the probability of adversary guesses two distinct elements \(d_1,d_2\in A_2\) correctly is Pr(Adv guess \(d_1,d_2)=\frac{1}{u}(\frac{1}{u-1})\). By using \(d_1\) and \(d_2\), adversary can compute c from \(d_1cd_2\). However, the information about a remains unknown to adversary. Finally, suppose that adversary knows \(A_1,A_2\subseteq \langle x \rangle \), then adversary is able to compute a, c with the probability Pr(Adv guess \(b_1,b_2,d_1,d_2)=\frac{1}{t}(\frac{1}{t-1})+ \frac{1}{u}(\frac{1}{u-1})\). Adversary can use a, c to compute \(c^{-1}a^{-1}\) then followed by shared key B. To summarize this, adversary is not able to compute the shared key B if he knows either \(A_1\) or \(A_2\) but not both. If adversary knows \(A_1,A_2\), where \(|A_1|=t,|A_2|=u\), then the probability of adversary computes shared key B correctly is \(\frac{1}{t}(\frac{1}{t-1})+ \frac{1}{u}(\frac{1}{u-1})\). Thus, if t and u are large integers, then \(\displaystyle \lim _{t\rightarrow \infty } \frac{1}{t}= \lim _{t\rightarrow \infty } \frac{1}{t-1}= \lim _{u\rightarrow \infty } \frac{1}{u}=\lim _{u\rightarrow \infty } \frac{1}{u-1}=0\). Hence, the probability of adversary to compute shared key B correctly is negligible and the scheme is secured. We summarize the results in the following Table 1.

3.5 Open Questions

For future research direction, researchers should analyze which assumptions can be reduced from Complete Decomposition Search Problem as proposed in this paper. We believe that there exists a relation between CDSP and Subset Sum Problem which known to be NP-hard. However, we are not able to provide any formal proof for this statement here. For the implementation of the proposed scheme in a real work scenario, one can investigate on the value of security parameter, for instance the size of subsets A and B to be used so that it provides the same security level like 2048 bit or 4098 bit Diffie Hellman key exchange. Besides, formal security proof or generic model of the proposed scheme should be considered.