Cryptology ePrint Archive: Report 2006/312

ElGamal type signature schemes for n-dimensional vector spaces

Iwan M. Duursma and SeungKook Park

Abstract: We generalize the ElGamal signature scheme for cyclic groups to a signature scheme for n-dimensional vector spaces. The higher dimensional version is based on the untractability of the vector decomposition problem (VDP). Yoshida has shown that under certain conditions, the VDP on a two-dimensional vector space is at least as hard as the computational Diffie-Hellman problem (CDHP) on a one-dimensional subspace. (Added November 19: Steven Galbraith recently showed that for the examples that are used in the paper, the VDP is at most as hard as the Discrete Logarithm problem (DLP) on a one-dimensional subspace. This has as a consequence for the proposed signature scheme that the given examples provide the same security as (ordinary) Elliptic Curve DLP based signature schemes.)

Category / Keywords: ElGamal signature scheme, Vector decomposition problem

Date: received 8 Sep 2006, last revised 19 Nov 2006

Contact author: skpark at uiuc edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Added November 19: Steven Galbraith recently showed that for the examples that are used in the paper, the VDP is at most as hard as the Discrete Logarithm problem (DLP) on a one-dimensional subspace. This has as consequence for the proposed signature scheme that the given examples provide the same security as (ordinary) Elliptic Curve DLP based signature schemes.

Version: 20061120:034458 (All versions of this report)

Discussion forum: Show discussion | Start new discussion