Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a keyed hash function. Our main motivation was to prove that universal hash functions can be employed as underlying primitives of MACs in order to provide provable security in ultra-low-power applications such as the next generation self-powered sensor networks. The idea of using a universal hash function (NH) was explored in the construction of UMAC. This work presents three variations on NH, namely PH, PR and WH. The first hash function we propose, PH, produces a hash of length 2w and is shown to be 2^(-w)-almost universal. The other two hash functions, i.e. PR and WH, reach optimality and are proven to be universal hash functions with half the hash length of w. In addition, these schemes are simple enough to allow for efficient constructions. To the best of our knowledge the proposed hash functions are the first ones specifically designed for low-power hardware implementations. We achieve drastic power savings of up to 59% and speedup of up to 7.4 times over NH. Note that the speed improvement and the power reduction are accomplished simultaneously. Moreover, we show how the technique of multi- hashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of key material. At low frequencies the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We develope formulae for estimation of leakage and dynamic power consumptions as well as energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. This enables us to optimize the hash function implementation for use in ultra-low-power applications such as "Smart Dust" motes, RFIDs, and Piconet nodes. Our simulation results indicate that the implementation of WH-16 consumes only 2.95 ìW 500 kHz. It can therefore be integrated into a self- powered device. By virtue of their security and implementation features mentioned above, we believe that the proposed universal hash functions fill an important gap in cryptographic hardware applications.

To protect against brute force attacks, modern password-based authentication systems usually employ mechanisms known as Password Hashing Schemes (PHS). Basically, a PHS is a cryptographic algorithm that generates a sequence of pseudorandom bits from a user-defined password, allowing the user to configure the computational costs involved in the process aiming to raise the costs of attackers testing multiple passwords trying to guess the correct one. Traditional schemes such as PBKDF2 and bcrypt, for example, include a configurable parameter that controls the number of iterations performed, allowing the user to adjust the time required by the password hashing process. The more recent scrypt and Lyra algorithms, on the other hand, allow users to control both processing time and memory usage. Despite these advances, there is still considerable interest by the research community in the development of new (and better) alternatives. Indeed, this led to the creation of a competition with this specific purpose, the Password Hashing Competition (PHC). In this context, the goal of this research effort is to propose a superior PHS alternative. Specifically, the objective is to improve the Lyra algorithm, a PHS built upon cryptographic sponges whose project counted with the authors\' participation. The resulting solution, called Lyra2, preserves the security, efficiency and flexibility of Lyra, including: the ability to configure the desired amount of memory and processing time to be used by the algorithm; and (2) the capacity of providing a high memory usage with a processing time similar to that obtained with scrypt. In addition, it brings important improvements when compared to its predecessor: (1) it allows a higher security level against attack venues involving time-memory trade-offs; (2) it includes tweaks for increasing the costs involved in the construction of dedicated hardware to attack the algorithm; (3) it balances resistance against side-channel threats and attacks relying on cheaper (and, hence, slower) storage devices. Besides describing the algorithm\'s design rationale in detail, this work also includes a detailed analysis of its security and performance in different platforms. It is worth mentioning that Lyra2, as hereby described, received a special recognition in the aforementioned PHC competition. / Para proteger-se de ataques de força bruta, sistemas modernos de autenticação baseados em senhas geralmente empregam algum Esquema de Hash de Senhas (Password Hashing Scheme - PHS). Basicamente, um PHS é um algoritmo criptográfico que gera uma sequência de bits pseudo-aleatórios a partir de uma senha provida pelo usuário, permitindo a este último configurar o custo computacional envolvido no processo e, assim, potencialmente elevar os custos de atacantes testando múltiplas senhas em paralelo. Esquemas tradicionais utilizados para esse propósito são o PBKDF2 e bcrypt, por exemplo, que incluem um parâmetro configurável que controla o número de iterações realizadas pelo algoritmo, permitindo ajustar-se o seu tempo total de processamento. Já os algoritmos scrypt e Lyra, mais recentes, permitem que usuários não apenas controlem o tempo de processamento, mas também a quantidade de memória necessária para testar uma senha. Apesar desses avanços, ainda há um interesse considerável da comunidade de pesquisa no desenvolvimento e avaliação de novas (e melhores) alternativas. De fato, tal interesse levou recentemente à criação de uma competição com esta finalidade específica, a Password Hashing Competition (PHC). Neste contexto, o objetivo do presente trabalho é propor uma alternativa superior aos PHS existentes. Especificamente, tem-se como alvo melhorar o algoritmo Lyra, um PHS baseado em esponjas criptográficas cujo projeto contou com a participação dos autores do presente trabalho. O algoritmo resultante, denominado Lyra2, preserva a segurança, eficiência e flexibilidade do Lyra, incluindo a habilidade de configurar do uso de memória e tempo de processamento do algoritmo, e também a capacidade de prover um uso de memória superior ao do scrypt com um tempo de processamento similar. Entretanto, ele traz importantes melhorias quando comparado ao seu predecessor: (1) permite um maior nível de segurança contra estratégias de ataque envolvendo trade-offs entre tempo de processamento e memória; (2) inclui a possibilidade de elevar os custos envolvidos na construção de plataformas de hardware dedicado para ataques contra o algoritmo; (3) e provê um equilíbrio entre resistância contra ataques de canal colateral (\"side-channel\") e ataques que se baseiam no uso de dispositivos de memória mais baratos (e, portanto, mais lentos) do que os utilizados em computadores controlados por usuários legítimos. Além da descrição detalhada do projeto do algoritmo, o presente trabalho inclui também uma análise detalhada de sua segurança e de seu desempenho em diferentes plataformas. Cabe notar que o Lyra2, conforme aqui descrito, recebeu uma menção de reconhecimento especial ao final da competição PHC previamente mencionada.

