# A Digital Signature Scheme Based onMST3 Cryptosystems

Authors: Haibo Hong; Jing Li; Licheng Wang; Yixian Yang; Xinxin Niu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

As special types of factorization of finite groups, logarithmic signature and cover have been used as the main components of cryptographic keys for secret key cryptosystems such asPGM and public key cryptosystems like MST1, MST2, and MST3. Recently, Svaba et. al proposed a revised MST3 encryption scheme with greater security. Meanwhile, they put forward an idea of constructing signature schemes on the basis of logarithmic signatures and random covers. In this paper, we firstly design a secure digital signature scheme based on logarithmic signatures and random covers. In order to complete the task, we devise a new encryption scheme based on MST3 cryptosystems.


---

## Body

## 1. Introduction

With the interdisciplinary development of information science, physical science, and biological science, a lot of new technology appeared in the field of cryptography and has made new progress. The new branches of cryptography mainly consist of quantum cryptography, chaotic cryptography, DNA cryptography, and so forth. The security of quantum cryptography is based on the Heisenberg uncertainty principle. Quantum cryptography is the only one that can realize unconditional security at present [1–4]. Matthews [5] firstly applied chaos theory in cryptography and proposed a chaotic stream cipher scheme based on revised logistic map. From then on, chaotic cryptography has attracted wide attention [6, 7]. Most of the researches in chaotic cryptography focus on secret key cryptography. With the recent constructions due to Wang et al. [8–14], chaos-based public key cryptographic protocols come to us. DNA cryptography, which utilizes DNA computing, is a new branch of cryptography in recent years [15, 16]. Using the high storage density and high parallelism of DNA molecular, DNA cryptography can realize the encryption, authentication, signature, and so forth [17].Meanwhile, cryptographers look forward to applying new intractable mathematical problems in classical cryptography. Currently, most public cryptographic primitives are based on the perceived intractability of certain mathematical problems in very large finite abelian groups [18]. Prominent hard problems consist of the problem of factoring large integers, the discrete logarithm problem over a finite field Fq or an elliptic curve, and so forth. However, due to quantum algorithms for factoring integer and solving the discrete logarithm problem, most known public-key cryptosystems will be insecure when quantum computers become practical. Therefore, it is an imminent work to design effective cryptographic schemes which can resist quantum attacks. Actually, since the 1980s, several experts have been trying to design new cryptography schemes based on difficult problems in group theory. In 1985, Wagner and Magyarik [19] proposed an approach to designing public-key cryptosystems based on groups and semigroups with undecidable word problem. In 2000, Ko et al. [20] developed the theory of braid-based cryptography based on the hardness of the conjugator search problem (CSP) in braid groups. In 2004, Eick and Kahrobaei [21] proposed a new cryptosystem based on polycyclic groups. In 2005, Shpilrain and Ushakov [22] suggested that Thompson’s group may be a good platform for constructing public-key cryptosystems. Recently, Kahrobaei et al. [23] proposed a public key exchange on the basis of matrices over group rings. Meanwhile, an active branch of noncommutative cryptography based on the hardness of group factorization problem has achieved great success during the last two decades. In 1986, Magliveras [24] proposed a symmetric cryptosystem PGM based on a special type of factorization of finite groups named logarithmic signatures for finite permutation groups. Then, the algebraic properties of logarithmic signatures and cryptosystem PGM were specifically discussed in [25, 26]. In 2002, Magliveras et al. [27] put forward two public key cryptosystems MST1 and MST2. In 2009, Lempken et al. [18] designed a new public key cryptosystem MST3 on the basis of random covers and logarithmic signatures for nonabelian finite groups. Meanwhile, there are some interesting papers studying attacks on MST1, MST2, and MST3 [28–33]. In 2010, Svaba and van Trung [34] constructed an eMST3 cryptosystem by adding a homomorphism as a component of secret key. However, until now, there is no paper on constructing digital signature schemes on the basis of MST cryptosystem. Hence, Svaba and van Trung put forward an open problem on constructing digital signature schemes based on random covers and logarithmic signatures.Our main contribution is to devise a digital signature scheme based on random covers and logarithmic signatures. In this process, we also construct a secure and more efficient encryption scheme based onMST3 cryptosystems.The rest of contents are organized as follows. Necessary preliminaries are given in Section2. In Section 3, we specifically describe a new encryption scheme and give corresponding security analysis. In Section 4, we propose a digital signature scheme based on random covers and logarithmic signatures; The related comparisons and illustrations are presented in Section 5.


## 2. Preliminaries

### 2.1. Cover and Logarithmic Signature

LetG be a finite abstract group and let X=[x1,x2,…,xr] and Y=[y1,y2,…,ys] be two elements in G[Z]. Then
(1)X⊗Y=[x1y1,…,x1ys,x2y1,…,x2ys,…,xry1,…,xrys].
If X=[x1,…,xr]∈G[Z], X¯ denotes the element ∑i=1rxi in the group ring ZG.Definition 1 (cover and logarithmic signature [18, 27]).
Suppose thatα=[A1,A2,…,As] is a sequence of Ai∈G[Z], such that ∑i=1s|Ai| is bounded by a polynomial in log⁡|G|. Let
(2)A1¯·A2¯⋯As¯=∑‍g∈Gagg,ag∈Z.
LetS be a subset of G. Then α is (i)
acover for G (or S) if ag>0 for all g∈G (g∈S),(ii)
alogarithmic signature for G (or S) if ag=1 for every g∈G (g∈S).The sequencesAi are called theblocks; the vector (r1,…,rs) with ri=|Ai| is thetype of α and thelength of α is defined to be l(α)=∑i=1sri.More generally, ifα=[A1,A2,…,As] is a logarithmic signature (cover) for G, then each element g∈G can be expressed uniquely (at least one way) as a product of the form [18]
(3)g=a1·a2⋯as,
for ai∈Ai. α is calledtame (factorizable) if the factorization above can be achieved in polynomial in the width w of G.Definition 2 (cover (logarithmic signature) mappings [35]).
Letα=[A1,A2,…,As] be a cover (logarithmic signature) of type (r1,r2,…,rs) for G with Ai=[ai,1,ai,2,…,ai,ri], where m=∏i=1s‍ri. Let m1=1 and mi=∏j=1i-1‍rj for i=2,…,s. Let τ denote the canonical bijection
(4)τ:Zr1×Zr2×⋯×Zrs⟶Zmτ(j1,j2,…,js)=∑i=1sji·mi.
Then the surjective (bijection)mappingα′:Zm→Ginduced byα is
(5)α′(x)=a1j1·a2j2⋯asjs,
where (j1,j2,…,js)=τ-1(x).


### 2.2.MST3 Cryptosystems and Suzuki 2-Groups

In [18], Lempken et al. utilized logarithmic signatures and random covers to construct a generic MST3 encryption scheme. In this scheme, the public key consists of a tame logarithmic signature as well as some random numbers, and the secret key is composed of a random cover and a sandwich transformation of the cover [27]. The intractability assumptions of this scheme are group factorization problem on nonabelian groups.Furthermore, motivated by attacks in [31], Svaba and van Trung devised an enhanced version of the generic scheme [34] named eMST3 cryptosystems. In this scheme, they introduced a secret homomorphism to mask the secret logarithmic signature with a transformation of a random cover. Meanwhile, they proposed a new setup with random encryption.Until now, the only instantiation ofMST3 cryptosystems is a Suzuki 2-group of order q2 with q=2m (m≥3) [18, 34]. From [34], the Suzuki 2-group of order q2 can be denoted by A(m,θ), where θ is an automorphism of Fq with an odd order. Moreover, the group A(m,θ) can be represented by a matrix group G and
(6)G={S(a,b)∣a,b∈Fq},
where
(7)S(a,b)=(1ab01aθ001)
is a 3×3 matrix over Fq. Hence, G is of order q2 and the center Z(G)={S(0,b)∣b∈Fq}. Besides, to store the group elements conveniently, S(a,b) can be denoted by (a,b,aθ), so the product of two elements in group G is
(8)S(a1,b1)S(a2,b2)=S(a1,b1,a1θ)S(a2,b2,a2θ)=(a1+a2,b1+b2+a1a2θ,a1θ+a2θ),
and the computation of the product just requires a single multiplication and four additions in Fq.Furthermore, the inverse of an element in groupG is
(9)S(a,b,aθ)-1=S(a,aθ·a+b,aθ)=S(a,aθ+1+b,aθ),
and it also requires a single multiplication and one addition in Fq. If g=S(x,y)∈G and x,y∈Fq, then x and y can be denoted by g·a and g·b, respectively. Hence, g=S(g·a,g·b), where g·a and g·b are the corresponding projections of g along the first and second coordinates.


## 2.1. Cover and Logarithmic Signature

