隨著網路科技的迅速發展及電子交易的盛行，如何保障雙方的通訊安全係當前重要議題之一，金鑰交換協定(key exchange protocol)可用以解決此問題，該協定主要目的為協助兩個或多個參與者建立共享的會議金鑰(session key)，以便在公開網路中有效率建立彼此之間的秘密通訊管道。Diffie和Hellman提出第一個金鑰交換協定，他們的協定可為兩位使用者建立共享的會議金鑰，然而，他們的金鑰交換協定並未提供秘密會議金鑰的鑑別性(authentication)，使其易遭受中間人攻擊(man-in-the-middle attack)。
因此，許多研究藉由整合鑑別機制提出不同的鑑別式金鑰交換協定(authenticated key exchange protocol)，例如：密碼基礎(password-based)、公開金鑰基礎(public-key-based)及身分基礎(identity-based)等。首先，密碼基礎鑑別機制為驗證使用者身分最簡單且方便的方式，由使用者選擇密碼並向伺服器(system authority)註冊後，使用者即可使用密碼驗證其身分，部分研究為了安全性的考量，將機制設計為伺服器無法得知使用者的密碼，並將密碼儲存於相關裝置，如智慧卡(smart cards)；接著，公開金鑰密碼系統(public key cryptosystems)提供高安全性、鑑別性及不可否認性，被廣泛應用在許多研究中，然而，其計算及通訊成本通常比對稱式密碼系統高，或許橢圓曲線密碼系統（elliptic curve cryptosystems）為理想的選擇之一，它可使用較小的金鑰長度達成與其他公開金鑰密碼系統相同的安全等級，非常適合被使用在具較小記憶體與運算能力的裝置上；最後，以密碼為基礎的鑑別機制有許多安全及應用上的限制，而公鑰金鑰密碼系統則需要較高的計算成本以維運及驗證憑證，身分基礎密碼系統可用以解決此問題，它以使用者的身分或相關資訊作為其公開金鑰，與其他密碼系統相比較，提供安全性及複雜性間的折衷作法。
在本論文中，我們以密碼基礎、公開金鑰基礎及身分基礎，分別提出雙方(two-party)鑑別式金鑰交換機制，用以建立使用者與伺服器間的會議金鑰；接著，我們延伸上述所提機制設計三方(three-party)鑑別式金鑰交換機制，兩個使用者可以透過一個伺服器的協助建立用以進行秘密通訊的會議金鑰。本論文針對三種認證機制，分別設計雙方及三方鑑別式金鑰交換機制，我們所提出的機制不僅可有效協助參與者建立共享的會議金鑰，更滿足效率、可行、簡單及安全等特性，通訊雙方可依不同的應用環境，選擇合適的鑑別式金鑰交換機制。

With the rapid development of electronic commerce transactions, achieving secure communications between communicating participants is an important issue. The typical solutions are protocols for key exchange, designed to efficiently implement secure channels for two or more parties communicating over a public network by providing them with a shared secret key, called a session key. Diffie and Hellman introduced the first key exchange protocol. Their protocol can help two participants to establish a session key. However, the Diffie and Hellman’s key exchange protocol does not provide authentication of the secret session key, and suffers from the man-in-the-middle attack.
Therefore, various approaches of integrating authentication into the key exchange scheme have been proposed, e.g. password-based, public-key-based, identity-based, etc. First, the password-based authentication scheme is the most simple and convenient method to authenticate the users. The user chooses a password and register with the server (the system authority). And then, the user can use the password to proof the identity. Sometimes, researchers design their schemes as the server is unknown about the user’s password due to the consideration of the security. And, the user’s password is stored in a security device, e.g. smart cards. Subsequently, public key cryptosystems are quite important parts in various approaches due to their high security achievement, authentication and non-repudiation. However, the costs of computation and communication usually are more than symmetric cryptosystems. The elliptic curve cryptosystems may be an ideal choice. They can possess fewer bits, to achieve the same security level as other public key cryptosystems. They are quite suitable to be used in the devices with less storage and computing power. Finally, there are several secure and applied limitations in password-based authentication scheme. On the other hand, it requires more computational costs to maintain and verify the certificates in public key cryptosystems. The identity-based cryptosystems can be used to resolve these drawbacks. They use user’s identity or some other information as one’s public key. This kind of cryptosystems provides a better compromise between security and complexity than previous systems.
In this dissertation, we propose two-party password-based, public-key-based and identity-based authenticated key exchange schemes, separately. The proposed schemes are used to establish a session key shared between the user and the server. And then, we extend the above mechanisms to design three-party authenticated key exchange schemes. Two participants can construct a shared session key with the server’s aid, and the session key is used for securing subsequent communication. This dissertation contributes two-party and three-party authenticated key exchange schemes based on three authentication mechanisms. Our proposed schemes not only assist the participants in establishing a shared session key, but also achieve efficiency, practicability, simplicity, and strong notions of security. Both communication participants can choice the proper authenticated key exchange mechanism according to the different applied environments.

