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.
Category / Keywords: public-key cryptography / Fujisaki-Okamoto transform, non-negligible correctness, puncturable encryption Original Publication (with major differences): IACR-ASIACRYPT-2020 Date: received 11 Dec 2020 Contact author: Valerio Cini at ait ac at,Sebastian Ramacher@ait ac at,Daniel Slamanig@ait ac at,Christoph Striecks@ait ac at Available format(s): PDF | BibTeX Citation Version: 20201213:165941 (All versions of this report) Short URL: ia.cr/2020/1548