Spring 2002

M.S. Thesis Defense: Versatile Montgomery Multiplier Architectures

Gunnar Gaubatz
Friday, April 26, 2002, 1:00 PM, Atwater Kent, WPI, Room 311

Abstract

Several algorithms for Public Key Cryptography (PKC), such as RSA, Diffie-Hellman, Elliptic Curve Cryptography, require modular multiplication of very large operands (sizes from 160 to 4096 bits) as their core arithmetic operation. The computing power of handheld devices often cannot perform these operations in short enough time without interrupting the user experience. Specialized hardware architectures help overcome such issues in the form of Cryptographical co-processors or instruction set extensions of existing processors. In order to accomodate such an architecture to any available chip area, a scalable hardware design is to be preferred over a specialized one that has to be redesigned for each particular application.

This M.S. thesis presents a new architecture that is scalable with respect to multiple parameters such as word size and pipelining depth. It is also able to handle operands of nearly unlimited size to support current and future public key algorithms. To our knowledge, this is the first time Montgomery's algorithm is implemented using high-radix digit multipliers in such a scalable and universal way. Our design is a unified architecture supporting arithmetic with integers as well as with binary polynomials for operation in rings Z_N and finite fields GF(p) and GF(2^k).

This talk will discuss the ideas behind the design of this hardware architecture and include an analysis of its performance and area requirements.

M.S. Thesis Defense: Efficient NTRU Implementation

Colleen M. O'Rourke
Tuesday, April 23, 2002, 1:00 PM, Atwater Kent, WPI, Room 218

Abstract

The NTRU Public Key Cryptosystem is a ring-based polynomial Cryptosystem that was fully introduced in 1998. The core and most time consuming operation in NTRU's public key creation, enCryption, and deCryption procedures is the polynomial multiplication. Since no Research has been published that enhances the performance of NTRU's polynomial multiplication through hardware, this led to the design of two hardware implementations. The first implementation is an optimized and scalable design that improves the performance of NTRU's polynomial multiplication. The second implementation is a unified multiplier that utilizes the Montgomery Multiplication algorithm to perform a modular multiplication for GF(p) and GF(2^k) as well as a polynomial multiplication for NTRU. This talk will introduce the unique features of NTRU's polynomial multiplication that provided the mathematical foundation for the hardware designs. In addition, a discussion of the hardware architecture as well as the performance of each implementation will be provided.

PhD Thesis Defense: Recongurable Computing for Symmetric-Key Algorithms

Adam J. Elbirt
Monday, April 22, 2002, 4:00 PM, Atwater Kent, WPI, Room 218

Abstract

Efficient implementation of block ciphers is critical towards achieving both high security and high speed processing. Numerous block ciphers have been proposed and implemented, covering a wide and varied range of functional operations. As a result, it has become increasingly more difficult to develop a hardware architecture that allows the efficient and fast realization of a wide variety of block ciphers. In an effort to achieve such a hardware architecture, a study of a wide range of block ciphers was undertaken to develop an understanding of the functional requirements of each algorithm. This study led to the development of COBRA, a programmable and configurable architecture for the efficient implementation of a wide variety of block ciphers. A detailed discussion of the top level architecture, interconnection scheme, and underlying elements of the architecture will be provided. System conguration and on-the-fly reconfiguration will be analyzed, and from this analysis it will be demonstrated that the COBRA architecture satisfies the requirements for achieving efficient implementation of a wide range of block ciphers.

A Mathematician's Introduction to Quantum Algorithms

Bill Martin, Mathematical Sciences and Computer Science, WPI
Friday, April 12, 2002, 2:00 PM, Atwater Kent, WPI, Room 218

Abstract

I will continue my physics-free introduction to quantum algorithms. After briefly reviewing the ideas introduced in the first talk, I will discuss Grover's O(sqrt(n)) quantum algorithm for searching an unordered list, I will outline Shor's algorithms for factoring and the discrete logarithm problem (these are based on the Quantum Fourier Transform) and, if time permits, I will introduce quantum error-correcting codes and give some examples of these. As with the first talk, this presentation is tutorial in nature and no original results will be presented.

A Mathematician's Introduction to Quantum Computing

Bill Martin, Mathematical Sciences and Computer Science, WPI
Thursday, March 28, 2002, 2:00 PM, Atwater Kent, WPI, Room 218

Abstract

This is an informal talk and contains no original results.

