Abstract
The notion of functional re-encryption security (funcCPA) for public-key encryption schemes was recently introduced by Akavia et al. (TCC’22), in the context of homomorphic encryption. This notion lies in between CPA security and CCA security: we give the attacker a functional re-encryption oracle instead of the decryption oracle of CCA security. This oracle takes a ciphertext \(\textsf{ct}\) and a function f, and returns fresh encryption of the output of f applied to the decryption of \(\textsf{ct}\); in symbols, \(\textsf{ct}'=\textrm{Enc}(f(\textrm{Dec}(\textsf{ct})))\). More generally, we even allow for a multi-input version, where the oracle takes an arbitrary number of ciphertexts \(\textsf{ct}_1,\ldots \textsf{ct}_\ell \) and outputs \(\textsf{ct}' = \textrm{Enc}(f(\textrm{Dec}(\textsf{ct}_1), \ldots , \textrm{Dec}(\textsf{ct}_\ell )))\).
In this work we observe that funcCPA security may have applications beyond homomorphic encryption, and set out to study its properties. As our main contribution, we prove that funcCPA is “closer to CPA than to CCA”; that is, funcCPA secure encryption can be constructed in a black-box manner from CPA-secure encryption. We stress that, prior to our work, this was not known even for basic re-encryption queries corresponding to the identity function f.
At the core of our result is a new technique, showing how to handle adaptive functional re-encryption queries using tools previously developed in the context of non-malleable encryption, which roughly corresponds to a single non-adaptive parallel decryption query.
Y. Dodis—Research Supported by NSF grant CNS-2055578, and gifts from JP Morgan, Protocol Labs and Algorand Foundation.
S. Halevi—Work was done while at the Algorand Foundation
D. Wichs—Research supported by NSF grant CNS-1750795, CNS-2055510 and the JP Morgan faculty research award.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Notice, this application requires FuncCPA security for queries consisting of multiple ciphertexts, which is why this will be our default notion of FuncCPA security.
- 2.
In fact, we show (see Lemma A.1) that FuncCPA security is implied by CCA security against “lunchtime attacks”, known as CCA1.
- 3.
- 4.
This aspect was not needed in the analysis of [3], as they did not have any re-encryption queries.
- 5.
Intuitively, multiple-ciphertext functional re-encryption oracle can be simulated by a single-ciphertext non-functional re-encryption oracle, by first homomorphically applying the function f “inside the encryption”, and then calling the simpler oracle to ensure the resulting encryption is “fresh”.
- 6.
All the results in this work apply out-of-the-box also to schemes with decryption errors, as long as they only occur with negligible probability. Otherwise one can amplify correctness of the underlying CPA-secure scheme before applying our transformation.
- 7.
Having two such flavors is reminiscent of definitions of circular security: Over there one notion asserts that an encryption of the secret key does not help the attacker violate semantic security, and the other requires that the attacker cannot distinguish such encryption from an encryption of zero.
- 8.
Valid ciphertexts are not necessarily correctly generated and may decrypt differently depending on the secret key.
- 9.
The theorem in [11, Thm 4] is stated for a non-tagged scheme, but it holds equally for the tagged version.
- 10.
We note that the requirements from \(\textrm{Extend}\) imply that t cannot be too close to n, at the very least we need \(n\ge t+k\) so that any t-symbol string can be extended to an encoding of any k-symbol information word.
- 11.
An “invisible” difference is that u’th output ciphertext is computed using \(\textrm{Extend}\) rather than applying the encoding \(\textsf{E}(\cdots )\), but this produces the same distribution over the codewords.
References
Akavia, A., Gentry, C., Halevi, S., Vald, M.: Achievable CCA2 relaxation for homomorphic encryption. In: Kiltz, E., Vaikuntanathan, V. (eds.) Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II. Lecture Notes in Computer Science, vol. 13748, pp. 70–99. Springer (2022). https://doi.org/10.1007/978-3-031-22365-5_3, also available from https://ia.cr/2022/282
Akavia, A., Vald, M.: private communication, November 2022
Choi, S.G., Dachman-Soled, D., Malkin, T., Wee, H.: A black-box construction of non-malleable encryption from semantically secure encryption. J. Cryptol. 31(1), 172–201 (2017). https://doi.org/10.1007/s00145-017-9254-z
Choi, S.G., Dachman-Soled, D., Malkin, T., Wee, H.: Improved, black-box, non-malleable encryption from semantic security. Des. Codes Crypt. 86(3), 641–663 (2017). https://doi.org/10.1007/s10623-017-0348-2
Coretti, S., Dodis, Y., Maurer, U., Tackmann, B., Venturi, D.: Non-malleable encryption: simpler, shorter, stronger. J. Cryptol. 33(4), 1984–2033 (2020). https://doi.org/10.1007/s00145-020-09361-0
Cramer, R., Hanaoka, G., Hofheinz, D., Imai, H., Kiltz, E., Pass, R., Shelat, A., Vaikuntanathan, V.: Bounded cca2-secure encryption. In: Kurosawa, K. (ed.) Advances in Cryptology - ASIACRYPT 2007, 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2–6, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4833, pp. 502–518. Springer (2007). https://doi.org/10.1007/978-3-540-76900-2_31
Fujisaki, E., Okamoto, T.: How to enhance the security of public-key encryption at minimum cost. In: Imai, H., Zheng, Y. (eds.) Public Key Cryptography, Second International Workshop on Practice and Theory in Public Key Cryptography, PKC ’99, Kamakura, Japan, March 1–3, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1560, pp. 53–68. Springer (1999). https://doi.org/10.1007/3-540-49162-7_5
Hohenberger, S., Koppula, V., Waters, B.: Chosen ciphertext security from injective trapdoor functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12170, pp. 836–866. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_28
Myers, S.A., Sergi, M., Shelat, A.: Black-box construction of a more than non-malleable CCA1 encryption scheme from plaintext awareness. J. Comput. Secur. 21(5), 721–748 (2013). https://doi.org/10.3233/JCS-130485
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Ortiz, H. (ed.) Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13–17, 1990, Baltimore, Maryland, USA, pp. 427–437. ACM (1990). https://doi.org/10.1145/100216.100273
Pass, R., shelat, Vaikuntanathan, V.: Construction of a non-malleable encryption scheme from any semantically secure one. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 271–289. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_16
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17–18 October, 1999, pp. 543–553. IEEE Computer Society, New York (1999). https://doi.org/10.1109/SFFCS.1999.814628
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Direct Implications and Separations
A Direct Implications and Separations
It follows directly from the definitions above that every CCA2-secure scheme is also nmCPA-secure, which is in turn also CPA secure. Additionally, in Lemma 2.5 we prove that every FuncCPA\(^+\)-secure scheme is also FuncCPA-secure, which is in turn CPA secure by definition. Here we study the other (non-)implications.
First, while our intuition tells us that every CCA2-secure scheme should also be FuncCPA\(^+\) secure, we note that this implication is not completely straightforward, because the FuncCPA attacker is allowed to copy the challenge ciphertext for its re-encryption queries, while the CCA2-attacker is not allowed to do so. Nonetheless, we show that our intuition is still correct. In fact, we show that already (weaker) CCA1-security implies FuncCPA\(^+\) security.
Lemma A.1
Every CCA1-secure encryption scheme is also FuncCPA\(^+\)-secure. (In particular, CCA2-security implies the original FuncCPA-security.)
Proof
Let q be the overall number of re-encryption queries made by the FuncCPA\(^+\)-attacker A. For \(0<i\le q\), we define hybrid \(H_i\) where the first i re-encryption queries \((\vec {\textsf{ct}},f)\) by A return \(\textsf{E}(\textsf{ek},f(\textrm{Dec}(\textsf{dk},\vec {\textsf{ct}})))\), and the remaining \((q-i)\) queries return \(\textsf{E}(\textsf{ek}, 0)\). By hybrid argument it is enough to prove that \(H_i\) is indistinguishable from \(H_{i+1}\), for every \(0<i\le q\), as \(H_0\) and \(H_q\) corresponding to \(b=0\) and \(b=1\) experiments, respectively.
For the latter, we have the following almost immediate reduction to CCA1-security from Definition 2.2. To simulate the j-th query \((\textsf{ct}_j,f_j)\) of an attacker A claiming to distinguish \(H_i\) from \(H_{i+1}\), the CCA1 attacker B does the following:
-
For \(j<i\), query its decryption oracle \(\mathcal{O}_1\) on the ciphertexts in \(\vec {\textsf{ct}}_j\), obtaining plaintexts \(\vec {\textsf{pt}}_j\). Compute \(\textsf{pt}_j' = f_j(\vec {\textsf{pt}}_j)\), and return to A an honestly generated \(\textsf{ct}_j' = \textrm{Enc}(\textsf{ek},\textsf{pt}_j')\).
-
For \(j=i\), query its decryption oracle \(\mathcal{O}_1\) on the ciphertexts in \(\vec {\textsf{ct}}_i\), obtaining plaintexts \(\vec {\textsf{pt}}_i\). Compute \(\textsf{pt}^* = f_i(\vec {\textsf{pt}}_i)\), and submit the tuple \((\textsf{pt}^*,0)\) as its challenge. Finally, return to A the resulting challenge ciphertext \(\textsf{ct}^*\) to the attacker.
-
For \(j>i\), ignore \((\vec {\textsf{ct}}_j,f_j)\), and return \(\textsf{E}(\textsf{ek}, 0)\) to A.
For \(b=0\), this run of B is a perfect simulation of \(H_i\), while for \(b=1\) it is a perfect simulation of \(H_{i+1}\), completing the proof.
In the opposite direction, Akavia et al. demonstrated in [1] that (somewhat surprisingly) CPA security of a scheme does not imply even the most basic ReEncCPA security of the same scheme. Below we extend their example to show that non-malleability (i.e., nmCPA-security) of a scheme also does not imply even ReEncCPA security. We also demonstrate that even FuncCPA\(^+\) security does not imply nmCPA-security.
Lemma A.2
If nmCPA-secure encryption schemes exist, then there exists a nmCPA-secure encryption scheme which is not ReEncCPA-secure. Conversely, if FuncCPA\(^+\)-secure encryption schemes exist, then there exists a FuncCPA\(^+\)-secure encryption scheme which is not nmCPA-secure.
Proof
Starting from the easy separation, we can append 0 to all honestly produced ciphertexts in a FuncCPA\(^+\)-secure encryption scheme, and have the decryption oracle simply ignore this appended bit. This clearly does not change FuncCPA\(^+\)-security, as all honestly re-encrypted ciphertexts will still end with 0. However, the scheme is obviously malleable, by flipping the last bit of the challenge ciphertext from 0 to 1, and calling the decryption oracle of the resulting (formally “distinct”) ciphertext.
For the other separation, let \(\mathcal {E}=(\textrm{Gen},\textrm{Enc},\textrm{Dec})\) be a scheme which is nmCPA-secure according to Definition 2.2, and we modify it into a scheme \(\mathcal {E}'=(\textrm{Gen}',\textrm{Enc}',\textrm{Dec}')\) as follows:
-
\(\textrm{Gen}'\) just runs \(\textrm{Gen}\) twice, outputting the two pairs \(((\textsf{dk},\textsf{dk}'),(\textsf{ek},\textsf{ek}'))\). Roughly, \(\textsf{dk},\textsf{ek}\) are the “real keys” for decryption and encryption, whereas \(\textsf{dk}',\textsf{ek}'\) are used for signalling various events.
-
The new encryption \(\textrm{Enc}'((\textsf{ek},\textsf{ek}'),\textsf{pt})\) checks if \(\textsf{pt}\) is the secret key corresponding to either \(\textsf{ek}\) or \(\textsf{ek}'\):
-
If \(\textsf{pt}\) is the secret key corresponding to \(\textsf{ek}\) or \(\textsf{ek}'\) then output \(1|\textsf{pt}\),
-
Otherwise output \(0|\textrm{Enc}(\textsf{ek},\textsf{pt})\).
-
-
The new decryption \(\textrm{Dec}((\textsf{dk},\textsf{dk}'),\textsf{ct}')\) parses \(\textsf{ct}'=b|\textsf{ct}\) with \(b\in \{0,1\}\), then proceeds as follows:
-
If \(b=1\) and \(\textsf{ct}=\textsf{dk}'\) then output \(\textsf{dk}\),
-
If \(b=1\) and \(\textsf{ct}\ne \textsf{dk}'\) then output \(\textsf{dk}'\),
-
Otherwise output \(\textrm{Dec}(\textsf{dk},\textsf{ct})\).
-
It is easy to see that the modified \(\mathcal {E}'\) is still nmCPA-secure: An nmCPA attack on \(\mathcal {E}'\) can be turned into nmCPA attack on the underlying \(\mathcal {E}\) by having the reduction generate \((\textsf{dk}',\textsf{ek}')\) itself, then simulate the sole decryption query to \(\mathcal {E}'\) using its decryption oracle to \(\mathcal {E}\): Unless the \(\mathcal {E}'\) attacker guesses \(\textsf{dk}'\) (on which it has no information other than seeing \(\textsf{ek}'\)), then it cannot trigger the 1st bullet on decryption above.
On the other hand, it is easy to see that a ReEncCPA attacker can break this scheme completely, first making a query with \(\textsf{ct}=11\ldots 1\) to get \(1|\textsf{dk}'\), then making a second query with \(1|\textsf{dk}'\) to get “the real key” \(\textsf{dk}\).
Next, we show separation between ReEncCPA and ReEncCPA\(^+\) notions (and conjecture that similar separations hold for FuncCPA and \(1\)-FuncCPA notions).
Lemma A.3
If ReEncCPA-secure encryption schemes exist, then there exists a ReEncCPA-secure encryption scheme which is not ReEncCPA\(^+\)-secure.
Proof
Let \(\mathcal {E}=(\textrm{Gen},\textrm{Enc},\textrm{Dec})\) be a scheme which is ReEncCPA-secure according to Definition 2.2, and we modify it into a scheme \(\mathcal {E}'=(\textrm{Gen}',\textrm{Enc}',\textrm{Dec}')\) as follows: The key generation remains unchanged, \(\textrm{Gen}'=\textrm{Gen}\). Encryption is modified by setting
(Note that it is possible to check efficiently whether the condition above holds.) Decryption is also modified, as follows:
It is easy to see that \(\mathcal {E}'\) is still ReEncCPA-secure according to Definition 2.2 (with a non-functional decryption oracle), since access to the oracle for \(\mathcal {E}'\) can be perfectly simulated using access to the oracle for \(\mathcal {E}\). (Indeed ciphertext beginning with 1 are answered with \(11\ldots 1\) and ciphertexts beginning with 0 are answered as in \(\mathcal {E}\), with a zero prepended to the reply.) On the other hand, it is easy to distinguish a true re-encryption oracle from a zero-encrypting one, just by querying it on any ciphertext that begins with a 1.
Finally, we show that a \(1\)-FuncCPA\(^+\)-secure scheme is not necessarily FuncCPA-secure (and, thus, not necessarily FuncCPA\(^+\)-secure), assuming the existence of CCA-secure schemes.
Lemma A.4
If CCA-secure encryption schemes exist, then there exists a \(1\)-FuncCPA\(^+\)-secure encryption scheme which is not FuncCPA-secure.
Proof
Let \(\mathcal {E}=(\textrm{Gen},\textrm{Enc},\textrm{Dec})\) be a CCA-secure scheme, and let \(OWF(\cdot )\) be a one-way function. (Recall that CCA-secure encryption implies the existence of one-way functions.) Consider the modified scheme \(\mathcal {E}'=(\textrm{Gen}',\textrm{Enc}',\textrm{Dec}')\), defined as follows:
-
\(\textrm{Gen}'(1^{\lambda })\) runs the underlying key-generation \((\textsf{dk},\textsf{ek}) \leftarrow \textrm{Gen}(1^{\lambda })\), and in addition chooses two uniformly random and independent strings \(r,s\leftarrow \{0,1\}^{\lambda }\) and sets \(y=OWF(r \oplus s)\). The public key is \(\textsf{ek}'=(\textsf{ek}, y)\) and the secret key is \(\textsf{dk}'=(\textsf{dk},r,s)\).
-
\(\textrm{Enc}'(\textsf{ek}',\textsf{pt})\): If \(y=OWF(\textsf{pt})\) then output \(\textsf{pt}\), else output \((0,\textrm{Enc}(\textsf{ek},\textsf{pt}))\).
-
\(\textrm{Dec}'(\textsf{dk}', (b,\textsf{ct}))\): If \(b=0\) then output \(\textrm{Dec}(\textsf{dk},\textsf{ct})\). If \(b=1\) then output r, if \(b=2\) then output s.
We show that \(\mathcal {E}'\) is \(1\)-FuncCPA\(^+\)-secure, but not FuncCPA-secure. To see that \(\mathcal {E}'\) is \(1\)-FuncCPA\(^+\)-secure, let us again consider only adversaries that never use the answers from previous re-encryption queries as inputs to future queries. (As we argued before, we can make this assumption without loss of generality.) Fixing one such adversary, we consider a sequence of hybrids, where in the i’th hybrid the first \(i-1\) queries are answered by encryption of 0, and the i’th query and later are answered by the single-ciphertext re-encryption oracle. Arguing that hybrid i is indistinguishable from hybrid \(i+1\) is done in two steps:
-
We first argue that the i’th query will not decrypt to \(r\oplus s\) (except with a negligible probability), by reduction to the one-wayness of \(OWF(\cdot )\). Here, the reduction algorithm is given the secret key \(\textsf{dk}\) of the underlying encryption scheme \(\textrm{Enc}\).
-
Then we replace the i’th query answer by an encryption of zero, and argue indistinguishability by reduction to the CCA-security of the underlying scheme \(\mathcal {E}\). Here the reduction algorithm is given access to the decryption oracle of \(\mathcal {E}\), that allows it to simulate the answers to all future queries.
On the other hand, it is clear that \(\mathcal {E}'\) is not FuncCPA-secure. The multi-ciphertext re-encryption oracle is easily distinguishable from a zero-encrypting oracle, because it enables easy extraction of a pre-image of y under \(OWF(\cdot )\): The multi-ciphertext query \((\textsf{ct}_1=(1,0^\lambda ), \textsf{ct}_2=(2,0^{\lambda }), f=\oplus )\) will decrypt \(\textsf{ct}_1\) to r and \(\textsf{ct}_2\) to s, then compute \(x=f(r,s)=r\oplus s\), and applying the modified encryption procedure it will return the pre-image x. (As above, obtaining a pre-image of y is hard given a zero-encrypting oracle, by reduction to the one-wayness of \(OWF(\cdot )\).)
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Dodis, Y., Halevi, S., Wichs, D. (2023). Security with Functional Re-encryption from CPA. In: Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14370. Springer, Cham. https://doi.org/10.1007/978-3-031-48618-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-48618-0_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-48617-3
Online ISBN: 978-3-031-48618-0
eBook Packages: Computer ScienceComputer Science (R0)