Spring 2003

M.S. Thesis Defense: Efficient Algorithms for Finite Fields, with Applications in Elliptic Curve Cryptography

Selcuk Baktir
Monday, April 21, 2003, 1:00 PM, Atwater Kent, WPI, Room 311

Abstract

Elliptic curve cryptography relies heavily on the existence of efficient algorithms for finite field arithmetic. Optimal Extension Fields have been found to be especially successful in embedded software implementations of elliptic curve schemes. The arithmetic operations in OEFs are much more efficient than in characteristic two extensions or prime fields due to the use of larger characteristic base field and the selection of a binomial as the field polynomial. In the elliptic curve scalar-point multiplication, a large number of field multiplications and inversions are computed. This poses a significant problem in embedded systems where computational power is quite limited and public-key operations are unacceptably slow. Inversion is inherently more complex and several times more costly than multiplication. Despite recent improvements, inversion is still the slowest operation in elliptic curve implementations. In this thesis, this issue is addressed by introducing a specialized tower field representation.

Optimal Tower Fields (OTFs), which facilitate efficient finite field arithmetic, are introduced. The recursive direct inversion method developed for OTFs is shown to have significantly lower complexity than the known best method for inversion in OEFs, i.e., Itoh-Tsujii method. The asymptotic complexity of OTF inversion algorithm is found to be O(m²), a significant improvement over the O(m²log₂m) asymptotic complexity of Itoh-Tsujii method. This complexity is further improved to O(m^log₂3) by utilizing the Karatsuba-Ofman algorithm. It is proven that OTFs are in fact a special class of OEFs, and an OTF element may be converted to OEF representation via a simple permutation of the coefficients. Hence, OTF operations are available to OEFs whenever a corresponding OTF exists, and similarly OEF operations can be used in OTF arithmetic with no overhead of conversion from one field representation to another.

The OTF inversion algorithm was implemented on the ARM family of processors for a medium and a large sized field whose elements can be represented with 192 and 320 bits, respectively. In the implementation, the new OTF inversion algorithm ran at least six to eight times faster than the known best method for inversion in OEFs, i.e., Itoh-Tsujii method. According to the implementation results obtained, it is indicated that using the OTF inversion method an elliptic curve scalar point multiplication operation can be performed at least two to three times faster than the known best implementation for the selected fields.

List decoding of error-correcting codes

Madhu Sudan, MIT, Cambridge, MA
Thursday, April 10, 2003, 4:00 PM, Stratton Hall, WPI, Room 203

Abstract

The task of dealing with errors (or correcting them) lies at the very heart of communication and computation. The mathematical foundations for this task were laid in two concurrent and interdependent works by Shannon and Hamming in the late 1940s. The two theories are strikingly powerful and distinct in their Modelling of the error. Shannon's theory Models errors as effected by a probabilistic/stochastic process, while Hamming envisions them as being introduced by an adversary. While the two theories share a lot in the underlying tools, the quantitative results are sharply diverging. Shannon's theory shows that a channel that corrupt (arbitrarily) close to 50% of the transmitted bits can still be used for transmission of information. Hamming's theory in contrast has often been interpreted to suggest it can handle at most 25% error on a binary channel.

So what can we do if an adversary is given the power to introduce more than 25% errors? Can we protect information against this, or do we just have to give up? The notion of list-decoding addresses precisely this question, and shows that under a relaxed notion of "decoding" (or recovering from errors), the quantitative gaps between the Shannon and Hamming theories can be bridged. In this talk, we will describe this notion and some recent algorithmic developments. If time permits we will show how this notion lies at the heart of many issues in modern complexity theory and the foundations of Cryptography.

Towards a Theory of Variable Privacy

Poorvi Vora, Hewlett-Packard Company, Corvallis, OR
Monday, January 20, 2003, 10:00 AM, Atwater Kent, WPI, Room 218

[Presentation Slides (pdf)] [Paper Draft (pdf)]

Abstract

The traditional theory of security, with its focus on perfect secrecy, does not provide a satisfactory framework for the study of situations where information revelation bears a privacy cost and also provides a benefit. We define variable privacy as the use of randomization with user participation in the choice of parameters, and propose the beginnings of a theory for its study. Variable privacy enables the user, or a computational agent working on the user's behalf, to choose a level of interaction, based on a personal cost-benefit analysis of an instance of information revelation.

Our theory is based on treating the randomization protocol as a channel for the information to be protected. We demonstrate a one-to-one correspondence between channel codes and a certain class of attacks. Shannon's theorems show the existence of very special attacks, and upper bounds on their efficiency. We use the bounds to motivate a privacy measure of randomization similar to one proposed the database literature, and thus provide connections between the theory of security and statistical privacy protection techniques.

We are not aware of any other work that uses Shannon's theorems to construct the special attacks on Cryptographic protocols. We are also not aware of any other work that connects error-correcting codes to attacks on randomization.

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