Algebraic analysis of small scale LEX-BES

This paper examines the algebraic cryptanalysis of small scale variants of the LEX-BES. LEX-BES is a stream cipher based on the Advanced Encryption Standard (AES) block cipher. LEX is a generic method proposed for constructing a stream cipher from a block cipher, initially introduced by Biryukov at eSTREAM, the ECRYPT Stream Cipher project in 2005. The Big Encryption System (BES) is a block cipher introduced at CRYPTO 2002 which facilitates the algebraic analysis of the AES block cipher. In this paper, experiments were conducted to find solution of the equation system describing small scale LEX-BES using Gröbner Basis computations. This follows a similar approach to the work by Cid, Murphy and Robshaw at FSE 2005 that investigated algebraic cryptanalysis on small scale variants of the BES. The difference between LEX-BES and BES is that due to the way the keystream is extracted, the number of unknowns in LEX-BES equations is fewer than the number in BES. As far as the author knows, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.

Algebraic analysis of small Scale LEX-BES

This work examines the algebraic cryptanalysis of small scale variants of the LEX-BES. LEX-BES is a stream cipher based on the Advanced Encryption Standard (AES) block cipher. LEX is a generic method proposed for constructing a stream cipher from a block cipher, initially introduced by Biryukov at eSTREAM, the ECRYPT Stream Cipher project in 2005. The Big Encryption System (BES) is a block cipher introduced at CRYPTO 2002 which facilitates the algebraic analysis of the AES block cipher. In this article, experiments were conducted to find solutions of equation systems describing small scale LEX-BES using Gröbner Basis computations. This follows a similar approach to the work by Cid, Murphy and Robshaw at FSE 2005 that investigated algebraic cryptanalysis on small scale variants of the BES. The difference between LEX-BES and BES is that due to the way the keystream is extracted, the number of unknowns in LEX-BES equations is fewer than the number in BES. As far as the authors know, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.

Analysis of nonlinear sequences and streamciphers

Streamciphers are common cryptographic algorithms used to protect the confidentiality of frame-based communications like mobile phone conversations and Internet traffic. Streamciphers are ideal cryptographic algorithms to encrypt these types of traffic as they have the potential to encrypt them quickly and securely, and have low error propagation. The main objective of this thesis is to determine whether structural features of keystream generators affect the security provided by stream ciphers.These structural features pertain to the state-update and output functions used in keystream generators. Using linear sequences as keystream to encrypt messages is known to be insecure. Modern keystream generators use nonlinear sequences as keystream.The nonlinearity can be introduced through a keystream generator's state-update function, output function, or both. The first contribution of this thesis relates to nonlinear sequences produced by the well-known Trivium stream cipher. Trivium is one of the stream ciphers selected in a final portfolio resulting from a multi-year project in Europe called the ecrypt project. Trivium's structural simplicity makes it a popular cipher to cryptanalyse, but to date, there are no attacks in the public literature which are faster than exhaustive keysearch. Algebraic analyses are performed on the Trivium stream cipher, which uses a nonlinear state-update and linear output function to produce keystream. Two algebraic investigations are performed: an examination of the sliding property in the initialisation process and algebraic analyses of Trivium-like streamciphers using a combination of the algebraic techniques previously applied separately by Berbain et al. and Raddum. For certain iterations of Trivium's state-update function, we examine the sets of slid pairs, looking particularly to form chains of slid pairs. No chains exist for a small number of iterations.This has implications for the period of keystreams produced by Trivium. Secondly, using our combination of the methods of Berbain et al. and Raddum, we analysed Trivium-like ciphers and improved on previous on previous analysis with regards to forming systems of equations on these ciphers. Using these new systems of equations, we were able to successfully recover the initial state of Bivium-A.The attack complexity for Bivium-B and Trivium were, however, worse than exhaustive keysearch. We also show that the selection of stages which are used as input to the output function and the size of registers which are used in the construction of the system of equations affect the success of the attack. The second contribution of this thesis is the examination of state convergence. State convergence is an undesirable characteristic in keystream generators for stream ciphers, as it implies that the effective session key size of the stream cipher is smaller than the designers intended. We identify methods which can be used to detect state convergence. As a case study, theMixer streamcipher, which uses nonlinear state-update and output functions to produce keystream, is analysed. Mixer is found to suffer from state convergence as the state-update function used in its initialisation process is not one-to-one. A discussion of several other streamciphers which are known to suffer from state convergence is given. From our analysis of these stream ciphers, three mechanisms which can cause state convergence are identified.The effect state convergence can have on stream cipher cryptanalysis is examined. We show that state convergence can have a positive effect if the goal of the attacker is to recover the initial state of the keystream generator. The third contribution of this thesis is the examination of the distributions of bit patterns in the sequences produced by nonlinear filter generators (NLFGs) and linearly filtered nonlinear feedback shift registers. We show that the selection of stages used as input to a keystream generator's output function can affect the distribution of bit patterns in sequences produced by these keystreamgenerators, and that the effect differs for nonlinear filter generators and linearly filtered nonlinear feedback shift registers. In the case of NLFGs, the keystream sequences produced when the output functions take inputs from consecutive register stages are less uniform than sequences produced by NLFGs whose output functions take inputs from unevenly spaced register stages. The opposite is true for keystream sequences produced by linearly filtered nonlinear feedback shift registers.

