| Presentation | 2012-12-12 [Invited Talk] On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Goichiro HANAOKA, Takahiro MATSUDA, Jacob C.N. SCHULDT, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this invited talk, we introduce the lecture with the same title presented at the 32nd International Cryptology Conference (CRYPTO 2012) held from August 19th to 23rd, 2012, at Santa Barbara, USA.\\ \\[Abstract from the original paper (with a slight modification):] In this work, 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 (one-way, 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 (one-way, bounded) CCA secure KEM based on the hardness of the computational 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, J. Cryptology'12) in the case of algebraic programmable hash functions in prime order groups. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | key encapsulation / chosen ciphertext security / programmable hash / algebraic black-box reductions |
| Paper # | ISEC2012-79 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2012/12/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Invited Talk] On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order |
| Sub Title (in English) | |
| Keyword(1) | key encapsulation |
| Keyword(2) | chosen ciphertext security |
| Keyword(3) | programmable hash |
| Keyword(4) | algebraic black-box reductions |
| 1st Author's Name | Goichiro HANAOKA |
| 1st Author's Affiliation | Research Institute for Secure Systems, National Institute of Advanced Industrial Science and Technology() |
| 2nd Author's Name | Takahiro MATSUDA |
| 2nd Author's Affiliation | Research Institute for Secure Systems, National Institute of Advanced Industrial Science and Technology |
| 3rd Author's Name | Jacob C.N. SCHULDT |
| 3rd Author's Affiliation | Royal Holloway, University of London |
| Date | 2012-12-12 |
| Paper # | ISEC2012-79 |
| Volume (vol) | vol.112 |
| Number (no) | 342 |
| Page | pp.pp.- |
| #Pages | 40 |
| Date of Issue | |