橢圓曲線密碼配對與其應用

Pairing-based Elliptic Curve Cryptography and Its Applications

顏子翔(Tze-Hsiang Yen)

指導教授 ： 陳君明

國立臺灣大學/理學院/數學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.01165

摘要

由於橢圓曲線雙線性Diffie-Hellman問題之計算困難度，藉由配對（pairing）實現之協定陸續被提出，例如：身份加密（ID-based encryption）及密鑰協議機制。密鑰協議機制為透過不安全的通訊管道，讓欲進行通聯的使用者協議出共同密鑰（common secret key）；多方密鑰協議機制則是允許多位使用者在進行通聯之前，立即協議出加解密之共同密鑰。本論文將藉由雙線性配對函數提出一套密鑰協議機制，可以在通聯者低於四人時，透過一次訊息交換，同時完成身份驗證與密鑰協議。此外，該機制大幅降低使用者必須妥善保存的私鑰量，僅為橢圓曲線上的一點。我們將說明任何成功假扮公證第三方（TTP, trusted third party）的第三者，必定具備對應的私鑰資訊或超級強大的計算能力。我們也將透過magma的實作，說明此篇論文提出的機制確實可行。

關鍵字

雙線性配對函數 ； 多方密鑰協議機制 ； 橢圓曲線密碼學 ； 橢圓曲線離散對數

並列摘要

Due to the computational infeasibility of Bilinear Diffie-Hellman Problem on elliptic curves, many protocols based on pairings are constructed, such as ID-based encryption and key agreement. A key agreement protocol is a cryptographical primitive which allows participants to share a common secret key via insecure channel. In particular, a multiparty key agreement protocol manages arbitrary number of participants. In the thesis, we present a new authenticated multiparty key agreement protocol by using pairing. The authentication and the key agreement in our scheme can be done in just one round if the number of participants is less than four. Another advantage is that all participants only need to possess one piece of secret information of their own (a point on elliptic curve), hence the cost of secret protection is reduced in embedded systems. In security aspects, we show that if the system is compromised by Eve (a malicious user), then Eve either has secret information or has overwhelming computational ability to fool others by acting as the TTP (Trusted Third Party). We also show our scheme is efficient by using “magma”.

並列關鍵字

Bilinear Pairing ； Multiparty Key Agreement Protocol ； Elliptic Curve Cryptography ； Elliptic Curve Discrete Logarithm Problem

參考文獻

[1] S. S. Al-Riyami and K. G. Paterson, “Tripartite Authenticated Key Agreement Protocols from Pairings”, IMA Conference on Cryptography and Coding, Lecture Notes in Computer Science, Vol. 2898, pp. 332-359, 2003.

[2] Christophe Arene, Tanja Lange, Michael Naehrig, and Christophe Ritzenthaler, “Faster Computation of the Tate Pairing”, Journal of Number Theory, Vol. 131, Issue 5, pages 842-857, 2011.

[3] P. S. L. M. Barreto and M. Naehrig, “Pairing-Friendly Elliptic Curves of Prime Order”, Lecture Notes in Computer Science, Vol. 3897, pp. 319-331, 2006.

[4] R. Barua, R. Dutta, and P. Sarkar, “Extending Joux’s Protocol to Multi-Party Key Agreement”, INDOCRYPT 2003, Lecture Notes in Computer Science, Vol. 2904, pp. 205-217, 2003.

[5] S. A. Baset and H. G. Schulzrinne,“An Analysis of the Skype Peer-to-Peer Internet Telephony”, Protocol INFOCOM 25th IEEE International Conference on Computer Communications, pp. 1-11, 2006.