Membrane associated transporter protein gene (SLC45A2) and the genetic basis of normal human pigmentation variation

This work is concerned with the genetic basis of normal human pigmentation variation. Specifically, the role of polymorphisms within the solute carrier family 45 member 2 (SLC45A2 or membrane associated transporter protein; MATP) gene were investigated with respect to variation in hair, skin and eye colour ― both between and within populations. SLC45A2 is an important regulator of melanin production and mutations in the gene underly the most recently identified form of oculocutaneous albinism. There is evidence to suggest that non-synonymous polymorphisms in SLC45A2 are associated with normal pigmentation variation between populations. Therefore, the underlying hypothesis of this thesis is that polymorphisms in SLC45A2 will alter the function or regulation of the protein, thereby altering the important role it plays in melanogenesis and providing a mechanism for normal pigmentation variation. In order to investigate the role that SLC45A2 polymorphisms play in human pigmentation variation, a DNA database was established which collected pigmentation phenotypic information and blood samples of more than 700 individuals. This database was used as the foundation for two association studies outlined in this thesis, the first of which involved genotyping two previously-described non-synonymous polymorphisms, p.Glu272Lys and p.Phe374Leu, in four different population groups. For both polymorphisms, allele frequencies were significantly different between population groups and the 272Lys and 374Leu alleles were strongly associated with black hair, brown eyes and olive skin colour in Caucasians. This was the first report to show that SLC45A2 polymorphisms were associated with normal human intra-population pigmentation variation. The second association study involved genotyping several SLC45A2 promoter polymorphisms to determine if they also played a role in pigmentation variation. Firstly, the transcription start site (TSS), and hence putative proximal promoter region, was identified using 5' RNA ligase mediated rapid amplification of cDNA ends (RLM-RACE). Two alternate TSSs were identified and the putative promoter region was screened for novel polymorphisms using denaturing high performance liquid chromatography (dHPLC). A novel duplication (c.–1176_–1174dupAAT) was identified along with other previously described single nucleotide polymorphisms (c.–1721C>G and c.–1169G>A). Strong linkage disequilibrium ensured that all three polymorphisms were associated with skin colour such that the –1721G, +dup and –1169A alleles were associated with olive skin in Caucasians. No linkage disequilibrium was observed between the promoter and coding region polymorphisms, suggesting independent effects. The association analyses were complemented with functional data, showing that the –1721G, +dup and –1169A alleles significantly decreased SLC45A2 transcriptional activity. Based on in silico bioinformatic analysis that showed these alleles remove a microphthalmia-associated transcription factor (MITF) binding site, and that MITF is a known regulator of SLC45A2 (Baxter and Pavan, 2002; Du and Fisher, 2002), it was postulated that SLC45A2 promoter polymorphisms could contribute to the regulation of pigmentation by altering MITF binding affinity. Further characterisation of the SLC45A2 promoter was carried out using luciferase reporter assays to determine the transcriptional activity of different regions of the promoter. Five constructs were designed of increasing length and their promoter activity evaluated. Constitutive promoter activity was observed within the first ~200 bp and promoter activity increased as the construct size increased. The functional impact of the –1721G, +dup and –1169A alleles, which removed a MITF consensus binding site, were assessed using electrophoretic mobility shift assays (EMSA) and expression analysis of genotyped melanoblast and melanocyte cell lines. EMSA results confirmed that the promoter polymorphisms affected DNA-protein binding. Interestingly, however, the protein/s involved were not MITF, or at least MITF was not the protein directly binding to the DNA. In an effort to more thoroughly characterise the functional consequences of SLC45A2 promoter polymorphisms, the mRNA expression levels of SLC45A2 and MITF were determined in melanocyte/melanoblast cell lines. Based on SLC45A2’s role in processing and trafficking TYRP1 from the trans-Golgi network to stage 2 melanosmes, the mRNA expression of TYRP1 was also investigated. Expression results suggested a coordinated expression of pigmentation genes. This thesis has substantially contributed to the field of pigmentation by showing that SLC45A2 polymorphisms not only show allele frequency differences between population groups, but also contribute to normal pigmentation variation within a Caucasian population. In addition, promoter polymorphisms have been shown to have functional consequences for SLC45A2 transcription and the expression of other pigmentation genes. Combined, the data presented in this work supports the notion that SLC45A2 is an important contributor to normal pigmentation variation and should be the target of further research to elucidate its role in determining pigmentation phenotypes. Understanding SLC45A2’s function may lead to the development of therapeutic interventions for oculocutaneous albinism and other disorders of pigmentation. It may also help in our understanding of skin cancer susceptibility and evolutionary adaptation to different UV environments, and contribute to the forensic application of pigmentation phenotype prediction.