LetG be a finite abstract group and let X=[x1,x2,…,xr] and Y=[y1,y2,…,ys] be two elements in G[Z]. Then
(1)X⊗Y=[x1y1,…,x1ys,x2y1,…,x2ys,…,xry1,…,xrys].
If X=[x1,…,xr]∈G[Z], X¯ denotes the element ∑i=1rxi in the group ring ZG.Definition 1 (cover and logarithmic signature [18, 27]).
Suppose thatα=[A1,A2,…,As] is a sequence of Ai∈G[Z], such that ∑i=1s|Ai| is bounded by a polynomial in log⁡|G|. Let
(2)A1¯·A2¯⋯As¯=∑‍g∈Gagg,ag∈Z.
LetS be a subset of G. Then α is (i)
acover for G (or S) if ag>0 for all g∈G (g∈S),(ii)
alogarithmic signature for G (or S) if ag=1 for every g∈G (g∈S).The sequencesAi are called theblocks; the vector (r1,…,rs) with ri=|Ai| is thetype of α and thelength of α is defined to be l(α)=∑i=1sri.More generally, ifα=[A1,A2,…,As] is a logarithmic signature (cover) for G, then each element g∈G can be expressed uniquely (at least one way) as a product of the form [18]
(3)g=a1·a2⋯as,
for ai∈Ai. α is calledtame (factorizable) if the factorization above can be achieved in polynomial in the width w of G.Definition 2 (cover (logarithmic signature) mappings [35]).
Letα=[A1,A2,…,As] be a cover (logarithmic signature) of type (r1,r2,…,rs) for G with Ai=[ai,1,ai,2,…,ai,ri], where m=∏i=1s‍ri. Let m1=1 and mi=∏j=1i-1‍rj for i=2,…,s. Let τ denote the canonical bijection
(4)τ:Zr1×Zr2×⋯×Zrs⟶Zmτ(j1,j2,…,js)=∑i=1sji·mi.
Then the surjective (bijection)mappingα′:Zm→Ginduced byα is
(5)α′(x)=a1j1·a2j2⋯asjs,
where (j1,j2,…,js)=τ-1(x).


## 2.2.MST3 Cryptosystems and Suzuki 2-Groups

In [18], Lempken et al. utilized logarithmic signatures and random covers to construct a generic MST3 encryption scheme. In this scheme, the public key consists of a tame logarithmic signature as well as some random numbers, and the secret key is composed of a random cover and a sandwich transformation of the cover [27]. The intractability assumptions of this scheme are group factorization problem on nonabelian groups.Furthermore, motivated by attacks in [31], Svaba and van Trung devised an enhanced version of the generic scheme [34] named eMST3 cryptosystems. In this scheme, they introduced a secret homomorphism to mask the secret logarithmic signature with a transformation of a random cover. Meanwhile, they proposed a new setup with random encryption.Until now, the only instantiation ofMST3 cryptosystems is a Suzuki 2-group of order q2 with q=2m (m≥3) [18, 34]. From [34], the Suzuki 2-group of order q2 can be denoted by A(m,θ), where θ is an automorphism of Fq with an odd order. Moreover, the group A(m,θ) can be represented by a matrix group G and
(6)G={S(a,b)∣a,b∈Fq},
where
(7)S(a,b)=(1ab01aθ001)
is a 3×3 matrix over Fq. Hence, G is of order q2 and the center Z(G)={S(0,b)∣b∈Fq}. Besides, to store the group elements conveniently, S(a,b) can be denoted by (a,b,aθ), so the product of two elements in group G is
(8)S(a1,b1)S(a2,b2)=S(a1,b1,a1θ)S(a2,b2,a2θ)=(a1+a2,b1+b2+a1a2θ,a1θ+a2θ),
and the computation of the product just requires a single multiplication and four additions in Fq.Furthermore, the inverse of an element in groupG is
(9)S(a,b,aθ)-1=S(a,aθ·a+b,aθ)=S(a,aθ+1+b,aθ),
and it also requires a single multiplication and one addition in Fq. If g=S(x,y)∈G and x,y∈Fq, then x and y can be denoted by g·a and g·b, respectively. Hence, g=S(g·a,g·b), where g·a and g·b are the corresponding projections of g along the first and second coordinates.


## 3. Building Block: A NewMST3 Encryption Scheme

Through comparison and analysis, we find that it is rather difficult to devise signature schemes based on the twoMST3 encryption schemes [18, 34]. Therefore, in order to complete the task, we design a new encryption scheme based on logarithmic signatures and random covers. In our scheme, the original secret key f becomes a component of public key, and the encryption process is also simplified. Meanwhile, compared with original schemes, our scheme has a bit improvement in efficiency.


### 3.1. Description of the Scheme

Key GenerationInput: a large group G=A(m,θ), q=2m.
Output: a public key [α,γ,f] with corresponding private key [β,(t0,…,ts)].
(1) Choose a tame logarithmic signatureβ=[B1,B2,…,Bs]=(bij)=(S(0,b(ij)·b)) of type (r1,r2,…,rs) for Z, where bij∈G and b(ij)·b∈Fq.
(2) Select a random coverα=[A1,A2,…,As]=(aij)=(S(a(ij)·a,a(ij)·b)) of the same type as β for a certain subset J of G such that A1,…,As⊆G∖Z, where aij∈G, a(ij)·a∈Fq∖{0}, and a(ij)·b∈Fq.
(3) Chooset0,t1,…,ts∈G∖Z.
(4) Construct a homomorphismf:G→Z defined by f(S(a,b))=S(0,a).
(5) Computeγ:=(hij)=(S(h(ij)·a,h(ij)·b)), where hij=ti-1-1·f(aij)·bij·ti.
(6) Output public key[α,γ,f] and private key [β,(t0,…,ts)].Encryption
Input: a message x∈Z and the public key [α,γ,f].
Output: a ciphertext (y1,y2) of the message m.
(1) Choose a randomR∈Z|Z|.
(2) Compute(10)y1=α′(R)·m,y2=γ′(R)y2=t0-1·f(α′(R))·β′(R)·ts.
(3) Output(y1,y2).Decryption
Input: a ciphertext pair (y1,y2) and the private key [β,t0,…,ts].
Output: the message m∈Z corresponding to ciphertext (y1,y2).
(1) ComputeR=β′-1(y2ts-1f(y1)-1t0).
(2) Computem=α′(R)-1·y1.
(3) Outputm.Correctness
Form∈Z and R∈Z|Z|, we have
(11)y1=α′(R)·m,y2=γ′(R)h1=b1jit0-1f(a1j1)t1⋯bsjsts-1-1f(asjs)tsh1=b1jib2j2⋯bsjst0-1f(a1j1a2j3⋯asjs)tsh1=β′(R)·t0-1·f(α′(R))·tsh1=β′(R)·t0-1·f(α′(R)·m)·tsh1=β′(R)·t0-1·f(y1)·tsh1⟹β′(R)=y2·ts-1·f(y1)-1·t0;
then usingβ′-1 we can recover the random number R by
(12)β′-1(β′(R))=β′-1(y2ts-1f(y1)-1t0)=R.
Consequently, usingy1 we can recover message m by
(13)m=α′(R)-1·y1.


### 3.2. Security Analysis

#### 3.2.1. Attack on Private Key

