On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups
In this paper, the authors 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, they 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 f a single group element and a string. This result suggests that, they 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.