**On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups**

*Goichiro Hanaoka and Takahiro Matsuda and Jacob C.N. Schuldt*

**Abstract: **In this paper, we focus on the problem of minimizing ciphertext overhead, and discuss the (im)possibility of constructing key encapsulation mechanisms (KEMs) with low ciphertext overhead. More specifically, we rule out the existence of algebraic black-box reductions from the (bounded) CCA security of a natural class of KEMs to any non-interactive problem. The class of KEMs captures the structure of the currently most efficient KEMs defined in standard prime order groups, but restricts an encapsulation to consist of a single group element and a string. This result suggests that we cannot rely on existing techniques to construct a CCA secure KEM in standard prime order groups with a ciphertext overhead lower than two group elements. Furthermore, we show how the properties of an (algebraic) programmable hash function can be exploited to construct a simple, efficient and CCA secure KEM based on the hardness of the decisional Diffie-Hellman problem with the ciphertext overhead of just a single group element. Since this KEM construction is covered by the above mentioned impossibility result, this enables us to derive a lower bound on the hash key size of an algebraic programmable hash function, and rule out the existence of algebraic $({\sf poly},n)$-programmable hash functions in prime order groups for any integer $n$. The latter result answers an open question posed by Hofheinz and Kiltz (CRYPTO'08) in the case of algebraic programmable hash functions in prime order groups.

**Category / Keywords: **public-key cryptography / key encapsulation, chosen ciphertext security, programmable hash functions, algebraic black-box reductions

**Publication Info: **CRYPTO 2012 -- This is the full version

**Date: **received 6 Aug 2012

**Contact author: **hanaoka-goichiro at aist go jp, t-matsuda@aist go jp, jacob schuldt@aist go jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20120807:181659 (All versions of this report)

**Short URL: **ia.cr/2012/448

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]