Welcome to the resource topic for 2012/448
Title:
On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups
Authors: Goichiro Hanaoka, Takahiro Matsuda, 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.
ePrint: https://eprint.iacr.org/2012/448
Talk: https://www.youtube.com/watch?v=WykFah6xjDI
Slides: https://iacr.org/cryptodb/archive/2012/CRYPTO/presentation/16-1-Schuldt.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .