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.

Effects of dry density and grain size distribution on soil-water characteristic curves of sandy soils

The unsaturated soil mechanics is receiving increasing attention from researchers and as well as from practicing engineers. However, the requirement of sophisticated devices to measure unsaturated soil properties and time consumption have made the geotechnical engineers keep away from implication of the unsaturated soil mechanics for solving practical geotechnical problems. The application of the conventional laboratory devices with some modifications to measure unsaturated soil properties can promote the application of unsaturated soil mechanics into engineering practice. Therefore, in the present study, a conventional direct shear device was modified to measure unsaturated shear strength parameters at low suction. Specially, for the analysis of rain-induced slope failures, it is important to measure unsaturated shear strength parameters at low suction where slopes become unstable. The modified device was used to measure unsaturated shear strength of two silty soils at low suction values (0 ~ 50 kPa) that were achieved by following drying path and wetting path of soil-water characteristic curves (SWCCs) of soils. The results revealed that the internal friction angle of soil was not significantly affected by the suction and as well as the drying-wetting SWCCs of soils. The apparent cohesion of soil increased with a decreasing rate as the suction increased. Further, the apparent cohesion obtained from soil in wetting was greater than that obtained from soil in drying. Shear stress-shear displacement curves obtained from soil specimens subjected to the same net normal stress and different suction values showed a higher initial stiffness and a greater peak stress as the suction increased. In addition, it was observed that soil became more dilative with the increase of suction. A soil in wetting exhibited slightly higher peak shear stress and more contractive volume change behaviour than that of in drying at the same net normal stress and the suction.

Attractive subfamilies of BLS curves for implementing high-security pairings

Barreto-Lynn-Scott (BLS) curves are a stand-out candidate for implementing high-security pairings. This paper shows that particular choices of the pairing-friendly search parameter give rise to four subfami- lies of BLS curves, all of which offer highly efficient and implementation- friendly pairing instantiations. Curves from these particular subfamilies are defined over prime fields that support very efficient towering options for the full extension field. The coefficients for a specific curve and its correct twist are automat-ically determined without any computational effort. The choice of an extremely sparse search parameter is immediately reflected by a highly efficient optimal ate Miller loop and final exponentiation. As a resource for implementors, we give a list with examples of implementation-friendly BLS curves through several high-security levels.

Group law computations on Jacobians of hyperelliptic Curves

We derive an explicit method of computing the composition step in Cantor’s algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor’s general composition involves arithmetic in the polynomial ring F_q[x], the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of the group elements. We apply this method to give more efficient formulas for group operations in both affine and projective coordinates for cryptographic systems based on Jacobians of genus 2 hyperelliptic curves in general form.

An exploration of affine group laws for elliptic curves

Several forms of elliptic curves are suggested for an efficient implementation of Elliptic Curve Cryptography. However, a complete description of the group law has not appeared in the literature for most popular forms. This paper presents group law in affine coordinates for three forms of elliptic curves. With the existence of the proposed affine group laws, stating the projective group law for each form becomes trivial. This work also describes an automated framework for studying elliptic curve group law, which is applied internally when preparing this work.

Fire safety of buildings based on realistic fire time-temperature curves

In recent times, fire has become a major disaster in buildings due to the increase in fire loads, as a result of modern furniture and light weight construction. This has caused problems for safe evacuation and rescue activities, and in some instances lead to the collapse of buildings (Lewis, 2008 and Nyman, 2002). Recent research has shown that the actual fire resistance of building elements exposed to building fires can be less than their specified fire resistance rating (Lennon and Moore, 2003, Jones, 2002, Nyman, 2002 and Abecassis-Empis et al. 2008). Conventionally the fire rating of building elements is determined using fire tests based on the standard fire time-temperature curve given in ISO 834. This ISO 834 curve was developed in the early 1900s, where wood was the basic fuel source. In reality, modern buildings make use of thermoplastic materials, synthetic foams and fabrics. These materials are high in calorific values and increase both the speed of fire growth and heat release rate, thus increasing the fire severity beyond that of the standard fire curve. Hence it suggests the need to use realistic fire time-temperature curves in tests. Real building fire temperature profiles depend on the fuel load representing the combustible building contents, ventilation openings and thermal properties of wall lining materials. Fuel load is selected based on a review and suitable realistic fire time-temperature curves were developed. Fire tests were then performed for plasterboard lined light gauge steel framed walls for the developed realistic fire curves. This paper presents the details of the development of suitable realistic building fire curves, and the fire tests using them. It describes the fire performance of tested walls in comparison to the standard fire tests and highlights the differences between them. This research has shown the need to use realistic fire exposures in assessing the fire resistance rating of building elements.

Development of realistic design fire time-temperature curves for the testing of cold-formed steel wall system