Chapter 1 Introduction1
1.1 Background and motivation1
1.2 Objectives10
1.3 Organization of dissertation13
Chapter 2 System models of authenticated key exchange14
2.1 System models14
2.2 Security goals and assumptions25
Chapter 3 Password-based approach30
3.1 2P-AKE scheme30
3.2 3P-AKE scheme36
3.3 Security analyses40
3.4 Performance evaluation48
Chapter 4 Public-key-based approach49
4.1 2PK-AKE scheme49
4.2 3PK-AKE scheme54
4.3 Security analyses58
4.4 Performance evaluation66
Chapter 5 Identity-based approach68
5.1 2I-AKE scheme69
5.2 3I-AKE scheme74
5.3 Security analyses78
5.4 Performance evaluation86
Chapter 6 Conclusions and future work89
Bibliography92
Biography101

[1]Bellovin, S. M., and Merritt, M., “Encrypted key exchange: password-based protocols secure against dictionary attacks,” Proceedings of the IEEE Symposium on Research in Security and Privacy, Oakland, California, United States, pp. 72-84 (1992)
[2]Blake-Wilson, S., Johnson, D., and Menezes, A., “Key agreement protocols and their security analysis,” Proceedings of the sixth IMA International Conference on Cryptography and Coding, Cirencester, United Kingdom, pp. 30-45 (1997)
[3]Boyd, C., and Choo, K. K. R., “Security of two-party identity-based key agreement,” Mycrypt 2005, Kuala Lumpur, Malaysia, pp. 229-243 (2005)
[4] Cagalj, M., Capkun, S., and Hubaux, J. P., “Key agreement in peer-to-peer wireless networks,” Proceedings of the IEEE, Vol. 94, No. 2, pp. 467-478 (2006)
[5] Canetti, R., and Krawczyk, H., “Analysis of key-exchange protocols and their use for building secure channels”, Proceedings of Advances in Cryptology - EUROCRYPT 2001, Innsbruck, Austria, pp. 453-474 (2001)
[6]Chang, C. C., and Wu, T. C., “Remote password authentication scheme with smart cards,” IEEE Proceedings-Computers and Digital Techniques, Vol.138, No. 3, pp.165-168 (1991)
[7]Chen, T. H., Lee, W. B., and Chen, H. B., “A round-and computation-efficient three-party authenticated key exchange protocol,” Journal of Systems and Software, Vol. 81, No. 9, pp. 1581-1590 (2008)
[8]Daemen, J., and Rijmen, V., The Design of Rijndael: AES-The Advanced Encryption Standard, Springer-Verlag (2002)
[9]Diffie, W., and Hellman, M., “New directions in cryptography,” IEEE Transactions on Information Theory , Vol. 22, No. 6, pp. 644-654 (1976)
[10]Ding, Y., and Horster, P., “Undetectable on-line password guessing attacks,” ACM Operating Systems Review, Vol. 29, No. 4, pp.77-86 (1995)
[11] Gehani, A., “PAST: probabilistic authentication of sensor timestamps,” Computer Security Applications Conference,. ACSAC '06. 22nd Annual, pp. 439-448 (2006)
[12]Gunther, C. G., “An identity-based key-exchange protocol,” Advances in Cryptology - EUROCRYPT 1989, Houthalen, Belgium, pp. 29-37 (1990)
[13]Guo, H., Li, Z., Mu, Y., and Zhang, X., “Cryptanalysis of simple three party key exchange protocol,” Computers & Security, Vol. 27, No. 1, pp. 16-21 (2008)
[14] He, D., Chen, J., and Hu, J., “An ID-based client authentication with key agreement protocol for mobile client-server environment on ECC with provable security,” Information Fusion, Vol. 13, No. 3, pp. 223-230 (2011)
[15]He, D., and Chen, Y., “An ID-based three-party authenticated key exchange protocol using elliptic curve cryptography for mobile-commerce environments,” Arabian Journal for Science and Engineering, DOI: 10.1007/s13369-013-0575-4, (2013)
[16]Holbl, M., and Welzer, T., “Two improved two-party identity based authenticated key agreement protocols,” Computer Standards and Interfaces, Vol. 31, pp. 1056-1060 (2009)
[17]Holbl, M., Welzer, T., and Brumen, B., “Attacks and improvement of an efficient remote mutual authentication and key agreement scheme,” Cryptologia, Vol. 34, No. 1, pp. 52-59 (2010)
[18]Holbl, M., Welzer, T., and Brumen, B., “Two proposed identity-based three-party authenticated key agreement protocols from pairings,” Computers & Security, Vol. 29, No. 2, pp. 244-252 (2010)
[19]Hsieh, B. T., Sun, H. M., Hwang, T., and Lin, C. T., “An improvement of Saeednia’s identity-based key exchange protocol,” Information Security Conference, pp. 41-43 (2002)
[20]Hwang, H., and Li, L., “A new remote user authentication scheme using smart cards,” IEEE Transactions on Consumer Electronics, Vol. 46, No. 1, pp. 28-30 (2000)
[21]Islam, S. H., and Biswas, G. P., “A more efficient and secure ID-based remote mutual authentication with key agreement scheme for mobile devices on elliptic curve cryptosystem,” The Journal of Systems and Software, Vol. 84, No. 11, pp. 1892-1898 (2011)
[22]Juang, W. S., “Efficient password authenticated key agreement using smart cards,” Computers & Security, Vol. 23, No. 2, pp. 167-173 (2004)
[23]Kaliski Jr. B., “An unknown key-share attack on the MQV key agreement protocol,” ACM Transactions on Information and System Security, Vol. 4, No. 3, pp. 275-288 (2001)
[24] Kaps, J. and Sunar, B., "Energy comparison of AES and SHA-1 for ubiquitous computing," EUC Workshops, Lecture Notes in Computer Science, Vol. 4097, pp 372-381 (2006)
[25]Knuth, D. E., The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition Addison-Wesley (1981)
[26]Koblitz, N., “Elliptic curve cryptosystem,” Mathematics of Computation, Vol. 48, No. 177, pp. 203-209 (1987)
[27]Kocher, P., Jaffe, J., and Jun, B., “Differential power analysis,” Advances in Cryptology - CRYPTO 1999, Santa Barbara, California, Unite States, pp. 388-397 (1999)
[28]Ku, W., and Chen, S., “Weaknesses and improvements of an efficient password based remote user authentication scheme using smart cards,” IEEE Transactions on Consumer Electronics, Vol. 50, No. 1, pp. 204-207 (2004)
[29]Kwon, T., and Song, J., “Security and efficiency in authentication protocols resistant to password guessing attacks,” Proceedings of the 22nd Annual Conference on Local Computer Networks, Minneapolis, Minnesota, Unite States, pp. 245-252 (1997)
[30]Kwon, T., and Song, J., “Authenticated key exchange protocols resistant to password guessing attacks,” IEE Proceedings- Communications, Vol. 145, No. 5, pp. 304-308 (1998)
[31]Lamport, L., “Password authentication with insecure communication,” Communications of the ACM, Vol. 24, No. 11, pp. 770-772 (1981)
[32]Lee, C. C., and Chang, Y. F., “On security of a practical three-party key exchange protocol with round efficiency,” Information Technology and Control, Vol. 37, No. 4, pp. 333-335 (2008)
[33]Lee, S. W., Kim, H. S., and Yoo, K. Y., “Efficient verifier-based key agreement protocol for three parties without server’s public key,” Applied Mathematics and Computation, Vol. 167, No. 2, pp. 996-1003 (2005)
[34] Lin Y. J., and Chan M. C., “A scalable monitoring approach based on aggregation and refinement,” IEEE Journal on Selected Areas in Communications (JSAC), Vol. 20, No. 4, pp. 677-690 (2002)
[35]Lu, R., and Cao, Z., “Simple three-party key exchange protocol,” Computers & Security, Vol. 26, No. 1, pp. 94-97 (2007)
[36] Malik, M.Y., “Efficient implementation of elliptic curve cryptography using low-power digital signal processor,” Advanced Communication Technology (ICACT), 2010 The 12th International Conference on (Volume 2), pp. 1464-1468 (2010)
[37]McCullagh, N., and Barreto, P. S. L. M., “A new two-party identity-based authenticated key agreement,” Proceedings of the 2005 international conference on Topics in Cryptology, San Francisco, California, United States, pp. 262-274 (2004)
[38]Menezes, A. J., VanOorschot P. C., and Vanstone, S. A., Handbook of Applied Cryptography, Chapter 12: Key Establishment Protocols. CRC Press (1996)
[39]Messerges, T. S., Dabbish, E. A., and Sloan, R. H., “Investigations of power analysis attacks on smartcards,” In USENIX Workshop on Smartcard Technology, Chicago, Illinois, United States, pp. 151-161 (1999)
[40]Messerges, T. S., Dabbish, E. A., and Sloan, R. H., “Examining smart card security under the threat of power analysis attacks,” IEEE Transactions on Computers, Vol. 51, No. 5, pp. 541-552 (2002)
[41]Miller, V. S., “Use of elliptic curve in cryptography,” Advances in Cryptology - CRYPTO 1985, Santa Barbara, California, United States, pp. 417-426 (1986)
[42]Padmavathy, R., “Improved three party EKE protocol,” Information Technology and Control, Vol. 39, No. 3, pp. 220-226 (2010)
[43]Rivest, R. L., Shamir, A., and Adleman, L. M., “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, pp. 120-126 (1978)
[44]Roy, S., Das, A. K., and Li, Y., “Cryptanalysis and security enhancement of an advanced authentication scheme using smart cards, and a key agreement scheme for two-party communication,” Proceedings of the IEEE 30th International Performance Computing and Communications Conference, Orlando, Florida, United States, pp. 1-7 (2011)
[45]Saeednia, S., “Improvement of Gunther’s identity-based key exchange protocol,” Electronics Letters, Vol. 36, No. 18, pp. 1535-1536 (2000)
[46]Schnorr, C. P., “Efficient identification and signatures for smart cards,” Advances in Cryptology - CRYPTO 1989, Santa Barbara, California, United States, pp. 239-252 (1989)
[47]Seo, D. H., and Sweeney, P., “Simple authenticated key agreement algorithm,” Electronics Letters, Vol. 35 , No. 13 , pp. 1073-1074 (1999)
[48] Shamir, A., “Identity-based cryptosystems and signature schemes,” Advances in Cryptology - CRYPTO 1984, Santa Barbara, California, United States, pp. 47-53 (1985)
[49]Shieh, W. G., and Wang, F. M., “Efficient remote mutual authentication and key agreement,” Computers & Security, Vol. 25, No. 1, pp. 72-77 (2006)
[50]Shim, K., “Efficient ID-based authenticated key agreement protocol based on Weil pairing,” Electronics Letters, Vol. 39, No. 8, pp. 653-654 (2003)
[51]Smart, N. P., “An identity based authenticated key agreement protocol based on the Weil pairing,” Electronics Letters, Vol. 38, No. 13, pp. 630-632 (2002)
[52]Song, R., “Advanced smart card based password authentication protocol,” Computer Standards & Interfaces, Vol. 32, No. 4, pp. 321-325 (2010)
[53]Sun, H., “An efficient remote user authentication scheme using smart cards,” IEEE Transactions on Consumer Electronics, Vol. 46, No. 4, pp. 958-961 (2000)
[54]Tan, Z., “An enhanced three-party authentication key exchange protocol for mobile commerce environments,” Journal of Communications, Vol. 5, No. 5, pp. 436-443 (2010)
[55]Tapiador, J.E., Hernandez-Castro, J. C., Peris-Lopez, P., and Clark, J. A., “Cryptanalysis of Song’s advanced smart card based password authentication protocol”, Technical report available at http://arxiv.org/pdf/1111.2744 (2011)
[56]Tsaur, W. J., and Chou, C. H., “Efficient algorithms for speeding up the computations of elliptic curve cryptosystems,” Applied Mathematics and Computation, Vol. 168, No. 2, pp. 1045-1064 (2005)
[57]Tseng, Y. M., “Weakness in simple authenticated key agreement protocol,” Electronics Letters, Vol. 36, No. 1, pp. 48-49 (2000)
[58]Tseng, Y.M., Jan, J. K., and Wang, C. H., “Cryptanalysis and improvement of an identity-based key exchange protocol,” Journal of Computers, Vol. 14, No. 3, pp. 17-22 (2002)
[59]Tseng, Y. M., “An efficient two-party identity-based key exchange protocol,” Informatica, Vol. 18, No. 1, pp. 125-136 (2007)
[60]Wang, S., Cao, Z., Choo, K. K. R., and Wang, L., “An improved identity-based key agreement protocol and its security proof,” Information Sciences, Vol. 179, No. 3, pp. 307-318 (2009)
[61]Xu, J., Zhu, W. T., and Feng, D. G., “An improved smart card based password authentication scheme with provable security,” Computer Standards & Interfaces, Vol. 31, No. 4, pp. 723-728 (2009)
[62]Yang, W., and Shieh, S., “Password authentication schemes with smart cards,” Computers & Security, Vol. 18, No. 8, pp. 727-733 (1999)
[63]Yang, J. H., and Chang, C. C., “An ID-based remote mutual authentication with key agreement scheme for mobile devices on elliptic curve cryptosystem,” Computers & Security, Vol. 28, pp. 138-143 (2009)
[64]Yang, J. H., and Chang, C. C., “An efficient three-party authenticated key exchange protocol using elliptic curve cryptography for mobile-commerce environments,” Journal of Systems and Software, Vol. 82, No. 9, pp. 1497-1502 (2009)
[65]Yoon, E., Choi, S., and Yoo, K., “A secure and efficiency ID-based authenticated key agreement scheme based on elliptic curve cryptosystem for mobile devices,” International Journal of Innovative Computing, Information and Control, Vol. 8, No. 4, pp. 2637-2653 (2012)
[66]Yoon, E., and Yoo, K., “Improving the novel three-party encrypted key exchange protocol,” Computer Standards & Interfaces, Vol. 30, No. 5, pp. 309-314 (2008)
[67]Yoon, E., and Yoo, K., “Robust ID-based remote mutual authentication with key agreement protocol for mobile devices on ECC,” Proceedings of 2009 International Conference on Computational Science and Engineering, Vancouver, Canada, pp. 633-640 (2009)