The genetic basis of human height : the role of estrogen

Height is a complex physical trait that displays strong heritability. Adult height is related to length of the long bones, which is determined by growth at the epiphyseal growth plate. Longitudinal bone growth occurs via the process of endochondral ossification, where bone forms over the differentiating cartilage template at the growth plate. Estrogen plays a major role in regulating longitudinal bone growth and is responsible for inducing the pubertal growth spurt and fusion of the epiphyseal growth plate. However, the mechanism by which estrogen promotes epiphyseal fusion is poorly understood. It has been hypothesised that estrogen functions to regulate growth plate fusion by stimulating chondrocyte apoptosis, angiogenesis and bone cell invasion in the growth plate. Another theory has suggested that estrogen exposure exhausts the proliferative capacity of growth plate chondrocytes, which accelerates the process of chondrocyte senescence, leading to growth plate fusion. The overall objective of this study was to gain a greater understanding of the molecular mechanisms behind estrogen-mediated growth and height attainment by examining gene regulation in chondrocytes and the role of some of these genes in normal height inheritance. With the heritability of height so well established, the initial hypothesis was that genetic variation in candidate genes associated with longitudinal bone growth would be involved in normal adult height variation. The height-related genes FGFR3, CBFA1, ER and CBFA1 were screened for novel polymorphisms using denaturing HPLC and RFLP analysis. In total, 24 polymorphisms were identified. Two SNPs in ER (rs3757323 C>T and rs1801132 G>C) were strongly associated with adult male height and displayed an 8 cm and 9 cm height difference between homozygous genotypes, respectively. The TC haplotype of these SNPs was associated with a 6 cm decrease in height and remarkably, no homozygous carriers of the TC haplotype were identified in tall subjects. No significant associations with height were found for polymorphisms in the FGFR3, CBFA1 or VDR genes. In the epiphyseal growth plate, chondrocyte proliferation, matrix synthesis and chondrocyte hypertrophy are all major contributors to long bone growth. As estrogen plays such a significant role in both growth and final height attainment, another hypothesis of this study was that estrogen exerted its effects in the growth plate by influencing chondrocyte proliferation and mediating the expression of chondrocyte marker genes. The examination of genes regulated by estrogen in chondrocyte-like cells aimed to identify potential regulators of growth plate fusion, which may further elucidate mechanisms involved in the cessation of linear growth. While estrogen did not dramatically alter the proliferation of the SW1353 cell line, gene expression experiments identified several estrogen regulated genes. Sixteen chondrocyte marker genes were examined in response to estrogen concentrations ranging from 10-12 M to 10-8 M over varying time points. Of the genes analysed, IHH, FGFR3, collagen II and collagen X were not readily detectable and PTHrP, GHR, ER, BMP6, SOX9 and TGF1 mRNAs showed no significant response to estrogen treatments. However, the expression of MMP13, CBFA1, BCL-2 and BAX genes were significantly decreased. Interestingly, the majority of estrogen regulated genes in SW1353 cells are expressed in the hypertrophic zone of the growth plate. Estrogen is also known to regulate systemic GH secretion and local GH action. At the molecular level, estrogen functions to inhibit GH action by negatively regulating GH signalling. GH treated SW1353 cells displayed increases in MMP9 mRNA expression (4.4-fold) and MMP13 mRNA expression (64-fold) in SW1353 cells. Increases were also detected in their respective proteins. Treatment with AG490, an established JAK2 inhibitor, blocked the GH mediated stimulation of both MMP9 and MMP13 mRNA expression. The application of estrogen and GH to SW1353 cells attenuated GH-stimulated MMP13 levels, but did not affect MMP9 levels. Investigation of GH signalling revealed that SW1353 cells have high levels of activated JAK2 and exposure to GH, estrogen, AG490 and other signalling inhibitors did not affect JAK2 phosphorylation. Interestingly, AG490 treatment dramatically decreased ERK2 signalling, although GH did stimulate ERK2 phosphorylation above control levels. AG490 also decreased CBFA1 expression, a transcription factor known to activate MMP9 and MMP13. Finally, GH and estrogen treatment increased expression of SOCS3 mRNA, suggesting that SOCS3 may regulate JAK/STAT signalling in SW1353 cells. The modulation of GH-mediated MMP expression by estrogen in SW1353 cells represents a potentially novel mechanism by which estrogen may regulate longitudinal bone growth. However, further investigation is required in order to elucidate the precise mechanisms behind estrogen and GH regulation of MMP13 expression in SW1353 cells. This study has provided additional evidence that estrogen and the ER gene are major factors in the regulation of growth and the determination of adult height. Newly identified polymorphisms in the ER gene not only contribute to our understanding of the genetic basis of human height, but may also be useful in association studies examining other complex traits. This study also identified several estrogen regulated genes and indicated that estrogen modifies the expression of genes which are primarily expressed in the hypertrophic region of the epiphyseal growth plate. Furthermore, synergistic studies incorporating GH and estrogen have revealed the ability of estrogen to attenuate the effects of GH on MMP13 expression, revealing potential pathways by which estrogen may modulate growth plate fusion, longitudinal bone growth and even arthritis.

A Reliable Basis for Approximate Association Rules

For most of the work done in developing association rule mining, the primary focus has been on the efficiency of the approach and to a lesser extent the quality of the derived rules has been emphasized. Often for a dataset, a huge number of rules can be derived, but many of them can be redundant to other rules and thus are useless in practice. The extremely large number of rules makes it difficult for the end users to comprehend and therefore effectively use the discovered rules and thus significantly reduces the effectiveness of rule mining algorithms. If the extracted knowledge can’t be effectively used in solving real world problems, the effort of extracting the knowledge is worth little. This is a serious problem but not yet solved satisfactorily. In this paper, we propose a concise representation called Reliable Approximate basis for representing non-redundant approximate association rules. We prove that the redundancy elimination based on the proposed basis does not reduce the belief to the extracted rules. We also prove that all approximate association rules can be deduced from the Reliable Approximate basis. Therefore the basis is a lossless representation of approximate association rules.