Systems that process big data (e.g., high-traffic networks and large-scale storage) prefer data structures and algorithms with small memory and fast processing speed. Efficient and fast algorithms play an essential role in system design, despite the improvement of hardware. This dissertation is organized around a novel algorithm called Othello Hashing. Othello Hashing supports ultra-fast and memory-efficient key-value lookup, and it fits the requirements of the core algorithms of many large-scale systems and big data applications. Using Othello hashing, combined with domain expertise in cloud, computer networks, big data, and bioinformatics, I developed the following applications that resolve several major challenges in the area. Concise: Forwarding Information Base. A Forwarding Information Base is a data structure used by the data plane of a forwarding device to determine the proper forwarding actions for packets. The polymorphic property of Othello Hashing the separation of its query and control functionalities, which is a perfect match to the programmable networks such as Software Defined Networks. Using Othello Hashing, we built a fast and scalable FIB named \textit{Concise}. Extensive evaluation results on three different platforms show that Concise outperforms other FIB designs. SDLB: Cloud Load Balancer. In a cloud network, the layer-4 load balancer servers is a device that acts as a reverse proxy and distributes network or application traffic across a number of servers. We built a software load balancer with Othello Hashing techniques named SDLB. SDLB is able to accomplish two functionalities of the SDLB using one Othello query: to find the designated server for packets of ongoing sessions and to distribute new or session-free packets. MetaOthello: Taxonomic Classification of Metagenomic Sequences. Metagenomic read classification is a critical step in the identification and quantification of microbial species sampled by high-throughput sequencing. Due to the growing popularity of metagenomic data in both basic science and clinical applications, as well as the increasing volume of data being generated, efficient and accurate algorithms are in high demand. We built a system to support efficient classification of taxonomic sequences using its k-mer signatures. SeqOthello: RNA-seq Sequence Search Engine. Advances in the study of functional genomics produced a vast supply of RNA-seq datasets. However, how to quickly query and extract information from sequencing resources remains a challenging problem and has been the bottleneck for the broader dissemination of sequencing efforts. The challenge resides in both the sheer volume of the data and its nature of unstructured representation. Using the Othello Hashing techniques, we built the SeqOthello sequence search engine. SeqOthello is a reference-free, alignment-free, and parameter-free sequence search system that supports arbitrary sequence query against large collections of RNA-seq experiments, which enables large-scale integrative studies using sequence-level data.

