A Digital Signature Scheme Based on MST3 Cryptosystems

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 as PGM and public key cryptosystems like MS[subscript]T1[/subscript] , MS[subscript]T2[/subscript] , and MS[subscript]T3[/subscript] . Recently, Svaba et. al proposed a revised MS[subscript]T3[/subscript] 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 MS[subscript]T3[/subscript] cryptosystems.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Wang Xing-yuan

Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received 5 December 2013; Revised 13 March 2014; Accepted 14 March 2014; 20 May 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 MS_T1 and MS_T2 . In 2009, Lempken et al. [18] designed a new public key cryptosystem MS_T3 on the basis of random covers and logarithmic signatures for nonabelian finite groups. Meanwhile, there are some interesting papers studying attacks on MS_T1 , MS_T2 , and MS_T3 [28-33]. In 2010, Svaba and van Trung [34] constructed an eMS_T3 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 on MS_T3 cryptosystems.

The rest of contents are organized as follows. Necessary preliminaries are given in Section 2. 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

Let G be a finite abstract group and let X=[_x1 ,_x2 ,...,_xr ] and Y=[_y1 ,_y2 ,...,_ys ] be two elements in ^G[Z] . Then [figure omitted; refer to PDF] If X=[_x1 ,...,_xr ]∈^G[Z] , X¯ denotes the element ^∑i=1r_xi 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 [figure omitted; refer to PDF]

Let S be a subset of G . Then α is

(i) a cover for G (or S ) if _ag >0 for all g∈G (g∈S ),

(ii) a logarithmic signature for G (or S ) if _ag =1 for every g∈G (g∈S ).

