# Conjugacy Systems Based on Nonabelian Factorization Problems and Their Applications in Cryptography

Authors: Lize Gu; Shihui Zheng
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

To resist known quantum algorithm attacks, several nonabelian algebraic structures mounted upon the stage of modern cryptography. Recently, Baba et al. proposed an important analogy from the integer factorization problem to the factorization problem over nonabelian groups. In this paper, we propose several conjugated problems related to the factorization problem over nonabelian groups and then present three constructions of cryptographic primitives based on these newly introduced conjugacy systems: encryption, signature, and signcryption. Sample implementations of our proposal as well as the related performance analysis are also presented.


---

## Body

## 1. Introduction

Background and Motivation. Although the idea of encryption has made it to the world thousands of years ago, the concept of public key cryptography (PKC) came to us no more than half of a century. To secure communications over insecure channels, the core idea of PKC is to exert a heavy burden, that is, computational cost in general, on eavesdroppers but meanwhile keep the additional workload of legitimate users as light as possible [1]. This idea is always instantiated by certain challenging problems for which the legitimate users know at least one feasible solution, while it is infeasible to find a solution even if the attackers exhaust all available resources. Along this roadmap, the well-known Diffie-Hellman key exchange protocol [2] as well as many public key cryptosystems, such as RSA [3], ElGamal [4], and ECC [5, 6], manifests their great success during the past four decades. However, considering that the famous problem P=?NP remained open up to now, all these cryptographic protocols/schemes relay their security on assumptions of the intractability of certain problems, say integer factorization problem (IFP), discrete logarithm problem over finite fields (DLP), or elliptic curves (ECDLP).Intractability assumptions of certain cryptographic problems themselves never mean the security of real systems. Instead, they must be embedded in implementing certain cryptographic primitives. In fact, security is a composite concept and it can be divided into several different properties. Among them, confidentiality, authenticity, and integrity attract a lot of attention in the community of PKC. Although the primitive of encryption is mainly intended to keep confidentiality, when an encryption scheme achieves indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2), the integrity of the ciphertexts is also granted. Similarly, the primitive of signature maintains the authenticity and integrity, simultaneously. Another cryptographic primitive, signcryption, is a data security technology by which confidentiality is protected and authenticity is achieved seamlessly at the same time [7–9]. The primitive of signcryption, invented in 1996 but firstly disclosed to the public at CRYPTO 1997 [7, 8], is now an international standard for data protection (ISO/IEC 29150, Dec 2011). Up-to-date, many constructions of signcryption were proposed, based on the intractability assumptions of IFP [10, 11] or DLP/ECDLP [12, 13]. Some constructions further utilize the bilinear pairing to enhance the functionalities and performance [14, 15], but the security of these constructions was also rooted in the intractability assumption of ECDLP. Unfortunately, IFP and DLP as well as ECDLP could be efficiently solved by Shor’s quantum algorithms [16, 17] and its extensions [18]. Thus, there is an urgent requirement to develop new signcryption schemes that have the potential capability to resist Shor-like quantum attacks. Although two lattice-based signcryption schemes were claimed recently [19, 20] to have the advantages in resisting known quantum algorithm attacks, the parameter size of these constructions is considerably large. Therefore, more efficient designs are expected.Contribution. In this paper, we made efforts from two aspects. At first, we define several conjugated problems related to the factorization problem over nonabelian groups and we name these problems as conjugacy systems. Next, we explore the usefulness of these conjugacy systems via presenting three constructions of cryptographic primitives: encryption, signature, and signcryption. In addition, sample implementations of our proposal as well as related performance analysis are presented.Related Work. Our work belongs to the line of the so-called noncommutative cryptography that has become noticeable recently [21]. Considering that Shor’s quantum algorithm and its extension work well over somecommutative groups, such as the multiplication group ℤn*, the multiplication group 𝔽q*, and the addition group over elliptic curves on finite field 𝔽q, and we have already known efficient quantum algorithms for hidden group problems (HSP) over allcommutative groups, a lot of attempts on developing cryptosystems are based onnoncommutative algebraic structures. During the past decade, braid groups [9, 22, 23], inner automorphism groups [24, 25], Thompson’s groups [26], linear groups and classical modular groups [27, 28], random covers and logarithmic signatures [29], and so forth have already mounted upon the stage of modern cryptography. However, this area is considerably immature and at present there are no practical, both in efficiency and security, noncommutative cryptosystems [9]. In particular, finding a secure nonabelian analogy of cryptosystems based on IFP remains open [21] until recently. In 2011, Baba et al. proposed a nonabelian factorization problem and presented associated cryptosystems [30]. Although BKT’s constructions failed to achieve semantic security, the insight embedded in the nonabelian factorization problem opens a new avenue for developing practical nonabelian cryptography [31]. In 2012, Gu et al. [31] proposed an IND-CCA2 secure encryption scheme based on BKT’s idea. Moreover, they gave the first arguments on resisting Shor’s quantum algorithm attacks based on noncommutativity (see Remark 11).Roadmap. The remaining content is organized as follows. In Section 2, we at first recall the definition of nonabelian factorization problem and related extensions, then define some new cryptographic problems (referred to as conjugacy systems), and finally present analysis on the hardness of these problems; in Section 3, we present new constructions on encryption, signature, and signcryption based on the newly introduced conjugacy systems; in Section 4, we discuss the possible implementation platforms and related performance; finally, concluded remarks are given in Section 5.


## 2. Conjugacy Systems Based on Nonabelian Factorization Problems

Most public key cryptosystems are based on certain intractability assumptions and thus finding new intractable assumptions is an interesting cryptographic practice. In this section, we will at first review the so-called nonabelian factorization problem that was firstly formulated in [30] and then introduce some new cryptographic problems by coupling related problems with conjugate operations. This idea is in fact enlightened by braid cryptosystems [23] and the CSP-based constructions [32] where conjugacy related problems play center roles. For abbreviation, we refer to these problems as conjugacy systems.


### 2.1. Nonabelian Factorization Problem and New Cryptographic Problems

