Abstract
We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE). We give new, tighter security reductions for several constructions. Our main result is an improved reduction for the security of the (formula presented)-transform of Hofheinz, Hövelmanns, and Kiltz (TCC’17) which turns OW-CPA secure deterministic PKEs into IND-CCA secure KEMs. This result is enabled by a new one-way to hiding (O2H) lemma which gives a tighter bound than previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability and non-deterministic PKEs. However, we assume that the derandomized PKE is injective with overwhelming probability. In addition, we analyze the impact of different variations of the (formula presented)-transform discussed in the literature on the security of the final scheme. We consider the difference between explicit ((formula presented)and implicit (formula presented) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least from a theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext (formula presented) or just from the message (formula presented).
| Original language | English |
|---|---|
| Title of host publication | Theory of Cryptography - 17th International Conference, TCC 2019, Proceedings |
| Editors | Dennis Hofheinz, Alon Rosen |
| Place of Publication | Berlin |
| Publisher | Springer |
| Chapter | 3 |
| Pages | 61-90 |
| Number of pages | 30 |
| Volume | 2 |
| ISBN (Electronic) | 978-3-030-36033-7 |
| ISBN (Print) | 978-3-030-36032-0 |
| DOIs | |
| Publication status | Published - 22 Nov 2019 |
| Event | 17th International Conference on Theory of Cryptography, TCC 2019 - Nuremberg, Germany Duration: 1 Dec 2019 → 5 Dec 2019 Conference number: 17th |
Publication series
| Name | Lecture notes in computer science |
|---|---|
| Volume | 11892 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Name | Security and cryptology |
|---|---|
| Volume | 11892 |
Conference
| Conference | 17th International Conference on Theory of Cryptography, TCC 2019 |
|---|---|
| Abbreviated title | TCC |
| Country/Territory | Germany |
| City | Nuremberg |
| Period | 1/12/19 → 5/12/19 |
Bibliographical note
Funding Information:Part of this work was done while the authors were participating in the 2019 Oxford Post-Quantum Cryptography Workshop. Special thanks to Daniel J. Bernstein, Edward Eaton and Mark Zhandry for helpful discussions; and to the anonymous TCC reviewers for their helpful comments and corrections. This work was supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701) and the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy (EXC 2092 CASA, 390781972).
Publisher Copyright:
© 2019, International Association for Cryptologic Research.