Chen等人利用環簽章，提出「同時簽章法」的觀念，在不需要公信的第三者以及雙方計算能力相同的假設之下，協助雙方公平地交換簽章。同時簽章法的安全特性，計有正確性、不可偽造性、公平性和模糊性。於2005年時，有別以往利用環簽章設計同時簽章法的方式，Nguyen提出新的設計同時簽章法的設計方法，名為「非對稱式同時簽章法」。基於使用者隱私權的保護，此方法強調滿足匿名性與無關聯性等新的安全特性。但匿名性對於Nguyen的方法產生識別性的問題，即交換簽章的簽章者，無法在交換簽章時，即時地驗證雙方身份與簽章，如此攻擊者就可以利用此點，戲弄交換簽章的簽章者，耗盡簽章者的計算資源；對具模糊性的同時簽章法而言，往往具有識別性，反而沒有此方面的問題，因此針對具匿名性的同時簽章法另外提出識別性。本研究將針對各類型同時簽章法進行研究，探討如何讓同時簽章法同時具有識別性與匿名性。在改良Nguyen的方法之後，滿足識別性、匿名性以及無關聯性，此三項特性無疑對使用者的隱私權提供一個良好的保障。

Chen et al. proposed the concept of concurrent signature scheme based on ring signature schemes to realize the fair signature exchange protocols without trusted third parties and the same computational power assumption.  Concurrent signature schemes should satisfy four security properties: correctness, unforgeability, fairness, and signer-ambiguity.  In 2005, Nguyen first proposed an asymmetric concurrent signature scheme without adopting ring signatures.  For the privacy protection, Nguyen’s scheme satisfies two new security properties: anonymity and unlinkability.  To satisfy the anonymity property, Nguyen’s scheme has identification problem that signers cannot identify each other during the exchange protocol.  So an attacker can make use of this problem to trick signers to exhaust computation resources of the signer.  However, the concurrent signature schemes with signer-ambiguity do not have the identification problem.  A new property, identification, is defined for the concurrent signature scheme with anonymity.  In this thesis, three improved concurrent schemes are proposed to provide anonymity and identification at the same time.  Among these three schemes, the improved Nguyen’s scheme satisfies identification, anonymity, and unlinkability at the same time.  With the identification, anonymity, and unlinkability, the signers’ privacy suffers a good protection.

