A Journal of Software Engineering and Applications, 2013, 6, 16-20
doi:10.4236/jsea.2013.65B004 Published Online May 2013 (http://www.scirp.org/journal/jsea)
Quantum Group Signature Scheme Based on Chinese
Remainder Theorem
Xin Sun1, Ying Guo1, Jin jing Shi1, Wei Zhang1, Qin Xiao1, Moon Ho Lee2
1School of Information Science & Engineering, Central South University, Changsha, China; 2Institute of Information and Communi-
cation, Chonbuk National University, Chonju, Korea.
Received 2013
ABSTRACT
A novel quantum group signature scheme is proposed based on Chinese Remainder Theorem (CRT), in order to im-
prove the security of quantum signature. The generation and verification of the signature can be successfully conducted
only if all the particip ants cooperate with each other and with the message owner's and the arbitrator's h elp. The quan-
tum parallel algorithm is applied to efficiently compare the restored quantum message to the original quan tum message.
All the operations in signing and verifying phase can be executed in quantum circuits. It has a wide application to
E-payment system, Online contract, O nl i ne notarization and etc.
Keywords: Quantum Signature; Group Signature; Chinese Remainder Theorem
1. Introduction
Digital signature is one of the most important part of
modern cryptography, which serves as a basic module to
design cryptography protocols [1]. Digital signature is
usually employed to gu arantee the authenticity, integrity,
and non-disavowal of transmitting messages. Group
signature scheme was introduced in 1991 by Chaum and
Heyst [2] firstly. In 1997, Camenisch and Stadler [3] im-
proved Chaums scheme and developed the more efficient
scheme CS97 for larger groups. CS97 was fu r ther enh anced
by Bresson and Sterm [4] to be revocable for group
numbers. Moreover, Ateniese and Came ni sch [5] proposed
a safe and efficient group signature scheme in 2000.
Those are mostly based on the complexity of the system
employed and they become increasingly vulnerable with
more powerful computation. This difficulty can be
overcome by quantum cryptography [6]. The biggest
difference between quantum cryptography and classical
cryptography is that quantum cryptography is the
combination of quantum mechanics and cryptography,
where the security is ensured by physical principles such
as the Heisenberg uncertainty principle and the quantum
no-cloning theorem. Now quantum cryptography has
attracted a great deal of attention because it can stand
against quantum attack, and has put forward many
advances in quantum cryptography, including quantum
secret sharing, quantum key distribution (QKD) [7-10]
and quantum secure direct communication (QSDC)
[10-14].
Taking advantage of the quantum properties of physical,
many quantum signature schemes have been introduced.
Zeng et al. introduced a quantum signature scheme based
on the classical signature theory and quantum cryptog-
raphy [15-18], whose algorithm is a symmetrical quan-
tum key cryptosystem with Greenberger-Horne-Zeilinger
(GHZ) triplet states. Li et al. proposed an arbitrated
quantum signature scheme using Bell states [19]. Got-
tesman and Chuang propo sed a quantum digital sign ature
scheme based on quantum one-way function [20], and
Lee also presented two quantum signature schemes with
message recovery [21]. Unconditional security of the
above quantum signature schemes have been proved, but
they are not designed for 'group'. Therefore, a group sig-
nature can be devised base d o n quantum crypto graphy.
In this paper, we propose a group signature scheme
based on Chinese Remainder Theorem (CRT). In our
scheme, secret key is unforgeable, generated by the
owner, and can be shared with the arbitrator based on
QSCD protocol. The signing group contains two partici-
pants, and they collaborate to sign on the message by
applying CRT with arbitrator and restore the message by
performing the inverse CRT with arbitrator's assistance
for the verification of signature. However, any t-1 or
fewer participants can neither sign on the message nor
restore the signed message. The message owner cooper-
ate to verify the message by applying a quantum com-
parison circuit for comparing the restored quantum mes-
sage to the original quantum message and arbitrator
could inform message owner and group participants of

Quantum Group Signature Scheme Based on Chinese Remainder Theorem 17
the verified result. Furthermore, all the quantum circuits
and operation gates are packaged in black boxes [22] to
enhance the security.
The rest of this paper is organized as follows. Sect. 2
introduces the basic knowledge about our scheme. Sect.
3 proposes a quantum group signature scheme which
includes an initial phase, a signing phase, and a verifica-
tion phase. Security analysis is made in Sect. 4, and a
brief conclusions are drawn in Sect. 5.
2. Preliminaries
The original Chinese Remainder Theorem was proposed
by SunZi and later republished in 1247 by Qin[23]. The
CRT is ofen applied in computer science, such as RSA
algorithm calculation, classical secret sharing and ect,
and several versions of the Chinese Remainder Theorem
have been proposed. The general CRT can be described
as follows.
Lemma 1. Let n > 2, , ,,n be relatively prime
in pairs, and . The system of equations
1
b
,
n
a2
b b
12
,,aa 
11
mod
mod
nn
Ya b
Ya b






 (1)
has solutions in Z if , for all

gcd ,1
ij
bb 1in

,
. The solution can be obtained as
1jn
1
mod
n
iii
i
YTBa

B (2)
where ,
12 n
Bbb bii BBb

, ,
for all , and Y < B. mod 1
ii i
TB b
1in
According to this theorem, Alice can obtain the group
signature. Suppose Alice sends the message number x to
the Bob(group pa rticipants) , Bob encrypts x by th e secret
key i based on Equation (1), and the result i is the
element of the sequence of the signature. In this way,
Alice can obtain his group signature.
b a
3. Scheme Descriptions
The text above shows the basic signing algorithm of this
scheme. Next the details of the scheme can be illustrated
as follows, which contains three participants Alice (the
message owner), G (the signing group), and Trent (the
arbitrator). The three phases of our quantum signature
scheme is introduced as follows.
3.1. Initial Phase
Step 1. Set up a signing group G, whose participants are
(1,2,,Bob n

Step 2. In this paper, we discuss the binary 3-qubit
system, which can be defined as
10(1)1
2
z
xyz ,
x
yx  y




 (3)
where


,, 0,1xyz.
3.2. Quantum Group Signing Phase
In this quantum group signature scheme, Alice prepares a
quantum message. The group G generates a signature
with assistance of Trent who doesn't understand the de-
tails about the signing algorithm. The participants of
group G don't communicate with other.
Step 1. Alice's quantum message sequence Pcon-
tains m qubits, i.e.


01 1
,,, ,,
m
Ppp pp
 
 , (4)
where p

forms as Eq. (3).
Step 2. Alice sends the sequence P to Trent with
superdense coding. Alice encodes p

as p


with
the unitary operations
x
yz
U. The transformations can be
summarized as
() , uvwxyz uvwxyz
pU p


 (5)
where


,,,,, 0,1,xyzuvw binary strings
x
yz and
correspond to the decimal numbers, and uvw
000
UIII

 , 001 UIIX


X
, ,
010
UIX I
011
UIX

,100 UXII


I
, ,
101
UXIX
110
UXX

, 111 UXXX

.
Step 3. Trent receives the


01 1
,,,,m Ppp pp

 

 .
According to Eq.(3) , the quantum message P

can be
rewritten as
1
0
10(1)1
2
mz
Pxy xy

 





,





 (6)
where


,, 0,1xyz

. The states of P refer to a
binary sequence


000111111
,, ,
mmm
yzxyz xyz

Rx, so
the corresponding classical message X can be acquired
by Trent.
For example, if Trent receives a quantum sequence
like


000,001,110P, it can be represented as
1000111001110010101 ,
22
P





  
corresponding a binary sequence

000111101 ,R
and Trent can derive the decimal classical message X =
28 + 26 + 25 + 24 = 368. Then Trent sends X to the
group G.
)

. According to QSDC protocol, G
can share the secret key (1,2,,)
K
n


 with Trent,
in which
K

deno tes the own pr ivate k e y of Bob

and
K

is relatively prime. Step 4. The participants of group G receives X collec-
tively. As discussed in CRT's function in the paper, Bob

Quantum Group Signature Scheme Based on Chinese Remainder Theorem
18

12
,,,
t
Bob BobBob

sign on the quantum message
P by transforming X as following algorithm
modSX K

 (7)
where

164,1,2, ,
K
KK t  

is theBob

’s
private key, and

1,2,,t063,SS S  

the generated classical remainder. is
K

and S

can be
represented by 6-bit binary sequence and according to
Equation (3) the state can be shown as


21
0
21
0
10(1)1
2
10(1)1
2
tz
S
tz
K
xy xy
xy xy


 

 



















(8)
Signature S can be donated as follows
12
,,,, S
t
SSSS








 (9)
where S

is the classical remainder, S

is the cor-
responding state of S

.
Step 5. Bob can send the signature S to Trent.
3.3. Verification Phase
A verification algorithm is developed here based on the
CRT such that Alice is able to verify Bob's signature
S. The verification process requires the assistance of
Trent.
Step 1.When Trent receives Bob's signatures S, he
restores message as Equation (2) to
X
. The algorithm
can be showed as follows,
1mod
t
X
TDS D




 (10)
where 12 ,
t
DKK K,DDK


 modTD


, for all . If 1K



t1, 2,,  
X
X
, the signa-
ture has obviously been forged and Trent may reject this
signature immediately. If
X
X
, Trent goes on for
further verification.
Step 2. Trent transforms
X

to the binary sequence
X

. The process can be described as follows,
-1 -1`
**
--1
*0mod ,0
*0, 0
m
XXd
z
z
Xd
d
X




















(11)
where d = 2. The binary sequence can be represented as


011
,,,
m
XXXX




, which corresponds to the states
of P
. In this way, Trent gets the quantum message
P

.
Step 3. Trent performs the corresponding reverse
transformations 1
x
yz
U

() on each state of

,, 0,1xyz
P

. He can obtain the the states of P . According to
Equation (3), P
can be described as
1
0
10(1)1
2
mz
P
x
yx

 




y






 

(12)
where


,, 0,1xyz


. At last the restored message is
acquered. Then Trent input it into the quantum verifica-
tion circuit which is shown in Figure 1 [24] directly, and
sends the signature S to Alice at the same time.
Step 4. The message owner Alice also input the origin-
nal message
P

into the quantum verification circuit
at the same time. Then Alice starts to wait for the verify-
cation from Trent.
Step 5. We generalize the qubit string comparator in-
troduced by Ref. [25] with quantum parallel algorithm
[22] which makes the quantum computation on quantum
message more effectively to compare
P

 with
P

.
The quantum circuit which is presented in Figure 1. In a
measurement of the outputs (and2), if 1= 1 and
= 0 then 1
O OO
2
O
P

>
P

; if 1
O= 0 and 2= 1 then O
P

<
P

; at last, if 1= 0 and 2= 0 then O O
P

=
P

. When 1= 0 and 2= 0, the arbitrator Trent
informs Alice and Bob the signature is legal and credible,
otherwise he informs them that signature is invalid.
O O
4. Conclusions
So far we have proposed a group signature scheme based
on CRT. Now let us discuss the security of the group
signature scheme. A secure quantum signature scheme
should satisfy two requirements: one is that the message
should not be forged by the attacker and the other is the
impossibility of disavowal by the message originator and
the signatory.
Figure 1. The quantum circuit for comparing
P

to P

in the black box. Each particle of P

and
P

is input-
ted into this quantum circuit from left, and (2) is a process-
ing unit of (1).

Quantum Group Signature Scheme Based on Chinese Remainder Theorem 19
4.1. Impossibility of Forgery
In this scheme, the arbitrator Trent is trusted, K» cannot
be forged. Anyone attempts to forge Bob's signature
would definitely be detected.
Specifically, assuming that Eve wants to imitate Bob's
signature S sign on X which corresponding the mes-
sage P. As shown by Equation (7), Eve must know
the se- cret keys
K

, but
K

cannot be forged.
The signature is unforgeable even by the message
owner Alice who knows the messages and the correspond-
ing signatures because of the unforgeable secret keys.
4.2. Impossibility of Disavowal by the Signatory
and the Message Originator
According to Equation (7), Bob(signatory) would send
S to Trent. Since S includes the keys
K

, which
is only known by Bob and Trent, Bob cannot disavow his
signa- ture S.
Alice also cannot disavow his recieving. Because the
verifier Bob who really has verified the signature cannot
later deny his involvement in that his verification of the
message needs the help of Trent. If he denies his in-
volvement, Trent can confirm that he tells a lie.
5. Conclusions
In this p aper, we present a gr oup signature scheme based
on Chinese Remainder Theorem in which participants
share their own key with arbitrator while they don't com-
municate with other. Only when all the t participants
cooperate with each other and with the message owner's
and the arbitrator's assistance, the signature can be gen-
erated and verified successfully. The analysis of this
scheme and show that secure signature can be derived.
Moreover, by allowing the arbitrator to keep a record of
all intermediate transmissions and computations, it is
able to arbitrate the dispute between two users.
6. Acknowledgements
This work was supported by the National Natural Sci-
ence Foundation of China (Grant Nos. 61272495), the
Program for New Century Excellent Talents in Univer-
sity of Ministry of Education of Ch ina (NCET-11-0510),
the Hunan Provincial Innovation Foundation For Post-
graduate (Grant Nos. CX2011B087), the Excellent Doc-
toral Dissertation Fund of Central South University (Grant
Nos. 2011ybjz030) and WCU 32-2010-000-20014-0 NRF
(Korea).
REFERENCES
[1] S. William, “Cryptography and Network Security, Princi-
ples and Practice,” 2nd Edition,Prentice Hall, New Jersey,
2003.
[2] D. Chaum and E. V. Heyst, “Group Signatures,” Lecture
Notes in Computer Science, Vol. 547, 1991, pp. 257-265.
doi:10.1007/3-540-46416-6_22
[3] J. Camenisch and M. Stadler, “Efficient Group Signature
Schemes for Large Groups,” Berlin, Springer 1296, 1997,
pp. 410-424.
[4] E. Bresson and J. Stem, “Efficient Revocation in Group
Signature,” Proceeding of PKC01 LNCS 1992, Berlin,
Springer, 2001, pp. 190-206.
[5] G. Ateniese, J. Camenisch and M. Joye, “A Practical and
Provably Secure Coalition-resistant Group Signature
Scheme,”Advances in Cryptology-Crypto2000 LNCS1880,
2000, pp. 255-270.
[6] N. Gisin, G. Ribordy, W. Tittel and H. Zbinden, “Quan-
tum Cryptography,” Reviews of Modern Physics, Vol. 74,
No. 145, 2002. doi:10.1103/RevM5odPhys.74.14
[7] C. H. Bennett and G. Brassard, “Quantum Cryptography:
Public Key Distribution and Coin Tossing,” Proceeding
of IEEE International Conference on Computers Systems,
1984, pp. 175-179.
[8] A. K. Ekert, “Quantum Cryptography Based on Bells
Theorem,” Physical Review Letters, Vol. 67, 1991, pp.
661-663. doi:10.1103/PhysRevLett.67.661
[9] N. R Zhou, L. J Wang, L. H Gong, X. W. Zuo and Y. Liu,
“Quantum Deterministic Key Distribution Protocols
Based on Teleportation and Entanglement Swapping,”
Optics Communication, Vol. 284, 2011, pp. 4836-4842.
[10] C. H. Bennett, “Quantum Cryptography Using any Two
Nonorthogonal States,” Physical Review.
[11] R. Cleve, D.Gottesman and H. K. Lo, “How to Share a
Quantum Secret,” Physical Review Letters, Vol. 83, 1999,
pp. 648-651. doi:10.1103/PhysRevLett.83.648
[12] M. Hillery, V. Buzek and A. Berthiaume, “Quantum
Secret Sharing,”Physics Review A, Vol. 59, 1999, pp.
1829-1834. doi:10.1103/PhysRevA.59.1829
[13] A. Karlsson, M. Koashi and N. Imoto, “Quantum Entan-
glement for Secret Sharing and Secret Splitting,” Physical
Review A, Vol. 59, 1999, pp. 162-168.
doi:10.1103/PhysRevA.59.162
[14] G. L. Long and X. S. Liu, “Theoretically Efficient
High-capacity Quantum-key-distribution Scheme,” Physi-
cal Review A, Vol. 65, 2002, pp 1-3.
[15] G. H. Zeng and C. H. Keitel, “Arbitrated Quantum Sig-
nature Scheme,” Physical Review A, Vol. 65, 2002, pp.
1-6.
[16] M. Curty and N. Lutkenhaus, Comment on “Arbitrated
Quantum-signature Scheme,” Physical Review A, 2008,
pp. 1-4.
[17] G. H. Zeng, Reply to “Comment on ‘Arbitrated Quan-
tum-signature Scheme,”Physical Review A, Vol. 78, 2008,
pp. 1-5.
[18] G. H. Zeng, M. H. Lee, Y. Guo and G. Q. He, “Continu-
ous Variable Quantum Signature Algorithm,” Interna-
tional Journal of Quantum Infermation, Vol. 5, No. 4,
2007, pp. 553-573. doi:10.1142/S0219749907003031

Quantum Group Signature Scheme Based on Chinese Remainder Theorem
20
[19] Q. Li, W. H. Chan and D. Y. Long, “Arbitrated Quantum
Signature Scheme Using Bell States,” Physics Review A.
79, 2009, pp. 1-4.
[20] D. Gottesman and I. Chuang, “Quantum Digital Signa-
tures,” 2001, pp. 1-8.
[21] H. Lee, C. H. Hong and H. Kim, “Arbitrated Quantum
Signature Scheme with Message Recovery,” Physical
Letters A, Vol. 32, 2004, pp. 295-300.
doi:10.1016/j.physleta.2003.12.036
[22] M. Nielsen and I. Chuang, “Quantum Computation and
Quantum Information,” Cambridge University Press,
Cambridge, 2000, pp. 171-180.
[23] C. Ding, D. Pei and A. Salomaa, “Chinese Remainder
Theorem: Applications in Computing, Coding, Cryptog-
raphy,” World Scientific Publishing Co., Inc., 1996, pp.
1-8. doi:10.1142/9789812779380_0001
[24] J. J. Shi, R. H. Shi, Y. Tang and M. H. Lee, “A Multi-
party Quantum Proxy Group Signature Scheme for the
Entangled-state Message with Quantum Fourier Trans-
form,” Quantum Information Processing, Vol. 10, No. 5,
2011, pp. 653-670. doi:10.1007/s11128-010-0225-7
[25] D. S. Oliveira and R. V. Ramos, “Quantum Bit String
Comparator: Circuits and Applications,” Quatum Com-
puters and computing, Vol. 7, No. 1, 2007, pp.17-26.
[26] X. J. Wen, “A Group Signature Scheme Based on Quan-
tum Teleportation,” Physica Scripta, Vol. 81, No. 5,
2001.
[27] X. J. Wen, X. M. Niu, L. P. Ji and Y. Tian, “A Weak
Blind Signature Scheme Based on Quantum Cryptogra-
phy,” Optics Communication, Vol. 282, No. 4, 2009, pp.
666-669.
[28] Y. G. Yang and Q. Y. Wen, “Arbitrated Quantum Signa-
ture of Classical Messages against Collective Amplitude
Damping Noise,” Opticcs Communication, Vol. 283, No.
16, 2010, pp. 3198-3201.
doi:10.1016/j.optcom.2010.04.020
[29] T. Hwang, S. K. Chong, Y. P. Luo and T. X. Wei, “New
Arbitrated Quantum Signature of Classical Messages
Against Collective Amplitude Damping Noise,” Optics
Communication, Vol. 284, 2011, No. 12. pp. 3144-3148.
doi:10.1016/j.optcom.2011.01.025
[30] R. Xu, L. S. Huang, W. Yang and L. B. He, “Quantum
Group Blind Signature Scheme without Entanglement,”
Optics Communication, Vol. 284, 2011, No. 14, pp.
3144-3148. doi:10.1016/j.optcom.2011.03.083
[31] M. M. Wang, X. B. Chen, X. X. Niu and Y. X. Yang,
“Re-examining the Security of Blind Quantum Signature
Protocols,” Physica Scripta, Vol. 86, No. 5, 2012.
doi:10.1088/0031-8949/86/05/055006
[32] T. Y. Wang and Q. Y. Wen, “Fair Quantum Blind Signa-
tures,” Chinese Physics B, Vol. 19, No. 6, 2010.
doi:10.1088/1674-1056/19/6/060307
[33] F. Gao, S. J. Qin, F. Z. Guo and Q. Y. Wen, “Cryptanaly-
sis of the Arbitrated Quantum Signature Protocols,”
Physical Review A, Vol. 84, No. 2, 2011.
doi:10.1103/PhysRevA.84.022344
[34] Q. Li, W. H. Chan and D. Y. Long, “Arbitrated Quantum
Signature Scheme Using Bell States,” Physics Review A,
Vol. 79, No.5, 2009.
doi:10.1103/PhysRevA.79.054307
[35] T. Hwang, Y. P. Luo and S. K. Chong, “Comment on
‘Security Analysis and Improvements of Arbitrated Quan-
tum Signature Schemes’,” Physics Review A, Vol. 85, No.
5, 2012.
doi:10.1103/PhysRevA.85.056301