Elliptic curve pairing-based cryptography

Download
2010
Kırlar, Barış Bülent
In this thesis, we explore the pairing-based cryptography on elliptic curves from the theoretical and implementation point of view. In this respect, we first study so-called pairing-friendly elliptic curves used in pairing-based cryptography. We classify these curves according to their construction methods and study them in details. Inspired of the work of Koblitz and Menezes, we study the elliptic curves in the form $y^{2}=x^{3}-c$ over the prime field $\F_{q}$ and compute explicitly the number of points $\#E(\mathbb{F}_{q})$. In particular, we show that the elliptic curve $y^{2}=x^{3}-1$ over $\mathbb{F}_{q}$ for the primes $q$ of the form $27A^{2}+1$ has an embedding degree $k=1$ and belongs to Scott-Barreto families in our classification. Finally, we give examples of those primes $q$ for which the security level of the pairing-based cryptographic protocols on the curve $y^{2}=x^{3}-1$ over $\mathbb{F}_{q}$ is equivalent to 128-, 192-, or 256-bit AES keys. From the implementation point of view, it is well-known that one of the most important part of the pairing computation is final exponentiation. In this respect, we show explicitly how the final exponentiation is related to the linear recurrence relations. In particular, this correspondence gives that finding an algoritm to compute final exponentiation is equivalent to finding an algorithm to compute the $m$-th term of the associated linear recurrence relation. Furthermore, we list all those work studied in the literature so far and point out how the associated linear recurrence computed efficiently.

Suggestions

Elliptic curves and use of their endomorphism rings in cryptography
Sülçe, Ali Mert; Akyıldız, Ersan; Department of Cryptography (2019)
Although elliptic curves have been studied for hundreds of years, the inception of elliptic curve cryptography is 1985 by Koblitz’s and Miller’s independent proposals that is based on the discrete logarithm problem on an elliptic curve defined over a finite field. After that date, there are a lot of advances and studies in elliptic curve cryptography(ECC) which provide high security with relatively small block sizes and high speed compared to the other public key cryptosystems. For instance, 160-bit ellipti...
ON THE IDEAL TRIANGULATION GRAPH OF A PUNCTURED SURFACE
Korkmaz, Mustafa (2012-01-01)
We study the ideal triangulation graph T(S) of an oriented punctured surface S of finite type. We show that if S is not the sphere with at most three punctures or the torus with one puncture, then the natural map from the extended mapping class group of S into the simplicial automorphism group of T(S) is an isomorphism. We also show that, the graph T(S) of such a surface S. equipped with its natural simplicial metric is not Gromov hyperbolic. We also show that if the triangulation graph of two oriented punc...
Algebraic Nahm transform for parabolic Higgs bundles on P-1
Aker, Kursat; Szabo, Szilard (2014-01-01)
We formulate the Nahm transform in the context of parabolic Higgs bundles on P-1 and extend its scope in completely algebraic terms. This transform requires parabolic Higgs bundles to satisfy an admissibility condition and allows Higgs fields to have poles of arbitrary order and arbitrary behavior. Our methods are constructive in nature and examples are provided. The extended Nahm transform is established as an algebraic duality between moduli spaces of parabolic Higgs bundles. The guiding principle behind ...
Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication
Taskin, Halil Kemal; Cenk, Murat (2018-01-24)
This paper proposes a new multiplication algorithm over F-2(255)-19 where the de-facto standard Curve25519 [2] algorithm is based on. Our algorithm for the underlying finite field multiplication exploits the Toeplitz matrix-vector multiplication and achieves salient results. We have used a new radix representation that is infeasible when used with schoolbook multiplication techniques but has notable advantages when used with Toeplitz matrix-vector multiplication methods. We present the new algorithm and dis...
Quasi-Cartan companions of elliptic cluster algebras
Velioğlu, Kutlucan; Seven, Ahmet İrfan; Department of Mathematics (2016)
There is an analogy between combinatorial aspects of cluster algebras and diagrams corresponding to skew-symmetrizable matrices. In this thesis, we study quasi-Cartan companions of skew-symmetric matrices in the mutation-class of exceptional elliptic diagrams. In particular, we establish the existence of semipositive admissible quasi-Cartan companions for these matrices and exhibit some other invariant properties.
Citation Formats
B. B. Kırlar, “Elliptic curve pairing-based cryptography,” Ph.D. - Doctoral Program, Middle East Technical University, 2010.