(a) In general, the adversary tries to obtainβ and (t0,ts) from the equation
(14)β′(R)=y2·ts-1·f(y1)-1·t0,
where R∈Z|Z|, y1=α′(R)·m, y2=γ′(R), and f(y1)-1∈Z.The adversary mainly attempts to compute enough valuesβ′(Ri) in order to construct β using the corresponding conclusion in [27]. If β is of type (r1,r2,…,rs), then one can construct a logarithmic signature equivalent to β by using n selected values β′(Ri), where n=1-s+∑k=1s‍rk. Let {R1,R2,…,Rn} be a collection of random numbers chosen by the adversary. Then
(15)β′(Ri)=yi2ts-1f(yi1)-1t0=f(yi1)-1yi2ts-1t0,i=1,…,n,
where yi1=α′(Ri)·m, yi2=γ′(Ri), and f(yi1)-1∈Z. Note that in the equation above, f(yi1)-1 and yi2 are known and β′(Ri)∈Z; then we have
(16)f(yi1)-1yi2ts-1t0∈Z⟹t0∈tsyi2-1f(yi1)Z.
Since ts∈G∖Z, there are q2-q possibilities for ts. If ts is chosen, from t0∈tsyi2-1f(yi1)Z, there are q possibilities for t0. Hence, there are q(q2-q) suitable pairs (t0,ts). Besides, for each solution pair (t0,ts), there are q equivalent solutions (t0z,tsz) with z∈Z. Consequently, there are q2-q different solutions, so the success probability of the attacker is 1/q(q-1).(b) In this attack, an adversary mainly wants to utilize equivalent secret key[β*,(t0*,…,ts*)] to replace the real secret key [β,(t0,…,ts)]. From [34], we can see that the adversary only needs to let ti*=tizi (1≤i≤s) and bij*=bijcij (1≤i≤s,1≤j≤ri) for zi,cij∈Z. So for the first block of γ, we have
(17)h1j=b1jt0*-1z0f(a1j)t1.
Let bi1*=id; then ci1=bi1; we have
(18)h11=b11*c11t0*-1z0f(a11)t1=b11*t0*-1f(a11)(t1c11z0)⟹t1*=t1c11z0,h1j=b1jt0*-1z0f(a1j)(t1*c11z0)j=2,…,r1,b1j*=b1jc1j=h1jt1*-1f(a1j)-1t0*⟹c1j=c11=b11,h21=b21*c21t1*-1c11z0f(a21)t2⟹t2*=t2c21c11z0,h2j=b2jt1*-1c11z0f(a2j)t2*c21c11z0j=2,…,r2,b2j*=b2jc2j=h2jt2*-1f(a2j)-1t1*⟹c2j=c21=b21⋮
We can get that cij=ci1=bi1 for all i=1,…,s. If we denote cij=ci, then ti*=tiz0∏k=1i‍ck. Consider
(19)γ′(R)=β′(R)t0-1f(α′(R))ts=β′(R)t0*-1z0-1f(α′(R))ts*z0∏k=1s‍ck=(β′(R)∏k=1s‍ck)t0*-1f(α′(R))ts*.
Let β′(R)=b1x1b2x2⋯bsxs, β*:=(bij*), and bij*=bijci for ci∈Z; then
(20)β*(R)=b1x1*b2x2*⋯bsxs*=b1x1c1b2x2c2⋯bsxscs=β′(R)∏k=1s‍ck.
Since β* is tame, so the adversary can use forgery secret key [β*,(t0*,…,ts*)] to recover the random number R. Meanwhile, from conclusions in [31], as there are q=|G/Z| possible choices for t0 in t0Z, the complexity for this attack is O(q). Since the center Z of Suzuki 2-group has a large order q, so the attack is computationally infeasible.


#### 3.2.2. Attack on Ciphertext

OW (onewayness). In the stage of encryption, from the equation y1=α′(R)·x, we can get that x=α′(R)-1·y1. Hence, if the adversary wants to recover message x, he either directly seeks the random number R or recovers R from γ′(R). However, since q is large enough and γ′ is a one-way map, so the attack is computationally infeasible.IND (indistinguishability). Although we cannot give a formal proof on the indistinguishability of the scheme, we would like to analyse it in a heuristic manner. Suppose that (y1*,y2*) is the ciphertext of m0 or m1, where y1*=α′(R)·mδ, y2*=γ′(R), δ=0 or 1, m0, and m1 are randomly selected by the adversary. Then we can analyse the following two cases:
(21)y1=α′(R)·m0y2=γ′(R),y1′=α′(R′)·m1y2′=γ′(R′).
Since R and R′ are randomly selected, and they admit the same distribution, thus, R and R′ are statistically indistinguishable for the adversary. It can be denoted by R≈sR′. Meanwhile, since α′ and β′ are both one-way maps, so we can get that α′(R)≈sα′(R′) and γ′(R)≈sγ′(R′). Besides, since m0≈sm1, so α′(R)·m0≈sα′(R′)·m1. Consequently, we can get that (y1,y2)≈s(y1′,y2′).


## 3.1. Description of the Scheme

Key GenerationInput: a large group G=A(m,θ), q=2m.
Output: a public key [α,γ,f] with corresponding private key [β,(t0,…,ts)].
(1) Choose a tame logarithmic signatureβ=[B1,B2,…,Bs]=(bij)=(S(0,b(ij)·b)) of type (r1,r2,…,rs) for Z, where bij∈G and b(ij)·b∈Fq.
(2) Select a random coverα=[A1,A2,…,As]=(aij)=(S(a(ij)·a,a(ij)·b)) of the same type as β for a certain subset J of G such that A1,…,As⊆G∖Z, where aij∈G, a(ij)·a∈Fq∖{0}, and a(ij)·b∈Fq.
(3) Chooset0,t1,…,ts∈G∖Z.
(4) Construct a homomorphismf:G→Z defined by f(S(a,b))=S(0,a).
(5) Computeγ:=(hij)=(S(h(ij)·a,h(ij)·b)), where hij=ti-1-1·f(aij)·bij·ti.
(6) Output public key[α,γ,f] and private key [β,(t0,…,ts)].Encryption
Input: a message x∈Z and the public key [α,γ,f].
Output: a ciphertext (y1,y2) of the message m.
(1) Choose a randomR∈Z|Z|.
(2) Compute(10)y1=α′(R)·m,y2=γ′(R)y2=t0-1·f(α′(R))·β′(R)·ts.
(3) Output(y1,y2).Decryption
Input: a ciphertext pair (y1,y2) and the private key [β,t0,…,ts].
Output: the message m∈Z corresponding to ciphertext (y1,y2).
(1) ComputeR=β′-1(y2ts-1f(y1)-1t0).
(2) Computem=α′(R)-1·y1.
(3) Outputm.Correctness
Form∈Z and R∈Z|Z|, we have
(11)y1=α′(R)·m,y2=γ′(R)h1=b1jit0-1f(a1j1)t1⋯bsjsts-1-1f(asjs)tsh1=b1jib2j2⋯bsjst0-1f(a1j1a2j3⋯asjs)tsh1=β′(R)·t0-1·f(α′(R))·tsh1=β′(R)·t0-1·f(α′(R)·m)·tsh1=β′(R)·t0-1·f(y1)·tsh1⟹β′(R)=y2·ts-1·f(y1)-1·t0;
then usingβ′-1 we can recover the random number R by
(12)β′-1(β′(R))=β′-1(y2ts-1f(y1)-1t0)=R.
Consequently, usingy1 we can recover message m by
(13)m=α′(R)-1·y1.


## 3.2. Security Analysis

### 3.2.1. Attack on Private Key

(a) In general, the adversary tries to obtainβ and (t0,ts) from the equation
(14)β′(R)=y2·ts-1·f(y1)-1·t0,
where R∈Z|Z|, y1=α′(R)·m, y2=γ′(R), and f(y1)-1∈Z.The adversary mainly attempts to compute enough valuesβ′(Ri) in order to construct β using the corresponding conclusion in [27]. If β is of type (r1,r2,…,rs), then one can construct a logarithmic signature equivalent to β by using n selected values β′(Ri), where n=1-s+∑k=1s‍rk. Let {R1,R2,…,Rn} be a collection of random numbers chosen by the adversary. Then
(15)β′(Ri)=yi2ts-1f(yi1)-1t0=f(yi1)-1yi2ts-1t0,i=1,…,n,
where yi1=α′(Ri)·m, yi2=γ′(Ri), and f(yi1)-1∈Z. Note that in the equation above, f(yi1)-1 and yi2 are known and β′(Ri)∈Z; then we have
(16)f(yi1)-1yi2ts-1t0∈Z⟹t0∈tsyi2-1f(yi1)Z.
Since ts∈G∖Z, there are q2-q possibilities for ts. If ts is chosen, from t0∈tsyi2-1f(yi1)Z, there are q possibilities for t0. Hence, there are q(q2-q) suitable pairs (t0,ts). Besides, for each solution pair (t0,ts), there are q equivalent solutions (t0z,tsz) with z∈Z. Consequently, there are q2-q different solutions, so the success probability of the attacker is 1/q(q-1).(b) In this attack, an adversary mainly wants to utilize equivalent secret key[β*,(t0*,…,ts*)] to replace the real secret key [β,(t0,…,ts)]. From [34], we can see that the adversary only needs to let ti*=tizi (1≤i≤s) and bij*=bijcij (1≤i≤s,1≤j≤ri) for zi,cij∈Z. So for the first block of γ, we have
(17)h1j=b1jt0*-1z0f(a1j)t1.
Let bi1*=id; then ci1=bi1; we have
(18)h11=b11*c11t0*-1z0f(a11)t1=b11*t0*-1f(a11)(t1c11z0)⟹t1*=t1c11z0,h1j=b1jt0*-1z0f(a1j)(t1*c11z0)j=2,…,r1,b1j*=b1jc1j=h1jt1*-1f(a1j)-1t0*⟹c1j=c11=b11,h21=b21*c21t1*-1c11z0f(a21)t2⟹t2*=t2c21c11z0,h2j=b2jt1*-1c11z0f(a2j)t2*c21c11z0j=2,…,r2,b2j*=b2jc2j=h2jt2*-1f(a2j)-1t1*⟹c2j=c21=b21⋮
We can get that cij=ci1=bi1 for all i=1,…,s. If we denote cij=ci, then ti*=tiz0∏k=1i‍ck. Consider
(19)γ′(R)=β′(R)t0-1f(α′(R))ts=β′(R)t0*-1z0-1f(α′(R))ts*z0∏k=1s‍ck=(β′(R)∏k=1s‍ck)t0*-1f(α′(R))ts*.
Let β′(R)=b1x1b2x2⋯bsxs, β*:=(bij*), and bij*=bijci for ci∈Z; then
(20)β*(R)=b1x1*b2x2*⋯bsxs*=b1x1c1b2x2c2⋯bsxscs=β′(R)∏k=1s‍ck.
Since β* is tame, so the adversary can use forgery secret key [β*,(t0*,…,ts*)] to recover the random number R. Meanwhile, from conclusions in [31], as there are q=|G/Z| possible choices for t0 in t0Z, the complexity for this attack is O(q). Since the center Z of Suzuki 2-group has a large order q, so the attack is computationally infeasible.


