Between Hashed DH and Computational DH: Compact Encryption from Weaker Assumption

Goichiro HANAOKA  Kaoru KUROSAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.11   pp.1994-2006
Publication Date: 2010/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1994
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Cryptography and Information Security
public key encryption,  chosen-ciphertext security,  Diffie-Hellman assumption,  

Full Text: PDF(409.5KB)>>
Buy this Article

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme (with arbitrary plaintext length) which is based on a weaker assumption than the HDH assumption.