Building Better Hardware
for the Elliptic Curve Discrete Logarithm Problem

Patrick Schaumont, Bradley Department of Electrical and Computer Engineering, VA

Abstract:

A cryptanalyst is a code-breaker - someone who can transform ciphertext (unreadable) into plaintext (readable) without knowledge of a proper decryption key. Using specialized hardware, the efficiency of cryptanalysis can be greatly improved.

This talk will compare two cryptanalytic machines, each one designed in a very different age. The first machine, the Bombe, was used by the Allied Forced during World War II to break the encrypted communications from the German Enigma machines. The Bombe was an electromechanical design, and it was sufficiently powerful to provide meaningful results within a single day.

The second machine is a hardware-accelerated computer. We use it to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP), a cornerstone of modern public-key cryptography. Typical parameters for present-day Elliptic Curve Cryptography (ECC) lead to ECDLP problems of enormous complexity. However, the study and design of cryptanalytic machines for ECDLP leads to better insight into the security margin of ECC. We will describe our efforts in building a ECDLP search engine. We use a tightly-coupled architecture with a multicore Xeon and an FPGA. We implement a highly parallel design using the Bluespec Hardware Description Language.

By comparing these two very different designs, the talk will demonstrate how effective modern cryptography is at thwarting cryptanalysis. Changing this will require significant improvements at algorithm level as well as at architecture level.

Speaker:

Patrick Schaumont is Associate Professor in the Bradley Department of Electrical and Computer Engineering at Virginia Tech. He obtained the PhD degree in Electrical Engineering from UCLA in 2004, and the MS degree in Computer Science from Ghent University, Belgium in 1990. His research interests are in design methods and design of secure embedded systems, resource-constrained devices that require trustworthy behavior. His research is supported through NSF and NIST.

He has served on the TPC of international conferences in this field including CHES, DATE, DAC, IEEE HOST. He has served as guest editor for IEEE D&T, ACM TRETS, IEEE TCAD, and he is serving as associate editor for the Journal of Cryptographic Engineering. He wrote a textbook on hardware-software codesign, is listed as inventor on 4 patents, and he co-authored over 100 peer-reviewed articles.