### 3.2.2. Attack on Ciphertext

OW (onewayness). In the stage of encryption, from the equation y1=α′(R)·x, we can get that x=α′(R)-1·y1. Hence, if the adversary wants to recover message x, he either directly seeks the random number R or recovers R from γ′(R). However, since q is large enough and γ′ is a one-way map, so the attack is computationally infeasible.IND (indistinguishability). Although we cannot give a formal proof on the indistinguishability of the scheme, we would like to analyse it in a heuristic manner. Suppose that (y1*,y2*) is the ciphertext of m0 or m1, where y1*=α′(R)·mδ, y2*=γ′(R), δ=0 or 1, m0, and m1 are randomly selected by the adversary. Then we can analyse the following two cases:
(21)y1=α′(R)·m0y2=γ′(R),y1′=α′(R′)·m1y2′=γ′(R′).
Since R and R′ are randomly selected, and they admit the same distribution, thus, R and R′ are statistically indistinguishable for the adversary. It can be denoted by R≈sR′. Meanwhile, since α′ and β′ are both one-way maps, so we can get that α′(R)≈sα′(R′) and γ′(R)≈sγ′(R′). Besides, since m0≈sm1, so α′(R)·m0≈sα′(R′)·m1. Consequently, we can get that (y1,y2)≈s(y1′,y2′).


## 3.2.1. Attack on Private Key

(a) In general, the adversary tries to obtainβ and (t0,ts) from the equation
(14)β′(R)=y2·ts-1·f(y1)-1·t0,
where R∈Z|Z|, y1=α′(R)·m, y2=γ′(R), and f(y1)-1∈Z.The adversary mainly attempts to compute enough valuesβ′(Ri) in order to construct β using the corresponding conclusion in [27]. If β is of type (r1,r2,…,rs), then one can construct a logarithmic signature equivalent to β by using n selected values β′(Ri), where n=1-s+∑k=1s‍rk. Let {R1,R2,…,Rn} be a collection of random numbers chosen by the adversary. Then
(15)β′(Ri)=yi2ts-1f(yi1)-1t0=f(yi1)-1yi2ts-1t0,i=1,…,n,
where yi1=α′(Ri)·m, yi2=γ′(Ri), and f(yi1)-1∈Z. Note that in the equation above, f(yi1)-1 and yi2 are known and β′(Ri)∈Z; then we have
(16)f(yi1)-1yi2ts-1t0∈Z⟹t0∈tsyi2-1f(yi1)Z.
Since ts∈G∖Z, there are q2-q possibilities for ts. If ts is chosen, from t0∈tsyi2-1f(yi1)Z, there are q possibilities for t0. Hence, there are q(q2-q) suitable pairs (t0,ts). Besides, for each solution pair (t0,ts), there are q equivalent solutions (t0z,tsz) with z∈Z. Consequently, there are q2-q different solutions, so the success probability of the attacker is 1/q(q-1).(b) In this attack, an adversary mainly wants to utilize equivalent secret key[β*,(t0*,…,ts*)] to replace the real secret key [β,(t0,…,ts)]. From [34], we can see that the adversary only needs to let ti*=tizi (1≤i≤s) and bij*=bijcij (1≤i≤s,1≤j≤ri) for zi,cij∈Z. So for the first block of γ, we have
(17)h1j=b1jt0*-1z0f(a1j)t1.
Let bi1*=id; then ci1=bi1; we have
(18)h11=b11*c11t0*-1z0f(a11)t1=b11*t0*-1f(a11)(t1c11z0)⟹t1*=t1c11z0,h1j=b1jt0*-1z0f(a1j)(t1*c11z0)j=2,…,r1,b1j*=b1jc1j=h1jt1*-1f(a1j)-1t0*⟹c1j=c11=b11,h21=b21*c21t1*-1c11z0f(a21)t2⟹t2*=t2c21c11z0,h2j=b2jt1*-1c11z0f(a2j)t2*c21c11z0j=2,…,r2,b2j*=b2jc2j=h2jt2*-1f(a2j)-1t1*⟹c2j=c21=b21⋮
We can get that cij=ci1=bi1 for all i=1,…,s. If we denote cij=ci, then ti*=tiz0∏k=1i‍ck. Consider
(19)γ′(R)=β′(R)t0-1f(α′(R))ts=β′(R)t0*-1z0-1f(α′(R))ts*z0∏k=1s‍ck=(β′(R)∏k=1s‍ck)t0*-1f(α′(R))ts*.
Let β′(R)=b1x1b2x2⋯bsxs, β*:=(bij*), and bij*=bijci for ci∈Z; then
(20)β*(R)=b1x1*b2x2*⋯bsxs*=b1x1c1b2x2c2⋯bsxscs=β′(R)∏k=1s‍ck.
Since β* is tame, so the adversary can use forgery secret key [β*,(t0*,…,ts*)] to recover the random number R. Meanwhile, from conclusions in [31], as there are q=|G/Z| possible choices for t0 in t0Z, the complexity for this attack is O(q). Since the center Z of Suzuki 2-group has a large order q, so the attack is computationally infeasible.


## 3.2.2. Attack on Ciphertext

OW (onewayness). In the stage of encryption, from the equation y1=α′(R)·x, we can get that x=α′(R)-1·y1. Hence, if the adversary wants to recover message x, he either directly seeks the random number R or recovers R from γ′(R). However, since q is large enough and γ′ is a one-way map, so the attack is computationally infeasible.IND (indistinguishability). Although we cannot give a formal proof on the indistinguishability of the scheme, we would like to analyse it in a heuristic manner. Suppose that (y1*,y2*) is the ciphertext of m0 or m1, where y1*=α′(R)·mδ, y2*=γ′(R), δ=0 or 1, m0, and m1 are randomly selected by the adversary. Then we can analyse the following two cases:
(21)y1=α′(R)·m0y2=γ′(R),y1′=α′(R′)·m1y2′=γ′(R′).
Since R and R′ are randomly selected, and they admit the same distribution, thus, R and R′ are statistically indistinguishable for the adversary. It can be denoted by R≈sR′. Meanwhile, since α′ and β′ are both one-way maps, so we can get that α′(R)≈sα′(R′) and γ′(R)≈sγ′(R′). Besides, since m0≈sm1, so α′(R)·m0≈sα′(R′)·m1. Consequently, we can get that (y1,y2)≈s(y1′,y2′).


## 4. A Digital Signature Scheme Based on the NewMST3 Cryptosystem

In this section, we utilize the encryption scheme above to construct a digital signature scheme based on random covers and logarithmic signatures.


### 4.1. Description of the Scheme

Key Generation
Input: a large group G=A(m,θ) and q=2m.
Output: a public key [α,γ,f,H] with corresponding private key [β,(t0,…,ts)].
(1) Choose a tame logarithmic signatureβ=[B1,B2,…,Bs]:=(bij)=(S(0,b(ij)·b)) of type (r1,r2,…,rs) for Z, where bij∈G and b(ij)·b∈Fq.
(2) Select a random coverα=[A1,A2,…,As]:=(aij)=(S(a(ij)·a,a(ij)·b)) of the same type as β for a certain subset J of G such that A1,…,As⊆G∖Z, where aij∈G, a(ij)·a∈Fq∖{0}, and a(ij)·b∈Fq.
(3) Chooset0,t1,…,ts∈G∖Z.
(4) Construct a homomorphismsf:G→Z defined by f(S(a,b))=S(0,a).
(5) Computeγ:=(hij)=(S(h(ij)·a,h(ij)·b)), where hij=ti-1-1·f(aij)·bij·ti.
(6) Define a hash functionH:G×G→G.
(7) Output public key[α,γ,f,H] and private key [β,(t0,…,ts)].Signature
Input: a message m∈G and private key [β,(t0,…,ts)].
Output: signature σ=(S1,S2).
(1) Randomly selectz∈Z and compute a random element r=t0-1zts∈G. Let c2=r, c1=H(m,r).
(2) ComputeS1=β′-1(f(c1)-1·t0·c2·ts-1) and S2=α′(S1)-1·c1.
(3) Outputσ=(S1,S2).Verification
Input: the message m∈G, signature σ=(S1,S2), and public key [α,γ,f,H].
Output: 0 or 1.
(1) ComputeA=α′(S1)·S2 and B=H(m,γ′(S1)·f(S2)).
(2) IfA=B, output 1; otherwise output 0.Correctness. For a given message m∈G,
(22)γ′(S1)=t0-1·f(α′(S1))·β′(S1)·ts⟹S1=β′-1(f(α′(S1))-1·t0·γ′(S1)·ts-1).Meanwhile,S1=β′-1(f(c1)-1·t0·c2·ts-1) and c1=α′(S1)·S2.Hence,(23)f(α′(S1))-1·t0·γ′(S1)·ts-1=f(c1)-1·t0·c2·ts-1=f(α′(S1)·S2)-1·t0·c2·ts-1=f(α′(S1))-1·t0·(f(S2)-1·c2)·ts-1⟹γ′(S1)=f(S2)-1·c2⟹c2=γ′(S1)·f(S2).
Consequently, we have
(24)H(m,c2)=c1⟹H(m,γ′(S1)·f(S2))=α′(S1)·S2.


