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.

Modelling urban public transit users’ route choice behaviour : a review and outlook

Public transport is one of the key promoters of sustainable urban transport. To encourage and increase public transport patronage it is important to investigate the route choice behaviours of urban public transit users. This chapter reviews the main developments of modelling urban public transit users’ route choice behaviours in a historical perspective, from the 1960s to the present time. The approaches re- viewed for this study include the early heuristic studies on finding the least-cost transit route and all-or- nothing transit assignment, the bus common lines problem, the disaggregate discrete choice models, the deterministic and stochastic user equilibrium transit assignment models, and the recent dynamic transit assignment models. This chapter also provides an outlook for the future directions of modelling transit users’ route choice behaviours. Through the comparison with the development of models for motorists’ route choice and traffic assignment problems, this chapter advocates that transit route choice research should draw inspiration from the research outcomes from the road area, and that the modelling practice of transit users’ route choice should further explore the behavioural complexities.

Public awareness of “green” and “energy efficient” residential property : an empirical survey based on data from New Zealand

Purpose – The purpose of this paper is to examine the buyer awareness and acceptance of environmental and energy efficiency measures in the New Zealand residential property markets. This study aims to provide a greater understanding of consumer behaviour in the residential property market in relation to green housing issues ---------- Design/methodology/approach – The paper is based on an extensive survey of Christchurch real estate offices and was designed to gather data on the factors that were considered important by buyers in the residential property market. The survey was designed to allow these factors to be analysed on a socio-economic basis and to compare buyer behaviour based on property values. ---------- Findings – The results show that regardless of income levels, buyers still consider that the most important factor in the house purchase decision is the location of the property and price. Although the awareness of green housing issues and energy efficiency in housing is growing in the residential property market, it is only a major consideration for young and older buyers in the high income brackets and is only of some importance for all other buyer sectors of the residential property market. Many of the voluntary measures introduced by Governments to improve the energy efficiency of residential housing are still not considered important by buyers, indicating that a more mandatory approach may have to be undertaken to improve energy efficiency in the established housing market, as these measures are not valued by the buyer. ---------- Originality/value – The paper confirms the variations in real estate buyer behaviour across the full range of residential property markets and the acceptance and awareness of green housing issues and measures. These results would be applicable to most established and transparent residential property markets.

Poster abstract : Energy-efficient rate adaptive MAC Protocol (RA-MAC) for long-lived sensor networks

This paper introduces an energy-efficient Rate Adaptive MAC (RA-MAC) protocol for long-lived Wireless Sensor Networks (WSN). Previous research shows that the dynamic and lossy nature of wireless communication is one of the major challenges to reliable data delivery in a WSN. RA-MAC achieves high link reliability in such situations by dynamically trading off radio bit rate for signal processing gain. This extra gain reduces the packet loss rate which results in lower energy expenditure by reducing the number of retransmissions. RA-MAC selects the optimal data rate based on channel conditions with the aim of minimizing energy consumption. We have implemented RA-MAC in TinyOS on an off-the-shelf sensor platform (TinyNode), and evaluated its performance by comparing RA-MAC with state-ofthe- art WSN MAC protocol (SCP-MAC) by experiments.

ERTP : Energy-efficient and reliable transport protocol for data streaming in wireless sensor networks

Emerging data streaming applications in Wireless Sensor Networks require reliable and energy-efficient Transport Protocols. Our recent Wireless Sensor Network deployment in the Burdekin delta, Australia, for water monitoring [T. Le Dinh, W. Hu, P. Sikka, P. Corke, L. Overs, S. Brosnan, Design and deployment of a remote robust sensor network: experiences from an outdoor water quality monitoring network, in: Second IEEE Workshop on Practical Issues in Building Sensor Network Applications (SenseApp 2007), Dublin, Ireland, 2007] is one such example. This application involves streaming sensed data such as pressure, water flow rate, and salinity periodically from many scattered sensors to the sink node which in turn relays them via an IP network to a remote site for archiving, processing, and presentation. While latency is not a primary concern in this class of application (the sampling rate is usually in terms of minutes or hours), energy-efficiency is. Continuous long-term operation and reliable delivery of the sensed data to the sink are also desirable. This paper proposes ERTP, an Energy-efficient and Reliable Transport Protocol for Wireless Sensor Networks. ERTP is designed for data streaming applications, in which sensor readings are transmitted from one or more sensor sources to a base station (or sink). ERTP uses a statistical reliability metric which ensures the number of data packets delivered to the sink exceeds the defined threshold. Our extensive discrete event simulations and experimental evaluations show that ERTP is significantly more energyefficient than current approaches and can reduce energy consumption by more than 45% when compared to current approaches. Consequently, sensor nodes are more energy-efficient and the lifespan of the unattended WSN is increased.

Efficient certificateless KEM in the standard model

