Faster pairings on special Weierstrass curves

This paper presents efficient formulas for computing cryptographic pairings on the curve y 2 = c x 3 + 1 over fields of large characteristic. We provide examples of pairing-friendly elliptic curves of this form which are of interest for efficient pairing implementations.

Jacobi quartic curves revisited

This paper provides new results about efficient arithmetic on Jacobi quartic form elliptic curves, y 2 = d x 4 + 2 a x 2 + 1. With recent bandwidth-efficient proposals, the arithmetic on Jacobi quartic curves became solidly faster than that of Weierstrass curves. These proposals use up to 7 coordinates to represent a single point. However, fast scalar multiplication algorithms based on windowing techniques, precompute and store several points which require more space than what it takes with 3 coordinates. Also note that some of these proposals require d = 1 for full speed. Unfortunately, elliptic curves having 2-times-a-prime number of points, cannot be written in Jacobi quartic form if d = 1. Even worse the contemporary formulae may fail to output correct coordinates for some inputs. This paper provides improved speeds using fewer coordinates without causing the above mentioned problems. For instance, our proposed point doubling algorithm takes only 2 multiplications, 5 squarings, and no multiplication with curve constants when d is arbitrary and a = ±1/2.

Elliptic curves, group law, and efficient computation

This thesis is about the derivation of the addition law on an arbitrary elliptic curve and efficiently adding points on this elliptic curve using the derived addition law. The outcomes of this research guarantee practical speedups in higher level operations which depend on point additions. In particular, the contributions immediately find applications in cryptology. Mastered by the 19th century mathematicians, the study of the theory of elliptic curves has been active for decades. Elliptic curves over finite fields made their way into public key cryptography in late 1980’s with independent proposals by Miller [Mil86] and Koblitz [Kob87]. Elliptic Curve Cryptography (ECC), following Miller’s and Koblitz’s proposals, employs the group of rational points on an elliptic curve in building discrete logarithm based public key cryptosystems. Starting from late 1990’s, the emergence of the ECC market has boosted the research in computational aspects of elliptic curves. This thesis falls into this same area of research where the main aim is to speed up the additions of rational points on an arbitrary elliptic curve (over a field of large characteristic). The outcomes of this work can be used to speed up applications which are based on elliptic curves, including cryptographic applications in ECC. The aforementioned goals of this thesis are achieved in five main steps. As the first step, this thesis brings together several algebraic tools in order to derive the unique group law of an elliptic curve. This step also includes an investigation of recent computer algebra packages relating to their capabilities. Although the group law is unique, its evaluation can be performed using abundant (in fact infinitely many) formulae. As the second step, this thesis progresses the finding of the best formulae for efficient addition of points. In the third step, the group law is stated explicitly by handling all possible summands. The fourth step presents the algorithms to be used for efficient point additions. In the fifth and final step, optimized software implementations of the proposed algorithms are presented in order to show that theoretical speedups of step four can be practically obtained. In each of the five steps, this thesis focuses on five forms of elliptic curves over finite fields of large characteristic. A list of these forms and their defining equations are given as follows: (a) Short Weierstrass form, y2 = x3 + ax + b, (b) Extended Jacobi quartic form, y2 = dx4 + 2ax2 + 1, (c) Twisted Hessian form, ax3 + y3 + 1 = dxy, (d) Twisted Edwards form, ax2 + y2 = 1 + dx2y2, (e) Twisted Jacobi intersection form, bs2 + c2 = 1, as2 + d2 = 1, These forms are the most promising candidates for efficient computations and thus considered in this work. Nevertheless, the methods employed in this thesis are capable of handling arbitrary elliptic curves. From a high level point of view, the following outcomes are achieved in this thesis. - Related literature results are brought together and further revisited. For most of the cases several missed formulae, algorithms, and efficient point representations are discovered. - Analogies are made among all studied forms. For instance, it is shown that two sets of affine addition formulae are sufficient to cover all possible affine inputs as long as the output is also an affine point in any of these forms. In the literature, many special cases, especially interactions with points at infinity were omitted from discussion. This thesis handles all of the possibilities. - Several new point doubling/addition formulae and algorithms are introduced, which are more efficient than the existing alternatives in the literature. Most notably, the speed of extended Jacobi quartic, twisted Edwards, and Jacobi intersection forms are improved. New unified addition formulae are proposed for short Weierstrass form. New coordinate systems are studied for the first time. - An optimized implementation is developed using a combination of generic x86-64 assembly instructions and the plain C language. The practical advantages of the proposed algorithms are supported by computer experiments. - All formulae, presented in the body of this thesis, are checked for correctness using computer algebra scripts together with details on register allocations.

