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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Chosen Ciphertext Security via BARGs

  • Takahiro Matsuda

摘要

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.