Research On Pairing And Discrete Logarithm Problem In Elliptic Curve Cryptography

In recent years, Elliptic Curve Cryptography (ECC) has become one hot topic in theresearch on public key cryptography. Many interesting cryptographic protocols based on theparticularity of pairings, which cannot be realized by other mathematical primitives. The securityof ECC is based on the difficulty of elliptic curve discrete logarithm problem. We discuss theefficiency of pairing computation, fault attack on pairing and the discrete logarithm problem onKoblitz curve. The main results are listed as follows:1. We speed up the efficiency of pairing computation via conjugate technique. We proposean efficient Miller algorithm computing Tate pairing based on the double-base chain. Throughthe application of norm function, our refinements reduce the total number of the lines andvertical lines in rational function. Further more, a modification of our algorithm which can avoidthe division via conjugate technique in extension fields, the performance of bilinear pairing canbe improved considerably. Experimental results show that our algorithm can be improved bymore than10%in comparison the previous algorithm.2. A fault attack method corresponding to the elliptic curve bilinear pairing Miller algorithmis presented. On the basis of bilinear pairing efficient computation, we discuss the fault attack onMiller algorithm. This scheme is inspired by the spirit of side channel attack, and the techniqueof fault-tolerant is implemented to yield to the fault output. Compared with normal output, wecan gain a nonlinear system. Thus, we recover the secret key through the resolution of thisnonlinear system, and analyze the successful probability. In the end, we show the practical attackscheme with embedding degree k=4in Hessian coordinate.3. Using a distinctive feature of the Frobenius map that is just the cyclic shift of its normalbasis representation on Koblitz curve, we improve the efficiency of solving Discrete LogarithmProblem (DLP) on Koblitz curve. Based on the analysis of the Pollard-ρ method solvingElliptic Curve Discrete Logarithm Problem (ECDLP), we propose an improvement of Pollard-ρmethod which restricts the random walk to a subset Sof G. We make an explicit constructionby Frobenius map, thus the variant of thePollard-ρ method requires approximatelysteps, where kis the embedding degree.