The n-Diffie-Hellman Problem and its Applications

Liqun Chen; Yu Chen

Paper 2011/397

The n-Diffie-Hellman Problem and its Applications

Liqun Chen and Yu Chen

Abstract

The main contributions of this paper are twofold. On the one hand, the twin Diffie-Hellman (twin DH) problem proposed by Cash, Kiltz and Shoup is extended to the $n$-Diffie-Hellman ($n$-DH) problem for an arbitrary integer $n$, and this new problem is shown to be at least as hard as the ordinary DH problem. Like the twin DH problem, the $n$-DH problem remains hard even in the presence of a decision oracle that recognizes solution to the problem. On the other hand, observe that the double-size key in the Cash et al. twin DH based encryption scheme can be replaced by two separated keys each for one entity, that results in a 2-party encryption scheme which holds the same security feature as the original scheme but removes the key redundancy. This idea is further extended to an $n$-party case, which is also known as $n$-out-of-$n$ encryption. As examples, a variant of ElGamal encryption and a variant of Boneh-Franklin IBE have been presented; both of them have proved to be CCA secure under the computational DH assumption and the computational bilinear Diffie-Hellman (BDH) assumption respectively, in the random oracle model. The two schemes are efficient, due partially to the size of their ciphertext, which is independent to the value $n$.

Note: Revise several lapses

Metadata

Available format(s): PS
Category: Public-key cryptography
Publication info: Published elsewhere. An extended abstract of this paper appears in the Proceedings of the 14th Information Security Conference (ISC 2011).
Keywords: the (strong) $n$-DH assumption the (strong) $n$-BDH assumption multiple public key encryption multiple identity-based encryption
Contact author(s): liqun chen @ hp com
History: 2011-10-09: revised; 2011-07-28: received; See all versions
Short URL: https://ia.cr/2011/397
License: CC BY

BibTeX

@misc{cryptoeprint:2011/397,
      author = {Liqun Chen and Yu Chen},
      title = {The n-Diffie-Hellman Problem and its Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/397},
      year = {2011},
      url = {https://eprint.iacr.org/2011/397}
}