Contents
Chapter 1 Introduction 1
1.1	Concept for Concurrent Signature Scheme 1
1.2	Related Work 2
1.3	Our Motivations and Contributions 4
Chapter 2 Review of Concurrent Signature Schemes 6
2.1	Concurrent Signature Scheme	6
2.1.1	 Generic Algorithms for Concurrent Signature Scheme 6
2.1.2	Generic Concurrent Signature Protocol 7
2.1.3	A Concrete Concurrent Signature Scheme 9
2.1.4	Remarks for Chen et al.’s Scheme 10
2.2	iPerfect Concurrent Signature Scheme	11
2.2.1	Generic Algorithms for iPerfect Concurrent Signature Algorithms 11
2.2.2	Generic iPerfect Concrete Concurrent Signature Protocol 12
2.2.3	A Concrete iPerfect Concurrent Signature Scheme 14
2.3	Asymmetric Concurrent Signature Scheme 15
2.3.1	Schnorr and Promise of Schnorr Signatures 15
2.3.1.1	Schnorr Signature Scheme 15
2.3.1.2	Promise of Schnorr Signature 16
2.3.2	Schnorr-like and Promise of Schnorr-like Signatures 16
2.3.2.1	Schnorr-like Signature Scheme 17
2.3.2.2	Promise of Schnorr-like Signature 17
2.3.3	Generic Algorithms for Asymmetric Concurrent Signature	 17
2.3.4	Generic Asymmetric Concurrent Signature Protocol 19
2.3.5	A Concrete Asymmetric Concurrent Signature Scheme 21
Chapter 3 Our Concurrent Signature Scheme with Anonymity 23
3.1	Generic Algorithms for Our Concurrent Signature Scheme 23
3.2	Generic Protocol for Our Concurrent Signature Scheme 24
3.3	Formal Security Model 26
3.3.1	Correctness 26
3.3.2	Unforgeability 26
3.3.3	Fairness	29
3.3.4	Anonymity	 30
3.3.5	Identification 30
3.4	A Concrete Concurrent Signature Scheme with Anonymity	 30
3.5	Security Analysis	32
3.5.1	Correctness 32
3.5.2	b1 - secrecy 33
3.5.3	Unforgeability 33
3.5.4	Fairness	37
3.5.5	Anonymity	 37
3.5.6	Identification 38
3.6	Comparison between Chen et al.’s Scheme and Our Proposed Scheme 38
Chapter 4 Our iPerfect Concurrent Signature Scheme with Anonymity	 40
4.1	Generic Algorithms for Our iPerfect Concurrent Signature Scheme 40
4.2	Generic Protocol for Our iPerfect Concurrent Signature Scheme 41
4.3	Formal Security Model 43
4.3.1	Correctness 43
4.3.2	Unforgeability 44
4.3.3	Fairness	46
4.3.4	Anonymity	 47
4.3.5	Identification 47
4.4	A Concrete iPerfect Concurrent Signature Scheme with Anonymity 48
4.5	Security Analysis 49
4.5.1	Correctness 49
4.5.2	b1 - secrecy 50
4.5.3	Unforgeability 50
4.5.4	Fairness 54
4.5.5	Anonymity	 54
4.5.6	 Identification 55
4.6	Comparison of Wang et al.’s Scheme and Our Proposed Scheme 55
Chapter 5 Our Asymmetric Concurrent Signature Scheme with Identification 57
5.1	Generic Algorithms for Our Asymmetric Concurrent Signature Scheme 57
5.2	Generic Protocol for Our Asymmetric Concurrent Signature Scheme 59
5.3	Formal Security Model 60
5.3.1	Correctness 60
5.3.2	Unforgeability 61
5.3.3	Fairness	64
5.3.4	Anonymity	 65
5.3.5	Unlinkability 65
5.3.6	Identification 66
5.4	A Concrete Asymmetric Concurrent Signature Scheme with Identification 66
5.5	Security Analysis	68
5.5.1	Correctness 68
5.5.2	b1 - secrecy 70
5.5.3	Unforgeability 70
5.5.4	Fairness 72
5.5.5	Anonymity	 73
5.5.6	Unlinkability 74
5.5.7	Identification 75
5.6	Comparison of Nguyen’s Scheme and Our Proposed Scheme 76
Chapter 6 Conclusions 78
References 80
Appendix	82


List of Tables
Table 1: Security Property Comparison between Chen et al.’s Scheme and Our Improvement 39
Table 2: Performance Comparison between Chen et al.’s Scheme and Our Improvement 39
Table 3: Security Property Comparison between Wang et al.’s Scheme and Our Improvement 56
Table 4: Performance Comparison between Wang et al.’s Scheme and Our Improvement 56
Table 5: Security Property Comparison between Nguyen’s Scheme and Our Improvement 77
Table 6: Performance Comparison between Nguyen’s Scheme and Our Improvement 77
Table 7: Security Property Comparison for Chen et al.’s Scheme, Wang et al.’s Scheme and Nguyen’s Scheme 78
Table 8: Security Property Comparison for Our Improvement 79