Definition 1 (factorization problem, FP [30, 31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The factorization problem with respect to G,g,h, denoted by FPg,hG, is to split the given product gxhy∈G into a pair (gx,hy)∈G2, where x and y are arbitrary integers picked at random.Definition 2 (computational Diffie-Hellman problem, CDH [30, 31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The computational Diffie-Hellman (CDH) problem with respect to G,g,h, denoted by CDHg,hG, is to recover ga+chb+d from the given pair (gahb,gchd)∈G2, where a,b,c,d are arbitrary integers picked at random.Definition 3 (decisional Diffie-Hellman problem, DDH [31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The decisional Diffie-Hellman (DDH) problem with respect to G,g,h, denoted by DDHg,hG, is to distinguish the distribution
(1)𝒟0≜{(gahb,gchd,gzhy):a,b,c,d,z,y∈Rℤ}
and the distribution
(2)𝒟1≜{(gahb,gchd,ga+chb+d):a,b,c,d∈Rℤ}.Definition 4 (gap computational Diffie-Hellman problem, Gap-CDH [31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The gap computational Diffie-Hellman (Gap-CDH) problem (In [31], this problem is called gap Diffie-Hellman (Gap-DH) problem) with respect to G,g,h, denoted by Gap-CDHg,hG, is to solve the CDHg,hG problem given access to an oracle that solves the DDHg,hG problem.Definition 5 (subgroup conjugator searching problem, SCSP).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The subgroup conjugator searching problem (SCSP) with respect to G,g,h, denoted by SCSPg,hG, is to recover gx from the given pair (hy,gxhyg-x)∈G2, where x,y are arbitrary integers picked at random.Definition 6 (subgroup conjugacy deciding problem, SCDP).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The subgroup conjugacy deciding problem (SCDP) with respect to G,g,h, denoted by SCDPg,hG, is to distinguish the distribution
(3)𝒟2≜{(hb,gahbgc):a,b,c∈Rℤ}
and the distribution
(4)𝒟3≜{(hb,gahbg-a):a,b∈Rℤ}.Definition 7 (conjugated computational Diffie-Hellman problem, CCDH).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The conjugated computational Diffie-Hellman (CCDH) problem with respect to G,g,h, denoted by CCDHg,hG, is to recover ga+chbg-a-c from the given triple
(5)(hb,gahbg-a,gchbg-c)∈G3,
where a,b,c,d are arbitrary integers picked at random.Definition 8 (conjugated decisional Diffie-Hellman problem, CDDH).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The conjugated decisional Diffie-Hellman (CDDH) problem with respect to G,g,h, denoted by CDDHg,hG, is to distinguish the distribution
(6)𝒟4≜{(hb,gahbg-a,gchbg-c,gdhbg-d)}
(where a,b,c,d∈Rℤ are drawn at random) and the distribution
(7)𝒟5≜{(hb,gahbg-a,gchbg-c,ga+chbg-a-c)}
(where a,b,c∈Rℤ are drawn at random).Definition 9 (gap conjugated computational Diffie-Hellman problem, Gap-CCDH).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The gap conjugated computational Diffie-Hellman (Gap-CCDH) problem with respect to G,g,h, denoted by Gap-CCDHg,hG, is to solve the CCDHg,hG problem, given access to an oracle that solves the CDDHg,hG problem.


### 2.2. Hardness Assumptions

Firstly, we should notice that the condition〈g〉∩〈h〉={e} implies that the FP problem is well-defined in the sense that the solution is unique for any given FP instance. In addition, if G is abelian and the orders of g and h are coprime and known, then the FP problem can be reduced to the discrete logarithm problem in G according to [30]. However, if the orders of g and h have common factors or are kept unrevealed or G is nonabelian, then the FP problem seems much hard. In this case, the naive method of trying all different pairs (x,y) is apparently infeasible if the orders of g and h are large enough. Therefore, we would like to introduce the meta-assumptions as follows:(i)
(G,e) is a nonabelian finite group, where e is the identity;(ii)
the orders ofg and h are large enough;(iii)
gh≠hg and 〈g〉∩〈h〉={e}.And then, based on this meta-assumption, our first hardness assumption states that the FPg,hG problem is intractable.Secondly, both theDDHg,hG problem and the Gap-DHg,hG problem are no harder than the CDHg,hG problem. But as far as we know, there is no better solution for the DDHg,hG problem and Gap-CDHg,hG problem other than solving the CDHg,hG problem. (Note that if g and h commute (i.e., gh=hg), although the FPg,hG problem is still meaningful, but the CDHg,hG problem, the DDHg,hG problem, and the Gap-DHg,hG problem become trivial, thus, the meta-assumption of noncommutativity of g and h is one of the crucial factors.) Therefore, our 2nd, 3rd, and 4th hardness assumptions state the intractabilities of the CDHg,hG problem, the DDHg,hG problem, and the Gap-DHg,hG problem, respectively.Thirdly, the SCDP problem might betractable for certain nonabelian groups, say matrix groups, considering that the trace of the matrix gahbg-a is the same as the trace of hb. However, even for matrix groups, it seems that both the CCDH problem and the CDDH problem are still intractable, since we have not found an easier way for solving them than using the naive method of enumerating all possible entries. Intuitively, it is hard to solve the CDDH problem without solving the SCSP problem when G is modeled as a generic semigroup model. In 2005, Maurer [33] proved that the discrete logarithm problem (DLP) and the corresponding decisional Diffie-Hellman (DDH) problem are polynomially equivalent in a generic cyclic group. By an analogical manner, we speculate that the SCSP problem and the CDDH problem in a generic noncommutative semigroup are polynomially equivalent. Furthermore, we do not know a better solution for the CDDHg,hG problem and Gap-CCDHg,hG problem other than solving the CCDHg,hG problem. Therefore, our 5th, 6rd, 7th, and 8th hardness assumptions state the intractabilities of the SCSPg,hG problem, the CCDHg,hG problem, the CDDHg,hG, and the Gap-CCDHg,hG problem, respectively. Note that in this paper, we do not assume that SCDPg,hG problem is hard. At present, we have no idea on whether (gap) conjugated computational (resp., decisional) Diffie-Hellman problem is harder than (gap) computational (resp., decisional) Diffie-Hellman problem or vice versa.Finally, a solution to theFPg,hG problem would imply a solution to all above problems [30]. In addition, hb is not required to be invertible in all above definitions; thus it is possible to instantiate these problems over nonabelian semigroups (see Figure 1).Figure 1
Cryptographic problems over nonabelian semigroups.Remark 10 (SCSP versus CSP).
Note that the subgroup conjugator searching problem (SCSP) and the subgroup conjugacy deciding problem (SCDP) introduced in this paper are in general at least as hard as the conjugator searching problem (CSP) and the conjugacy deciding problem (CDP) given in [21] in the sense that SCSP and SCDP further require the potential conjugator gx coming from a specified subgroup 〈g〉⊂G.Remark 11 (quantum attack resistant).
Note that in [31], we give detailed analysis of the core role of noncommutativity on resisting Shor's quantum algorithm attacks. To make this paper self-contained, we briefly recall some points. We know that the main part of Shor’s quantum algorithm is a quantum algorithm to solve the order-finding problem over the abelian group ℤn* [16, 17]. Now, suppose that a quantum algorithm to solve the order-finding problem over the underlying group G is at hand and we have already worked out g’s order a and h’s order b. However, the following lifting reductions are blocked by noncommutativity:
(8)(gxhy)a≠gx·ahy·a=e·hy·a=hy·a,(gxhy)b≠gx·bhy·b=gx·b·e=gx·b.
The above two inequalities are very important in our arguments. Without them, one can reduce the FPg,hG problem to the DLP problems over the cyclic groups 〈g〉 and 〈h〉, which are quantumly tractable by using Shor’s algorithm [31]. In this sense, we can see that BKT’s method pins down the true meaning of noncommutativity for resisting Shor’s quantum algorithm attacks (see Section 7.1 of [31] for more details).


## 2.1. Nonabelian Factorization Problem and New Cryptographic Problems

Definition 1 (factorization problem, FP [30, 31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The factorization problem with respect to G,g,h, denoted by FPg,hG, is to split the given product gxhy∈G into a pair (gx,hy)∈G2, where x and y are arbitrary integers picked at random.Definition 2 (computational Diffie-Hellman problem, CDH [30, 31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The computational Diffie-Hellman (CDH) problem with respect to G,g,h, denoted by CDHg,hG, is to recover ga+chb+d from the given pair (gahb,gchd)∈G2, where a,b,c,d are arbitrary integers picked at random.Definition 3 (decisional Diffie-Hellman problem, DDH [31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The decisional Diffie-Hellman (DDH) problem with respect to G,g,h, denoted by DDHg,hG, is to distinguish the distribution
(1)𝒟0≜{(gahb,gchd,gzhy):a,b,c,d,z,y∈Rℤ}
and the distribution
(2)𝒟1≜{(gahb,gchd,ga+chb+d):a,b,c,d∈Rℤ}.Definition 4 (gap computational Diffie-Hellman problem, Gap-CDH [31]).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The gap computational Diffie-Hellman (Gap-CDH) problem (In [31], this problem is called gap Diffie-Hellman (Gap-DH) problem) with respect to G,g,h, denoted by Gap-CDHg,hG, is to solve the CDHg,hG problem given access to an oracle that solves the DDHg,hG problem.Definition 5 (subgroup conjugator searching problem, SCSP).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The subgroup conjugator searching problem (SCSP) with respect to G,g,h, denoted by SCSPg,hG, is to recover gx from the given pair (hy,gxhyg-x)∈G2, where x,y are arbitrary integers picked at random.Definition 6 (subgroup conjugacy deciding problem, SCDP).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The subgroup conjugacy deciding problem (SCDP) with respect to G,g,h, denoted by SCDPg,hG, is to distinguish the distribution
(3)𝒟2≜{(hb,gahbgc):a,b,c∈Rℤ}
and the distribution
(4)𝒟3≜{(hb,gahbg-a):a,b∈Rℤ}.Definition 7 (conjugated computational Diffie-Hellman problem, CCDH).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The conjugated computational Diffie-Hellman (CCDH) problem with respect to G,g,h, denoted by CCDHg,hG, is to recover ga+chbg-a-c from the given triple
(5)(hb,gahbg-a,gchbg-c)∈G3,
where a,b,c,d are arbitrary integers picked at random.Definition 8 (conjugated decisional Diffie-Hellman problem, CDDH).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The conjugated decisional Diffie-Hellman (CDDH) problem with respect to G,g,h, denoted by CDDHg,hG, is to distinguish the distribution
(6)𝒟4≜{(hb,gahbg-a,gchbg-c,gdhbg-d)}
(where a,b,c,d∈Rℤ are drawn at random) and the distribution
(7)𝒟5≜{(hb,gahbg-a,gchbg-c,ga+chbg-a-c)}
(where a,b,c∈Rℤ are drawn at random).Definition 9 (gap conjugated computational Diffie-Hellman problem, Gap-CCDH).
LetG be any nonabelian finite group with identity e. Let g,h∈G be two random elements so that 〈g〉∩〈h〉={e}. The gap conjugated computational Diffie-Hellman (Gap-CCDH) problem with respect to G,g,h, denoted by Gap-CCDHg,hG, is to solve the CCDHg,hG problem, given access to an oracle that solves the CDDHg,hG problem.


## 2.2. Hardness Assumptions

Firstly, we should notice that the condition〈g〉∩〈h〉={e} implies that the FP problem is well-defined in the sense that the solution is unique for any given FP instance. In addition, if G is abelian and the orders of g and h are coprime and known, then the FP problem can be reduced to the discrete logarithm problem in G according to [30]. However, if the orders of g and h have common factors or are kept unrevealed or G is nonabelian, then the FP problem seems much hard. In this case, the naive method of trying all different pairs (x,y) is apparently infeasible if the orders of g and h are large enough. Therefore, we would like to introduce the meta-assumptions as follows:(i)
(G,e) is a nonabelian finite group, where e is the identity;(ii)
the orders ofg and h are large enough;(iii)
gh≠hg and 〈g〉∩〈h〉={e}.And then, based on this meta-assumption, our first hardness assumption states that the FPg,hG problem is intractable.Secondly, both theDDHg,hG problem and the Gap-DHg,hG problem are no harder than the CDHg,hG problem. But as far as we know, there is no better solution for the DDHg,hG problem and Gap-CDHg,hG problem other than solving the CDHg,hG problem. (Note that if g and h commute (i.e., gh=hg), although the FPg,hG problem is still meaningful, but the CDHg,hG problem, the DDHg,hG problem, and the Gap-DHg,hG problem become trivial, thus, the meta-assumption of noncommutativity of g and h is one of the crucial factors.) Therefore, our 2nd, 3rd, and 4th hardness assumptions state the intractabilities of the CDHg,hG problem, the DDHg,hG problem, and the Gap-DHg,hG problem, respectively.Thirdly, the SCDP problem might betractable for certain nonabelian groups, say matrix groups, considering that the trace of the matrix gahbg-a is the same as the trace of hb. However, even for matrix groups, it seems that both the CCDH problem and the CDDH problem are still intractable, since we have not found an easier way for solving them than using the naive method of enumerating all possible entries. Intuitively, it is hard to solve the CDDH problem without solving the SCSP problem when G is modeled as a generic semigroup model. In 2005, Maurer [33] proved that the discrete logarithm problem (DLP) and the corresponding decisional Diffie-Hellman (DDH) problem are polynomially equivalent in a generic cyclic group. By an analogical manner, we speculate that the SCSP problem and the CDDH problem in a generic noncommutative semigroup are polynomially equivalent. Furthermore, we do not know a better solution for the CDDHg,hG problem and Gap-CCDHg,hG problem other than solving the CCDHg,hG problem. Therefore, our 5th, 6rd, 7th, and 8th hardness assumptions state the intractabilities of the SCSPg,hG problem, the CCDHg,hG problem, the CDDHg,hG, and the Gap-CCDHg,hG problem, respectively. Note that in this paper, we do not assume that SCDPg,hG problem is hard. At present, we have no idea on whether (gap) conjugated computational (resp., decisional) Diffie-Hellman problem is harder than (gap) computational (resp., decisional) Diffie-Hellman problem or vice versa.Finally, a solution to theFPg,hG problem would imply a solution to all above problems [30]. In addition, hb is not required to be invertible in all above definitions; thus it is possible to instantiate these problems over nonabelian semigroups (see Figure 1).Figure 1
Cryptographic problems over nonabelian semigroups.Remark 10 (SCSP versus CSP).
Note that the subgroup conjugator searching problem (SCSP) and the subgroup conjugacy deciding problem (SCDP) introduced in this paper are in general at least as hard as the conjugator searching problem (CSP) and the conjugacy deciding problem (CDP) given in [21] in the sense that SCSP and SCDP further require the potential conjugator gx coming from a specified subgroup 〈g〉⊂G.Remark 11 (quantum attack resistant).
Note that in [31], we give detailed analysis of the core role of noncommutativity on resisting Shor's quantum algorithm attacks. To make this paper self-contained, we briefly recall some points. We know that the main part of Shor’s quantum algorithm is a quantum algorithm to solve the order-finding problem over the abelian group ℤn* [16, 17]. Now, suppose that a quantum algorithm to solve the order-finding problem over the underlying group G is at hand and we have already worked out g’s order a and h’s order b. However, the following lifting reductions are blocked by noncommutativity:
(8)(gxhy)a≠gx·ahy·a=e·hy·a=hy·a,(gxhy)b≠gx·bhy·b=gx·b·e=gx·b.
The above two inequalities are very important in our arguments. Without them, one can reduce the FPg,hG problem to the DLP problems over the cyclic groups 〈g〉 and 〈h〉, which are quantumly tractable by using Shor’s algorithm [31]. In this sense, we can see that BKT’s method pins down the true meaning of noncommutativity for resisting Shor’s quantum algorithm attacks (see Section 7.1 of [31] for more details).


## 3. Cryptographic Applications

Let us proceed to demonstrate the usefulness of the conjugacy systems defined above. Suppose thatG is a nonabelian group. At first, the common setting on the public parameters of the proposed schemes are given by a quintuple 〈𝔇,g,h,H1,H2〉, where(i)
𝔇 is a description of G. Without loss of generality, we assume the length of 𝔇 is bounded by 𝒪(log⁡|G|) for finite G. When G is infinite but admits a finite presentation, say G=〈X∣R〉, then the description of 𝔇 is given by the description of X and R.(ii)
g,h∈G are two fixed elements that are picked at random so that
(a)
g and h do not commute; that is, gh≠hg;(b)
〈g〉∩〈h〉={e};(c)
the order ofg is large enough. Typically, we assume that the order of g is no less than the system security parameter k that will be specified later.(iii)
H1:G→G2 and H2:G2→G are two cryptographic hash functions that are modeled as random oracles.


### 3.1. Encryption with IND-CPA Security

Now, as a warming-up, an Elgamal-like encryption scheme, denoted byV1, is described as follows.(i)
KeyGen(1k): this is the key generation algorithm that takes, as input, the system security parameter 1k, picks an integer s∈{0,1}k at random and calculates x=gshg-s∈G, and finally outputs (gs,x)∈G2 as the private/public key pair.(ii)
Enc(x;m): this is the encryption algorithm that takes as inputs the public key x∈G and the message m∈G and performs the following steps:
(a)
pickt∈{0,1}k at random,(b)
computec1=gthg-t and c2=mgtxg-t,(c)
output(c1,c2).(iii)
Dec(gs;c1,c2): this is the decryption algorithm that takes as inputs the private key gs∈G and the ciphertext pair (c1,c2)∈G2 and then outputs the intended message m=c2(gsc1g-s)-1.Correctness. The correctness of the scheme is granted by the following calculation:
(9)c2(gsc1g-s)-1=mgtxg-t(gsgthg-tg-s)-1=mgtxg-t(gtgshg-sg-t)-1=m(gtxg-t)(gtxg-t)-1=m.Security. The security of the above encryption scheme is essentially similar to the security of the well-known Elgamal encryption scheme [4]. That is, it is indistinguishable against chosen plaintext attack (IND-CPA) under the assumption of the intractability of the CDDHg,hG problem. One can also find similar proofs from either [9] or [32]. In addition, since neither H1 nor H2 are used in this scheme, it is secure in the standard model. By using two random oracles H1 and H2, one can easily convert it into an IND-CCA2 secure encryption scheme according to the well-known FO transformation theorem [34] (see the proof of Theorem 14).


### 3.2.  Signature with the Lowest Security

Next, let us describe a signature scheme, denoted byV2, that can be viewed as a simplified variant of the noncommutative signature scheme given in [35].(i)
KeyGen(1k): it is the same as in Section 3.1.(ii)
Sign(gs;m): this is the signing algorithm that takes as inputs the private key gs∈G and the message m∈G and performs the following steps:
(a)
pickt∈{0,1}k at random,(b)
computeu=gthg-t, v=H2(m,u), and w=H2(u,v)g-tgs,(c)
output the signatureσ=(u,w)∈G2.(iii)
Verify(x;m,σ): this is the verifying algorithm that takes as inputs the public key x∈G and the message-signature pair (m,σ) and then performs the following steps:
(a)
parseσ into (u,w)∈G2,(b)
computev=H2(m,u) and verify whether the following equality holds
(10)wuw-1=?H2(u,v)xH2(u,v)-1,(c)
if so, accept this signature; otherwise, reject it.Correctness. The correctness of the scheme is granted by the following calculation:
(11)wuw-1=H2(u,v)g-tgs(gthg-t)g-sgtH2(u,v)-1=H2(u,v)(g-shgs)H2(u,v)-1=H2(u,v)xH2(u,v)-1.Security. On one hand, under the assumptions of the intractability of the SCSPg,hG problem and H2 being a random oracle, this signature scheme merely achieves unforgeability against no message attacks (UF-NMA)—this is the lowest security level for a signature scheme where adversaries are merely given the public key and asked to output a successful forgery. The arguments are similar to the security analysis given in [35]. On the other hand, taking this scheme as a building block, we can design a signcryption scheme that achieves existential unforgeability against external adaptively chosen message attack (see the next subsection).


### 3.3.  Signcryption with IND-CCA2 Security

Based on the encryption schemeV1 and the signature scheme V2, let us proceed to present a signcryption scheme, denoted by V3.(i)
KeyGen(1k): it the same as in Section 3.1.(ii)
SignCrypt(gs,y;m): this is the signcryption algorithm that takes as inputs the sender’s private key gs∈G, the receiver’s public key y∈G, and the message m∈G and performs the following steps:
(a)
pickt∈{0,1}k at random,(b)
compute(12)c1=gthg-t,τ=H2(m,c1),σ=τc1gsg-t,γ=H1(gtyg-t),c2=(m∥σ)⊕γ,
where operator “⊕” should be viewed as XOR operation over bit-strings that are encoding results of a pair in G2,(c)
output(c1,c2).(iii)
UnSignCrypt(gr,x;c1,c2): this is the unsigncryption algorithm that takes as inputs the receiver’s private key gr∈G, the sender’s public key x∈G, and the ciphertext pair (c1,c2) and performs the following steps:
(a)
computem′∥σ′=c2⊕H1(grc1g-r),(b)
letτ′=H2(m′,c1),(c)
outputm′ if σ′c1σ′-1=(τ′c1)x(τ′c1)-1 and ⊥otherwise.Remark 12.
The above signcryption scheme inherits the same framework from [9]. However, the construction given here is featured by the following differences. (i)
Different platforms with different security bases. In [9], the platform is the braid group Bn and the underlying intractability assumption is the conjugator searching problem (CSP), while in this paper, the platform could be any nonabelian group and the underlying intractability assumption is the subgroup conjugator searching problem (SCSP) that is based on the intractability assumption of the nonabelian factorization problem. In general, we think the SCSP problem is at least as hard as the CSP problem (see Remark 10). In particular, based on nonabelian factorization related problems, noncommutativity plays a core role in resisting Shor’s quantum algorithm attacks.(ii)
Different settings with different trade-off in computational/storage cost. As suggested in [9], with the braid group B50, we need about 4 Kbits to represent a braid with canonical length ℓ≤10. This is a bit inefficient in storage. Therefore, instead of keeping a braid as the private key, we merely use a positive integer s∈{0,1}k to indicate the private key. Considering that the braid exponentiation can be finished very efficiently, the real private key as∈B50 can be reconstructed whenever it is required. However in this paper, our proposal could be instantiated over arbitrary nonabelian groups only if the related intractability assumptions remain reasonable. Thus, we directly use gs∈G as the private key. To deploy our proposal in real systems, the engineers are responsible for making proper trade-off choice between the storage cost and the computational cost.Correctness. The correctness of the above scheme is given by the following theorem.Theorem 13.
The proposed signcryption is consistent.Proof.
Suppose the sender and the receiver perform honestly and their inputs are well formed. That is,x=gshg-s and y=grhg-r. Then, since
(13)grc1g-r=grgthg-tg-r=gtgrhg-rg-t=gtyg-t,m′∥σ′=c2⊕H1(grc1g-r)=(m∥σ)⊕H1(gtyg-t)⊕H1(gtyg-t)=m∥σ,τ′=H2(m′,c1)=H2(m,c1)=τ,σ=τc1gsg-t,
we have that
(14)σ′c1σ′-1=σ(gthg-t)σ-1=(τc1gsg-t)(gthg-t)(τc1gsg-t)-1=(τ′c1)(gshg-s)(τ′c1)-1=(τ′c1)x(τ′c1)-1.
Then, m′=m will be output correctly.Security. As for a signcryption scheme, the security includes two aspects: indistinguishability and unforgeability.Theorem 14.
Suppose thatH1 and H2 are random oracles. The proposed signcryption is indistinguishable against adaptive chosen ciphertext attack (IND-CCA2) assuming that the CDDHg,hG problem is intractable.Proof (sketch of the proof).
The proof threads are similar to what is given in [9]. At first, we can apply the well-known Fujisaki-Okamoto transformation theorem [34] to conclude the IND-CCA2 security of the following encryption scheme, denoted by V4.(i)
KeyGen(1k): it is the same as in Section 3.1.(ii)
Enc′(y;m): this is the encryption algorithm that takes as inputs the receiver’s public key y and a message m∈G and then performs the following steps:
(a)
picku∈G at random,(b)
let(c1,c2)←Enc(y;u), where Enc is the encryption algorithm in Section 3.1,(c)
letc3=m⊕H1(u) and c4=H2(m,u),(d)
output(c1,c2,c3,c4).(iii)
Dec′(gr;c1,c2,c3,c4): this is the decryption algorithm that takes as inputs the receiver’s private key gr∈G and the ciphertext quadruple (c1,c2,c3,c4) and then performs the following steps:
(a)
letu′←Dec(gr;c1,c2), where Dec is the decryption algorithm in Section 3.1,(b)
letm′←c3⊕H1(u′),(c)
outputm′ if c4=H2(m′,u′) and ⊥otherwise.Apparently, V4 is an FO-like variant of V1 and its security is enhanced to IND-CCA2 assuming that both H1 and H2 are random oracles [34].
Now, let us show that, with the same random oracles, if there exists a probabilistic polynomial time adversary𝒜 that can break the IND-CCA2 security of the proposed signcryption scheme V3, then there also exists another probabilistic polynomial time adversary ℬ that can break the IND-CCA2 security of V4.
In fact, sinceℬ controls the response of the random oracles H1 and H2, it can break the IND-CCA2 security of V4 easily: whenever seeing a ciphertext (c1,c2,c3,c4), it can retrieve the message m and random salt u by looking up the response list of H2 under the reasonable assumption that the probability for different pair (m′,u′) with same hash value with the pair (m,u) is negligible. The thing left is to showhowℬ, without knowing the receiver's private key gr∈G,can simulate the response on decryption queries for 𝒜 by a perfect manner.
Whenever𝒜 invokes an unsigncryption query by submitting a signcryption pair (c1,c2), ℬ responds as follows.(1)
Lookup(*,c1,*) in H2-list, where * indicates a wildcard that can be matched with arbitrary inputs. If there is no matched triple, ℬ sends ⊥ to 𝒜 as the response.(2)
For each matched triple(mi,c1,τi), ℬ performs the following steps:
(a)
for each(u,γ) in H1 list, do the following steps:
(i)
extract a possibleσi according to the following formula:
(15)c2=(mi∥σi)⊕γ,(ii)
test whether the equality(16)σic1σi-1=?(τic1)x(τic1)-1
holds. If so, reply 𝒜 with mi and end the response; otherwise, continue.(3)
If up to nowℬ has no output response to 𝒜 yet, then ℬ sends ⊥ to 𝒜 as the response and then end the response.
Finally, without accessing hash queries on random oraclesH1 and H2, 𝒜’s probability for submitting a valid signcryption pair (c1,c2) is negligible. Thus, whenever 𝒜 invokes hash queries on H1 and H2 for forming a valid signcryption pair, related materials are recorded, and ℬ can retrieve them and finally send 𝒜 a perfect response.Theorem 15.
Suppose thatH1 and H2 are random oracles. The proposed signcryption scheme is existential unforgeable againstexternal adaptive chosen message attacks (EUF-ext-CMA) assuming that the SCSPg,hG problem is intractable.Proof.
Here, the term “external” means that the forger is neither the singer, nor the intended receiver. Let us show that whenever an external attacker𝒜 outputs a successful forgery, then this must mean a contrary against the UF-NMA security of the signature scheme V2 given in Section 3.2. At first, without invoking any query, 𝒜’s successful forgery itself means an attack against the UF-NMA security. Next, suppose that 𝒜 invokes many polynomial signcryption queries or unsigncryption queries. Let us show that the responses for these queries have no help to 𝒜 for making a forged signcryption.
Suppose𝒜 invokes a signcryption query on some message m and receives a pair (c1,c2) as the response. After then, 𝒜 invokes a random oracle query on H2 with inputs m and c1 and then he/she obtains τ. Now, 𝒜 still has no means to obtain a valid signature from (m,c1,c2,τ) since both gsg-t and γ remain unknown. Suppose 𝒜 can get γ via invoking a random oracle query on H1 with input gtyg-t. Then, its query input gives a solution to the SCSP instance (c1=gthg-t,y=grhg-r). This is a contrary to the assumption of the intractability of the SCSP problem.
Now, suppose𝒜 invokes an unsigncryption query on some signcryption pair (c1,c2). Similar to the response of ℬ given in the proof of Theorem 14, 𝒜 gets either a symbol ⊥ or a message mi. In the former case, 𝒜’s query is invalid and rejected. In the latter case, 𝒜’s query is valid and there exists a matched entry γ in H1 list. This in turn implies that there exists a matched entry gtyg-t in H1 list. However, this is impossible since it again means a solution to the SCSP instance (c1=gthg-t,y=grhg-r).
This concludes the theorem.Remark 16.
To proof the unforgeability of a signature scheme, it is reasonable to exclude the signer from forgeries. But just as what was done in [9], the so-called external attacker model enables us to further exclude the intended receiver from the forgeries. Unlike the primitive authenticated encryption, the authenticity embedded in the primitive of signcryption is unidirectional to some extent. That is, it seems that there is no reason for an intended receiver to forge a signature on behalf of some signer and then encrypt the signature for himself/herself, except for planting false evidence against some senders. Otherwise, an existentially unforgeable signature scheme, such as the noncommutative signature scheme in [36], should be embedded therein.


## 3.1. Encryption with IND-CPA Security

Now, as a warming-up, an Elgamal-like encryption scheme, denoted byV1, is described as follows.(i)
KeyGen(1k): this is the key generation algorithm that takes, as input, the system security parameter 1k, picks an integer s∈{0,1}k at random and calculates x=gshg-s∈G, and finally outputs (gs,x)∈G2 as the private/public key pair.(ii)
Enc(x;m): this is the encryption algorithm that takes as inputs the public key x∈G and the message m∈G and performs the following steps:
(a)
pickt∈{0,1}k at random,(b)
computec1=gthg-t and c2=mgtxg-t,(c)
output(c1,c2).(iii)
Dec(gs;c1,c2): this is the decryption algorithm that takes as inputs the private key gs∈G and the ciphertext pair (c1,c2)∈G2 and then outputs the intended message m=c2(gsc1g-s)-1.Correctness. The correctness of the scheme is granted by the following calculation:
(9)c2(gsc1g-s)-1=mgtxg-t(gsgthg-tg-s)-1=mgtxg-t(gtgshg-sg-t)-1=m(gtxg-t)(gtxg-t)-1=m.Security. The security of the above encryption scheme is essentially similar to the security of the well-known Elgamal encryption scheme [4]. That is, it is indistinguishable against chosen plaintext attack (IND-CPA) under the assumption of the intractability of the CDDHg,hG problem. One can also find similar proofs from either [9] or [32]. In addition, since neither H1 nor H2 are used in this scheme, it is secure in the standard model. By using two random oracles H1 and H2, one can easily convert it into an IND-CCA2 secure encryption scheme according to the well-known FO transformation theorem [34] (see the proof of Theorem 14).


## 3.2.  Signature with the Lowest Security

Next, let us describe a signature scheme, denoted byV2, that can be viewed as a simplified variant of the noncommutative signature scheme given in [35].(i)
KeyGen(1k): it is the same as in Section 3.1.(ii)
Sign(gs;m): this is the signing algorithm that takes as inputs the private key gs∈G and the message m∈G and performs the following steps:
(a)
pickt∈{0,1}k at random,(b)
computeu=gthg-t, v=H2(m,u), and w=H2(u,v)g-tgs,(c)
output the signatureσ=(u,w)∈G2.(iii)
Verify(x;m,σ): this is the verifying algorithm that takes as inputs the public key x∈G and the message-signature pair (m,σ) and then performs the following steps:
(a)
parseσ into (u,w)∈G2,(b)
computev=H2(m,u) and verify whether the following equality holds
(10)wuw-1=?H2(u,v)xH2(u,v)-1,(c)
if so, accept this signature; otherwise, reject it.Correctness. The correctness of the scheme is granted by the following calculation:
(11)wuw-1=H2(u,v)g-tgs(gthg-t)g-sgtH2(u,v)-1=H2(u,v)(g-shgs)H2(u,v)-1=H2(u,v)xH2(u,v)-1.Security. On one hand, under the assumptions of the intractability of the SCSPg,hG problem and H2 being a random oracle, this signature scheme merely achieves unforgeability against no message attacks (UF-NMA)—this is the lowest security level for a signature scheme where adversaries are merely given the public key and asked to output a successful forgery. The arguments are similar to the security analysis given in [35]. On the other hand, taking this scheme as a building block, we can design a signcryption scheme that achieves existential unforgeability against external adaptively chosen message attack (see the next subsection).


## 3.3.  Signcryption with IND-CCA2 Security

Based on the encryption schemeV1 and the signature scheme V2, let us proceed to present a signcryption scheme, denoted by V3.(i)
KeyGen(1k): it the same as in Section 3.1.(ii)
SignCrypt(gs,y;m): this is the signcryption algorithm that takes as inputs the sender’s private key gs∈G, the receiver’s public key y∈G, and the message m∈G and performs the following steps:
(a)
pickt∈{0,1}k at random,(b)
compute(12)c1=gthg-t,τ=H2(m,c1),σ=τc1gsg-t,γ=H1(gtyg-t),c2=(m∥σ)⊕γ,
where operator “⊕” should be viewed as XOR operation over bit-strings that are encoding results of a pair in G2,(c)
output(c1,c2).(iii)
UnSignCrypt(gr,x;c1,c2): this is the unsigncryption algorithm that takes as inputs the receiver’s private key gr∈G, the sender’s public key x∈G, and the ciphertext pair (c1,c2) and performs the following steps:
(a)
computem′∥σ′=c2⊕H1(grc1g-r),(b)
letτ′=H2(m′,c1),(c)
outputm′ if σ′c1σ′-1=(τ′c1)x(τ′c1)-1 and ⊥otherwise.Remark 12.
The above signcryption scheme inherits the same framework from [9]. However, the construction given here is featured by the following differences. (i)
Different platforms with different security bases. In [9], the platform is the braid group Bn and the underlying intractability assumption is the conjugator searching problem (CSP), while in this paper, the platform could be any nonabelian group and the underlying intractability assumption is the subgroup conjugator searching problem (SCSP) that is based on the intractability assumption of the nonabelian factorization problem. In general, we think the SCSP problem is at least as hard as the CSP problem (see Remark 10). In particular, based on nonabelian factorization related problems, noncommutativity plays a core role in resisting Shor’s quantum algorithm attacks.(ii)
Different settings with different trade-off in computational/storage cost. As suggested in [9], with the braid group B50, we need about 4 Kbits to represent a braid with canonical length ℓ≤10. This is a bit inefficient in storage. Therefore, instead of keeping a braid as the private key, we merely use a positive integer s∈{0,1}k to indicate the private key. Considering that the braid exponentiation can be finished very efficiently, the real private key as∈B50 can be reconstructed whenever it is required. However in this paper, our proposal could be instantiated over arbitrary nonabelian groups only if the related intractability assumptions remain reasonable. Thus, we directly use gs∈G as the private key. To deploy our proposal in real systems, the engineers are responsible for making proper trade-off choice between the storage cost and the computational cost.Correctness. The correctness of the above scheme is given by the following theorem.Theorem 13.
The proposed signcryption is consistent.Proof.
Suppose the sender and the receiver perform honestly and their inputs are well formed. That is,x=gshg-s and y=grhg-r. Then, since
(13)grc1g-r=grgthg-tg-r=gtgrhg-rg-t=gtyg-t,m′∥σ′=c2⊕H1(grc1g-r)=(m∥σ)⊕H1(gtyg-t)⊕H1(gtyg-t)=m∥σ,τ′=H2(m′,c1)=H2(m,c1)=τ,σ=τc1gsg-t,
we have that
(14)σ′c1σ′-1=σ(gthg-t)σ-1=(τc1gsg-t)(gthg-t)(τc1gsg-t)-1=(τ′c1)(gshg-s)(τ′c1)-1=(τ′c1)x(τ′c1)-1.
Then, m′=m will be output correctly.Security. As for a signcryption scheme, the security includes two aspects: indistinguishability and unforgeability.Theorem 14.
Suppose thatH1 and H2 are random oracles. The proposed signcryption is indistinguishable against adaptive chosen ciphertext attack (IND-CCA2) assuming that the CDDHg,hG problem is intractable.Proof (sketch of the proof).
The proof threads are similar to what is given in [9]. At first, we can apply the well-known Fujisaki-Okamoto transformation theorem [34] to conclude the IND-CCA2 security of the following encryption scheme, denoted by V4.(i)
KeyGen(1k): it is the same as in Section 3.1.(ii)
Enc′(y;m): this is the encryption algorithm that takes as inputs the receiver’s public key y and a message m∈G and then performs the following steps:
(a)
picku∈G at random,(b)
let(c1,c2)←Enc(y;u), where Enc is the encryption algorithm in Section 3.1,(c)
letc3=m⊕H1(u) and c4=H2(m,u),(d)
output(c1,c2,c3,c4).(iii)
Dec′(gr;c1,c2,c3,c4): this is the decryption algorithm that takes as inputs the receiver’s private key gr∈G and the ciphertext quadruple (c1,c2,c3,c4) and then performs the following steps:
(a)
letu′←Dec(gr;c1,c2), where Dec is the decryption algorithm in Section 3.1,(b)
letm′←c3⊕H1(u′),(c)
outputm′ if c4=H2(m′,u′) and ⊥otherwise.Apparently, V4 is an FO-like variant of V1 and its security is enhanced to IND-CCA2 assuming that both H1 and H2 are random oracles [34].
Now, let us show that, with the same random oracles, if there exists a probabilistic polynomial time adversary𝒜 that can break the IND-CCA2 security of the proposed signcryption scheme V3, then there also exists another probabilistic polynomial time adversary ℬ that can break the IND-CCA2 security of V4.
In fact, sinceℬ controls the response of the random oracles H1 and H2, it can break the IND-CCA2 security of V4 easily: whenever seeing a ciphertext (c1,c2,c3,c4), it can retrieve the message m and random salt u by looking up the response list of H2 under the reasonable assumption that the probability for different pair (m′,u′) with same hash value with the pair (m,u) is negligible. The thing left is to showhowℬ, without knowing the receiver's private key gr∈G,can simulate the response on decryption queries for 𝒜 by a perfect manner.
Whenever𝒜 invokes an unsigncryption query by submitting a signcryption pair (c1,c2), ℬ responds as follows.(1)
Lookup(*,c1,*) in H2-list, where * indicates a wildcard that can be matched with arbitrary inputs. If there is no matched triple, ℬ sends ⊥ to 𝒜 as the response.(2)
For each matched triple(mi,c1,τi), ℬ performs the following steps:
(a)
for each(u,γ) in H1 list, do the following steps:
(i)
extract a possibleσi according to the following formula:
(15)c2=(mi∥σi)⊕γ,(ii)
test whether the equality(16)σic1σi-1=?(τic1)x(τic1)-1
holds. If so, reply 𝒜 with mi and end the response; otherwise, continue.(3)
If up to nowℬ has no output response to 𝒜 yet, then ℬ sends ⊥ to 𝒜 as the response and then end the response.
Finally, without accessing hash queries on random oraclesH1 and H2, 𝒜’s probability for submitting a valid signcryption pair (c1,c2) is negligible. Thus, whenever 𝒜 invokes hash queries on H1 and H2 for forming a valid signcryption pair, related materials are recorded, and ℬ can retrieve them and finally send 𝒜 a perfect response.Theorem 15.
Suppose thatH1 and H2 are random oracles. The proposed signcryption scheme is existential unforgeable againstexternal adaptive chosen message attacks (EUF-ext-CMA) assuming that the SCSPg,hG problem is intractable.Proof.
Here, the term “external” means that the forger is neither the singer, nor the intended receiver. Let us show that whenever an external attacker𝒜 outputs a successful forgery, then this must mean a contrary against the UF-NMA security of the signature scheme V2 given in Section 3.2. At first, without invoking any query, 𝒜’s successful forgery itself means an attack against the UF-NMA security. Next, suppose that 𝒜 invokes many polynomial signcryption queries or unsigncryption queries. Let us show that the responses for these queries have no help to 𝒜 for making a forged signcryption.
Suppose𝒜 invokes a signcryption query on some message m and receives a pair (c1,c2) as the response. After then, 𝒜 invokes a random oracle query on H2 with inputs m and c1 and then he/she obtains τ. Now, 𝒜 still has no means to obtain a valid signature from (m,c1,c2,τ) since both gsg-t and γ remain unknown. Suppose 𝒜 can get γ via invoking a random oracle query on H1 with input gtyg-t. Then, its query input gives a solution to the SCSP instance (c1=gthg-t,y=grhg-r). This is a contrary to the assumption of the intractability of the SCSP problem.
Now, suppose𝒜 invokes an unsigncryption query on some signcryption pair (c1,c2). Similar to the response of ℬ given in the proof of Theorem 14, 𝒜 gets either a symbol ⊥ or a message mi. In the former case, 𝒜’s query is invalid and rejected. In the latter case, 𝒜’s query is valid and there exists a matched entry γ in H1 list. This in turn implies that there exists a matched entry gtyg-t in H1 list. However, this is impossible since it again means a solution to the SCSP instance (c1=gthg-t,y=grhg-r).
This concludes the theorem.Remark 16.
To proof the unforgeability of a signature scheme, it is reasonable to exclude the signer from forgeries. But just as what was done in [9], the so-called external attacker model enables us to further exclude the intended receiver from the forgeries. Unlike the primitive authenticated encryption, the authenticity embedded in the primitive of signcryption is unidirectional to some extent. That is, it seems that there is no reason for an intended receiver to forge a signature on behalf of some signer and then encrypt the signature for himself/herself, except for planting false evidence against some senders. Otherwise, an existentially unforgeable signature scheme, such as the noncommutative signature scheme in [36], should be embedded therein.


## 4. Sample Implementations and Performance Evaluation

In [30], the authors suggested to consider the intractability assumption of the FPg,hG problem over three kinds of platforms:(1)
GLn(𝔽q), that is, the general linear group over finite field,(2)
UTn(𝔽q), that is, the nonabelian subgroup of GLn(𝔽q) consisting of unitriangular matrices,(3)
braids setBn(l), that is, the set of braids in the braid group Bn with l canonical factors.At first, a braidBn(l) can be represented by a bit string of size ⌈ln⁡⁡log⁡n⌉ [23] and the complexities of the braid operations such as multiplication, inversion, and canonical form computation are bounded by 𝒪(l2nlog⁡n) in the sense of bit operations [9]. Thus, if we follow Maffre’s suggestions by setting n=50 and l=10 [37], then the number of bit operations for implementing these braid operations is proportional to 215 and the sizes of the system parameters, the private key, the public key, and the ciphertexts are 5650 bits, 80 bits, 2822 bits, and 8466 bits, respectively. More detailed evaluation on the performance of braid-based cryptosystems can be found either in [36] or in [9].Next, let us pay attention toGLn(𝔽q) and UTn(𝔽q). In particular, we mainly focus on two aspects: the time complexity of exponentiation and the related parameter sizes. Since the classical techniques for matrix multiplication/inversion in GLn(𝔽q) (resp., UTn(𝔽q)) take about n3 (resp., n(n+1)(n+2)/6) 𝔽q-operations, while each 𝔽q-operation needs 𝒪(log⁡2q) bit operations [38], thus by employing the idea of “square-multiply,” the time complexity of calculating an exponentiation gs with s∈R{0,1}k in both GLn(𝔽q) and UTn(𝔽q) is 𝒪(n3klog⁡2q) in sense of bit operations. To represent a matrix in GLn(𝔽q) (resp., UTn(𝔽q)), we need n2 (resp., n(n-1)/2) 𝔽q-elements, while each 𝔽q-element occupies exactly log⁡q bits. In practice, n need not to be too large. Typically, we set n=4 and then collect our analysis in Table 1. From this table, we can see that the computational/storage cost of cryptosystems over UTn(𝔽q) is about merely 1/3 times of those over GLn(𝔽q) when n=4. (Note that since both the encryption scheme V1 and the signature scheme V2 are embedded into the signcryption scheme V3, we merely present performance analysis on V3.)Table 1
Performance of signcryption schemeV3 (n=4).
Platforms
Operations* and complexities†
Parameters and sizes‡
KeyGen
SignCrypt
UnSignCrypt
pk§
sk
Ciphertext
G
1
e
+
2
m
+
1
i
1
e
+
7
m
+
1
i
7
m
+
3
i
log
⁡
|
G
|
log
⁡
|
G
|
2
log
⁡
|
G
|
G
L
n
(
𝔽
q
)
~64klog⁡2q
~640log⁡2q
~16log⁡q
~16log⁡q
~32log⁡q
U
T
n
(
𝔽
q
)
~20klog⁡2q
~200log⁡2q
~6logq
~6log⁡q
~12log⁡q
B
50
(
10
)
~215
5730
2822
8466
*
e
/
m
/
i: exponentiation/multiplication/inversion in the nonabelian group G.
†In the sense of bit operations.
‡In the sense of bit length.
§Including system parameters shared by all users.


## 5. Conclusion

The booming of quantum algorithm casts distrust on many public key cryptosystems based on integer factorization problem, discrete logarithm, and other assumed intractable problems over certain abelian groups. Some breakthrough in developing new public key cryptography based on nonabelian algebraic structures has been made during the past decade. In particular, Baba et al. made the first step toward construct cryptographic schemes based on nonabelian factorization problems. In this paper, we at first present several conjugacy systems based on the factorization problem over nonabelian groups and then present new construction of encryption, signature, and signcryption based on the newly introduced cryptographic intractable assumptions. Some possible implementation platforms and the related performance analysis are also given. Two possible future perspectives are to investigate more efficient platforms for implementing our proposal and to investigate possible reductions from the hardness of the related conjugated problems to the hardness of the underlying problems.



---

*Source: 630607-2014-04-28.xml*