An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

abstract: In Iwasawa theory, one studies how an arithmetic or geometric object grows as its field of definition varies over certain sequences of number fields. For example, let $F/\mathbb{Q}$ be a finite extension of fields, and let $E:y^2 = x^3 + Ax + B$ with $A,B \in F$ be an elliptic curve. If $F = F_0 \subseteq F_1 \subseteq F_2 \subseteq \cdots F_\infty = \bigcup_{i=0}^\infty F_i$, one may be interested in properties like the ranks and torsion subgroups of the increasing family of curves $E(F_0) \subseteq E(F_1) \subseteq \cdots \subseteq E(F_\infty)$. The main technique for studying this sequence of curves when $\Gal(F_\infty/F)$ has a $p$-adic analytic structure is to use the action of $\Gal(F_n/F)$ on $E(F_n)$ and the Galois cohomology groups attached to $E$, i.e. the Selmer and Tate-Shafarevich groups. As $n$ varies, these Galois actions fit into a coherent family, and taking a direct limit one obtains a short exact sequence of modules $$0 \longrightarrow E(F_\infty) \otimes(\mathbb{Q}_p/\mathbb{Z}_p) \longrightarrow \Sel_E(F_\infty)_p \longrightarrow \Sha_E(F_\infty)_p \longrightarrow 0 $$ over the profinite group algebra $\mathbb{Z}_p[[\Gal(F_\infty/F)]]$. When $\Gal(F_\infty/F) \cong \mathbb{Z}_p$, this ring is isomorphic to $\Lambda = \mathbb{Z}_p[[T]]$, and the $\Lambda$-module structure of $\Sel_E(F_\infty)_p$ and $\Sha_E(F_\infty)_p$ encode all the information about the curves $E(F_n)$ as $n$ varies. In this dissertation, it will be shown how one can classify certain finitely generated $\Lambda$-modules with fixed characteristic polynomial $f(T) \in \mathbb{Z}_p[T]$ up to isomorphism. The results yield explicit generators for each module up to isomorphism. As an application, it is shown how to identify the isomorphism class of $\Sel_E(\mathbb{Q_\infty})_p$ in this explicit form, where $\mathbb{Q}_\infty$ is the cyclotomic $\mathbb{Z}_p$-extension of $\mathbb{Q}$, and $E$ is an elliptic curve over $\mathbb{Q}$ with good ordinary reduction at $p$, and possessing the property that $E(\mathbb{Q})$ has no $p$-torsion. / Dissertation/Thesis / Ph.D. Mathematics 2011

