ElGamal type signature schemes for n-dimensional vector spaces

Iwan M.  Duursma; SeungKook Park

Paper 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.)

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.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: ElGamal signature scheme Vector decomposition problem
Contact author(s): skpark @ uiuc edu
History: 2006-11-20: revised; 2006-09-12: received; See all versions
Short URL: https://ia.cr/2006/312
License: CC BY

BibTeX

@misc{cryptoeprint:2006/312,
      author = {Iwan M.  Duursma and SeungKook Park},
      title = {{ElGamal} type signature schemes for n-dimensional vector spaces},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/312},
      year = {2006},
      url = {https://eprint.iacr.org/2006/312}
}