### 4.2. Security Analysis

#### 4.2.1. Attack on Private Key

(a) Compared with the encryption scheme in Section3, we add a secure hash function in the signature scheme. Hence, analysis of the security of the signature scheme is similar to that in the encryption scheme. In the signature scheme, the goal of the general attack is also to determine β and (t0,ts) from the equation
(25)β′(R)=y2ts-1f(y1)-1t0,
where y1=α′(R)·x, y2=γ′(R), and f(y1)-1∈Z. Let {R1,R2,…,Rn} be a collection of random numbers chosen by the adversary. Then we have
(26)β′(Ri)=yi2ts-1f(yi1)-1t0=f(yi1)-1yi2ts-1t0,
where yi1=α′(Ri)·x, yi2=γ′(Ri), and f(yi1)-1∈Z. Then
(27)f(yi1)-1yi2ts-1t0∈Z⟹t0∈tsyi2-1f(yi1)Z.
As described in Section 3, there are q2-q different solutions; the success probability of the adversary is 1/q(q-1).(b) In our signature scheme, we construct a ciphertext pair(c1,c2) then obtain the signature σ=(S1,S2) by decrypting the pair (c1,c2). Therefore, analysis of the equivalent key is similar to that in Section 3. In this attack, an adversary mainly wants to utilize equivalent secret key [β*,(t0*,…,ts*)] to replace the real secret key [β,(t0,…,ts)]. As described in Section 3, for a random number R∈Z|Z|,
(28)γ′(R)=β′(R)t0-1f(α′(R))ts=β′(R)t0*-1z0f(α′(R))ts*z0∏k=1s‍ck=(β′(R)∏k=1s‍ck)t0*-1f(α′(R))ts*.
Let β′(R)=b1x1b2x2⋯bsxs and β*:=(bij*), bij*=bijci; then
(29)β*(R)=b1x1*b2x2*⋯bsxs*=b1x1c1b2x2c2⋯bsxscs=β′(R)∏k=1s‍ck.
Consequently, the complexity for this attack is O(q). While, due to the center Z of Suzuki 2-group having a large order q, so the attack is computationally infeasible.


#### 4.2.2. Unforgeability

Suppose that Eve attempts to forge a message-signature pair(m*,S1*,S2*) such that
(30)α(S1*)·S2*=H(m*,γ′(S1*)·f(S2*)).Case 1.
Eve chooses a random numberS1*∈Z|Z| and S2*∈G then computes α(S1*)·S2* and γ(S1*)·f(S2*). If Eve can get a message m* satisfying the above equation, then he can answer the preimage of hash function H, but it is infeasible since H is a secure cryptographic hash function.Case 2.
Eve randomly selects two elementsm*∈G and S2*∈G and computes c2*=H(m*,c1*). In order to obtain a valid S1*, Eve selects c1* and computes y=H(m*,c1*·f(S2*))·(S2*)-1. Getting a right S1* such that α(S1*)·S2*=H(m*,γ′(S1*)·f(S2*)) is equivalent to solving the equations c1*=γ′(S1*) and y=α′(S1*). Since α′ and γ′ are both one-way functions, so Eve cannot answer right S1* by considering the corresponding ciphertext (c1*,y).Case 3.
Eve randomly chooses one pair(m*,S1*) and r∈Z then computes S2*=α′(S1*)-1·H(m*,γ′(S1*)·r). If f(S2*)=r, then Eve can forge one valid signature. Note that the probability of this case is Pr[f(S2*)=r]=1/q for |Z|=q. Since q is large enough, this attack is computationally infeasible.


## 4.1. Description of the Scheme

Key Generation
Input: a large group G=A(m,θ) and q=2m.
Output: a public key [α,γ,f,H] with corresponding private key [β,(t0,…,ts)].
(1) Choose a tame logarithmic signatureβ=[B1,B2,…,Bs]:=(bij)=(S(0,b(ij)·b)) of type (r1,r2,…,rs) for Z, where bij∈G and b(ij)·b∈Fq.
(2) Select a random coverα=[A1,A2,…,As]:=(aij)=(S(a(ij)·a,a(ij)·b)) of the same type as β for a certain subset J of G such that A1,…,As⊆G∖Z, where aij∈G, a(ij)·a∈Fq∖{0}, and a(ij)·b∈Fq.
(3) Chooset0,t1,…,ts∈G∖Z.
(4) Construct a homomorphismsf:G→Z defined by f(S(a,b))=S(0,a).
(5) Computeγ:=(hij)=(S(h(ij)·a,h(ij)·b)), where hij=ti-1-1·f(aij)·bij·ti.
(6) Define a hash functionH:G×G→G.
(7) Output public key[α,γ,f,H] and private key [β,(t0,…,ts)].Signature
Input: a message m∈G and private key [β,(t0,…,ts)].
Output: signature σ=(S1,S2).
(1) Randomly selectz∈Z and compute a random element r=t0-1zts∈G. Let c2=r, c1=H(m,r).
(2) ComputeS1=β′-1(f(c1)-1·t0·c2·ts-1) and S2=α′(S1)-1·c1.
(3) Outputσ=(S1,S2).Verification
Input: the message m∈G, signature σ=(S1,S2), and public key [α,γ,f,H].
Output: 0 or 1.
(1) ComputeA=α′(S1)·S2 and B=H(m,γ′(S1)·f(S2)).
(2) IfA=B, output 1; otherwise output 0.Correctness. For a given message m∈G,
(22)γ′(S1)=t0-1·f(α′(S1))·β′(S1)·ts⟹S1=β′-1(f(α′(S1))-1·t0·γ′(S1)·ts-1).Meanwhile,S1=β′-1(f(c1)-1·t0·c2·ts-1) and c1=α′(S1)·S2.Hence,(23)f(α′(S1))-1·t0·γ′(S1)·ts-1=f(c1)-1·t0·c2·ts-1=f(α′(S1)·S2)-1·t0·c2·ts-1=f(α′(S1))-1·t0·(f(S2)-1·c2)·ts-1⟹γ′(S1)=f(S2)-1·c2⟹c2=γ′(S1)·f(S2).
Consequently, we have
(24)H(m,c2)=c1⟹H(m,γ′(S1)·f(S2))=α′(S1)·S2.


## 4.2. Security Analysis

### 4.2.1. Attack on Private Key

(a) Compared with the encryption scheme in Section3, we add a secure hash function in the signature scheme. Hence, analysis of the security of the signature scheme is similar to that in the encryption scheme. In the signature scheme, the goal of the general attack is also to determine β and (t0,ts) from the equation
(25)β′(R)=y2ts-1f(y1)-1t0,
where y1=α′(R)·x, y2=γ′(R), and f(y1)-1∈Z. Let {R1,R2,…,Rn} be a collection of random numbers chosen by the adversary. Then we have
(26)β′(Ri)=yi2ts-1f(yi1)-1t0=f(yi1)-1yi2ts-1t0,
where yi1=α′(Ri)·x, yi2=γ′(Ri), and f(yi1)-1∈Z. Then
(27)f(yi1)-1yi2ts-1t0∈Z⟹t0∈tsyi2-1f(yi1)Z.
As described in Section 3, there are q2-q different solutions; the success probability of the adversary is 1/q(q-1).(b) In our signature scheme, we construct a ciphertext pair(c1,c2) then obtain the signature σ=(S1,S2) by decrypting the pair (c1,c2). Therefore, analysis of the equivalent key is similar to that in Section 3. In this attack, an adversary mainly wants to utilize equivalent secret key [β*,(t0*,…,ts*)] to replace the real secret key [β,(t0,…,ts)]. As described in Section 3, for a random number R∈Z|Z|,
(28)γ′(R)=β′(R)t0-1f(α′(R))ts=β′(R)t0*-1z0f(α′(R))ts*z0∏k=1s‍ck=(β′(R)∏k=1s‍ck)t0*-1f(α′(R))ts*.
Let β′(R)=b1x1b2x2⋯bsxs and β*:=(bij*), bij*=bijci; then
(29)β*(R)=b1x1*b2x2*⋯bsxs*=b1x1c1b2x2c2⋯bsxscs=β′(R)∏k=1s‍ck.
Consequently, the complexity for this attack is O(q). While, due to the center Z of Suzuki 2-group having a large order q, so the attack is computationally infeasible.


### 4.2.2. Unforgeability

Suppose that Eve attempts to forge a message-signature pair(m*,S1*,S2*) such that
(30)α(S1*)·S2*=H(m*,γ′(S1*)·f(S2*)).Case 1.
Eve chooses a random numberS1*∈Z|Z| and S2*∈G then computes α(S1*)·S2* and γ(S1*)·f(S2*). If Eve can get a message m* satisfying the above equation, then he can answer the preimage of hash function H, but it is infeasible since H is a secure cryptographic hash function.Case 2.
Eve randomly selects two elementsm*∈G and S2*∈G and computes c2*=H(m*,c1*). In order to obtain a valid S1*, Eve selects c1* and computes y=H(m*,c1*·f(S2*))·(S2*)-1. Getting a right S1* such that α(S1*)·S2*=H(m*,γ′(S1*)·f(S2*)) is equivalent to solving the equations c1*=γ′(S1*) and y=α′(S1*). Since α′ and γ′ are both one-way functions, so Eve cannot answer right S1* by considering the corresponding ciphertext (c1*,y).Case 3.
Eve randomly chooses one pair(m*,S1*) and r∈Z then computes S2*=α′(S1*)-1·H(m*,γ′(S1*)·r). If f(S2*)=r, then Eve can forge one valid signature. Note that the probability of this case is Pr[f(S2*)=r]=1/q for |Z|=q. Since q is large enough, this attack is computationally infeasible.


## 4.2.1. Attack on Private Key

(a) Compared with the encryption scheme in Section3, we add a secure hash function in the signature scheme. Hence, analysis of the security of the signature scheme is similar to that in the encryption scheme. In the signature scheme, the goal of the general attack is also to determine β and (t0,ts) from the equation
(25)β′(R)=y2ts-1f(y1)-1t0,
where y1=α′(R)·x, y2=γ′(R), and f(y1)-1∈Z. Let {R1,R2,…,Rn} be a collection of random numbers chosen by the adversary. Then we have
(26)β′(Ri)=yi2ts-1f(yi1)-1t0=f(yi1)-1yi2ts-1t0,
where yi1=α′(Ri)·x, yi2=γ′(Ri), and f(yi1)-1∈Z. Then
(27)f(yi1)-1yi2ts-1t0∈Z⟹t0∈tsyi2-1f(yi1)Z.
As described in Section 3, there are q2-q different solutions; the success probability of the adversary is 1/q(q-1).(b) In our signature scheme, we construct a ciphertext pair(c1,c2) then obtain the signature σ=(S1,S2) by decrypting the pair (c1,c2). Therefore, analysis of the equivalent key is similar to that in Section 3. In this attack, an adversary mainly wants to utilize equivalent secret key [β*,(t0*,…,ts*)] to replace the real secret key [β,(t0,…,ts)]. As described in Section 3, for a random number R∈Z|Z|,
(28)γ′(R)=β′(R)t0-1f(α′(R))ts=β′(R)t0*-1z0f(α′(R))ts*z0∏k=1s‍ck=(β′(R)∏k=1s‍ck)t0*-1f(α′(R))ts*.
Let β′(R)=b1x1b2x2⋯bsxs and β*:=(bij*), bij*=bijci; then
(29)β*(R)=b1x1*b2x2*⋯bsxs*=b1x1c1b2x2c2⋯bsxscs=β′(R)∏k=1s‍ck.
Consequently, the complexity for this attack is O(q). While, due to the center Z of Suzuki 2-group having a large order q, so the attack is computationally infeasible.


## 4.2.2. Unforgeability

Suppose that Eve attempts to forge a message-signature pair(m*,S1*,S2*) such that
(30)α(S1*)·S2*=H(m*,γ′(S1*)·f(S2*)).Case 1.
Eve chooses a random numberS1*∈Z|Z| and S2*∈G then computes α(S1*)·S2* and γ(S1*)·f(S2*). If Eve can get a message m* satisfying the above equation, then he can answer the preimage of hash function H, but it is infeasible since H is a secure cryptographic hash function.Case 2.
Eve randomly selects two elementsm*∈G and S2*∈G and computes c2*=H(m*,c1*). In order to obtain a valid S1*, Eve selects c1* and computes y=H(m*,c1*·f(S2*))·(S2*)-1. Getting a right S1* such that α(S1*)·S2*=H(m*,γ′(S1*)·f(S2*)) is equivalent to solving the equations c1*=γ′(S1*) and y=α′(S1*). Since α′ and γ′ are both one-way functions, so Eve cannot answer right S1* by considering the corresponding ciphertext (c1*,y).Case 3.
Eve randomly chooses one pair(m*,S1*) and r∈Z then computes S2*=α′(S1*)-1·H(m*,γ′(S1*)·r). If f(S2*)=r, then Eve can forge one valid signature. Note that the probability of this case is Pr[f(S2*)=r]=1/q for |Z|=q. Since q is large enough, this attack is computationally infeasible.


## 5. Comparisons and Illustrations

### 5.1. Comparisons