[1] M. Abadi, N. Glew, B. Horne, and B. Pinkas, “Certified E-Mail with a Light On-Line Trusted Third Party: Design and Implementation,” Proc. of the 11th International World Wide Web Conference, WWW 2002, Honolulu, Hawaii, USA, May 7-11, 2002, pp. 387-395.
[2] M. Abe, M. Ohkubo, and K. Suzuki, “1-out-of-n Signatures from a Dariety of Keys,” Advances in Cryptology - ASIACRYPT 2002, LNCS, Vol. 2501, New York: Springer-Verlag, 2002, pp. 415-432.
[3] N. Asokan, V. Shoup, and M. Waidner, “Optimistic Fair Exchange of Digital Signatures,” Advances in Cryptology - EUROCRYPT 1998, LNCS, Vol. 1403, New York: Springer-Verlag, 1998, pp.591-606.
[4] E. F. Brickell, D. Chaum, I.B. Damgård, and J. van de Graaf, “Gradual and Verifiable Release of a Secret,” Advances in Cryptology - 1987, LNCS, Vol. 293, New York: Springer-Verlag, 1987, pp.156-166.
[5] C. Cachin and J. Camenisch, “Optimistic Fair Secure Computation,” Advances in Cryptology - CRYPTO 2000, LNCS, Vol. 1880, New York: Springer-Verlag, 2000, pp.94-112.
[6] L. Chen, C. Kudla, and K. G. Paterson. “Concurrent Signatures,” Advances in Cryptology – EUROCRYPT 2004, LNCS, Vol. 3207, New York: Springer-Verlag, 2004, pp. 287-305.
[7] Y.-C. Chen, On the Research of Fair Exchange Protocols and Micropayment Schemes, Master Thesis, National Central University, Taiwan, R.O.C, 2006.
[8] R. Cleve, “Controlled Gradual Disclosure Schemes for Random Bits and their Applications,” Advances in Cryptology-CRYPTO 1989, LNCS, Vol. 435, New York: Springer-Verlag, 1990, pp.573-588.
[9] I. B. Damgård, “Practical and Provably Secure Release of a Secret and Exchange of Signatures,” Advances in Cryptology - EUROCRYPT 1993, LNCS, Vol. 765, New York: Springer-Verlag, 1994, pp. 200-217.
[10] S. Even, O. Goldreich, and A. Lempel, “A Randomized Protocol for Signing Contracts,” Communications of the ACM, 1985, Vol. 28(6), pp.637-647.
[11] M. K. Franlin and M. K. Reiter, “Fair Exchange with a Semi-Trusted Third Party,” Proc. of the 4th ACM Conference on Computer and Communications Security, Zurich, Switzerland, 1997, pp.1-5. 
[12] M. K. Franlin and G. Tsudik, “Secure Group Barter: Multi-Party Fair Exchange with Semi-Trusted Neutral Parties,” Proc. of Financial Cryptology - EUROCRYPT 1998, LNCS, Vol. 1465, New York: Springer-Verlag, 1998, pp.90-102.
[13] J.A. Garay, M. Jakobsson, and P. MacKenzie, “Abuse-Free Optimistic Contract Signing,” Advances in Cryptology - CRYPTO 1999, LNCS, Vol. 1666, New York: Springer-Verlag, 1999, pp.449-466.
[14] O. Goldreich, “Sending Certified Mail Using Oblivious Transfer and a Threshold Scheme,” Technical Report, Computer Science Department, Israel Institute of Technology, 1984.
[15] O.	Goldreich, “A Simple Protocol for Signing Contracts,” Advances in Cryptology-CRYPTO 1983, New York: Springer-Verlag, 1984, pp.133-136.
[16] K. Nguyen, “Asymmetric Concurrent Signatures,” Proc. of Information and Communications Security Conference, ICICS 2004, LNCS, Vol. 3783, New York: Springer-Verlag, 2005, pp. 181-193.
[17] B. Pfitzmann, M. Schunter, and M. Waidner, “Optimal Efficiency of Optimistic Contract Signing,” Proc. of the 7th Annual ACM Symposium on Principles of Distributed Computing, New York, U.S.A., 1998, pp.113-122.
[18] R. L. Rivest, A. Shamir, and Y. Tauman. “How to Leak a Secret,” Asiacrypt’ 01, LNCS, Vol. 2248, New York: Springer-Verlag, 2001, pp.552-565.
[19] C. P. Schnorr, “Efficient Identification and Signatures for Smart Cards,” Advances in Cryptology-CRYPTO 1989, LNCS, Vol. 435, New York: Springer-Verlag, 1990, pp.239-252.
[20] W. Susilo, Y. Mu, and F. Zhang, “Perfect Concurrent Signature Schemes,” Proc. of Information and Communications Security Conference, ICICS 2004, LNCS, Vol. 3269, New York: Springer-Verlag, 2004, pp. 14-26.
[21] G. Wang, F. Bao, and J. Zhou, “The Fairness of Perfect Concurrent Signatures,” The 8th International Conference on Information and Communications Security (ICICS 2006), LNCS, Vol. 4307, New York: Springer-Verlag, 2006, pp. 435-451.