In modern computer systems, memory accesses and power management are the two major performance limiting factors. Accesses to main memory are very slow when compared to operations within a processor chip. Hardware write buffers, caches, out-of-order execution, and prefetch logic, are commonly used to reduce the time spent waiting for main memory accesses. Compiler loop interchange and data layout transformations also can help. Unfortunately, large data structures often have access patterns for which none of the standard approaches are useful. Using smaller data structures can significantly improve performance by allowing the data to reside in higher levels of the memory hierarchy. This dissertation proposes using lossy data compression technology called ’Compressive Hashing’ to create “surrogates”, that can augment original large data structures to yield faster typical data access. One way to optimize system performance for power consumption is to provide a predictive control of system-level energy use. This dissertation creates a novel instruction-level cost model called the variable-n-gram model, which is closely related to N-Gram analysis commonly used in computational linguistics. This model does not require direct knowledge of complex architectural details, and is capable of determining performance relationships between instructions from an execution trace. Experimental measurements are used to derive a context-sensitive model for performance of each type of instruction in the context of an N-instruction sequence. Dynamic runtime power prediction mechanisms often suffer from high overhead costs. To reduce the overhead, this dissertation encodes the static instruction-level predictions into a data structure and uses compressive hashing to provide on-demand runtime access to those predictions. Genetic programming is used to evolve compressive hash functions and performance analysis of applications shows that, runtime access overhead can be reduced by a factor of ~3x-9x.

Η παρούσα εργασία ασχολείται με τη μελέτη των τεχνολογιών ανάπτυξης εφαρμογών σε περιβάλλον φορητών συσκευών και συγκεκριμένα σε Windows Phone 7.5 (ή Mango) συσκευές. Ιδιαίτερα δόθηκε έμφαση στη δημιουργία πολυμεσικών εφαρμογών πολιτισμικού περιεχομένου, οι οποίες θα είναι όχι μόνο λειτουργικές αλλά θα διαθέτουν επίσης ένα φιλικό περιβάλλον διεπαφής έτσι ώστε να αποτελούν μια ευχάριστη εμπειρία για τον τελικό χρήστη. Με αφορμή αυτό το ερέθισμα, σχεδιάσαμε και αναπτύξαμε το Museum Guide – ένα ολοκληρωμένο περιβάλλον διαχείρισης περιεχομένου που έχει σαν στόχο την ξενάγηση σε ένα χώρο πολιτισμού, όπως για παράδειγμα ένα μουσείο, εκμεταλλευόμενο τις πολλές δυνατότητες που προσφέρει μια Windows Phone 7.5 συσκευή. Έτσι χρησιμοποιώντας το Museum Guide ο επισκέπτης του μουσείου μπορεί να βλέπει τα εκθέματα καθώς και συνοδευτικό υλικό που περιλαμβάνει κείμενο, εικόνες, αρχεία ήχου και βίντεο. Επιπλέον μπορεί να επιλέγει κάποια από αυτά τα εκθέματα ως αγαπημένα και να μοιράζεται τις εμπειρίες του με τα υπόλοιπα μέλη της ομάδας του μέσω άμεσων μηνυμάτων. Για τη λειτουργία των άμεσων μηνυμάτων δημιουργήσαμε έναν ενσωματωμένο messenger που λειτουργεί πάνω από xmpp πρωτόκολλο με τη βοήθεια της βιβλιοθήκης Matrix. Εκτός από τα παραπάνω, το Museum Guide δίνει τη δυνατότητα στον χρήστη να λάβει πληροφορίες για ένα συγκεκριμένο έκθεμα, βγάζοντας απλά μια φωτογραφία τού εν λόγω εκθέματος με την κάμερα του κινητού. Την λειτουργία αυτή την ονομάζουμε on-demand ξενάγηση και δόθηκε ιδιαίτερη έμφαση στον αλγόριθμο με βάση τον οποίο γίνεται η αναγνώριση της φωτογραφίας που βγάζει ο χρήστης. Για το σκοπό αυτό μελετήσαμε και αξιολογήσαμε διάφορους αλγορίθμους αναγνώρισης εικόνας και καταλήξαμε στη χρήση hashing τεχνικών με τη βοήθεια της βιβλιοθήκης pHash. / The current thesis is on study of application development technologies in portable devices environment and namely in Windows Phone 7.5 (or Mango) devices. Especially emphasis was placed on creation of multimedia applications with cultural content which will not only be functional but also have a friendly interface in order to be a pleasant experience for the end user. In response to this stimulus, we designed and developed the Museum Guide – an integrated content management environment which aims at guidance in an area of culture, for example a museum, exploiting the capabilities of a Windows Phone 7.5 device. Thereby the visitor of the museum can use the Museum Guide to see the exhibits as well as accompanying material including text, photos, audios and videos. Additionally the visitor can mark any of these exhibits as favorites and share their experiences with the other members of their group through instant messages. For the operation of instant messaging, we have created an embedded messenger which works over the xmpp protocol using the Matrix library. Besides the above, the Museum Guide gives to the user the opportunity to receive information about a specific exhibit, just taking a photo of this exhibit with phone’s camera. We call this operation on-demand guidance and we emphasized especially on the algorithm of user’s photo recognition. For this purpose we studied and evaluated various image recognition algorithms and came to the conclusion to use hashing techniques with help of pHash library.