Faster pairing computations on curves with high-degree twists

Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than 2 is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that admit twists of degree 3, 4 or 6. A few papers have presented explicit formulas for the doubling and the addition step in Miller’s algorithm, but the optimizations were all done for the Tate pairing with degree-2 twists, so the main usage of the high- degree twists remained incompatible with more efficient formulas. In this paper we present efficient formulas for curves with twists of degree 2, 3, 4 or 6. These formulas are significantly faster than their predecessors. We show how these faster formulas can be applied to Tate and ate pairing variants, thereby speeding up all practical suggestions for efficient pairing implementations over fields of large characteristic.

Le infrastrutture viarie dismesse o declassate ed il progetto di paesaggio

Paesaggio ed infrastrutture viarie sono un binomio molto forte: il primo ha insito il concetto di accessibilità, in quanto non può esistere senza la presenza di un osservatore; la strada, invece, trova i fattori che la connotano nel suo rapporto con la morfologia su cui insiste. Le infrastrutture viarie sono elemento strutturale e strutturante non solo di un territorio, ma anche di un paesaggio. Le attuali esigenze di mobilità portano oggi a ripensare ed adeguare molte infrastrutture viarie: laddove è possibile si potenziano le strutture esistenti, in diversi casi si ricorre a nuovi tracciati o a varianti di percorso. Porsi il problema di conservare itinerari testimoni della cultura materiale ed economica di una società implica considerazioni articolate, che travalicano i limiti del sedime: una via è un organismo più complesso della semplice linea di trasporto in quanto implica tutta una serie di manufatti a supporto della mobilità e soprattutto il corridoio infrastrutturale che genera e caratterizza, ovvero una porzione variabile di territorio definita sia dal tracciato che dalla morfologia del contesto. L’evoluzione dei modelli produttivi ed economici, che oggi porta quote sempre maggiori di popolazione a passare un tempo sempre minore all’interno del proprio alloggio, rende la riflessione sulle infrastrutture viarie dismesse o declassate occasione per la progettazione di spazi per l’abitare collettivo inseriti in contesti paesaggistici, tanto urbani che rurali, tramite reti di percorsi pensate per assorbire tagli di mobilità specifici e peculiari. Partendo da queste riflessioni la Tesi si articola in: Individuazioni del contesto teorico e pratico: Lo studio mette in evidenza come la questione delle infrastrutture viarie e del loro rapporto con il paesaggio implichi riflessioni incrociate a diversi livelli e tramite diverse discipline. La definizione dello spazio fisico della strada passa infatti per la costruzione di un itinerario, un viaggio che si appoggia tanto ad elementi fisici quanto simbolici. La via è un organismo complesso che travalica il proprio sedime per coinvolgere una porzione ampia di territorio, un corridoio variabile ed articolato in funzione del paesaggio attraversato. Lo studio propone diverse chiavi di lettura, mettendo in luce le possibili declinazioni del tema, in funzione del taglio modale, del rapporto con il contesto, del regime giuridico, delle implicazioni urbanistiche e sociali. La mobilità dolce viene individuata quale possibile modalità di riuso, tutela e recupero, del patrimonio diffuso costituito dalle diversi reti di viabilità. Antologia di casi studio: Il corpo principale dello studio si basa sulla raccolta, analisi e studio dello stato dell’arte nel settore; gli esempi raccolti sono presentati in due sezioni: la prima dedicata alle esperienze più significative ed articolate, che affrontano il recupero delle infrastrutture viarie a più livelli ed in modo avanzato non concentrandosi solo sulla conversione del sedime, ma proponendo un progetto che coinvolga tutto il corridoio attraversato dall’infrastruttura; la seconda parte illustra la pratica corrente nelle diverse realtà nazionali, ponendo in evidenza similitudini e differenze tra i vari approcci.

Fast formulas for computing cryptographic pairings

The most powerful known primitive in public-key cryptography is undoubtedly elliptic curve pairings. Upon their introduction just over ten years ago the computation of pairings was far too slow for them to be considered a practical option. This resulted in a vast amount of research from many mathematicians and computer scientists around the globe aiming to improve this computation speed. From the use of modern results in algebraic and arithmetic geometry to the application of foundational number theory that dates back to the days of Gauss and Euler, cryptographic pairings have since experienced a great deal of improvement. As a result, what was an extremely expensive computation that took several minutes is now a high-speed operation that takes less than a millisecond. This thesis presents a range of optimisations to the state-of-the-art in cryptographic pairing computation. Both through extending prior techniques, and introducing several novel ideas of our own, our work has contributed to recordbreaking pairing implementations.

Are we there yet? Early years reform in Queensland : stakeholder perspectives on the introduction of funded preschool programs in long day care services

