Paper 2023/1957 Original: eprint.iacr.org/2023/1957 ↗

Chosen Ciphertext Security via BARGs

Abstract

In this paper, we show a new set of cryptographic primitives that generically leads to chosen ciphertext secure (CCA secure) public-key encryption (PKE). Specifically, we show how a (non-interactive, publicly verifiable) batch argument (BARG) for NP can be combined with a chosen plaintext secure (CPA secure) PKE scheme to achieve a CCA secure one. The requirement of the succinctness of the proof size of a BARG used as a building block is arguably very mild: We require it to be only at most $(1 - \frac{1}{p(\lambda, n)}) \cdot k + q(\lambda, n) \cdot k^{\epsilon}$ for some non-negative constant $\epsilon < 1$ and polynomials $p, q$, where $\lambda$ denotes the security parameter, $n$ denotes the statement size, and $k$ denotes the batch size (i.e. the number of statements whose correctness is simultaneously proved), and thus it can even be (slightly) linear in $k$. A BARG with such succinctness is so weak that it cannot be used in the recent constructions of a non-interactive zero-knowledge proof system for NP based on a BARG (and a one-way function) by Bitansky et al. (STOC 2024) and Bradley, Waters, and Wu (TCC 2024). Therefore, our result gives a new building block that can upgrade CPA security into CCA security.