In this subsection, we compareeMST3 encryption scheme in [34] and our encryption scheme on number of basic operations. Then, we make further efforts to show the performance of our signature scheme. We summarize the number of basic operations (addition (ADD), multiplication (MULT), exponentiation with θ (EXP(θ)), etc.).Table1 shows the number of operations required for eMST3 scheme and our scheme. The corresponding operations are namely addition (ADD), multiplication (MULT), exponentiation with θ (EXP(θ)), generation of m-bit random R (PRNG) [36], and factorization of β′(R)∈Z with respect to a logarithmic signature β using the Algorithms 9, 10, and 11 (FACTOR) [34].Table 1
Number of basic operations for one encryption/decryption.
F
2
m ADD
F
2
m MULT
F
2
m EXP(θ)
F
2
m PRNG
Factor
Encryption1
e
M
S
T
3 scheme [34]
8
s
-
6
2
s
-
2
—
1
—
Our scheme
8
s
-
7
2
s
-
2
—
1
—
Decryption2
e
M
S
T
3 scheme
4
s
+
15
s
+
5
1
—
1
Our scheme
4
s
+
10
s
+
3
—
—
1
1Compared with eMST3 scheme, our scheme reduces a step of multiplication with the element of the center Z in the stage of encryption. Thus, the number of (F2m ADD) reduces once.
2In the stage of decryption, our scheme reduces a step of inverse operation, a step of multiplication operation, and a F2m EXP(θ)  operation, so the number of (F2m ADD) reduces five times and (F2m MULT) reduces twice.Table2 presents the number of operations required for public key and secret key. The corresponding operations are, namely, addition (ADD) and multiplication (MULT) generation of m-bit random R (PRNG) [36].Table 2
Number of basic operations for public key generation.
Secret keyβ
Secret key[t0,…,ts]
Public keyα
Public keyγ
F
2
m ADD
T
3
—
T
9
T
+
s
F
2
m MULT
—
s
+
1
4
T
-
s
2
T
+
s
F
2
m PRNG
∑
l
=
1
v
‍
r
l
*
5
2
(
s
+
1
)
2
T
-
s
—
3
T
=
∑
i
=
1
s
‍
r
i, ri=∏j=1ui‍rij*·wi for 1≤i≤s and ∑i=1s‍ui=v, where wi={0ifui=11ifui>1.
4For a∈Fq, θ:a→a2 is a Frobenius automorphism. Hence, θ can be reduced to a multiplication.
5
v represents the number of blocks before fusion.For example, whens=26, v=52, the number of multiplication for secret key β is 1792 and the number of generation of m-bit random R is 760; when s=23, v=44, the number of multiplication for secret key β is 2688 and the number of generation of m-bit random R is 948; when s=20, v=58, the number of multiplication for secret key β is 4864 and the number of generation of m-bit random R is 712.Table3 indicates the performance of the signature scheme. Table 4 indicates parameter size in our schemes. Here, we mainly analyse the number of elements in Suzuki 2-group.Table 3
Number of basic operations for digital signature scheme.
F
2
m ADD
F
2
m MULT
F
2
m EXP(θ)
F
2
m PRNG
Factor
Signature
4
s
+
11
s
+
3
—
1
1
Verification
8
s
-
7
2
s
-
2
—
—
—Table 4
Parameter size.
Public key
Secret key
Encryption
Signature
Number of elements
2
T
6
T
+
s
+
1
2
2
6
T is the same as Table 2.Remark 3.
In the community of cryptography based on chaos theory, a lot of efforts were focused on secret key cryptography in early years [5–7]. Recently, Wang et al. [8–14] made progress on building public key agreement protocols by using chaos theory. The corresponding schemes also have high efficiency and strong security. Being different from quantum cryptography, chaotic cryptography, and DNA cryptography, MST3 cryptosystem is a public key cryptosystem of classical cryptography. The hardness of our encryption scheme is based on a type of intractable mathematical problem called group factorization problem. Meanwhile, our encryption scheme and signature scheme are efficient in classical computer.


### 5.2. A Toy Example

In this subsection, we present a toy example of signing a random elementm∈Fq. In fact, our method is universal in the sense that it can be used to sign documents or realize authentication protocols based on images.Key Generation
Input: a Suzuki 2-groupG=A(m,θ) with m=8, q=28 and s=2.
Output: public key[α,γ,f,H] and private key [β,t0,t1,t2].In general, let a pair(a,b) denote an element of group G. For simplicity, we use a binary number of an element b∈Fq to present (0,b)∈Z and a binary numbers pair to present (a,b)∈G.(i) For simplicity, we use a one-way functionH as the hash function in our scheme. That is, H: G×G→G is given by
(31)H((a1,b1),(a2,b2))=(a1a2,b1b2).
Actually, one can also use standard hash functions like SHA1 and so forth.(ii) A factorizable logarithmic signatureβ=[B1,B2]=(bi,j)=(S(0,b(ij)·2)) of type (r1,…,rs) for Z.(1) We first construct canonical logarithmic signature[B1*,B2*,B3*] of type (4,8,8) in standard form:
(32)B1*={[00000000],[01000000],hhh[10000000],[11000000]},B2*={[11000000],[01001000],hhh[01010000],[00011000],hhh[00100000],[00101000],hhh[11110000],[11111000]},B3*={[11010000],[11110001],hhh[01010010],[11111011],hhh[01101100],[01110101],hhh[10100110],[01111111]}.(2) Fuse blocksB1*, B3* to construct the product B2=(B1*·B3*) and let B1=B2*. That is, B1, B2 is the logarithmic signature of type (r1,r2) (r1=8,r2=32)
(33)B1={[11000000],[01001000],hhh[01010000],[00011000],hhh[00100000],[00101000],hh[11110000],[11111000]},(34)B2={[11010000],[11110001],hhh[01010010],[11111011],hhh[01101100],[01110101],hhh[10100110],[01111111],hhh[10010000],[10110001],hhh[00010010],[10111011],hhh[00101100],[00110101],hhh[11100110],[00111111],hhh[01010000],[01110001],hhh[11010010],[01111011],hhh[11101100],[11110101],hhh[00100110],[11111111],hhh[00010000],[00110001],hhh[10010010],[00111011],hhh[10101100],[10110101],hh[01100110],[10111111]}.(i) A random coverα=[A1,A2]=(aij)=(S(a(ij)·1,a(ij)·2)) of the same type as β(35)A1={([01010101],[00101000]),hhh([01100010],[00000100]),hhh([10111010],[11110000]),hhh([11111010],[01011110]),hhh([11111000],[10011110]),hhh([11000111],[00010100]),hhh([01011011],[11101011]),hhh([00010011],[10101111])},A2={([01011101],[00111110]),hhh([00110010],[00001000]),hhh([01001010],[11100011]),hhh([11001100],[00001011]),hhh([11101001],[10011110]),hhh([10001011],[10110000]),hhh([00111011],[11011010]),hhh([01110101],[01011101]),hhh([00110001],[01111100]),hhh([00101110],[00100110]),hhh([11011111],[11001011]),hhh([01000011],[11000110]),hhh([01110111],[10010011]),hhh([10100100],[10100001]),hhh([11100000],[11001110]),hhh([00000001],[00101100]),hhh([11101101],[00100010]),hhh([11000000],[00000100]),hhh([01101111],[10000001]),hhh([00100000],[11000000]),hhh([11011010],[00011010]),hhh([01001010],[01011100]),hhh([11110111],[00101010]),hhh([10010111],[11100101]),hhh([01001110],[10111011]),hhh([11111010],[01001100]),hhh([11110100],[10011100]),hhh([00000011],[10101110]),hhh([00001100],[10101101]),hhh([11111001],[00101000]),hhh([00001101],[01000010]),hhh([01011101],[01101011])}.(ii) Selectt0,t1,t2∈G∖Z:
(36)t0=([11110100],[11111001]),t1=([00100010],[01001111]),t2=([11101011],[10110000]).(iii) Construct a homomorphismf: G→Z: f(a,b)=(0,a).(iv) Computeγ=(hi,j), hi,j=ti-1-1·f(ai,j)·bi,j·ti=[V1,V2], and i=0,1,2:
(37)V1={([11010110],[10101111]),hhh([11010110],[00010000]),hhh([11010110],[11010000]),hhh([11010110],[11011000]),hhh([11010110],[11100010]),hhh([11010110],[11010101]),hhh([11010110],[10010001]),hhh([11010110],[11010001])},(38)V2={([11001001],[11011111]),hhh([11001001],[10010001]),hhh([11001001],[01001010]),hhh([11001001],[01100101]),hhh([11001001],[11010111]),hhh([11001001],[10101100]),hhh([11001001],[11001111]),hhh([11001001],[01011000]),hhh([11001001],[11110011]),hhh([11001001],[11001101]),hhh([11001001],[10011111]),hhh([11001001],[10101010]),hhh([11001001],[00001001]),hhh([11001001],[11000011]),hhh([11001001],[01010100]),hhh([11001001],[01101100]),hhh([11001001],[11101111]),hhh([11001001],[11100011]),hhh([11001001],[11101111]),hhh([11001001],[00001001]),hhh([11001001],[01100100]),hhh([11001001],[11101101]),hhh([11001001],[10000011]),hhh([11001001],[00111010]),hhh([11001001],[00001100]),hhh([11001001],[10011001]),hhh([11001001],[00110100]),hhh([11001001],[01101010]),hhh([11001001],[11110010]),hhh([11001001],[00011110]),hhh([11001001],[00111001]),hhh([11001001],[10110000])}.Signature(i) Choose a messageM=([10011101], [11010101]).(ii) Samplez=([00000000], [10011010]) (∈Z) and compute r=t0-1·z·t2(39)c2=r=([00011111],[00011011]),c1=H(M,r)c1=([00010101],[01100100]).(iii) Signatureσ=(S1,S2):
(40)S1=71(∈Zq),S2=([00111011],[01010110]).Verification(i) Compute(41)Y1=α′(S1)·S2=([00010101],[01100100]).(ii) Compute(42)γ′(S1)=([00011111],[00100000]),f(S2)=([00000000],[00111011]),Y2=γ′(S1)·f(S2)=([00011111],[00011011]).SinceY1-c1=[00000000] and Y2-c2=[00000000], so we can get that H(M,γ′(S1)·f(S2))=α′(S1)·S2.


## 5.1. Comparisons

In this subsection, we compareeMST3 encryption scheme in [34] and our encryption scheme on number of basic operations. Then, we make further efforts to show the performance of our signature scheme. We summarize the number of basic operations (addition (ADD), multiplication (MULT), exponentiation with θ (EXP(θ)), etc.).Table1 shows the number of operations required for eMST3 scheme and our scheme. The corresponding operations are namely addition (ADD), multiplication (MULT), exponentiation with θ (EXP(θ)), generation of m-bit random R (PRNG) [36], and factorization of β′(R)∈Z with respect to a logarithmic signature β using the Algorithms 9, 10, and 11 (FACTOR) [34].Table 1
Number of basic operations for one encryption/decryption.
F
2
m ADD
F
2
m MULT
F
2
m EXP(θ)
F
2
m PRNG
Factor
Encryption1
e
M
S
T
3 scheme [34]
8
s
-
6
2
s
-
2
—
1
—
Our scheme
8
s
-
7
2
s
-
2
—
1
—
Decryption2
e
M
S
T
3 scheme
4
s
+
15
s
+
5
1
—
1
Our scheme
4
s
+
10
s
+
3
—
—
1
1Compared with eMST3 scheme, our scheme reduces a step of multiplication with the element of the center Z in the stage of encryption. Thus, the number of (F2m ADD) reduces once.
2In the stage of decryption, our scheme reduces a step of inverse operation, a step of multiplication operation, and a F2m EXP(θ)  operation, so the number of (F2m ADD) reduces five times and (F2m MULT) reduces twice.Table2 presents the number of operations required for public key and secret key. The corresponding operations are, namely, addition (ADD) and multiplication (MULT) generation of m-bit random R (PRNG) [36].Table 2
Number of basic operations for public key generation.
Secret keyβ
Secret key[t0,…,ts]
Public keyα
Public keyγ
F
2
m ADD
T
3
—
T
9
T
+
s
F
2
m MULT
—
s
+
1
4
T
-
s
2
T
+
s
F
2
m PRNG
∑
l
=
1
v
‍
r
l
*
5
2
(
s
+
1
)
2
T
-
s
—
3
T
=
∑
i
=
1
s
‍
r
i, ri=∏j=1ui‍rij*·wi for 1≤i≤s and ∑i=1s‍ui=v, where wi={0ifui=11ifui>1.
4For a∈Fq, θ:a→a2 is a Frobenius automorphism. Hence, θ can be reduced to a multiplication.
5
v represents the number of blocks before fusion.For example, whens=26, v=52, the number of multiplication for secret key β is 1792 and the number of generation of m-bit random R is 760; when s=23, v=44, the number of multiplication for secret key β is 2688 and the number of generation of m-bit random R is 948; when s=20, v=58, the number of multiplication for secret key β is 4864 and the number of generation of m-bit random R is 712.Table3 indicates the performance of the signature scheme. Table 4 indicates parameter size in our schemes. Here, we mainly analyse the number of elements in Suzuki 2-group.Table 3
Number of basic operations for digital signature scheme.
F
2
m ADD
F
2
m MULT
F
2
m EXP(θ)
F
2
m PRNG
Factor
Signature
4
s
+
11
s
+
3
—
1
1
Verification
8
s
-
7
2
s
-
2
—
—
—Table 4
Parameter size.
Public key
Secret key
Encryption
Signature
Number of elements
2
T
6
T
+
s
+
1
2
2
6
T is the same as Table 2.Remark 3.
In the community of cryptography based on chaos theory, a lot of efforts were focused on secret key cryptography in early years [5–7]. Recently, Wang et al. [8–14] made progress on building public key agreement protocols by using chaos theory. The corresponding schemes also have high efficiency and strong security. Being different from quantum cryptography, chaotic cryptography, and DNA cryptography, MST3 cryptosystem is a public key cryptosystem of classical cryptography. The hardness of our encryption scheme is based on a type of intractable mathematical problem called group factorization problem. Meanwhile, our encryption scheme and signature scheme are efficient in classical computer.


## 5.2. A Toy Example

In this subsection, we present a toy example of signing a random elementm∈Fq. In fact, our method is universal in the sense that it can be used to sign documents or realize authentication protocols based on images.Key Generation
Input: a Suzuki 2-groupG=A(m,θ) with m=8, q=28 and s=2.
Output: public key[α,γ,f,H] and private key [β,t0,t1,t2].In general, let a pair(a,b) denote an element of group G. For simplicity, we use a binary number of an element b∈Fq to present (0,b)∈Z and a binary numbers pair to present (a,b)∈G.(i) For simplicity, we use a one-way functionH as the hash function in our scheme. That is, H: G×G→G is given by
(31)H((a1,b1),(a2,b2))=(a1a2,b1b2).
Actually, one can also use standard hash functions like SHA1 and so forth.(ii) A factorizable logarithmic signatureβ=[B1,B2]=(bi,j)=(S(0,b(ij)·2)) of type (r1,…,rs) for Z.(1) We first construct canonical logarithmic signature[B1*,B2*,B3*] of type (4,8,8) in standard form:
(32)B1*={[00000000],[01000000],hhh[10000000],[11000000]},B2*={[11000000],[01001000],hhh[01010000],[00011000],hhh[00100000],[00101000],hhh[11110000],[11111000]},B3*={[11010000],[11110001],hhh[01010010],[11111011],hhh[01101100],[01110101],hhh[10100110],[01111111]}.(2) Fuse blocksB1*, B3* to construct the product B2=(B1*·B3*) and let B1=B2*. That is, B1, B2 is the logarithmic signature of type (r1,r2) (r1=8,r2=32)
(33)B1={[11000000],[01001000],hhh[01010000],[00011000],hhh[00100000],[00101000],hh[11110000],[11111000]},(34)B2={[11010000],[11110001],hhh[01010010],[11111011],hhh[01101100],[01110101],hhh[10100110],[01111111],hhh[10010000],[10110001],hhh[00010010],[10111011],hhh[00101100],[00110101],hhh[11100110],[00111111],hhh[01010000],[01110001],hhh[11010010],[01111011],hhh[11101100],[11110101],hhh[00100110],[11111111],hhh[00010000],[00110001],hhh[10010010],[00111011],hhh[10101100],[10110101],hh[01100110],[10111111]}.(i) A random coverα=[A1,A2]=(aij)=(S(a(ij)·1,a(ij)·2)) of the same type as β(35)A1={([01010101],[00101000]),hhh([01100010],[00000100]),hhh([10111010],[11110000]),hhh([11111010],[01011110]),hhh([11111000],[10011110]),hhh([11000111],[00010100]),hhh([01011011],[11101011]),hhh([00010011],[10101111])},A2={([01011101],[00111110]),hhh([00110010],[00001000]),hhh([01001010],[11100011]),hhh([11001100],[00001011]),hhh([11101001],[10011110]),hhh([10001011],[10110000]),hhh([00111011],[11011010]),hhh([01110101],[01011101]),hhh([00110001],[01111100]),hhh([00101110],[00100110]),hhh([11011111],[11001011]),hhh([01000011],[11000110]),hhh([01110111],[10010011]),hhh([10100100],[10100001]),hhh([11100000],[11001110]),hhh([00000001],[00101100]),hhh([11101101],[00100010]),hhh([11000000],[00000100]),hhh([01101111],[10000001]),hhh([00100000],[11000000]),hhh([11011010],[00011010]),hhh([01001010],[01011100]),hhh([11110111],[00101010]),hhh([10010111],[11100101]),hhh([01001110],[10111011]),hhh([11111010],[01001100]),hhh([11110100],[10011100]),hhh([00000011],[10101110]),hhh([00001100],[10101101]),hhh([11111001],[00101000]),hhh([00001101],[01000010]),hhh([01011101],[01101011])}.(ii) Selectt0,t1,t2∈G∖Z:
(36)t0=([11110100],[11111001]),t1=([00100010],[01001111]),t2=([11101011],[10110000]).(iii) Construct a homomorphismf: G→Z: f(a,b)=(0,a).(iv) Computeγ=(hi,j), hi,j=ti-1-1·f(ai,j)·bi,j·ti=[V1,V2], and i=0,1,2:
(37)V1={([11010110],[10101111]),hhh([11010110],[00010000]),hhh([11010110],[11010000]),hhh([11010110],[11011000]),hhh([11010110],[11100010]),hhh([11010110],[11010101]),hhh([11010110],[10010001]),hhh([11010110],[11010001])},(38)V2={([11001001],[11011111]),hhh([11001001],[10010001]),hhh([11001001],[01001010]),hhh([11001001],[01100101]),hhh([11001001],[11010111]),hhh([11001001],[10101100]),hhh([11001001],[11001111]),hhh([11001001],[01011000]),hhh([11001001],[11110011]),hhh([11001001],[11001101]),hhh([11001001],[10011111]),hhh([11001001],[10101010]),hhh([11001001],[00001001]),hhh([11001001],[11000011]),hhh([11001001],[01010100]),hhh([11001001],[01101100]),hhh([11001001],[11101111]),hhh([11001001],[11100011]),hhh([11001001],[11101111]),hhh([11001001],[00001001]),hhh([11001001],[01100100]),hhh([11001001],[11101101]),hhh([11001001],[10000011]),hhh([11001001],[00111010]),hhh([11001001],[00001100]),hhh([11001001],[10011001]),hhh([11001001],[00110100]),hhh([11001001],[01101010]),hhh([11001001],[11110010]),hhh([11001001],[00011110]),hhh([11001001],[00111001]),hhh([11001001],[10110000])}.Signature(i) Choose a messageM=([10011101], [11010101]).(ii) Samplez=([00000000], [10011010]) (∈Z) and compute r=t0-1·z·t2(39)c2=r=([00011111],[00011011]),c1=H(M,r)c1=([00010101],[01100100]).(iii) Signatureσ=(S1,S2):
(40)S1=71(∈Zq),S2=([00111011],[01010110]).Verification(i) Compute(41)Y1=α′(S1)·S2=([00010101],[01100100]).(ii) Compute(42)γ′(S1)=([00011111],[00100000]),f(S2)=([00000000],[00111011]),Y2=γ′(S1)·f(S2)=([00011111],[00011011]).SinceY1-c1=[00000000] and Y2-c2=[00000000], so we can get that H(M,γ′(S1)·f(S2))=α′(S1)·S2.



---

*Source: 630421-2014-05-20.xml*