A Journal of Software Engineering and Applications, 2013, 6, 1620 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. Email: sunxinshifeng@163.com, moonho@chonbuk.ac.kr 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 Epayment 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 nondisavowal 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 nocloning 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) [710] and quantum secure direct communication (QSDC) [1014]. 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 [1518], whose algorithm is a symmetrical quan tum key cryptosystem with GreenbergerHorneZeilinger (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 oneway 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 t1 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 Copyright © 2013 SciRes. JSEA
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 a2 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 bii 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 3qubit system, which can be defined as 10(1)1 2 z xyz , 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 yz U. The transformations can be summarized as () , uvwxyz uvwxyz pU p (5) where ,,,,, 0,1,xyzuvw binary strings yz and correspond to the decimal numbers, and uvw 000 UIII , 001 UIIX X , , 010 UIX I 011 UIX ,100 UXII I , , 101 UXIX 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,,) n with Trent, in which deno tes the own pr ivate k e y of Bob and is relatively prime. Step 4. The participants of group G receives X collec tively. As discussed in CRT's function in the paper, Bob Copyright © 2013 SciRes. JSEA
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, , KK t is theBob ’s private key, and 1,2,,t063,SS S the generated classical remainder. is and S can be represented by 6bit 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 . The algorithm can be showed as follows, 1mod t TDS D (10) where 12 , t DKK K,DDK modTD , for all . If 1K t1, 2,, X , the signa ture has obviously been forged and Trent may reject this signature immediately. If X , Trent goes on for further verification. Step 2. Trent transforms to the binary sequence . 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 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 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 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 with . 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 > ; if 1 O= 0 and 2= 1 then O < ; at last, if 1= 0 and 2= 0 then O O = . 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). Copyright © 2013 SciRes. JSEA
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 , but 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 , 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 (NCET110510), 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 322010000200140 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. 257265. doi:10.1007/3540464166_22 [3] J. Camenisch and M. Stadler, “Efficient Group Signature Schemes for Large Groups,” Berlin, Springer 1296, 1997, pp. 410424. [4] E. Bresson and J. Stem, “Efficient Revocation in Group Signature,” Proceeding of PKC01 LNCS 1992, Berlin, Springer, 2001, pp. 190206. [5] G. Ateniese, J. Camenisch and M. Joye, “A Practical and Provably Secure Coalitionresistant Group Signature Scheme,”Advances in CryptologyCrypto2000 LNCS1880, 2000, pp. 255270. [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. 175179. [8] A. K. Ekert, “Quantum Cryptography Based on Bells Theorem,” Physical Review Letters, Vol. 67, 1991, pp. 661663. 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. 48364842. [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. 648651. doi:10.1103/PhysRevLett.83.648 [12] M. Hillery, V. Buzek and A. Berthiaume, “Quantum Secret Sharing,”Physics Review A, Vol. 59, 1999, pp. 18291834. 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. 162168. doi:10.1103/PhysRevA.59.162 [14] G. L. Long and X. S. Liu, “Theoretically Efficient Highcapacity Quantumkeydistribution Scheme,” Physi cal Review A, Vol. 65, 2002, pp 13. [15] G. H. Zeng and C. H. Keitel, “Arbitrated Quantum Sig nature Scheme,” Physical Review A, Vol. 65, 2002, pp. 16. [16] M. Curty and N. Lutkenhaus, Comment on “Arbitrated Quantumsignature Scheme,” Physical Review A, 2008, pp. 14. [17] G. H. Zeng, Reply to “Comment on ‘Arbitrated Quan tumsignature Scheme,”Physical Review A, Vol. 78, 2008, pp. 15. [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. 553573. doi:10.1142/S0219749907003031 Copyright © 2013 SciRes. JSEA
Quantum Group Signature Scheme Based on Chinese Remainder Theorem Copyright © 2013 SciRes. JSEA 20 [19] Q. Li, W. H. Chan and D. Y. Long, “Arbitrated Quantum Signature Scheme Using Bell States,” Physics Review A. 79, 2009, pp. 14. [20] D. Gottesman and I. Chuang, “Quantum Digital Signa tures,” 2001, pp. 18. [21] H. Lee, C. H. Hong and H. Kim, “Arbitrated Quantum Signature Scheme with Message Recovery,” Physical Letters A, Vol. 32, 2004, pp. 295300. 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. 171180. [23] C. Ding, D. Pei and A. Salomaa, “Chinese Remainder Theorem: Applications in Computing, Coding, Cryptog raphy,” World Scientific Publishing Co., Inc., 1996, pp. 18. 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 Entangledstate Message with Quantum Fourier Trans form,” Quantum Information Processing, Vol. 10, No. 5, 2011, pp. 653670. doi:10.1007/s1112801002257 [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.1726. [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. 666669. [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. 31983201. 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. 31443148. 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. 31443148. doi:10.1016/j.optcom.2011.03.083 [31] M. M. Wang, X. B. Chen, X. X. Niu and Y. X. Yang, “Reexamining the Security of Blind Quantum Signature Protocols,” Physica Scripta, Vol. 86, No. 5, 2012. doi:10.1088/00318949/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/16741056/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