Australian educators are currently engaging with wide-ranging, national early childhood reform that is reshaping early childhood education and care. The Australian reform agenda reflects many of the early childhood policy directions championed by bodies such as the Organisation for Economic Cooperation and Development and the United Nations Children's Education Fund, and is based on the dual discourse of (i) starting strong and (ii) investing in the early years. However, despite its traction in policy rhetoric and policy there is little empirical evidence of how reform is being played out. This paper reports on research undertaken in collaboration with the Queensland Office for Early Childhood Education and Care to generate sector feedback on one element of the reform agenda, the implementation of universal preschool in Queensland. The study aimed to determine the efficacy of the new policy in supporting the provision of 'approved preschool programs' within long day care services. Drawing together the views and experiences of a range of stakeholders, including peak organisations, service providers, directors, preschool teachers and government policy officers, it provides a situated case study of the implementation of universal preschool, and offers empirical evidence of how this policy is being played out at the local level. The paper identifies the opportunities and challenges in implementing universal preschool in Queensland that may have bearing on early childhood reform in Australia as well as other countries. Discussion of key findings is set within an overview of the ECEC policy agenda in Australia, with a particular focus on the commitment to universal preschool. Les éducateurs australiens s’engagent présentement dans une vaste réforme nationale de la petite enfance qui remodèle l'éducation et l’accueil de la petite enfance. Le programme de la réforme australienne reflète plusieurs des orientations en politique de la petite enfance soutenues par des organismes comme l'Organisation de coopération et de développement économiques (OCDE) et le Fonds des Nations Unies pour les enfants (UNICEF). Il s’appuie sur le double discours de (i) un bon départ et de (ii) l’investissement dans les premières années. Cependant, en dépit de son attrait en rhétorique de politique et en politique il y a peu de données empiriques sur la façon dont la réforme se déroule. Cet article rend compte de la recherche entreprise en collaboration avec le bureau de l'éducation et l’accueil à la petite enfance du Queensland afin d’obtenir une rétroaction du secteur sur un élément de la réforme, la mise sur pied du préscolaire universel dans le Queensland. L'étude visait à déterminer l'efficacité de la nouvelle politique pour soutenir la disposition «programmes préscolaires approuvés» dans les services de garde à temps plein. En regroupant les perspectives et les expériences d'une gamme d’intervenants, y compris d’importantes organisations, des prestataires de service, des directeurs, des enseignants du préscolaire et des fonctionnaires de politique gouvernementale, elle constitue une étude de cas localisée de l'exécution la mise sur pied du préscolaire universel, et fournit des données empiriques sur la façon dont cette politique se met en place au niveau local. L’article identifie les opportunités et les défis liés à l’implantation du préscolaire universel au Queensland, qui pourraient avoir une portée sur la réforme de petite enfance en Australie ainsi que dans d'autres pays. La discussion des principaux résultats est faite en lien avec un aperçu global de la politique d'éducation et d’accueil de la petite enfance en Australie, avec un accent particulier sur l'engagement envers le préscolaire universel. Los educadores australianos actualmente están involucrados en una amplia reforma de la educación temprana nacional que está revolucionando la educación preescolar y los servicios de cuidado. El programa de reforma Australiana refleja muchas de las direcciones políticas relacionadas con la infancia temprana incitadas por organismos como la Organización de Cooperación y Desarrollo Económicos y el Fondo Educacional Infantil de las Naciones Unidas, y se basa en el doble discurso de (i) empezando fuertemente e (ii) invertir en los primeros años. Sin embargo, a pesar de su política de tracción en retórica y política, hay pocos datos empíricos de cómo la reforma se está llevando a cabo. Este documento informa sobre las investigaciones llevadas a cabo en colaboración con la Oficina de Queensland de Educación tempana y cuidados, para generar comentarios del sector, sobre uno de los elementos de la agenda de reforma, la aplicación del preescolar universal en Queensland. El estudio tiene como objetivo determinar la eficacia de la nueva política para apoyar la prestación de "programas preescolares aprovados" dentro se los servicios de guardería y cuidado. Reuniendo los puntos de vista y las experiencias de una serie de interesados, entre ellos algunas organizaciones cumbre, proveedores de servicios, los directores, los maestros preescolares y oficiales de política y gobierno, se logra un estudio simulado de la implementación del preescolar universal, y ofrece evidencia empírica de cómo esta política se está llevando a cabo en el plano local. El documento identifica las oportunidades y desafíos en la implementación del preescolar universal en Queensland, que puede repercutir en la reforma de la indancia temprana en Australia, así como en otros países. La discusión de los resultados claves se encuentra en el interior de una visión de la agenda política de ECEC en Australia, con un enfoque particular en el compromiso con el preescolar universal.