Interaction between genes has become a major topic in quantitative genetics. It is believed that these interactions play a significant role in genetic variations causing complex diseases. Due to the number of tests required for an exhaustive search in genome-wide association studies (GWAS), a large amount of computational power is required. In this paper, we present a hybrid architecture consisting of tightly interconnected CPUs, GPUs and FPGAs and a fine-tuned software suite to outperform other implementations in pairwise interaction analysis while consuming less than 300Watts and fitting into a standard desktop computer case.

High-throughput genotyping technologies (such as SNP-arrays) allow the rapid collection of up to a few million genetic markers of an individual. Detecting epistasis (based on 2-SNP interactions) in Genome-Wide Association Studies is an important but time consuming operation since statistical computations have to be performed for each pair of measured markers. Computational methods to detect epistasis therefore suffer from prohibitively long runtimes; e.g., processing a moderately-sized dataset consisting of about 500,000 SNPs and 5,000 samples requires several days using state-of-the-art tools on a standard 3 GHz CPU. In this paper, we demonstrate how this task can be accelerated using a combination of fine-grained and coarse-grained parallelism on two different computing systems. The first architecture is based on reconfigurable hardware (FPGAs) while the second architecture uses multiple GPUs connected to the same host. We show that both systems can achieve speedups of around four orders-of-magnitude compared to the sequential implementation. This significantly reduces the runtimes for detecting epistasis to only a few minutes for moderately-sized datasets and to a few hours for large-scale datasets.

Quote data are a vital part of information almost every trading algorithm relies on. While increasing effort is put into making trading algorithms better, the quote data as foundation of the algorithms is often asserted to be perfect. In reality, much work is needed to acquire good quote data. This paper shows methods of collecting and storing quote data and how to measure and improve its quality and completeness. Applying these methods leads to greatly improved results and higher speed of algorithms which rely on this quote data.

A weakness of many security systems is the strength of the chosen password or key derivation function. We show how FPGA technology can be used to effectively attack cryptographic applications with a password dictionary. We have implemented two independent PBKDF2 cores each using four HMAC cores with pipelines calculating a RIPEMD-160 hash to derive encryption keys together with one resource optimized AES-256 XTS core for direct decryption on a Xilinx Spartan6-LX150 FPGA. Our design targets TRUECRYPT containers, but may be applied to similar encryption tools with little adaption. In order to save resources and maximize speed, we have further optimized the RIPEMD-160 hash function for this purpose. Our design executed on the multi-FPGA system RIVYERA S6-LX150 containing 128 S6-LX150 FPGAs, finally reaches a peak performance of about 245,000 passwords per second.

The popular free encryption software True Crypt uses whole device or partition encryption as well as encrypted container files to protect sensible data from unauthorized access. Several combinations of encryption algorithms and hash functions used for the key derivation can be chosen by the user. This paper regards the combination with SERPENT as encryption algorithm and WHIRLPOOL as hash function for the key derivation. A dictionary attack has been implemented for this combination using the FPGA-based high-performance computer RIVYERA S3-5000. The achieved performance reaches more than 200,000 passwords per second. Compared to 820 passwords per second, achieved by a fully threaded Intel Core i7-970 system at 3.2GHz using the Crypto++ library, this leads to a speedup of more than 247 with energy savings of about 99%.

Cryptanalysis of symmetric and asymmetric ciphers is a challenging task due to the enormous amount of involved computations. To tackle this computational complexity, usually the employment of special-purpose hardware is considered as best approach. We have built a massively parallel cluster system (COPACOBANA) based on low-cost FPGAs as a cost-efficient platform primarily targeting cryptanalytical operations with these high computational efforts but low communication and memory requirements. However, some parallel applications in the field of cryptography are too complex for low-cost FPGAs and also require the availability of at least moderate communication and memory facilities. Particularly, this holds true for arithmetic intensive application as well as ones with a highly complex data flow. In this contribution, we describe a novel architecture for a more versatile and reliable COPACOBANA capable to host advanced cryptographic applications like high-performance digital signature generation according to the elliptic curve digital signature algorithm (ECDSA) and integer factorization based on the elliptic curve method (ECM). In addition to that, the new cluster design allows even to run more supercomputing applications beyond the field of cryptography.

