Computing and Information Systems - Theses

Permanent URI for this collection

Search Results

Now showing 1 - 2 of 2
  • Item
    Thumbnail Image
    Rapid de novo methods for genome analysis
    HALL, ROSS STEPHEN ( 2013)
    Next generation sequencing methodologies have resulted in an exponential increase in the amount of genomic sequence data available to researchers. Valuable tools in the initial analysis of such data for novel features are de novo techniques - methods which employ a minimum of comparative sequence information from known genomes. In this thesis I describe two heuristic algorithms for the rapid de novo analysis of genomic sequence data. The first algorithm employs a multiple Fast Fourier Transform, mapped to two dimensional spaces. The resulting bitmap clearly illustrates periodic features of a genome including coding density. The compact representation allows mega base scales of genomic data to be rendered in a single bitmap. The second algorithm RTASSS, (RNA Template Assisted Secondary Structure Search) predicts potential members of RNA gene families that are related by similar secondary structure, but not necessarily conserved sequence. RTASSS has the ability to find candidate structures similar to a given template structure without the use of sequence homology. Both algorithms have a linear complexity.
  • Item
    Thumbnail Image
    Efficient mixnets with application to electronic voting
    Ramchen, Kim ( 2013)
    Cryptographic mixnets are a fundamental tool in the construction of secure electronic elections. Traditional mixnets rely upon third party mixers to perform vote anonymisation at election time. This approach places inherent limitations on the robustness and efficiency of mixing. In this thesis we show that third party mixers are not required to be active at election time - in fact it is highly feasible for the shuffle to be constructed before the election. A basic primitive used is the public key obfuscator for a re-encryption shuffle. We show that the seminal obfuscator of Paillier shuffles by Adida and Wikstro ̈m [AW07a] can be extended to generalised Paillier shuffles [DJ01]. The resulting obfuscations are composable, allowing obfuscation of re-encryption permutation networks. This, in turn, implies an obfuscator for a Paillier shuffle with improved efficiency (N log^3.5 N vs. N^2). This leads to a very robust and efficient mixnet: when distributed over O(N) nodes the mixnet achieves mixing in polylogarithmic time, independent of the level of privacy or verifiability required. In fact, our mixnet is the first to achieve mixing in time sublinear in the number of inputs, assuming the number of nodes available is bounded by the number of inputs. Although the mixnet may have a biased distribution, we show that using particular networks leads to an acceptable bias-efficiency tradeoff. We additionally show that the mixnet is secure in the sense of indistinguishability of chosen permutations [NSNK04].