Paper 2012/448

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

Goichiro Hanaoka, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CRYPTO 2012 -- This is the full version
Keywords
key encapsulationchosen ciphertext securityprogrammable hash functionsalgebraic black-box reductions
Contact author(s)
hanaoka-goichiro @ aist go jp
t-matsuda @ aist go jp
jacob schuldt @ aist go jp
History
2012-08-07: received
Short URL
https://ia.cr/2012/448
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/448,
      author = {Goichiro Hanaoka and Takahiro Matsuda and Jacob C. N.  Schuldt},
      title = {On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2012/448},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/448}},
      url = {https://eprint.iacr.org/2012/448}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.