Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can “freely” perform the operation inevitably means that ciphertexts are malleable, and it is well-known that adaptive chosen ciphertext (CCA) security and the homomorphic property can never be achieved simultaneously. In this paper, we show that CCA security and the homomorphic property can be simultaneously handled in situations that the user(s) who can perform homomorphic operations on encrypted data should be controlled/limited, and propose a new concept of homomorphic public-key encryption, which we call keyed-homomorphic public-key encryption (KH-PKE). By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation. To construct KH-PKE schemes, we introduce a new concept, transitional universal property, and present a practical KH-PKE scheme with multiplicative homomorphic operations from the decisional Diffie-Hellman (DDH) assumption. For \(\ell \)-bit security, our DDH-based KH-PKE scheme yields only \(\ell \)-bit longer ciphertext size than that of the Cramer–Shoup PKE scheme. Finally, we consider an identity-based analogue of KH-PKE, called keyed-homomorphic identity-based encryption and give its concrete construction from the Gentry IBE scheme.

1. When there are only less than \(\kappa \) refreshing processes, we simply ignore the case of \(\kappa '\) beyond the number of the refreshing processes. Similar remarks are applied to the following arguments.

2. We remark that such a transition is acceptable if we make an information-theoretic jump, i.e., Assumption I. However, we still require that, for Assumptions A and U, PPT adversaries need to use the private evaluation algorithms of \(\mathbf {P}\) and \(\widehat{\mathbf {P}}\) for regular input by using k and \(\widehat{k}\) since we use computationally universal properties. However, again the projective property of the projective hash family implies that the computed value is not changed by the modification, and thus still the simulation works well. See the description of adversaries \({\mathcal {A}}_{3,1}\) and \({\mathcal {A}}_{3,2}\) later.

3. More precisely, the adversary outputs any object that trivially yields loss of the game.

4. Note that this process does not require the key for \(\widetilde{\mathbf {P}}\); since all the ciphertexts appearing during the refreshing process are guaranteed to be \(\widetilde{H}\)-consistent, and the consistency checks for the fourth components can be omitted.

5. Note that this notion is (somewhat similar to but) different from the smoothness of a projective hash family.

6. Even if this “non-uniform” security assumption is not justified (and only security against uniform PPT adversaries is assumed), n can still be as small as at most \(2\ell \)-bit, which is still smaller than (or in some group equal to) the size of an element in the group \({\mathbb {G}}\).See our analysis of smoothness of these cryptographic functions in Appendix 1.

7. The probability that \(g_*\) is not a generator of L is \(1 - (1 - 1/p')(1 - 1/q') = 1/p' + 1/q' - 1 / (p'q')\), which is negligible (otherwise, the DCR assumption can be trivially broken since \({\mathbb {Z}}^*_{N^2}\) is not large enough).

8. The distribution of the \(g_*^{\omega }\) and the uniform distribution on L have statistical distance \((\lfloor N/4 \rfloor - p'q')(2/(p'q') - 1/(p'q')) \le (2p'+1)(2q'+1)/(4p'q') - 1 = 1/(2p') + 1/(2q') + 1/(4p'q')\), which is negligible.

9. In this paper, we assume that the \(\mathsf{IBE.KeyGen}\) algorithm is deterministic as in the definition of the Gentry IBE.

10. Recall that a non-uniform algorithm is an algorithm that takes as an advice string (which is dependent only on the input length) as an additional input. The class of non-uniform PPT algorithms is equivalent to the class of polynomial-sized circuit families.

11. In general, there could be multiple strings \(y \in \{0,1\}^{\ell }\) that maximize the probability \(\Pr _{x \mathop {\leftarrow }\limits ^{\$} {\mathcal {X}}_{\ell }}[f(x) = y]\). Choosing the lexicographically smallest one is to canonically specify one of such strings.

We thank the anonymous reviewers and the members of Shin-Akarui-Angou-Benkyou-Kai for their helpful comments. This work was supported by JSPS KAKENHI Grant Number JP24700009 and by JST PRESTO Grant Number JPMJPR14E8, Japan.

Authors and Affiliations

1. National Institute of Information and Communications Technology (NICT), Tokyo, Japan

   Keita Emura

2. National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

   Goichiro Hanaoka, Koji Nuida, Takahiro Matsuda & Shota Yamada

3. Japan Broadcasting Corporation, Tokyo, Japan

   Go Ohtake

Corresponding author

Correspondence to Keita Emura.

Communicated by M. Albrecht.

An extended abstract appears in the 16th International Conference on Practice and Theory in Public Key Cryptography (PKC 2013) [19]. This is the full version.

Appendix A: Smoothness of cryptographic functions

In this section, we show that natural cryptographic functions, a one-way function (OWF), an always second-preimage resistant (aSec secure) hash function [41], and a key derivation function (KDF) [16], are smooth in the sense of Definition 10.

Interestingly, although the amount of smoothness, \({\mathsf {Smth}}_f\), is always negligible, its “tightness” is different depending on whether the function f is secure against uniform adversaries or against non-uniform adversaries.^{Footnote 10} More specifically, for each cryptographic function f considered here, we show that the smoothness of f is (essentially) upperbounded by the square root of the advantage of some (uniform) PPT adversary \({\mathcal {A}}\) attacking the security of the function f. We also show that the smoothness of f is (essentially) upperbounded by the advantage of some non-uniform PPT adversary \(\mathrm {A}_{\mathrm {nu}}\). These results suggest that if we can assume the security of these cryptographic functions against non-uniform adversaries, then the output length can be as small as \(\ell \)-bit for \(\ell \)-bit security, because the smoothness of the functions are “tightly” upperbounded by the advantage of “non-uniform” adversaries attacking the security of the cryptographic functions Furthermore, even if this “non-uniform” security assumption is not justified (and instead only security against uniform adversaries is assumed), the output length the function can still be as small as at most \(2\ell \)-bit, because the main term that contribute to the smoothness is the square root of the advantage of an adversary attacking the security of the cryptographic functions (against uniform PPT adversaries).

In practice, for example, (an appropriate modification of) cryptographic hash functions such as SHA-series, can be assumed to be the cryptographic functions (secure against non-uniform adversaries) considered here.

Some notation To show the smoothness of each cryptographic function, it is useful to introduce the following notation. Let \(f :{\mathcal {X}}_{\ell } \rightarrow \{0,1\}^{\ell }\) be a function. For each \(\ell \in {{\mathbb {N}}}\), let \(y^{\max }_{\ell } \in \{0,1\}^{\ell }\) be the lexicographically smallest string^{Footnote 11} such that \(\Pr _{x \mathop {\leftarrow }\limits ^{\$} {\mathcal {X}}_{\ell }}[f(x) = y^{\max }_{\ell }] \ge \Pr _{x \mathop {\leftarrow }\limits ^{\$} {\mathcal {X}}_{\ell }}[f(x) = y]\) holds for any \(y \in \{0,1\}^{\ell }\). Then, by definition, we have \({\mathsf {Smth}}_f = \max _{y \in \{0,1\}^{\ell }} \Pr _{x \mathop {\leftarrow }\limits ^{\$} {\mathcal {X}}_{\ell }}[f(x) = y] = \Pr _{x \mathop {\leftarrow }\limits ^{\$} {\mathcal {X}}_{\ell }}[f(x) = y^{\max }_{\ell }]\). Next, for each \(\ell \in {{\mathbb {N}}}\), we define \(x^{\max }_{\ell } \in {\mathcal {X}}_{\ell }\) to be the lexicographically smallest string in the set \(\{x \in {\mathcal {X}}_{\ell } | f(x) = y^{\max }_{\ell }\}\). Note that \(y^{\max }_{\ell } \in \{0,1\}^{\ell }\) and \(x^{\max }_{\ell } \in {\mathcal {X}}_{\ell }\) are uniquely determined for each \(\ell \in {{\mathbb {N}}}\).

For the function f, it is also useful to note the following properties about the probability of “collision” for random inputs:

where the former is by definition, and the latter is obtained as follows:

1.1 A.1 One-way function

Definition 18

(One-Way Function (OWF)) Let \(f : {\mathcal {X}}_{\ell } \rightarrow \{0,1\}^{\ell }\) be a function, where \(n = n(\ell ) := \log _2 |{\mathcal {X}}_{\ell }| \in \omega (\log _2 \ell )\). We say that f is a one-way function (OWF) if (1) f is efficiently computable in terms of the security parameter \(\ell \) (and thus n is some polynomial of \(\ell \)), (2) we can efficiently sample an element uniformly at random from the domain \({\mathcal {X}}_{\ell }\), and (3) \(Adv^\mathsf{{OWF}}_{{\mathcal {A}}}(\ell ):=\Pr _{x\mathop {\leftarrow }\limits ^{\$}{\mathcal {X}}_{\ell }}[x' \leftarrow {\mathcal {A}}(1^{\ell },f(x)) : f(x') = f(x)]\) is negligible for any PPT algorithm \({\mathcal {A}}\).

