**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 format(s): **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)

**Short URL: **ia.cr/2006/312

[ Cryptology ePrint archive ]