CCA-Secure (Puncturable) KEMs from Encryption With Non-Negligible Decryption Errors

Valerio Cini, Sebastian Ramacher, Daniel Slamanig, and Christoph Striecks

Abstract

Public-key encryption (PKE) schemes or key-encapsulation mechanisms (KEMs) are fundamental cryptographic building blocks to realize secure communication protocols. There are several known transformations that generically turn weakly secure schemes into strongly (i.e., IND-CCA) secure ones. While most of these transformations require the weakly secure scheme to provide perfect correctness, Hofheinz, Hövelmanns, and Kiltz (HHK) (TCC 2017) have recently shown that variants of the Fujisaki-Okamoto (FO) transform can work with schemes that have negligible correctness error in the (quantum) random oracle model (QROM). Many recent schemes in the NIST post-quantum competition (PQC) use variants of these transformations. Some of their CPA-secure versions even have a non-negligible correctness error and so the techniques of HHK cannot be applied. In this work, we study the setting of generically transforming PKE schemes with potentially large, i.e., non-negligible, correctness error to ones having negligible correctness error. While there have been previous treatments in an asymptotic setting by Dwork, Naor, and Reingold (EUROCRYPT 2004), our goal is to come up with practically efficient compilers in a concrete setting and apply them in two different contexts. Firstly, we show how to generically transform weakly secure deterministic or randomized PKEs into CCA-secure KEMs in the (Q)ROM using variants of HHK. This applies to essentially all candidates to the NIST PQC based on lattices and codes with non-negligible error for which we provide an extensive analysis. We thereby show that it improves some of the code-based candidates. Secondly, we study puncturable KEMs in terms of the Bloom Filter KEM (BFKEM) proposed by Derler et al. (EUROCRYPT 2018) which inherently have a non-negligible correctness error. BFKEMs are a building block to construct fully forward-secret zero round-trip time (0-RTT) key-exchange protocols. In particular, we show the first approach towards post-quantum secure BFKEMs generically from lattices and codes by applying our techniques to identity-based encryption (IBE) schemes with (non-)negligible correctness error.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
Fujisaki-Okamoto transformnon-negligible correctnesspuncturable encryption
Contact author(s)
Valerio Cini @ ait ac at
Sebastian Ramacher @ ait ac at
Daniel Slamanig @ ait ac at
Christoph Striecks @ ait ac at
History
Short URL
https://ia.cr/2020/1548

CC BY

BibTeX

@misc{cryptoeprint:2020/1548,
author = {Valerio Cini and Sebastian Ramacher and Daniel Slamanig and Christoph Striecks},
title = {CCA-Secure (Puncturable) KEMs from Encryption With Non-Negligible Decryption Errors},
howpublished = {Cryptology ePrint Archive, Paper 2020/1548},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1548}},
url = {https://eprint.iacr.org/2020/1548}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.