Let E be an elliptic curve defined over the rationals Q, and p be a prime at least 5 where E has multiplicative reduction. This thesis studies the Iwasawa theory of E over certain false Tate curve extensions F[infinity], with Galois groupG = Gal(F[infinity]/Q). I show how the p[infinity]-Selmer group of E over F[infinity] controls the p[infinity]-Selmer rank growth within the false Tate curve extension, and how it is connected to the root numbers of E twisted by absolutely irreducible orthogonal Artin representations of G, and investigate the parity conjecture for twisted modules.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第22979号 / 理博第4656号 / 新制||理||1669(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 玉川 安騎男, 教授 小野 薫, 教授 望月 新一 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Ένα από τα βασικά προβλήματα κρυπτογραφίας είναι η δημιουργία και διαχείριση κλειδιών.Αν δύο ή περισσότερες οντότητες θέλουν να επικοινωνήσουν ασφαλώς, τότε πρέπει να διασφαλίσουν το απόρρητο της επικοινωνίας τους μέσω κρυπτογράφησης δεδομένων. Για να γίνει, όμως, αυτό πρέπει να γεννηθεί ένα κοινό κλειδί(κλειδί συνεδρίας) στο οποίο πρέπει να συμφωνήσουν όλοι οι εμπλεκόμενοι και το οποίο θα μπορεί να πιστοποιηθεί και να διανεμηθεί ασφαλώς. Ένα πρωτόκολλο συμφωνίας κλειδιών είναι μια τεχνική δημιουργίας κλειδιών στην οποία ένα μοιραζόμενο μυστικό προκύπτει από δύο ή περισσότερους εμπλεκόμενους ως συνάρτηση πληροφοριών που συνεισφέρονται ή σχετίζονται με κάθε έναν εμπλεκόμενο έτσι, ώστε(ιδανικά), κανένας εμπλεκόμενος από μόνος του να μην μπορεί να προϋπολογίσει,προαποφασίσει το προκύπτoν μυστικό. Με άλλα λόγια ,όλες οι οντότητες που εμπλέκονται στο πρωτόκολλο πρέπει να συνεισφέρουν μια δικιά τους πληροφορία(την ψηφιακή τους ταυτότητα, το προσωπικό τους δημόσιο κλειδί, ένα password κ.τ.λ.) έτσι, ώστε να προκύψει το συνολικό κλειδί ασφάλισης του καναλιού επικοινωνίας τους. Τέτοια πρωτόκολλα είναι τα πρωτόκολλα Diffie-Hellman τα οποία εμφανίζονται σε πολλές παραλλαγές (και επίπεδα ασφαλείας). Η υλοποιησή τους, όμως, για πολλούς εμπλεκόμενους φορείς παραμένει δύσκολη, επειδή απαιτεί κόστος σε πόρους υλικού και δεν διασφαλίζει πλήρως ένα υψηλό επίπεδο ασφαλείας. Βασίζονται στις αρχές της κρυπτογραφίας Δημοσίου κλειδιού και η λειτουργικότητά τους για παραπάνω από έναν χρήστη αποτελεί ένα ανοικτό κεφάλαιο έρευνας. Στα πλαίσια αυτής της διπλωματικής θα μελετηθεί η λειτουργία αυτών των πρωτοκόλλων και θα επικεντρωθούμε σε σύγχρονες τεχνικές τους με την χρήση ελλειπτικών καμπυλών (Πρωτόκολλα Diffie Hellman ελλειπτικών καμπυλών).Θα αναλυθεί η ασφάλεια των πρωτοκόλλων αυτών και θα σχεδιαστεί ένα μοντέλο επίθεσης. Στόχος είναι να προταθεί μια λύση πάνω σε αυτά τα πρωτόκολλα που θα διασφαλίζει το υψηλό επίπεδο ασφάλειας των εμπλεκόμενων φορέων και θα έχει υψηλή απόδοση και χαμηλές απαιτήσεις υλικού. Για να γίνει αυτό το προτεινόμενο πρωτόκολλο θα αναλυθεί και μια αρχιτεκτονική υλικού θα σχεδιαστεί. Η αρχιτεκτονική αυτή θα υλοποιηθεί μέσω της γλώσσας VHDL σε τεχνολογία FPGA με στόχο να μετρηθεί το επίπεδο απόδοσης της αρχιτεκτονικής και του πρωτοκόλλου γενικότερα. / One of the basic problems in cryptography is the creation and management of keys. If two or more entities want to communicate securely then they must ensure the confidentiality of communication through data encryption. In order to do this must be born a public key (session key) in which they have to agree all the participants and which will be certified and distributed securely. A protocol of key agreement is a technique of creation keys in which a shared secret results from two or more participants as interelation of informations that contributed or is related with each one involved, so (ideally) nobody from himself cannot budget or predetermine the resulting secret. In other words all entities that are involved in the protocol should contribute their own information (their digital identity, their personal public key, password etc.) so as to result the total key of insurance of their channel of communication. Such protocols are the protocols Diffie-Hellman which are presented in a lot of variants (and levels of safety). Their implementation however for a lot of involved entities remains difficult and requires cost in resources of hardware and does not ensure completely a high level of safety. They are based on the principles of cryptography of Public key and their functionalism for more than one user constitutes an open chapter of research. Within this thesis, we study the function of these protocols and focus on modern techniques using Elliptic Curves (Diffie Hellman Elliptic Curves Protocols). We analyze the security of these protocols and design a model attack. The aim is to propose a solution on these protocols to ensure the highest level of security among the involved entities and have high efficiency and low hardware requirements. To do that the proposed protocol will be analyzed and a hardware architecture will be designed. This architecture will be implemented by the language VHDL on FPGA technology in order to measure the performance level of the architecture and the protocol in general.

Elliptic curves are the basis for a relative new class of public-key schemes. It is predicted that elliptic curves will replace many existing schemes in the near future. It is thus of great interest to develop algorithms which allow efficient implementations of elliptic curve crypto systems. This thesis deals with such algorithms. Efficient algorithms for elliptic curves can be classified into low-level algorithms, which deal with arithmetic in the underlying finite field and high-level algorithms, which operate with the group operation. This thesis describes three new algorithms for efficient implementations of elliptic curve cryptosystems. The first algorithm describes the application of the Karatsuba-Ofman Algorithm to multiplication in composite fields GF((2n)m). The second algorithm deals with efficient inversion in composite Galois fields of the form GF((2n)m). The third algorithm is an entirely new approach which accelerates the multiplication of points which is the core operation in elliptic curve public-key systems. The algorithm explores computational advantages by computing repeated point doublings directly through closed formulae rather than from individual point doublings. Finally we apply all three algorithms to an implementation of an elliptic curve system over GF((216)11). We provide ablolute performance measures for the field operations and for an entire point multiplication. We also show the improvements gained by the new point multiplication algorithm in conjunction with the k-ary and improved k-ary methods for exponentiation.

This thesis examines the Mordell-Weil group for application in cryptography. This approach has recently been proposed by Gerhard Frey. The use of the Mordell-Weil group for discrete logarithm schemes is a variant of elliptic curve cryptosystems. We extended the original idea by Frey with the goal of a performance improvement. The arithmetic complexity using the Mordell-Weil group will be compared to ordinary elliptic curve cryptosystems. The main goals of this thesis are (1) to investigate the algorithmic complexity of Mordell-Weil cryptosystems relative to elliptic curve cryptosystems; (2) the appropriate selection of the group parameters for a successful adaptation to different platforms; (3) a C++ library which makes it possible to easily use this algebra for cryptographic systems based on groups; and (4) to obtain software performance measures for the new cryptosystem. Point multiplication, the crucial operation for elliptic curve cryptosystems, is more than 20% less complex in the Mordell-Weil group than in an ordinary elliptic curve while preserving the same level of security. We show how to further improve the system such that it is particularly suited to 32-bit and 16-bit hardware platforms. The speed-up of the Mordell-Weil group approach comes at the cost of a slightly larger bit-size that is needed to represent a curve point and a more costly curve generation.

The main focus of this paper is the study of elliptic curves, non-singular projective curves of genus 1. Under a geometric operation, the rational points E(Q) of an elliptic curve E form a group, which is a finitely-generated abelian group by Mordell’s theorem. Thus, this group can be expressed as the finite direct sum of copies of Z and finite cyclic groups. The number of finite copies of Z is called the rank of E(Q). From John Tate and Joseph Silverman we have a formula to compute the rank of curves of the form E: y2 = x3 + ax2 + bx. In this thesis, we generalize this formula, using a purely group theoretic approach, and utilize this generalization to find the rank of curves of the form E: y2 = x3 + c. To do this, we review a few well-known homomorphisms on the curve E: y2 = x3 + ax2 + bx as in Tate and Silverman's Elliptic Curves, and study analogous homomorphisms on E: y2 = x3 + c and relevant facts.

Let E be a one-parameter family of elliptic curves over a number field. It is natural to expect the average root number of the curves in the family to be zero. All known counterexamples to this folk conjecture occur for families obeying a certain degeneracy condition. We prove that the average root number is zero for a large class of families of elliptic curves of fairly general type. Furthermore, we show that any non-degenerate family E has average root number 0, provided that two classical arithmetical conjectures hold for two homogeneous polynomials with integral coefficients constructed explicitly in terms of E.<br />The first such conjecture -- commonly associated with Chowla -- asserts the equidistribution of the parity of the number of primes dividing the integers represented by a polynomial. We prove the conjecture for homogeneous polynomials of degree 3.<br />The second conjecture used states that any non-constant homogeneous polynomial yields to a square-free sieve. We sharpen the existing bounds on the known cases by a sieve refinement and a new approach combining height functions, sphere packings and sieve methods.

In an ever-increasing digital world, the need for secure communications over unsecured channels like Internet has exploded. To meet the different security requirements, communication devices have to perform expensive cryptographic operations. Hardware processors are therefore often needed to meet goals such as speed, ubiquity or cost-effectiveness. For such devices, the size of security parameters is chosen as small as possible to save resources and time. It is therefore necessary to know the effective security of given sets of parameters in order to achieve the best trade-off between efficiency and security. The best way to address this problem is by means of accurate estimations of dedicated hardware attacks. In this thesis, we investigate two aspects of cryptographic hardware: constructive applications that deal with general purpose secure devices and destructive applications that handle dedicated hardware attacks against cryptosystems. Their set of constraints is clearly different but they both need efficient algorithms and hardware architectures. First, we deal with efficient and novel modular inversion and division algorithms on Field-Programmable Gate Array (FPGA) hardware platform. Such algorithms are an important building block for both constructive and destructive use of elliptic curve cryptography. Then, we provide new or highly improved architectures for attacks against RC5 cipher, GF(2m) elliptic curves and RSA by means of efficient elliptic curve-based factorization engines (ECM). We prove that FPGA-based solutions are much more cost-effective and low power than software-based solutions. Our resulting cost assessments should serve as a basis for improving the accuracy of current hardware or software-based security evaluations. Finally, we handle the efficiency-flexibility trade-off problem for high-speed hardware implementations of elliptic curve. Then, we present efficient elliptic curve digital signature algorithm coprocessors for smart cards. We also show that, surprisingly, affine coordinates can be an attractive solution for such an application.