Paper 2024/1166

Relationships among FuncCPA and Its Related Notions

Abstract

Akavia, Gentry, Halevi, and Vald (TCC’22, JoC'25) introduced the security notion of function-chosen-plaintext-attack ($\mathsf{FuncCPA}$ security) for public-key encryption schemes. $\mathsf{FuncCPA}$ is defined by adding a functional re-encryption oracle to the $\mathsf{IND}$-$\mathsf{CPA}$ game. This notion is crucial for secure computation applications where the server is allowed to delegate a part of the computation to the client. Dodis, Halevi, and Wichs (TCC’23) introduced a stronger variant called $\mathsf{FuncCPA^+}$, and conjectured that $\mathsf{FuncCPA^+}$ is strictly stronger than $\mathsf{FuncCPA}$, while they showed $\mathsf{FuncCPA^+}$ implies $\mathsf{FuncCPA}$. Seeking insights into this conjecture, they showed that $\mathsf{ReEncCPA^+}$ is strictly stronger than $\mathsf{ReEncCPA}$, where $\mathsf{ReEncCPA}$ and $\mathsf{ReEncCPA^+}$ are restricted versions of $\mathsf{FuncCPA}$ and $\mathsf{FuncCPA^+}$ respectively. In this paper, contrary to their conjecture, we show that $\mathsf{FuncCPA^+}$ is equivalent to $\mathsf{FuncCPA}$. We also introduce new variants of $\mathsf{FuncCPA}$; $\mathsf{WeakFuncCPA}$, $\mathsf{OW}$-$\mathsf{FuncCPA}$, and $\mathsf{OW}$-$\mathsf{WeakFuncCPA}$. $\mathsf{WeakFuncCPA}$ is a restricted variant of $\mathsf{FuncCPA}$ in that an oracle query is prohibited after the challenge query (like $\mathsf{IND}$-$\mathsf{CCA1}$). $\mathsf{OW}$-$\mathsf{FuncCPA}$ and $\mathsf{OW}$-$\mathsf{WeakFuncCPA}$ are the one-way ($\mathsf{OW}$) versions of $\mathsf{FuncCPA}$ and $\mathsf{WeakFuncCPA}$, respectively. This paper shows that $\mathsf{WeakFuncCPA}$ and $\mathsf{OW}$-$\mathsf{FuncCPA}$ are equivalent to $\mathsf{FuncCPA}$, that is, all of $\mathsf{FuncCPA}$, $\mathsf{FuncCPA^+}$, $\mathsf{WeakFuncCPA}$, and $\mathsf{OW}$-$\mathsf{FuncCPA}$ are equivalent. Considering the separation of $\mathsf{IND}$-$\mathsf{CCA1}$ and $\mathsf{IND}$-$\mathsf{CCA2}$, and that of $\mathsf{OW}$-$\mathsf{CPA}$ and $\mathsf{IND}$-$\mathsf{CPA}$, these results are surprising. To show the equivalence, we develop novel techniques to utilize functional re-encryption oracles. We then provide the separation results that $\mathsf{OW}$-$\mathsf{WeakFuncCPA}$ does not imply $\mathsf{FuncCPA}$ and $\mathsf{ReEncCPA^+}$ does not imply $\mathsf{FuncCPA}$.