We give a direct construction of a certificateless key encapsulation mechanism (KEM) in the standard model that is more efficient than the generic constructions proposed before by Huang and Wong \cite{DBLP:conf/acisp/HuangW07}. We use a direct construction from Kiltz and Galindo's KEM scheme \cite{DBLP:conf/acisp/KiltzG06} to obtain a certificateless KEM in the standard model; our construction is roughly twice as efficient as the generic construction. We also address the security flaw discovered by Selvi et al. \cite{cryptoeprint:2009:462}.

Pathogenicity of Plesiomonas shigelloides : interactions with eukaryotic host cells in vitro

Diarrhoea is one of the leading causes of morbidity and mortality in populations in developing countries and is a significant health issue throughout the world. Despite the frequency and the severity of the diarrhoeal disease, mechanisms of pathogenesis for many of the causative agents have been poorly characterised. Although implicated in a number of intestinal and extra-intestinal infections in humans, Plesiomonas shigelloides generally has been dismissed as an enteropathogen due to the lack of clearly demonstrated virulence-associated properties such as production of cytotoxins and enterotoxins or invasive abilities. However, evidence from a number of sources has indicated that this species may be the cause of a number of clinical infections. The work described in this thesis seeks to resolve this discrepancy by investigating the pathogenic potential of P. shigelloides using in vitro cell models. The focus of this research centres on how this organism interacts with human host cells in an experimental model. Very little is known about the pathogenic potential of P. shigel/oides and its mechanisms in human infections and disease. However, disease manifestations mimic those of other related microorganisms. Chapter 2 reviews microbial pathogenesis in general, with an emphasis on understanding the mechanisms resulting from infection with bacterial pathogens and the alterations in host cell biology. In addition, this review analyses the pathogenic status of a poorly-defined enteropathogen, P. shigelloides. Key stages of pathogenicity must occur in order for a bacterial pathogen to cause disease. Such stages include bacterial adherence to host tissue, bacterial entry into host tissues (usually required), multiplication within host tissues, evasion of host defence mechanisms and the causation of damage. In this study, these key strategies in infection and disease were sought to help assess the pathogenic potential of P. shigelloides (Chapter 3). Twelve isolates of P. shigelloides, obtained from clinical cases of gastroenteritis, were used to infect monolayers of human intestinal epithelial cells in vitro. Ultrastructural analysis demonstrated that P. shigelloides was able to adhere to the microvilli at the apical surface of the epithelial cells and also to the plasma membranes of both apical and basal surfaces. Furthermore, it was demonstrated that these isolates were able to enter intestinal epithelial cells. Internalised bacteria often were confined within vacuoles surrounded by single or multiple membranes. Observation of bacteria within membranebound vacuoles suggests that uptake of P. shigelloides into intestinal epithelial cells occurs via a process morphologically comparable to phagocytosis. Bacterial cells also were observed free in the host cell cytoplasm, indicating that P. shige/loides is able to escape from the surrounding vacuolar membrane and exist within the cytosol of the host. Plesiomonas shigelloides has not only been implicated in gastrointestinal infections, but also in a range of non-intestinal infections such as cholecystitis, proctitis, septicaemia and meningitis. The mechanisms by which P. shigelloides causes these infections are not understood. Previous research was unable to ascertain the pathogenic potential of P. shigel/oides using cells of non-intestinal origin (HEp-2 cells derived from a human larynx carcinoma and Hela cells derived from a cervical carcinoma). However, with the recent findings (from this study) that P. shigelloides can adhere to and enter intestinal cells, it was hypothesised, that P. shigel/oides would be able to enter Hela and HEp-2 cells. Six clinical isolates of P. shigelloides, which previously have been shown to be invasive to intestinally derived Caco-2 cells (Chapter 3) were used to study interactions with Hela and HEp-2 cells (Chapter 4). These isolates were shown to adhere to and enter both nonintestinal host cell lines. Plesiomonas shigelloides were observed within vacuoles surrounded by single and multiple membranes, as well as free in the host cell cytosol, similar to infection by P. shigelloides of Caco-2 cells. Comparisons of the number of bacteria adhered to and present intracellularly within Hela, HEp-2 and Caco-2 cells revealed a preference of P. shigelloides for Caco-2 cells. This study conclusively showed for the first time that P. shigelloides is able to enter HEp-2 and Hela cells, demonstrating the potential ability to cause an infection and/or disease of extra-intestinal sites in humans. Further high resolution ultrastructural analysis of the mechanisms involved in P. shigelloides adherence to intestinal epithelial cells (Chapter 5) revealed numerous prominent surface features which appeared to be involved in the binding of P. shige/loides to host cells. These surface structures varied in morphology from small bumps across the bacterial cell surface to much longer filaments. Evidence that flagella might play a role in bacterial adherence also was found. The hypothesis that filamentous appendages are morphologically expressed when in contact with host cells also was tested. Observations of bacteria free in the host cell cytosol suggests that P. shigelloides is able to lyse free from the initial vacuolar compartment. The vacuoles containing P. shigel/oides within host cells have not been characterised and the point at which P. shigelloides escapes from the surrounding vacuolar compartment has not been determined. A cytochemical detection assay for acid phosphatase, an enzymatic marker for lysosomes, was used to analyse the co-localisation of bacteria-containing vacuoles and acid phosphatase activity (Chapter 6). Acid phosphatase activity was not detected in these bacteria-containing vacuoles. However, the surface of many intracellular and extracellular bacteria demonstrated high levels of acid phosphatase activity, leading to the proposal of a new virulence factor for P. shigelloides. For many pathogens, the efficiency with which they adhere to and enter host cells is dependant upon the bacterial phase of growth. Such dependency reflects the timing of expression of particular virulence factors important for bacterial pathogenesis. In previous studies (Chapter 3 to Chapter 6), an overnight culture of P. shigelloides was used to investigate a number of interactions, however, it was unknown whether this allowed expression of bacterial factors to permit efficient P. shigelloides attachment and entry into human cells. In this study (Chapter 7), a number of clinical and environmental P. shigelloides isolates were investigated to determine whether adherence and entry into host cells in vitro was more efficient during exponential-phase or stationary-phase bacterial growth. An increase in the number of adherent and intracellular bacteria was demonstrated when bacteria were inoculated into host cell cultures in exponential phase cultures. This was demonstrated clearly for 3 out of 4 isolates examined. In addition, an increase in the morphological expression of filamentous appendages, a suggested virulence factor for P. shigel/oides, was observed for bacteria in exponential growth phase. These observations suggest that virulence determinants for P. shigel/oides may be more efficiently expressed when bacteria are in exponential growth phase. This study demonstrated also, for the first time, that environmental water isolates of P. shigelloides were able to adhere to and enter human intestinal cells in vitro. These isolates were seen to enter Caco-2 host cells through a process comparable to the clinical isolates examined. These findings support the hypothesis of a water transmission route for P. shigelloides infections. The results presented in this thesis contribute significantly to our understanding of the pathogenic mechanisms involved in P. shigelloides infections and disease. Several of the factors involved in P. shigelloides pathogenesis have homologues in other pathogens of the human intestine, namely Vibrio, Aeromonas, Salmonella, Shigella species and diarrhoeaassociated strains of Escherichia coli. This study emphasises the relevance of research into Plesiomonas as a means of furthering our understanding of bacterial virulence in general. As well it provides tantalising clues on normal and pathogenic host cell mechanisms.