The well-accepted formalism of quantum mechanics allows an outsider like myself to bypass the physics and work only with the linear algebraic Model for the operation of a quantum computer. Suppose then that state of our CPU is a non-zero vector in a finite-dimensional complex vector space, that we can manipulate this state via unitary matrices, but that we can only measure the system by randomly projecting the state vector onto one of a collection of subspaces (of our choosing). Can one actually compute with such a Model? Is it more powerful than a Turing machine? What is the current state of affairs regarding quantum algorithms?

In this talk, I will try to give a very basic introduction to these ideas without using any physics. I will try to separate myth from fact and will try to give an idea why Peter Shor's quantum algorithms for factoring integers and for solving the discrete logarithm problem have generated so much interest. Finally, I will make some comments about quantum error correction and fault-tolerant computation, which will be crucial if we are ever to realize these mysterious machines.

I anticipate discussing these topics over a 2-week period. In the first week, I will focus on the basic ideas. In the second week, I will comment on Shor's algorithms and explore quantum codes.

PhD Thesis Defense: Efficient Elliptic Curve Processor Architectures for Field Programmable Logic

Gerardo Orlando
Monday, March 4, 2002, 10:00 AM, Atwater Kent, WPI, Room 218

Abstract

Neil Koblitz and Victor Miller independently proposed the first elliptic curve Cryptosystems in 1985. Since its inception, elliptic curve Cryptography (ECC) has been the subject of extensive Cryptanalysis. Today, after more than 15 years of study, elliptic curve Cryptosystems are deemed secure for commercial as well as government use as is evident by several federal and international standards (e.g., ANSI, IEEE, IPsec).

Elliptic curve Cryptosystems are public-key Cryptosystems that offer security comparable to that of traditional Cryptosystems --- i.e., those based on the integer factorization problem, such as RSA, and those based on the discrete logarithm problem in a finite field, such as the Diffie-Hellman key agreement algorithm --- but using computationally simpler algorithms. The computational simplicity of elliptic curve algorithms makes their use very attractive for computationally and power constrained environments, such as wireless devices and smart-cards. Another application area for which elliptic curves are very attractive are systems that work under heavy loads, such as secure networking devices, especially on the server side.

This talk introduces new, high-performance elliptic curve processor (ECP) architectures designed to take advantage of the features offered by reprogrammable hardware, in particular field programmable gate array (FPGA) hardware. One Main aspect of the work is the development of efficient arithmetic architectures for fields GF(2^m) and GF(p) optimized for modern reprogammable devices. The performance of prototype implementations of the ECP processors ranks among the highest ones published.

Lattices, Cryptography, and the NTRU Cryptosystem

Dr. Joseph H. Silverman, Department of Mathematics, Brown University and NTRU Cryptosystems, Inc.
Wednesday, February 13, 2002, 11:00 AM SH203, Room 203, Stratton Hall, WPI

Abstract

The application of hard problems from the theory of lattices has led to the creation of compact and fast Cryptographic constructions that outperform traditional systems based on integer factorization or discrete logarithm problems. In this talk I will explain some of the underlying theory of lattice reduction and describe how hard mathematical problems associated to a certain class of lattices can be used to construct an extremely efficient public key Cryptosystem and digital signature scheme.

Algorithms and Architectures for Resource Constrained Elliptic Curve Cryptosystems

Anwar Hasan, Center for Applied Cryptographic Research, University of Waterloo, Ontario, Canada.
Monday, January 28, 2002; 1:00 pm; Hagglund Room, Campus Center, WPI

Abstract

Cryptographic systems based on elliptic curves use shorter key sizes. As a result, they are being increasingly used in practical applications, and specific curves and parameters have been proposed by a number of standardization bodies, such as the National Institute of Standards and Technology (NIST), and Standards for Efficient Cryptography Group (SECG). These curves and parameters are not only to resist known attacks, but also to improve the performance of the Cryptosystem. However, efficient implementation of elliptic curve Cryptographic schemes is quite challenging, especially in resource constrained systems, such as smart cards and various hand-held wireless devices. In this Seminar the speaker will highlight the challenges and will talk about a number of algorithms and architectures suitable for embedding elliptic curve Cryptographic schemes into resource constrained general purpose computing environments. Choices of curves, curve-point rePresentations, and algorithms for the underlying finite field computations that can make elliptic curve Cryptosystems efficient will be presented.

Maintained by webmaster@wpi.edu
Last modified: Tuesday, 29-Jun-2004 09:52:16 EDT