On the Impossibility of
Constructing Efficient Key Encapsulation and Programmable Hash Functions in
Prime Order Groups
Goichiro Hanaoka
(RISEC, AIST,
Takahiro
Matsuda (RISEC, AIST,
Jacob
C.N. Schuldt (RISEC, AIST,
Abstract:
In this paper, we discuss the (im)possibility
of constructing chosen ciphertext secure (CCA
secure) 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 used to construct a simple,
efficient and CCA secure KEM based on the hardness of the decisional Diffie-Hellman problem with a 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 (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.