Paper 2004/306
The Static Diffie-Hellman Problem
Daniel R. L. Brown and Robert P. Gallant
Abstract
The static Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. We establish that the SDHP is almost as hard as the associated discrete logarithm problem. We do this by giving a reduction that shows that if the SDHP can be solved then the associated private key can be found. The reduction also establishes that certain systems have less security than anticipated. The systems affected are based on static Diffie-Hellman key agreement and do not use a key derivation function. This includes some cryptographic protocols: basic ElGamal encryption; Chaum and van Antwerpen's undeniable signature scheme; and Ford and Kaliski's key retrieval scheme, which is currently being standardized in IEEE P1363.2.
Note: revisions in the interest of clarity
Metadata
- Available format(s)
- PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Submitted to Eurocrypt 2005 (preliminary version)
- Keywords
- Static Diffie-HellmanElGamal EncryptionFord-Kaliski Key RetrievalProvable Security
- Contact author(s)
- dbrown @ certicom com
- History
- 2005-06-24: revised
- 2004-11-16: received
- See all versions
- Short URL
- https://ia.cr/2004/306
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2004/306,
author = {Daniel R. L. Brown and Robert P. Gallant},
title = {The Static Diffie-Hellman Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2004/306},
year = {2004},
url = {https://eprint.iacr.org/2004/306}
}