Computationally efficient numerical methods for time- and space-fractional Fokker–Planck equations

Fractional Fokker–Planck equations have been used to model several physical situations that present anomalous diffusion. In this paper, a class of time- and space-fractional Fokker–Planck equations (TSFFPE), which involve the Riemann–Liouville time-fractional derivative of order 1-α (α(0, 1)) and the Riesz space-fractional derivative (RSFD) of order μ(1, 2), are considered. The solution of TSFFPE is important for describing the competition between subdiffusion and Lévy flights. However, effective numerical methods for solving TSFFPE are still in their infancy. We present three computationally efficient numerical methods to deal with the RSFD, and approximate the Riemann–Liouville time-fractional derivative using the Grünwald method. The TSFFPE is then transformed into a system of ordinary differential equations (ODE), which is solved by the fractional implicit trapezoidal method (FITM). Finally, numerical results are given to demonstrate the effectiveness of these methods. These techniques can also be applied to solve other types of fractional partial differential equations.

Transit users' route-choice modelling in transit assignment : a review

This paper reviews the main studies on transit users’ route choice in thecontext of transit assignment. The studies are categorized into three groups: static transit assignment, within-day dynamic transit assignment, and emerging approaches. The motivations and behavioural assumptions of these approaches are re-examined. The first group includes shortest-path heuristics in all-or-nothing assignment, random utility maximization route-choice models in stochastic assignment, and user equilibrium based assignment. The second group covers within-day dynamics in transit users’ route choice, transit network formulations, and dynamic transit assignment. The third group introduces the emerging studies on behavioural complexities, day-to-day dynamics, and real-time dynamics in transit users’ route choice. Future research directions are also discussed.

Bayesian multinomial logit: Theory and route choice example

Statisticians along with other scientists have made significant computational advances that enable the estimation of formerly complex statistical models. The Bayesian inference framework combined with Markov chain Monte Carlo estimation methods such as the Gibbs sampler enable the estimation of discrete choice models such as the multinomial logit (MNL) model. MNL models are frequently applied in transportation research to model choice outcomes such as mode, destination, or route choices or to model categorical outcomes such as crash outcomes. Recent developments allow for the modification of the potentially limiting assumptions of MNL such as the independence from irrelevant alternatives (IIA) property. However, relatively little transportation-related research has focused on Bayesian MNL models, the tractability of which is of great value to researchers and practitioners alike. This paper addresses MNL model specification issues in the Bayesian framework, such as the value of including prior information on parameters, allowing for nonlinear covariate effects, and extensions to random parameter models, so changing the usual limiting IIA assumption. This paper also provides an example that demonstrates, using route-choice data, the considerable potential of the Bayesian MNL approach with many transportation applications. This paper then concludes with a discussion of the pros and cons of this Bayesian approach and identifies when its application is worthwhile