The n-Diffie–Hellman problem and multiple-key encryption

摘要

The main contributions of this paper are twofold. On the one hand, the twin Diffie–Hellman (twin DH) problem proposed by Cash et al. 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 chosen ciphertext attack secure under the computational DH assumption and the computational bilinear Diffie–Hellman 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.