International Association
for Cryptologic Research

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.

Non-committing encryption (NCE) introduced by Canetti et al. (STOC '96) is a central tool to achieve multi-party computation protocols secure in the adaptive setting. Recently, Yoshida et al. (ASIACRYPT '19) proposed an NCE scheme based on the hardness of the DDH problem, which has ciphertext expansion $\mathcal{O}(\log\lambda)$ and public-key expansion $\mathcal{O}(\lambda^2)$. In this work, we improve their result and propose a methodology to construct an NCE scheme that achieves \emph{constant} ciphertext expansion. Our methodology can be instantiated from the DDH assumption and the LWE assumption. When instantiated from the LWE assumption, the public-key expansion is $\lambda\cdot\mathsf{poly}(\log\lambda)$. They are the first NCE schemes satisfying constant ciphertext expansion without using iO or common reference strings. Along the way, we define a weak notion of NCE, which satisfies only weak forms of correctness and security. We show how to amplify such a weak NCE scheme into a full-fledged one using wiretap codes with a new security property.

Non-committing encryption (NCE) was introduced by Canetti et al. (STOC ’96). Informally, an encryption scheme is non-committing if it can generate a dummy ciphertext that is indistinguishable from a real one. The dummy ciphertext can be opened to any message later by producing a secret key and an encryption random coin which “explain” the ciphertext as an encryption of the message. Canetti et al. showed that NCE is a central tool to achieve multi-party computation protocols secure in the adaptive setting. An important measure of the efficiently of NCE is the ciphertext rate, that is the ciphertext length divided by the message length, and previous works studying NCE have focused on constructing NCE schemes with better ciphertext rates.We propose an NCE scheme satisfying the ciphertext rate based on the decisional Diffie-Hellman (DDH) problem, where is the security parameter. The proposed construction achieves the best ciphertext rate among existing constructions proposed in the plain model, that is, the model without using common reference strings. Previously to our work, an NCE scheme with the best ciphertext rate based on the DDH problem was the one proposed by Choi et al. (ASIACRYPT ’09) that has ciphertext rate . Our construction of NCE is similar in spirit to that of the recent construction of the trapdoor function proposed by Garg and Hajiabadi (CRYPTO ’18).