Selected Article

Title

雙線性配對計算之研究與實作

Creator

劉兆樑

Description

[[abstract]]由於現今的技術只能以指數時間解決橢圓曲線離散對數問題,因此橢圓曲線離散對數問題提供了許多密碼學上的應用。值得一提的是,橢圓曲線密碼系統所使用的金鑰長度遠較傳統密碼所使用的短很多(如RSA 型態的密碼系統)。 在早年,只有少數的數學家研究Weil/Tate pairing 的相關性質,直到Bilinear Pairing被發現可以使用在密碼學的分析上,可將橢圓曲線離散對數問題對應到一個有限體上的離散對數問題,Bilinear Pairing 的研究才開始受到重視。然而隨著ID-based 密碼系統的興起,更擴大了Bilinear Pairing 的應用層面。使得植基於Bilinear Pairing 的密碼系統設計有了極大的發展空間,相關的研究包括:加密系統、認證式金鑰協定、數位簽章等等。時至今日,這些Bilinear Pairing 的相關應用更在近代密碼學上扮演一個重要的角色。然而在這些相關的應用中,Bilinear Pairing 的計算往往是整個系統中最吃重的部分。然而,如何實作出Bilinear Pairing 的運算儼然成為這些應用系統的最重要課題。因此,分析並以物件導向語言實作出Bilinear Pairing 計算相關的物件將是本計劃的目標。 然而第一個能有效率計算Bilinear Pairing 的演算法,是由Miller 在1986 所提出,而直到近幾年才有學者針對不同的方向,研究提升Bilinear Pairing 運算效能的方法。由於國內卻十分欠缺Bilinear Pairing 計算的研究與實作,因此,在本研究計劃將對申請人之博士論文進行延伸研究,並具體實作相關程式物件。所以對於各種影響Bilinear Pairing運算效能的因素都將仔細的分析,並將Pairing-based 密碼系統的各個應用加以分類,同時針對不同類別的應用,設計出有效率且具有應用價值的Bilinear Pairing 計算程式。因此本計劃的成果將對加速Bilinear Pairing 計算應用有非常大的幫助,並對國家發展新一代的加密系統上扮演著重要的地位。 Many possibilities in the field of cryptography arise from the fact that elliptic curve discrete logarithmic problem can only be solved in the exponential time. It is significant that elliptic curve cryptography can be performed with shorter key size than conventional cryptography (e.g. RSA-like cryptosystem). Weil/Tate pairings were only studied by mathematicians until the bilinear pairings were used to reduce the elliptic curve discrete logarithm problem on some curves to the discrete logarithm problem in a finite field. Further, the rise of ID-based cryptography has led to extensive use of such pairings. Since then, the design of pairing-based cryptosystems has been an important issue in the cryptography, such as, encryption system, key-agreement protocol, signature scheme and so on. Henceforth, applications utilizing these bilinear pairings have played an important role in modern cryptography. In many of these applications, the calculation of these bilinear pairings is one of the dominant computational tasks. Therefore, in the view of programming, the computation of such bilinear pairings is a critical issue for applications based on pairings. To analyze these pairing computation algorithms and then to design a practice object in objecting-oriented programming such as Java language is the goal of this project. The first efficient algorithm for computing pairings was proposed by Miller in 1986. Recently, in order to improve efficiency, most researches on pairing computation have been directed at many different aspects. Unfortunately, there is very few researchers study for these issues in our country. In this project, we will analyze the effects of many important factors to computation of such bilinear pairings. Also, we will classify the applications of pairing-based cryptosystem into several groups. Finally, we will separately design the efficient and applicable program for pairing computation in these groups. Therefore, the achievement of this project is helpful to the research of pairing computation and its applications. And it will play an important role for the development of advanced cryptology in our country.