Fire resistance rating of light gauge steel frame (LSF) wall systems is obtained from fire tests based on the standard fire time-temperature curve. However, fire severity has increased in modern buildings due to higher fuel loads as a result of modern furniture and light weight constructions that make use of thermoplastics materials, synthetic foams and fabrics. Some of these materials are high in calorific values and increase both the spread of fire growth and heat release rate, thus increasing the fire severity beyond that of the standard fire curve. Further, the standard fire curve does not include a decay phase that is present in natural fires. Despite the increasing usage of LSF walls, their behaviour in real building fires is not fully understood. This paper presents the details of a research study aimed at developing realistic design fire curves for use in the fire tests of LSF walls. It includes a review of the characteristics of building fires, previously developed fire time-temperature curves, computer models and available parametric equations. The paper highlights that real building fire time-temperature curves depend on the fuel load representing the combustible building contents, ventilation openings and thermal properties of wall lining materials, and provides suitable values of many required parameters including fuel loads in residential buildings. Finally, realistic design fire time-temperature curves simulating the fire conditions in modern residential buildings are proposed for the testing of LSF walls.

Meltdown : a tool to help in the interpretation of thermal melt curves acquired by differential scanning fluorimetry

The output of a differential scanning fluorimetry (DSF) assay is a series of melt curves, which need to be interpreted to get value from the assay. An application that translates raw thermal melt curve data into more easily assimilated knowledge is described. This program, called “Meltdown,” conducts four main activities—control checks, curve normalization, outlier rejection, and melt temperature (Tm) estimation—and performs optimally in the presence of triplicate (or higher) sample data. The final output is a report that summarizes the results of a DSF experiment. The goal of Meltdown is not to replace human analysis of the raw fluorescence data but to provide a meaningful and comprehensive interpretation of the data to make this useful experimental technique accessible to inexperienced users, as well as providing a starting point for detailed analyses by more experienced users.

Fire design rules for load bearing cold-formed steel frame walls exposed to realistic design fire curves

Light gauge Steel Frame (LSF) walls are extensively used in the building industry due to the many advantages they provide over other wall systems. Although LSF walls have been used widely, fire design of LSF walls is based on approximate prescriptive methods based on limited fire tests. Also these fire tests were conducted using the standard fire curve [1] and the applicability of available design rules to realistic design fire curves has not been verified. This paper investigates the accuracy of existing fire design rules in the current cold-formed steel standards and the modifications proposed by previous researchers. Of these the recently developed design rules by Gunalan and Mahendran [2] based on Eurocode 3 Part 1.3 [3] and AS/NZS 4600 [4] for standard fire exposure [1] were investigated in detail to determine their applicability to predict the axial compression strengths and fire resistance ratings of LSF walls exposed to realistic design fire curves. This paper also presents the fire performance results of LSF walls exposed to a range of realistic fire curves obtained using a finite element analysis based parametric study. The results from the parametric study were used to develop a simplified design method based on the critical hot flange temperature to predict the fire resistance ratings of LSF walls exposed to realistic fire curves. Finally, the stud failure times (fire resistance rating) obtained from the fire design rules and the simplified design method were compared with parametric study results for LSF walls lined with single and double plasterboards, and externally insulated with rock fibres under realistic fire curves.

Energy based time equivalent approach to determine the fire resistance ratings of light gauge steel frame walls exposed to realistic design fire curves

Structural fire safety has become one of the key considerations in the design and maintenance of the built infrastructure. Conventionally the fire resistance rating of load bearing Light gauge Steel Frame (LSF) walls is determined based on the standard time-temperature curve given in ISO 834. Recent research has shown that the true fire resistance of building elements exposed to building fires can be less than their fire resistance ratings determined based on standard fire tests. It is questionable whether the standard time-temperature curve truly represents the fuel loads in modern buildings. Therefore an equivalent fire severity approach has been used in the past to obtain fire resistance rating. This is based on the performance of a structural member exposed to a realistic design fire curve in comparison to that of standard fire time-temperature curve. This paper presents the details of research undertaken to develop an energy based time equivalent approach to obtain the fire resistance ratings of LSF walls exposed to realistic design fire curves with respect to standard fire exposure. This approach relates to the amount of energy transferred to the member. The proposed method was used to predict the fire resistance ratings of single and double layer plasterboard lined and externally insulated LSF walls. The predicted fire ratings were compared with the results from finite element analyses and fire design rules for three different wall configurations exposed to both rapid and prolonged fires. The comparison shows that the proposed energy method can be used to obtain the fire resistance ratings of LSF walls in the case of prolonged fires.

Equivariant Birch-Swinnerton-Dyer Conjecture for the Base Change of Elliptic Curves: An Example

Let E be an elliptic curve defined over Q and let K/Q be a finite Galois extension with Galois group G. The equivariant Birch-Swinnerton-Dyer conjecture for h(1)(E x(Q) K)(1) viewed as amotive over Q with coefficients in Q[G] relates the twisted L-values associated with E with the arithmetic invariants of the same. In this paper I prescribe an approach to verify this conjecture for a given data. Using this approach, we verify the conjecture for an elliptic curve of conductor 11 and an S-3-extension of Q.

Simplified dispersion curves for circular cylindrical shells using shallow shell theory.

An alternative derivation of the dispersion relation for the transverse vibration of a circular cylindrical shell is presented. The use of the shallow shell theory model leads to a simpler derivation of the same result. Further, the applicability of the dispersion relation is extended to the axisymmetric mode and the high frequency beam mode.