The sequences _Ai are called the blocks ; the vector (_r1 ,...,_rs ) with _ri =|_Ai | is the type of α and the length of α is defined to be l(α)=^∑i=1s_ri .

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] [figure omitted; refer to PDF] for _ai ∈_Ai . α is called tame (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 [figure omitted; refer to PDF]

Then the surjective (bijection) mapping ^{α[variant prime]} :_Zm [arrow right]G induced by α is [figure omitted; refer to PDF] where (_j1 ,_j2 ,...,_js )=^τ-1 (x) .

2.2. MST₃ Cryptosystems and Suzuki 2-Groups

In [18], Lempken et al. utilized logarithmic signatures and random covers to construct a generic MS_T3 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 eMS_T3 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 of MS_T3 cryptosystems is a Suzuki 2-group of order ^q2 with q=^2m (m...5;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 [figure omitted; refer to PDF] where [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF] and the computation of the product just requires a single multiplication and four additions in _Fq .

Furthermore, the inverse of an element in group G is [figure omitted; refer to PDF] 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 New MST₃ Encryption Scheme

Through comparison and analysis, we find that it is rather difficult to devise signature schemes based on the two MS_T3 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 Generation

: Input : 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) Choose _t0 ,_t1 ,...,_ts ∈G\Z .

: (4) Construct a homomorphism f:G[arrow right]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 random R∈_Z|Z| .

: (2) Compute [figure omitted; refer to PDF]

: (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) Compute R=^{β[variant prime]-1} (_y2^ts-1 f(_y1^)-1_t0 ) .

: (2) Compute m=^{α[variant prime]} (R^)-1 ·_y1 .

: (3) Output m .

Correctness

: For m∈Z and R∈_Z|Z| , we have [figure omitted; refer to PDF]

: then using ^{β[variant prime]-1} we can recover the random number R by [figure omitted; refer to PDF]

: Consequently, using _y1 we can recover message m by [figure omitted; refer to PDF]

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 [figure omitted; refer to PDF] where R∈_Z|Z| , _y1 =^{α[variant prime]} (R)·m , _y2 =^{γ[variant prime]} (R) , and f(_y1^)-1 ∈Z .

The adversary mainly attempts to compute enough values ^{β[variant prime]} (_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 ^{β[variant prime]} (_Ri ) , where n=1-s+^∑k=1s ..._rk . Let {_R1 ,_R2 ,...,_Rn } be a collection of random numbers chosen by the adversary. Then [figure omitted; refer to PDF] where _yi1 =^{α[variant prime]} (_Ri )·m , _yi2 =^{γ[variant prime]} (_Ri ) , and f(_yi1^)-1 ∈Z . Note that in the equation above, f(_yi1^)-1 and _yi2 are known and ^{β[variant prime]} (_Ri )∈Z ; then we have [figure omitted; refer to PDF] Since _ts ∈G\Z , there are ^q2 -q possibilities for _ts . If _ts is chosen, from _t0 ∈_ts^yi2-1 f(_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 (_t0 z,_ts z) 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...4;i...4;s ) and ^bij* =_bijcij (1...4;i...4;s,1...4;j...4;_ri ) for _zi ,_cij ∈Z . So for the first block of γ , we have [figure omitted; refer to PDF] Let ^bi1* =id ; then _ci1 =_bi1 ; we have [figure omitted; refer to PDF] We can get that _cij =_ci1 =_bi1 for all i=1,...,s . If we denote _cij =_ci , then ^ti* =_tiz0^∏k=1i ..._ck . Consider [figure omitted; refer to PDF] Let ^{β[variant prime]} (R)=_b1x1b2x2 ..._bsxs , ^β* :=(^bij* ) , and ^bij* =_bijci for _ci ∈Z ; then [figure omitted; refer to PDF] 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 _t0 Z , 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 =^{α[variant prime]} (R)·x , we can get that x=^{α[variant prime]} (R^)-1 ·_y1 . Hence, if the adversary wants to recover message x , he either directly seeks the random number R or recovers R from ^{γ[variant prime]} (R) . However, since q is large enough and ^{γ[variant prime]} 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* =^{α[variant prime]} (R)·_mδ , ^y2* =^{γ[variant prime]} (R) , δ=0 or 1, _m0 , and _m1 are randomly selected by the adversary. Then we can analyse the following two cases: [figure omitted; refer to PDF] Since R and ^{R[variant prime]} are randomly selected, and they admit the same distribution, thus, R and ^{R[variant prime]} are statistically indistinguishable for the adversary. It can be denoted by R[approximate]s^{R[variant prime]} . Meanwhile, since ^{α[variant prime]} and ^{β[variant prime]} are both one-way maps, so we can get that ^{α[variant prime]} (R)[approximate]s^{α[variant prime]} (^{R[variant prime]} ) and ^{γ[variant prime]} (R)[approximate]s^{γ[variant prime]} (^{R[variant prime]} ) . Besides, since _m0 [approximate]s_m1 , so ^{α[variant prime]} (R)·_m0 [approximate]s^{α[variant prime]} (^{R[variant prime]} )·_m1 . Consequently, we can get that (_y1 ,_y2 )[approximate]s(^{y1[variant prime]} ,^{y2[variant prime]} ) .

4. A Digital Signature Scheme Based on the New MST₃ 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) Choose _t0 ,_t1 ,...,_ts ∈G\Z .

: (4) Construct a homomorphisms f:G[arrow right]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 function H:G×G[arrow right]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 select z∈Z and compute a random element r=^t0-1 z_ts ∈G . Let _c2 =r , _c1 =H(m,r) .

: (2) Compute _S1 =^{β[variant prime]-1} (f(_c1^)-1 ·_t0 ·_c2 ·^ts-1 ) and _S2 =^{α[variant prime]} (_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) Compute A=^{α[variant prime]} (_S1 )·_S2 and B=H(m,^{γ[variant prime]} (_S1 )·f(_S2 )) .

: (2) If A=B , output 1; otherwise output 0.

Correctness. For a given message m∈G , [figure omitted; refer to PDF]

Meanwhile, _S1 =^{β[variant prime]-1} (f(_c1^)-1 ·_t0 ·_c2 ·^ts-1 ) and _c1 =^{α[variant prime]} (_S1 )·_S2 .

Hence, [figure omitted; refer to PDF] Consequently, we have [figure omitted; refer to PDF]

4.2. Security Analysis

4.2.1. Attack on Private Key

(a) Compared with the encryption scheme in Section 3, 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 [figure omitted; refer to PDF] where _y1 =^{α[variant prime]} (R)·x , _y2 =^{γ[variant prime]} (R) , and f(_y1^)-1 ∈Z . Let {_R1 ,_R2 ,...,_Rn } be a collection of random numbers chosen by the adversary. Then we have [figure omitted; refer to PDF] where _yi1 =^{α[variant prime]} (_Ri )·x , _yi2 =^{γ[variant prime]} (_Ri ) , and f(_yi1^)-1 ∈Z . Then [figure omitted; refer to PDF] 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| , [figure omitted; refer to PDF] Let ^{β[variant prime]} (R)=_b1x1b2x2 ..._bsxs and ^β* :=(^bij* ) , ^bij* =_bijci ; then [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF]

Case 1.

Eve chooses a random number ^S1* ∈_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 elements ^m* ∈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* ,^{γ[variant prime]} (^S1* )·f(^S2* )) is equivalent to solving the equations ^c1* =^{γ[variant prime]} (^S1* ) and y=^{α[variant prime]} (^S1* ) . Since ^{α[variant prime]} and ^{γ[variant prime]} 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* =^{α[variant prime]} (^S1*)-1 ·H(^m* ,^{γ[variant prime]} (^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 compare eMS_T3 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.).

Table 1 shows the number of operations required for eMS_T3 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 ^{β[variant prime]} (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

¹ Compared with eMS_T3 scheme, our scheme reduces a step of multiplication with the element of the center Z in the stage of encryption. Thus, the number of (_F^2m ADD) reduces once.

² In the stage of decryption, our scheme reduces a step of inverse operation, a step of multiplication operation, and a _F^2m EXP(θ) operation, so the number of (_F^2m ADD) reduces five times and (_F^2m MULT) reduces twice.

Table 2 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	--

³ T = ^{∑ i = 1 s} ... _{r i} , _ri =^∏j=1_ui ...^{r_ij *} ·_wi for 1...4;i...4;s and ^∑i=1s ..._ui =v , where _wi ={0if _ui =11if _ui >1 .

⁴ For a∈_Fq , θ:a[arrow right]^a2 is a Frobenius automorphism. Hence, θ can be reduced to a multiplication.

⁵ v represents the number of blocks before fusion.

For example, when s=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.

Table 3 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

⁶ 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, MS_T3 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 element m∈_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-group G=A(m,θ) with m=8 , q=²⁸ 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 function H as the hash function in our scheme. That is, H : G×G[arrow right]G is given by [figure omitted; refer to PDF] 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: [figure omitted; refer to PDF]

(2) Fuse blocks ^B1* , ^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 ) [figure omitted; refer to PDF]

(i) A random cover α=[_A1 ,_A2 ]=(_aij )=(S(_a(ij)·1 ,_a(ij)·2 )) of the same type as β [figure omitted; refer to PDF]

(ii) Select _t0 ,_t1 ,_t2 ∈G\Z : [figure omitted; refer to PDF]

(iii) Construct a homomorphism f : G[arrow right]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 : [figure omitted; refer to PDF]

Signature

(i) Choose a message M=([10011101] , [11010101]) .

(ii) Sample z=([00000000] , [10011010]) (∈Z ) and compute r=^t0-1 ·z·_t2 [figure omitted; refer to PDF]

(iii) Signature σ=(_S1 ,_S2 ) : [figure omitted; refer to PDF]

Verification

(i) Compute [figure omitted; refer to PDF]

(ii) Compute [figure omitted; refer to PDF]

Since _Y1 -_c1 =[00000000] and _Y2 -_c2 =[00000000] , so we can get that H(M,^{γ[variant prime]} (_S1 )·f(_S2 ))=^{α[variant prime]} (_S1 )·_S2 .

Acknowledgments

This work is partially supported by the National Natural Science Foundation of China (NSFC) (nos. 61103198, 61121061, 61370194) and the NSFC A3 Foresight Program (no. 61161140320).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] C. H. Bennett, G. Brassard, "Quantum cryptography: public key distribution and coin tossingin," in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pp. 175-179, Bangalore, India, 1984.

[2] C. H. Bennett, "Quantum cryptography using any two nonorthogonal states," Physical Review Letters , vol. 68, no. 21, pp. 3121-3124, 1992.

[3] C. H. Bennett, G. Brassard, N. D. Mermin, "Quantum cryptography without Bell's theorem," Physical Review Letters , vol. 68, no. 5, pp. 557-559, 1992.

[4] N. Gisin, G. Ribordy, W. Tittel, H. Zbinden, "Quantum cryptography," Reviews of Modern Physics , vol. 74, no. 1, pp. 146-195, 2002.

[5] R. Matthews, "On the derivation of a "chaotic" encryption algorithm," Cryptologia , vol. 13, no. 1, pp. 29-42, 1989.

[6] M. S. Baptista, "Cryptography with chaos," Physics Letters A , vol. 240, no. 1-2, pp. 50-54, 1998.

[7] G. Alvarez, G. Pastor, F. Montoya, M. Romera, "Chaotic cryptosystems," in Proceedings of the IEEE International Carnahan Conference on Security Technology, pp. 332-338, 1999.

[8] X.-Y. Wang, Q. Yu, "Block encryption algorithm based on dynamic sequences of multiple chaotic systems," Communications in Nonlinear Science and Numerical Simulation , vol. 14, no. 2, pp. 574-581, 2009.

[9] X. Wang, J. Zhao, "An improved key agreement protocol based on chaos," Communications in Nonlinear Science and Numerical Simulation , vol. 15, no. 12, pp. 4052-4057, 2010.

[10] Y. Niu, X. Wang, "An anonymous key agreement protocol based on chaotic maps," Communications in Nonlinear Science and Numerical Simulation , vol. 16, no. 4, pp. 1986-1992, 2011.

[11] L. Hongjun, W. Xingyuan, K. Abdurahman, "Image encryption using DNA complementary rule and chaotic maps," Applied Soft Computing , vol. 12, no. 5, pp. 1457-1466, 2012.

[12] X. Wang, D. Luan, "A novel image encryption algorithm using chaos and reversible cellular automata," Communications in Nonlinear Science and Numerical Simulation , vol. 18, no. 11, pp. 3075-3085, 2013.

[13] W. Xingyuan, L. Dapeng, "A secure key agreement protocol based on chaotic maps," Chinese Physics B , vol. 22, no. 11, 2013.

[14] Y.-Q. Zhang, X.-Y. Wang, "Spatiotemporal chaos in mixed linear--nonlinear coupled logistic map lattice," Physica A: Statistical Mechanics and Its Applications , vol. 402, pp. 104-118, 2014.

[15] L. M. Adleman, "Molecular computation of solutions to combinatorial problems," Science , vol. 266, no. 5187, pp. 1021-1024, 1994.

[16] D. Boneh, C. Dunworth, R. J. Lipton, J. Sgall, "On the computational power of DNA," Discrete Applied Mathematics , vol. 71, no. 1-3, pp. 79-94, 1996.

[17] G. Cui, L. Qin, Y. Wang, X. Zhang, "An encryption scheme using DNA technology," in Proceedings of the 3rd International Conference on Bio-Inspired Computing: Theories and Applications (BICTA '08), pp. 37-41, October 2008.

[18] W. Lempken, T. van Trung, S. S. Magliveras, W. Wei, "A public key cryptosystem based on non-abelian finite groups," Journal of Cryptology , vol. 22, no. 1, pp. 62-74, 2009.

[19] N. R. Wagner, M. R. Magyarik, "A public-key cryptosystem based on the word problem," Advances in Cryptology , vol. 196, of Lecture Notes in Computer Science, pp. 19-36, Springer, Berlin, Germany, 1985.

[20] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, C. Park, "New public-key cryptosystem using braid groups," Advances in cryptology--CRYPTO 2000 , vol. 1880, of Lecture Notes in Computer Science, pp. 166-183, Springer, Berlin, Germany, 2000.

[21] B. Eick, D. Kahrobaei, "Polycyclic groups: a new platform for cryptology?," http://arxiv.org/abs/math/0411077

[22] V. Shpilrain, A. Ushakov, "Thompsons group and public key cryptography," Applied Cryptography and Network Security , vol. 3531, of Lecture Notes in Computer Science, pp. 151-164, 2005.

[23] D. Kahrobaei, C. Koupparis, V. Shpilrain, "Public key exchange using matrices over group rings," Groups, Complexity, and Cryptology , vol. 5, no. 1, pp. 97-115, 2013.

[24] S. S. Magliveras, "A cryptosystem from logarithmic signatures of finite groups," in Proceedings of the 29th Midwest Symposium on Circuits and Systems, pp. 972-975, Elsevier Publishing, Amsterdam, The Netherlands, 1986.

[25] S. S. Magliveras, N. D. Memon, "Algebraic properties of cryptosystem PGM," Journal of Cryptology , vol. 5, no. 3, pp. 167-183, 1992.

[26] A. Caranti, F. Dalla Volta, "The round functions of cryptosystem PGM generate the symmetric group," Designs, Codes and Cryptography , vol. 38, no. 1, pp. 147-155, 2006.

[27] S. S. Magliveras, D. R. Stinson, T. van Trung, "New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups," Journal of Cryptology , vol. 15, no. 4, pp. 285-297, 2002.

[28] M. I. González Vasco, R. Steinwandt, "Obstacles in two public key cryptosystems based on group factorizations," Tatra Mountains Mathematical Publications , vol. 25, pp. 23-37, 2002.

[29] J.-M. Bohli, R. Steinwandt, M. I. González Vasco, C. Martínez, "Weak keys in MS_T1 ," Designs, Codes and Cryptography , vol. 37, no. 3, pp. 509-524, 2005.

[30] M. I. González Vasco, C. Martínez, R. Steinwandt, "Towards a uniform description of several group based cryptographic primitives," Designs, Codes and Cryptography , vol. 33, no. 3, pp. 215-226, 2004.

[31] S. S. Magliveras, P. Svaba, T. van Trung, P. Zajac, "On the security of a realization of cryptosystem MS_T3 ," Tatra Mountains Mathematical Publications , vol. 41, pp. 65-78, 2008.

[32] S. R. Blackburn, C. Cid, C. Mullan, "Cryptanalysis of the MS_T3 public key cryptosystem," Journal of Mathematical Cryptology , vol. 3, no. 4, pp. 321-338, 2009.

[33] M. I. G. Vasco, A. L. P. del Pozo, P. T. Duarte, "A note on the security of MS_T3 ," Designs, Codes and Cryptography , vol. 55, no. 2-3, pp. 189-200, 2010.

[34] P. Svaba, T. van Trung, "Public key cryptosystem MS_T3 cryptanalysis and realization," Journal of Mathematical Cryptology , vol. 4, no. 3, pp. 271-315, 2010.

[35] W. Lempken, T. van Trung, "On minimal logarithmic signatures of finite groups," Experimental Mathematics , vol. 14, no. 3, pp. 257-269, 2005.

[36] P. Marquardt, P. Svaba, T. van Trung, "Pseudorandom number generators based on random covers for finite groups," Designs, Codes and Cryptography , vol. 64, no. 1-2, pp. 209-220, 2012.