International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Relationships among FuncCPA and Its Related Notions

Authors:
Takumi Shinozaki , Institute of Science Tokyo
Tatsuaki Okamoto , Institute of Science Tokyo, NTT Social Informatics Laboratories
Keisuke Tanaka , Institute of Science Tokyo
Masayuki Tezuka , Institute of Science Tokyo
Yusuke Yoshida , Institute of Science Tokyo
Download:
Search ePrint
Search Google
Conference: TCC 2025
Abstract: Akavia, Gentry, Halevi, and Vald (TCC’22, JoC'25) introduced the security notion of function-chosen-plaintext-attack (FuncCPA security)for public-key encryption schemes. FuncCPA is defined by adding a functional re-encryption oracle to the IND-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 FuncCPA+, and conjectured that FuncCPA+ is strictly stronger than FuncCPA, while they showed FuncCPA+ implies FuncCPA. Seeking insights into this conjecture, they showed that ReEncCPA+ is strictly stronger than ReEncCPA, where ReEncCPA and ReEncCPA+ are restricted versions of FuncCPA and FuncCPA+ respectively. In this paper, contrary to their conjecture, we show that FuncCPA+ is equivalent to FuncCPA. We also introduce new variants of FuncCPA; WeakFuncCPA, OW-FuncCPA, and OW-WeakFuncCPA. WeakFuncCPA is a restricted variant of FuncCPA in that an oracle query is prohibited after the challenge query (like IND-CCA1). OW-FuncCPA and OW-WeakFuncCPA are the one-way (OW) versions of FuncCPA and WeakFuncCPA, respectively. This paper shows that WeakFuncCPA and OW-FuncCPA are equivalent to FuncCPA, that is, all of FuncCPA, FuncCPA+, WeakFuncCPA, and OW-FuncCPA are equivalent. Considering the separation of IND-CCA1 and IND-CCA2, and that of OW-CPA and IND-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 OW-WeakFuncCPA does not imply FuncCPA and ReEncCPA+ does not imply FuncCPA.
BibTeX
@inproceedings{tcc-2025-36269,
  title={Relationships among FuncCPA and Its Related Notions},
  publisher={Springer-Verlag},
  author={Takumi Shinozaki and Tatsuaki Okamoto and Keisuke Tanaka and Masayuki Tezuka and Yusuke Yoshida},
  year=2025
}