Cryptology ePrint Archive: Report 2021/227

Rate-1 Key-Dependent Message Security via Reusable Homomorphic Extractor against Correlated-Source Attacks

Qiqi Lai and Feng-Hao Liu and Zhedong Wang

Abstract: In this work, we first present general methods to construct information rate-1 PKE that is $\KDM^{(n)}$-secure with respect to \emph{block-affine} functions for any unbounded polynomial $n$. To achieve this, we propose a new notion of extractor that satisfies \emph{reusability}, \emph{homomorphic}, and \emph{security against correlated-source attacks}, and show how to use this extractor to improve the information rate of the \KDM-secure PKE of Brakerski et al.~(Eurocrypt 18). Then, we show how to amplify \KDM~security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting.

Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates $1-o(1)$ against a slightly smaller yet still general class -- block leakage functions. We can instantiate the required building blocks from $\LWE$ or $\DDH$.

Category / Keywords: public-key cryptography / PKE/IBE, KDM-security, Information rate-1

Original Publication (with major differences): IACR-PKC-2021

Date: received 28 Feb 2021, last revised 8 May 2021

Contact author: laiqq at snnu edu cn, liuf at fau edu, wangz at fau edu

Available format(s): PDF | BibTeX Citation

Version: 20210508:122933 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]