依所需安全等級產生適用於雙線性配對之橢圓曲線

Generating Pairing-Friendly Curves for Required Security Levels

張奕棠(Yi-Tang Chang)

指導教授 ： 陳榮傑

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00672

摘要

近年來有越來越多關於雙線性配對運算的應用被提出，如：密文可搜尋式加密, 身分基礎公鑰系統以及許多他們的延伸研究。首要面對的課題便是要如何去選一條適用於雙線性配對的橢圓曲線，且同時要兼顧可運算性與安全性。前者即是指該曲線的 embedding degree 必須夠小。而後者則是建立於橢圓曲線離散對數問題(ECDLP)以及有限體上的離散對數問題(DLP)之上。然而如此「適當」的曲線非常稀少，所以我們必須要用特殊的方法來尋找。事實上，已經有許多能解這個問題的方法被提出。在這篇論文中，首先我們將介紹關於雙線性配對的基本概念。接著介紹如何能建構一條適用於雙線性配對的橢圓曲線以及一些現有的方法。再來我們會提出我們實作的幾個細節與一些實驗數據。我們的實作著重於隱藏繁雜的數學運算，只留下間單的介面供使用者設定數個簡單的參數，如安全等級與偏好的方法。最後我們會在選擇雙線性配對應用的曲線上給予一些建議。

關鍵字

雙線性配對 ； 複乘法

並列摘要

In recent years, more and more applications based on bilinear pairing computation have been constructed, like Public Key Encryption with Keyword Search, Identity-Based Encryption, and their extension studies. The very first issue is to pick up a pairing-friendly elliptic curve, which is computable and secure. The former means that the embedding degree of a curve should be small. And the latter is based on elliptic curve discrete logarithm problem (ECDLP) and the finite field discrete logarithm problem (DLP). However, such "ideal" curves are rare, so they should be searched by special methods. In fact, some schemes have been published to solve this problem. In this thesis, we will firstly give basic concepts of pairing. Second, we introduce how to generate pairing-friendly curves and some famous construction methods. Third, we go through the implementation details of the most popular ones and show some experimental results. We focus on leaving difficult mathematic behind but providing a clear interface for user to set up some simple parameters, like security levels and preferring methods. Finally, we give some advices to select curves for pairing applications.

並列關鍵字

bilinear pairing ； complex multiplication

參考文獻

[4] Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public

[1] Neal Koblitz. Elliptic curve cryptosystems. Mathematics of computation, 48(177):203–

209, 1987.

[2] Victor Miller. Use of elliptic curves in cryptography. In Advances in Cryptology—

[3] Dan Boneh and Matt Franklin. Identity-based encryption from the weil pairing. In