Furthermore, we say that f is a OWF against non-uniform adversaries if the condition (3) is replaced with “\(Adv^\mathsf{{OWF}}_{{\mathcal {A}}_{\mathrm {nu}}}(\ell )\) is negligible for any non-uniform PPT algorithms \({\mathcal {A}}_{\mathrm {nu}}\).”

Lemma 12

If f is a OWF as defined in Definition 18, then f is smooth. Specifically, there exists a PPT algorithm \({\mathcal {A}}\) such that

Furthermore, there exists a non-uniform PPT algorithm \({\mathcal {A}}_{\mathrm {nu}}\) such that

Proof

We first show the existence of the uniform PPT adversary \({\mathcal {A}}\) against the one-wayness of f. Consider the algorithm \({\mathcal {A}}\) that takes \(1^{\ell }\) and \(y = f(x)\) (where \(x \in {\mathcal {X}}_{\ell }\) is chosen uniformly at random) as input, picks \(x' \in {\mathcal {X}}_{\ell }\) uniformly at random, and terminates with output this \(x'\). Note that \({\mathcal {A}}\) is a (uniform) PPT algorithm, and its one-wayness advantage is as follows:

where in the last step we use the inequation (3). Therefore, we have \({\mathsf {Smth}}_f \le \sqrt{Adv^{{\mathsf {OWF}}}_{{\mathcal {A}}}(\ell )}\), as required.