This thesis deals with the pattern matching methods based on finite automata and describes their optimizations. It presents a methodology for the measurement of reliability of pattern matching methods, by comparing their results to the results of the PCRE library. Experiments were conducted for a finite automaton with perfect hashing and faulty transition table. Finally, the resulting reliability evaluation of the algorithm is shown and possible solutions of the identified problems are proposed.

This thesis deals with design and implementation of mapping of match action tables from P4 language to FPGA technology. Goal of the thesis was to describe key principles, which need to be understood in order to design such a mapping and function of algorithms needed, apply these principles by implementing them and analyze the speed and memory requirements of such an implementation. Outcome provides configurable hardware unit capable of classifying packets and connection between the unit and match action tables from P4 language. The implementation is based on DCFL algorithm and requires less memory compared to HiCuts and HyperCuts algorithms while being comparably fast at worst-case scenarios.

Title: Mining Parallel Corpora from the Web Author: Bc. Jakub Kúdela Author's e-mail address: jakub.kudela@gmail.com Department: Department of Software Engineering Thesis supervisor: Doc. RNDr. Irena Holubová, Ph.D. Supervisor's e-mail address: holubova@ksi.mff.cuni.cz Thesis consultant: RNDr. Ondřej Bojar, Ph.D. Consultant's e-mail adress: bojar@ufal.mff.cuni.cz Abstract: Statistical machine translation (SMT) is one of the most popular ap- proaches to machine translation today. It uses statistical models whose parame- ters are derived from the analysis of a parallel corpus required for the training. The existence of a parallel corpus is the most important prerequisite for building an effective SMT system. Various properties of the corpus, such as its volume and quality, highly affect the results of the translation. The web can be considered as an ever-growing source of considerable amounts of parallel data to be mined and included in the training process, thus increasing the effectiveness of SMT systems. The first part of this thesis summarizes some of the popular methods for acquiring parallel corpora from the web. Most of these methods search for pairs of parallel web pages by looking for the similarity of their structures. How- ever, we believe there still exists a non-negligible amount of parallel...

The thesis explains several algorithms for pattern matching. Algorithms work in both software and hardware. A part of the thesis is dedicated to extensions of finite automatons. The second part explains hashing and introduces concept of perfect hashing and CRC. The thesis also includes a suggestion of possible structure of a pattern matching unit based on deterministic finite automatons in FPGA. Experiments for determining the structure and size of resulting automatons were done in this thesis.

No description available.