Chaum-van Antwerpen Undeniable Signatures on Elliptic Curves

Student:	Alex Blank
Chair:	Professor S. Radziszowski
Reader:	Professor A. Agarwal
Observer:	Professor R. Zanibbi

Hypothesis

The use of elliptic curves as applied to undeniable signatures will provide a significant speed enhancement over conventional modular arithmetic while maintaining the same level of strength with regard to security. This is due largely to the smaller key size provided by the absence of sub-exponential algorithms for solving the discrete logarithm problem over elliptic curves (ECDLP).

Problem Description

Elliptic curves (EC) are algebraic curves defined by the equation y² = x³ + ax + b on the prime field Z_p. Cryptographic techniques utilizing elliptic curves make use of the difficulty in computing the multiplicand n within the equation Q = nP, where Q and P represent points on the curve within a cyclic subgroup. This intractability is analogous to the discrete logarithm problem in modular arithmetic, and has been leveraged by other cryptographic primitives that use discrete logs to provide security (most notably the ElGamal cryptosystem and DSA). Besides this interesting correlation, the most beneficial aspect of using elliptic curves is that most known algorithms for solving discrete logarithms (Pollard Rho, Pohlig-Hellman, etc.) achieve exponential complexity, and the only known sub-exponential method, index calculus, has yet to be successfully applied to the realm of elliptic curves. This results in much smaller key size requirements, yielding faster computations and decreased memory consumption.

Digital signatures allow a user to “sign” a piece of data, much like they would a paper document, with the ability to verify that signature at a later date. Current standards for digital signatures offer simple sign-and-verify features. This is true for the current Digital Signature Algorithm (DSA) as well as its derivative ECDSA, or elliptic curve DSA. More advanced signature algorithms, those that offer other features such as undeniability (the signer is able to prove that the signature on a signed document is a forgery), have been previously described but have yet to be well experimented with using elliptic curves. The Chaum-van Antwerpen (CVA) Undeniable Signature Scheme is one such algorithm.

This project centers around the study of undeniable signatures as applied over elliptic curves. It seeks to demonstrate strong security and the performance benefits associated with elliptic curves in order to add further confidence in their use as a successor to cryptosystems based on modular arithmetic.

Documents

Report
Anonymous Report
Proposal
Pre-proposal
Progress