We next show the existence of the non-uniform adversary \({\mathcal {A}}_{\mathrm {nu}}\) against the one-wayness of f. Consider the non-uniform PPT algorithm \({\mathcal {A}}_{\mathrm {nu}}\) that has \(x^{\max }_{\ell }\) as an advice (i.e. \(x^{\max }_{\ell }\) is hard-wired inside \({\mathcal {A}}_{\mathrm {nu}}\) for each security parameter \(\ell \in {{\mathbb {N}}}\)), takes \(1^{\ell }\) and \(y = f(x)\) as input (where \(x \in {\mathcal {X}}_{\ell }\) is chosen uniformly at random), and terminates with output the string \(x^{\max }_{\ell }\). Clearly \({\mathcal {A}}_{\mathrm {nu}}\) is PPT, and its one-wayness advantage is:

as required.

This completes the proof of Lemma 12. \(\square \)

1.2 A.2 Always second-preimage resistant hash functions

Definition 19

(Always Second-Preimage Resistant (aSec) Hash Functions [41]) Let \({\mathsf {H}} : {\mathcal {X}}_{\ell } \rightarrow \{0,1\}^{\ell }\) be a function, where \(n = n(\ell ) := \log _2 |{\mathcal {X}}_{\ell }| \in \omega (\log _2 \ell )\). We say that \({\mathsf {H}}\) is an always second-preimage resistant (aSec secure) hash function if (1) \({\mathsf {H}}\) is efficiently computable in terms of the security parameter \(\ell \) (and thus n is some polynomial of \(\ell \)), (2) we can efficiently sample an element uniformly at random from the domain \({\mathcal {X}}_{\ell }\), (3) \(Adv^\mathsf{{aSec}}_{{\mathcal {A}}}(\ell ):= \Pr _{x\mathop {\leftarrow }\limits ^{\$}{\mathcal {X}}_{\ell }}[x' \leftarrow {\mathcal {A}}(1^{\ell },x) : \mathsf {H}(x') = \mathsf {H}(x) \wedge x' \ne x]\) is negligible for any PPT algorithm \({\mathcal {A}}\).

Furthermore, we say that \(\mathsf {H}\) is an aSec secure hash function against non-uniform adversaries if the condition (3) is replaced with “\(Adv^\mathsf{{aSec}}_{{\mathcal {A}}}(\ell )\) is negligible for any non-uniform PPT algorithm.”

We remark that an aSec secure hash function is (close to but) different from the notion of universal one way hash function (UOWHF) [5]. UOWHF is a family of hash functions (or a keyed hash function), and in the security experiment, an adversary is allowed to choose the first message x for which the adversary has to find a collision, but is required to find a colliding input \(x'\) under a randomly chosen key hk.

Lemma 13

If \(\mathsf {H}\) is an aSec secure hash function as defined in Definition 19, then \(\mathsf {H}\) is smooth. Specifically, there exists a PPT algorithm \({\mathcal {A}}\) such that

Furthermore, there exists a non-uniform PPT algorithm \({\mathcal {A}}_{\mathrm {nu}}\) such that

Proof

The proof proceeds very similarly to that of Lemma 12. First, we show the existence of the uniform PPT adversary \({\mathcal {A}}\) against the aSec security of \(\mathsf {H}\). Consider the algorithm \({\mathcal {A}}\) that takes \(1^{\ell }\) and x (for a uniformly chosen value \(x \in {\mathcal {X}}_{\ell }\)) as input, picks \(x' \in {\mathcal {X}}_{\ell }\) uniformly at random, and terminates with output this \(x'\). Note that \({\mathcal {A}}\) is trivially a (uniform) PPT algorithm, and its advantage against aSec security of \({\mathcal {H}}\) is as follows:

Therefore, we have \({\mathsf {Smth}}_{\mathsf {H}} \le \sqrt{Adv^{{\mathsf {aSec}}}_{{\mathcal {A}}}(\ell ) + |{\mathcal {X}}_{\ell }|^{-1}}\), as required.

We next show the existence of the non-uniform adversary \({\mathcal {A}}_{\mathrm {nu}}\) against the aSec security of \(\mathsf {H}\). Consider the non-uniform PPT algorithm \({\mathcal {A}}_{\mathrm {nu}}\) that has \(x^{\max }_{\ell } \in {\mathcal {X}}_{\ell }\) as an advice (i.e. \(x^{\max }_{\ell }\) is hard-wired inside \({\mathcal {A}}_{\mathrm {nu}}\) for each security parameter \(\ell \in {{\mathbb {N}}}\)), takes \(1^{\ell }\) and x as input (where x is chosen uniformly at random), and terminates with output the string \(x^{\max }_{\ell }\). Clearly \({\mathcal {A}}_{\mathrm {nu}}\) is PPT, and its advantage is:

Therefore, we have \({\mathsf {Smth}}_{\mathsf {H}} = Adv^{{\mathsf {aSec}}}_{{\mathcal {A}}_{\mathrm {nu}}}(\ell ) + |{\mathcal {X}}_{\ell }|^{-1}\), as required.

This completes the proof of Lemma 13. \(\square \)

1.3 A.3 Key derivation function

Definition 20

(Key Derivation Function (KDF) [16]) Let \(\mathsf {KDF}:{\mathcal {X}}_{\ell } \rightarrow \{0,1\}^\ell \) be a function, where \(n = n(\ell ):= \log _2 |{\mathcal {X}}_{\ell }| \in \omega (\log _2 \ell )\). We say that \(\mathsf {KDF}\) is a secure key derivation function (KDF) if (1) \(\mathsf {KDF}\) is efficiently computable in terms of the security parameter \(\ell \) (and thus n is some polynomial of \(\ell \)), (2) We can efficiently sample an element uniformly at random from the domain \({\mathcal {X}}_{\ell }\), and (3) \(Adv^{{\mathsf {KDF}}}_{{\mathcal {A}}}(\ell ):=|\Pr _{x\mathop {\leftarrow }\limits ^{\$}\varDelta }[{\mathcal {A}}(1^{\ell },\mathsf{KDF}(x))=1]-\Pr _{y \mathop {\leftarrow }\limits ^{\$}\{0,1\}^\ell }[{\mathcal {A}}(1^{\ell }, y)=1]|\) is negligible for any PPT algorithm \({\mathcal {A}}\).

Furthermore, we say that \(\mathsf {KDF}\) is a secure KDF against non-uniform adversaries if \(Adv^{\mathsf {KDF}}_{{\mathcal {A}}_{\mathrm {nu}}}(\ell )\) is negligible for any non-uniform algorithm \({\mathcal {A}}_{\mathrm {nu}}\).

Lemma 14

If \(\mathsf {KDF}\) be a secure key derivation function as defined in Definition 20, then \(\mathsf {KDF}\) is smooth. Specifically, there exists a uniform PPT algorithm \({\mathcal {A}}\) such that

Furthermore, there exists a non-uniform PPT algorithm \({\mathcal {A}}_{nu}\) such that

Proof

We first show the existence of the uniform PPT adversary \({\mathcal {A}}\) against the security of \(\mathsf {KDF}\). Consider the algorithm \({\mathcal {A}}\) that takes \(1^{\ell }\) and \(y \in \{0,1\}^{\ell }\) as input, picks \(x' \in {\mathcal {X}}_{\ell }\) uniformly at random, and returns 1 if \(G(x') = y\) or returns 0 otherwise. Note that \({\mathcal {A}}\) is clearly PPT, and its advantage is as follows:

where in the last inequality we use the inequality (3) and the fact that y is chosen uniformly at random from \(\{0,1\}^{\ell }\). Therefore, we have \(\mathsf {Smth}_{\mathsf {KDF}} \le \sqrt{Adv^{\mathsf {KDF}}_{{\mathcal {A}}}(\ell ) + 2^{-\ell }}\), as required.

Next, we show the existence of the non-uniform PPT adversary \({\mathcal {A}}_{\mathrm {nu}}\) against the security of \(\mathsf {KDF}\). Consider the algorithm \({\mathcal {A}}_{\mathrm {nu}}\) that has \(y^{\max }_{\ell } \in \{0,1\}^{\ell }\) as an advice (i.e. \(y^{\max }_{\ell }\) is hard-wired inside \({\mathcal {A}}_{\mathrm {nu}}\) for each \(\ell \in {{\mathbb {N}}}\)), takes \(1^{\ell }\) and \(y \in \{0,1\}^{\ell }\) as input, and returns 1 if \(y = y^{\max }_{\ell }\) or returns 0 otherwise. Note that \({\mathcal {A}}_{\mathrm {nu}}\) is clearly PPT, and its advantage is as follows:

Therefore, we have \({\mathsf {Smth}}_{{\mathsf {KDF}}} = Adv^{{\mathsf {KDF}}}_{{\mathcal {A}}_{\mathrm {nu}}}(\ell ) + 2^{-\ell }\), as required.

This completes the proof of Lemma 14. \(\square \)

Reprints and permissions