Wyniki wyszukiwania - BazTech

1

Constructing Elliptic Curves for the GLV Method with Low-cost Decomposition

Wroński M., Dryło R., Kijko T., Bora P.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 4

399--413

EN

The GLV method allows to improve scalar multiplication on an elliptic curve E/Fqwith an efficiently computable endomorphism Φ : E → E over Fq. For points in a subgroup of large prime order r this requires decomposition of scalar k = k0 + k1λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∊ Fr and k0, k1 are integers O(√r) . In this note we consider the case when λ is of the form λ = 2s + a, where a is a small integer and λ=O(√r), which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∊ {2s, 2s - 1} and various security levels.

2

Konstruowanie krzywych genusu 2 z danym stopniem zanurzeniowym

Dryło R.

Studia Bezpieczeństwa Narodowego

|

2014

|

R. 4, Nr 6

95--124

PL

W kryptograﬁi opartej na iloczynach dwuliniowych stosuje się specjalne krzywe, dla których iloczyny dwuliniowe Weila i Tate można efektywnie obliczyć. Takie krzywe, zwykle nazywane pairing-friendly, mają mały stopień zanurzeniowy i wymagają specjalnej konstrukcji. W praktyce stosuje się głównie krzywe eliptyczne i hipereliptyczne genusu 2. Konstrukcje takich krzywych opierają się na metodzie mnożeń zespolonych (CM metodzie) i stąd ograniczają się do krzywych, których pierścień endomorﬁzmów jakobianu jest generowany przez odpowiednio małe liczby. Aby skonstruować krzywą najpierw wyznacza się parametry jej jakobianu, które zwykle są dane przez liczby Weila dla krzywych genusu 2, a następnie stosuje się CM metodę, aby znaleźć równanie krzywej. Freeman, Scott i Teske zebrali i opisali w ujednolicony sposób metody konstruowania krzywych eliptycznych z danym stopniem zanurzeniowym. Istnieje kilka różnych podejść do konstruowania krzywych genusu 2, z których pierwsze podali Freeman, Stevenhagen i Streng, Kawazoe-Takahashi i Freeman-Satoh. W tym opracowaniu opisujemy podejście oparte na idei autora, w którym wykorzystujemy odpowiednie wielomiany wielu zmiennych, aby jako ich wartości otrzymywać liczby Weila odpowiadające jakobianom krzywych genusu 2 z danym stopniem zanurzeniowym. Takie podejście pozwala konstruować zarówno krzywe genusu 2 o jakobianie absolutnie prostym oraz prostym, ale nie absolutnie prostym. Podajemy bezpośrednie wzory, które wyznaczają rodziny parametryczne krzywych genusu 2 z danym stopniem zanurzeniowym.

EN

For applications in pairing-based cryptography we need special curves for which the Weil and Tate pairings can be eﬃciently computed. Such curves, commonly called pairing-friendly, require speciﬁc constructions. In practice we mainly use elliptic curves or hyperelliptic curves of genus 2. Methods for constructing pairing-friendly curves are based on the complex multiplication (CM) method, and thus are restricted to curves whose endomorphism ring of the Jacobian is generated by suitably small numbers. To construct such a curve one ﬁrst determines parameters of its Jacobian, which are usually given by Weil numbers for genus 2 curves, and then one uses the CM method to ﬁnd a curve equation. Methods for constructing pairing-friendly elliptic curves were gathered and described in a coherent language by Freeman, Scott and Teske. There are several approaches to construct pairing-friendly genus 2 curves the ﬁrst of which were developed by Freeman, Stevenhagen, and Streng, Kawazoe-Takahashi, and Freeman-Satoh. In this paper we describe an approach based on the idea of the author, where we use suitable polynomials of several variables to obtain as their values Weil numbers corresponding to Jacobians of pairing-friendly genus 2 curves. This approach can be used to construct both genus 2 with absolutely simple Jacobian, and with simple, but not absolutely simple. We give explicit formulas, which determine parametric families of pairing-friendly genus 2 curves.

3

Konstruowanie krzywych eliptycznych z podgrupą danego rzędu i z danym pierścieniem endomorﬁzmów

Dryło R., Jelonek Z.

Studia Bezpieczeństwa Narodowego

|

2014

|

R. 4, Nr 6

81--94

PL

Metoda mnożeń zespolonych (CM metoda) pozwala skonstruować krzywą eliptyczną nad ciałem skończonych, której pierścień endomorﬁzmów jest ordynkiem maksymalnym w ciele urojonym kwadratowym o odpowiednio małym wyróżniku. Stosując CM metodę Lay i Zimmer oraz Bröker i Stevenhagen podali metodę konstruowania krzywej eliptycznej danego rzędu n nad pewnym ciałem prostym. Ich metoda ma heurystycznie wielomianowy czas działania, jeśli n nie ma zbyt wielu dzielników pierwszych. W tym opracowaniu pokażemy, że w analogiczny sposób można skonstruować krzywą eliptyczną, która zawiera podgrupę danego rzędu r i ma dany pierścień endomorﬁzmów o odpowiednio małym wyróżniku. Przy pewnych heurystycznych założeniach metoda ma wielomianowy czas działania, jeśli r jest liczbą pierwszą.

EN

The complex multiplication (CM) method allows one to construct an elliptic curve over a ﬁnite ﬁeld, whose endomorphism ring is the maximal order in an imaginary quadratic ﬁeld with a suitably small discriminant. Using CM method Lay-Zimmer and Bröker-Stevenhagen gave a method to construct an elliptic curve of a given order n over some prime ﬁeld. Their method has a heuristic polynomial time if n has not too many prime factors. In this paper we show that in an analogous way one can construct an elliptic curve, which contains a subgroup of a given order r and has a given endomorphism ring with a suitably small discriminant. We give heuristic arguments, which show that the method works in a polynomial time if r is prime.

4

A Remark on a Paper of Crachiola and Makar-Limanov

Dryło R.

Bulletin of the Polish Academy of Sciences. Mathematics

|

2011

|

Vol. 59, no 3

203--206

EN

A. Crachiola and L. Makar-Limanov [J. Algebra 284 (2005)] showed the following: if X is an affine curve which is not isomorphic to the affine line A1k, then ML(X×Y)=k[X]⊗ML(Y) for every affine variety Y, where k is an algebraically closed field. In this note we give a simple geometric proof of a more general fact that this property holds for every affine variety X whose set of regular points is not k-uniruled.