Cryptanalysis of symmetric and asymmetric ciphers is computationally extremely demanding. Since the security parameters (in particular the key length) of almost all practical crypto algorithms are chosen such that attacks with conventional computers are computationally infeasible, the only promising way to tackle existing ciphers (assuming no mathematical breakthrough) is to build special-purpose hardware. Dedicating those machines to the task of cryptanalysis holds the promise of a dramatically improved cost-performance ratio so that breaking of commercial ciphers comes within reach. This contribution presents the design and realization of the COPACOBANA (Cost-Optimized Parallel Code Breaker) machine, which is optimized for running cryptanalytical algorithms and can be realized for less than US$ 10,000. It will be shown that, depending on the actual algorithm, the architecture can outperform conventional computers by several orders in magnitude. COPACOBANA hosts 120 low-cost FPGAs and is able to, e.g., perform an exhaustive key search of the Data Encryption Standard (DES) in less than nine days on average. As a real-world application, our architecture can be used to attack machine readable travel documents (ePass). COPACOBANA is intended, but not necessarily restricted to solving problems related to cryptanalysis. The hardware architecture is suitable for computational problems which are parallelizable and have low communication requirements. The hardware can be used, e.g., to attack elliptic curve cryptosystems and to factor numbers. Even though breaking full-size RSA (1024 bit or more) or elliptic curves (ECC with 160 bit or more) is out of reach with COPACOBANA, it can be used to analyze cryptosystems with a (deliberately chosen) small bitlength to provide reliable security estimates of RSA and ECC by extrapolation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Cryptanalysis of symmetric and asymmetric ciphers is computationally extremely demanding. Since the security parameters of almost all practical crypto algorithms are chosen such that attacks with conventional computers are computationally infeasible, the only promising way to tackle existing ciphers (assuming no mathematical breakthrough) is to build special-purpose hardware. This contribution presents a special-purpose hardware labeled COPACOBANA (cost-optimized parallel code breaker), which is optimized for running crypt-analytical algorithms with low communication overhead. The price-performance ratio as primary and a cost margin of less than US$ 10,000 as secondary design goal led to a reconfigurable computer built as cluster of programmable logic devices

The computational fundament of most public-key cryptosystems is the modular multiplication. Improving the efficiency of the modular multiplication is directly associated with the efficiency of the whole cryptosystem. This paper presents an implementation and comparison of three recently proposed, highly efficient architectures for modular multiplication on FPGAs: interleaved modular multiplication and two variants of the Montgomery modular multiplication. This (first) hardware implementation of these designs shows their relative performance regarding area and speed. One of the main findings is that the interleaved multiplication has the least area time product of all investigated architectures. As a typical cryptographic application, we show that a 1024-bit RSA exponentiation can be performed in less than 6.1ms at a clock rate of 69MHz on a Xilinx Virtex FPGA.

A new modular multiplication algorithm and its corresponding architecture is presented. It is optimised with respect to hardware complexity and latency. Based on the dataflow of the well known interleaved modular multiplication the product of two n-bit-integers X and Y modulo M is computed by n iterations of a simple loop. The loop consists of one single carry save addition, a comparison of constant complexity, and a table lookup, where the table contains 6 precomputed values and two constants. By this construction the arithmetical complexity of the modular multiplication is reduced to n additions without carry propagation in total which leads to a speedup of at least two in comparison to all methods previously known. It consists of a first algorithm A2 implementing the new idea of combining carry save addition and constant time comparison. A2 is not optimal with respect to area and time. Its correctness is proven. By use of a small amount of precomputing the loop of A2 can be modified such that the effort within the loop is minimised. This leads to the algorithm A3 and it is verified.

The author presents a solution for the following problem: given an undirected bridgeless graph G=(V, E), find an orientation of each edge such that the resulting directed graph is strongly connected. He assumes the input graph to be given as an adjacency matrix stored in the processors of a mesh connected processor array such that each processor contains one entry. The algorithm is a modification off R.E. Tarjan and U. Vishkin's strong orientation method (1985) for a CREW PRAM. It takes time O(n) for an n-vertex graph which is asymptotically optimal for the considered computer model.>

A correction network C is introduced that can be added to an arbitrary N-input sorting net in order to achieve single-fault tolerance. Multiple $(k)$ fault robustness is attained by adding $C^k $. For single-fault correction, C is proved to be asymptotically optimal.

A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed.