Robust Encryption, Extended

Abstract

Robustness is a notion often tacitly assumed while working with encrypted data. Roughly speaking, it states that a ciphertext cannot be decrypted under different keys. Initially formalized in a public-key context, it has been further extended to key-encapsulation mechanisms, and more recently to pseudorandom functions, message-authentication codes and authenticated encryption. In this work, we motivate the importance of establishing similar guarantees for functional encryption schemes, even under adversarially generated keys. Our main security notion is intended to capture the scenario where a ciphertext obtained under a master key (corresponding to Authority 1) is decrypted by functional keys issued under a different master key (Authority 2). Furthermore, we show there exist simple functional encryption schemes where robustness under adversarial key-generation is not achieved. As a secondary and independent result, we formalize robustness for digital signatures – a signature should not verify under multiple keys – and point out that certain signature schemes are not robust when the keys are adversarially generated.

We present simple, generic transforms that turn a scheme into a robust one, while maintaining the original scheme’s security. For the case of public-key functional encryption, we look into ciphertext anonymity and provide a transform achieving it.

1 Introduction

Cryptographic primitives, such as encryption and signature schemes, provide security guarantees under the condition, often left implicit, that they are “used correctly”. Fatal examples of cryptographic misuse abound, from weak key generation to nonce-reuse. This reliance on operational security has attracted attackers, who can for instance impose faulty or backdoored random number generators to erode cryptographic protections. At the same time, the social usage of technology leans towards a more open environment than the one in which historic primitives were designed: keys are generated by one party, shared with another, certified by third... These two observations raise new interesting questions, which have only recently been addressed in the cryptographic literature. For instance, if Alice generates keys that she is using, but doesn’t share, can an adversary (observing Alice or influencing her in some way) nevertheless generate a different set of keys, which would allow decryption (maybe only partial)? Intuitively this should not be the case, but it was not until the seminal work of Abdalla, Bellare and Neven [1], that this situation was formally analysed. They introduced the notion of robustness, which ensures that a ciphertext cannot be decrypted under multiple keys.

Imagine a scenario where users within a network exchange messages by broadcasting them, and further encrypt them with the public key of the recipient to ensure confidentiality. If this is the case, we usually assume that there is only one receiver, by arguing that no other members apart from the intended recipient can decrypt the ciphertext and obtain a valid (non-$\perp$) plaintext. But if the adversary can somehow tamper with the key generation process, she may “craft” keys that behave unexpectedly for some messages, or design alternative keys that give at least some information on some of the messages.

Farshim et al. [12] refined the original definition of robustness, by covering the cases where the keys are adversarially generated, under a master notion called “complete robustness”. Mohassel addressed the question in the context of key-encapsulation mechanisms [19]. More recently, Farshim et al. also defined robustness for symmetric primitives [13], motivated by the security of oblivious transfer protocols [9] or message authentication codes. Further extensions of their security notions found applications in novel password-authenticated key-exchange protocols described by Jarecki et al. [17] or (fast) message-franking schemes [16]. The above line of work, however, leaves open several questions. Indeed, to the best of our knowledge there has been no notion of robustness defined for digital signatures [15], functional signatures [7] or functional encryption [6, 20]. Yet, some existing schemes seem to be vulnerable to attacks that a proper notion of robustness would prevent.

Consider digital signature schemes (DS), that are used to authenticate electronic documents. The textbook notion, capturing the existential unforgeability of a DS ensures that an adversary, interacting with one signing oracle, cannot forge a signature (for a message he did not previously query). On the other hand, a real-world scenario is placed in a multi-user context, where it is often assumed (but not necessarily proven) that a signature can only be verified under the issuer’s key.

Example 1:

Consider a practical situation where a clerk has acquired a digital signature for daily use, with a third party generating the pairs of keys. Even if the scheme remains unforgeable according to the classical definition, we do not have formal guarantees that two pairs of keys—$(\mathsf {sk},\mathsf {pk})$ and $(\mathsf {sk}',\mathsf {pk}')$—generated by the third party (potentially malicious), cannot be used to produce a signature $\sigma$ for some chosen message $M$, verifiable under both $\mathsf {pk}$ and $\mathsf {pk}'$—something completely undesirable in practice. To be fully explicit with our example, let us suppose one pair of keys $(\mathsf {pk}, \mathsf {sk})$ is given to the clerk and the second pair $(\mathsf {pk}', \mathsf {sk}')$, is issued by the third party and is covertly used by a local/global security agency. When needed (and if needed), an operator can issue a signature (using $\mathsf {sk}'$) for the message: “I attest [...] is true.” which can later be verified under $\mathsf {pk}$, thus having baleful consequences for the clerk.

To give a flavour of a signature scheme where such an attack is feasible, consider the one obtained from a toy version of the Boneh–Boyen scheme [4]. The construction is pairing-based and can be summarized as follows: (1) key-generation samples two group generators $g_1 \in \mathbb {G}_1$ and $g_2 \in \mathbb {G}_2$, both of prime order p, and publishes as a public key $(g_1, g_2, g_2^x, e(g_1,g_2))$—for a uniformly sampled x over $\mathbb {Z}_p$—keeping x as a secret key. To sign the message $M$, one computes $\sigma \leftarrow g_1^{1/(x+ M )}$. A robustness attack against this simple signature scheme exploits the randomness in choosing the secret keys, observing that for a different pair $(\mathsf {pk}', \mathsf {sk}')$, one can choose ${g'_1} \equiv g_1^t \pmod p$ and then can set $x' \equiv t(x+ M ) - M \pmod p$ such that $\sigma \equiv {g'_1}^{1/(x'+ M )}$.

The above example provides the intuition that robustness has practical consequences. As expected, under correct key generation, standard unforgeability does imply robustness. But it fails in a malicious setting. Fortunately, we can provide a trivial construction that generically transforms any unforgeable signature scheme into a completely robust one (allowing for adversarial, yet well-formed keys). As we prove in Sect. 4.1, the natural idea of including the public key (or a collision-resistant hash of it) in the signature is indeed sufficient.

Speaking roughly about robustness as the property of a ciphertext of not being decryptable under multiple keys, then, when it comes to decryption, an ${\textsf {FE}}$ scheme trivially does not exhibit this property. The reason resides in the broken symmetry to the way decryption works in symmetric/public-key schemes. Through its purpose, a functional ciphertext can be decrypted under multiple keys [6, 20]. In this respect, an adversary holding multiple functional keys (which is not a restriction by itself) will be able to decrypt under multiple keys. Therefore, defining robustness in terms of decryption itself is fallacious. Instead, an appropriate definition should ensure the ${\textsf {FE}}$ ciphertext can be decrypted only by the intended set of receivers.

Example 2:

Consider a simple use case of a functional encryption scheme for the “inner product” function (IP FE) [2, 3]. From a technical perspective, suppose the ciphertext is generated by encrypting a plaintext $M$ as $\textit{C} \leftarrow {\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}, M ; R )$. If $\mathsf {msk}$ is somehow corrupted¹ to $\mathsf {msk}'$, then is it possible that performing decryption under $\mathsf {sk}_y'$ reveals a different plaintext $M ' \ne M$? Intuitively, if the functional encryption scheme meets robustness, we expect that no ciphertext can be decrypted under functional keys issued by a different master secret keys.

As a concrete scenario, consider a Computer Science (CS) department’s registry, which holds the marks obtained by each student in the Crypto course, the final grade being computed as a weighted average of the stored marks (i.e. homework counts 30%, midterm 20% and final 50%). A priori established confidentiality rules ask that a clerk should not have access to the marks, but still, it must be possible to compute the final grade. Therefore, considering the set of marks as the vector ${\varvec{x}}$ and the weights as ${\varvec{y}}$, one can use an IP FE scheme, to obtain the final grade, its formula mapping to ${\varvec{x}}^\top \cdot {\varvec{y}}$. In order to achieve this, for each course: (1) the course leader encrypts the marks; (2) later, the clerk obtains a new key $\mathsf {sk}_y$ (depending on the established course weights), and uses it to obtain the final average. A failure to guarantee robustness could result in decryption to succeed, but the final average being incorrect (and possibly under the control of an adversary). To illustrate this, consider the (bounded-norm) IP FE scheme instantiated from ElGamal and introduced in [2]: encrypting a plaintext under —where $\mathsf {msk}={\varvec{s}}=(s_1, \ldots , s_n)$—is done as follows: , for r sampled uniformly at random in $\mathbb {Z}_p$. If an attacker wishes to obtain the same $\textit{C}$, then r remains the same, but it can use different and , implicitly changing the value of $\mathsf {msk}$. As expected, even if ${\textsf {FE}}.\mathsf {KDer}$ is correct, and the queried key is indeed issued for the vector ${\varvec{y}}$, the final decrypted result corresponds to rather than to ${\varvec{x}}^\top \cdot {\varvec{y}}$.

We begin by motivating and defining the notion of robust signature schemes under honest and adversarial keys, denoted as strong ($\mathrm {SROB}$) and complete ($\mathrm {CROB}$) robustness (Sect. 3.1). A natural question is whether existing schemes already possess a form of robustness: we show that while $\mathrm {SROB}$ is indeed typically guaranteed, it is not the case of $\mathrm {CROB}$, thus providing a separation between the two security concepts. Fortunately, there exist a simple generic transform, in the standard model, that turn a $\mathrm {SROB}$ signature scheme into a $\mathrm {CROB}$ one (Sect. 4.1).

In Sect. 3.2, we define robustness for functional encryption in a multi-authority context. The strongest security notion we propose (FEROB) is intended to capture adversaries able to generate the keys and the randomness used during encryption and key-derivation, while remaining as simple as possible. As regards the generic transforms, we provide them in the public and private-key paradigms Sect. 4.2. The case for private-key FE schemes [8, 18] relies on right-injective PRGs and collision-resistant PRFs, concepts that we review in Sect. 2. Finally, in the original spirit of the security notion we consider, we discuss anonymity for the context of functional encryption schemes.

2 Preliminaries

We denote the security parameter by $\lambda \in \mathbb {N}^*$ and we assume it is implicitly given to all algorithms in the unary representation $1^\lambda$. An algorithm is equivalent to a Turing machine. Algorithms are assumed to be randomized unless stated otherwise; $\mathrm {PPT}$ stands for “probabilistic polynomial-time,” in the security parameter (rather than the total length of its inputs). Given a randomized algorithm $\mathcal {A}$ we denote the action of running $\mathcal {A}$ on input(s) with uniform random coins r and assigning the output(s) to by . When $\mathcal {A}$ is given oracle access to some procedure $\mathcal {O}$, we write $\mathcal {A}^{\mathcal {O}}$. For a finite set S, we denote its cardinality by |S| and the action of sampling a uniformly at random element x from X by . We define . A real-valued function $\textsc {Negl}(\lambda )$ is negligible if $\textsc {Negl}(\lambda ) \in \mathcal {O}(\lambda ^{-\omega (1)})$. We denote the set of all negligible functions by $\textsc {Negl}$. Throughout the paper $\bot$ stands for a special error symbol, while $||$ denotes concatenation. For completeness, we recall below definitions for the more important concepts to be used throughout the paper.

2.1 (Right-Injective) Pseudorandom Generators

Definition 1

A pseudorandom generator $\mathsf {PRG}:\{0,1\}^n \rightarrow \{0,1\}^{n+\ell }$ takes as input a random seed s of length n and outputs a pseudorandom binary string of length $n+\ell$. We require a negligible advantage for any $\mathrm {PPT}$ adversary $\mathcal {A}$ against the $\mathsf {PRG}$ security experiment defined in Fig. 1:

We will make use of length-doubling, right-injective $\mathsf {PRG}$s, where the right-injectivity condition is defined as

$$ R _2 = R _2' \implies s = s' $$

for $R _1|| R _2 \leftarrow \mathsf {PRG}(s)$ and $R _1'|| R _2'\leftarrow \mathsf {PRG}(s')$. Such constructions can be achieved assuming the existence of one-way permutations, as shown by Yao [21].

2.2 (Collision-Resistant) Pseudorandom Functions

The notion of a pseudorandom function ($\mathsf {PRF}$), introduced in the seminal work of Goldreich, Goldwasser, and Micali [14], is a foundational building block in theoretical cryptography. A $\mathsf {PRF}$ is a keyed functionality guaranteeing the randomness of its output under various assumptions. $\mathsf {PRF}$s found applications in the construction of both symmetric and public-key primitives.

Definition 2

A $\mathsf {PRF}$ is a pair of $\mathrm {PPT}$ algorithms $(\mathsf {PRF}.\mathsf {Gen}, \mathsf {PRF}.\mathsf {Eval})$ such that:

• : is the randomized procedure that samples a secret key $\mathsf {sk}$, given as input the unary version of the security parameter.

• $y \leftarrow \mathsf {PRF}.\mathsf {Eval}(\mathsf {sk}, M )$: is the deterministic procedure that outputs y, corresponding to the evaluation of $M$ under $\mathsf {sk}$.

We require the advantage of any $\mathrm {PPT}$ adversary $\mathcal {A}$ in the $\mathrm {PRF}$ security experiment defined in Fig. 1 to be negligible:

Fig. 1.

Experiments defining pseudorandomness for PRGs (left) and PRFs (middle). Anonymity for public-key functional encryption is defined on the right.

We make use of collision-resistant PRFs [13]. The collision-resistance property is defined over both the secret-keys and the inputs:

$$ \mathsf {PRF}.\mathsf {Eval}(\mathsf {sk}, M ) = \mathsf {PRF}.\mathsf {Eval}(\mathsf {sk}', M ') \implies (\mathsf {sk}, M )=(\mathsf {sk}', M '). $$

Such constructions can be obtained for instance from key-injective PRFs via the GGM construction - see for instance [10, Appendix C] and length-doubling right-injective PRGs.

2.3 Functional Encryption

Definition 3

(Functional Encryption Scheme - Public-Key Setting). A functional encryption scheme ${\textsf {FE}}$ in the public-key setting consists of a tuple of $\mathrm {PPT}$ algorithms $(\mathsf {Setup},$ $\mathsf {Gen},$ $\mathsf {KDer},$ $\mathsf {Enc},$ $\mathsf {Dec})$ such that:

• : we assume the existence of a $\mathsf {Setup}$ algorithm producing a set of public parameters which are implicitly given to all algorithms. When omitted, the output of ${\textsf {FE}}.\mathsf {Setup}$ is $\emptyset$.

• takes as input the unary representation of the security parameter $\lambda$ and outputs a pair of master secret/public keys.

• : given the master secret key and a function $f$, the (possibly randomized) key-derivation procedure outputs a corresponding ${\mathsf {sk}_f}$.

• : the randomized encryption procedure encrypts the plaintext $M$ with respect to $\mathsf {mpk}$.

• : decrypts the ciphertext $\textit{C}$ using the functional key ${\mathsf {sk}_{f}}$ in order to learn a valid message $f( M )$ or a special symbol $\perp$, in case the decryption procedure fails.

A functional encryption scheme is -secure if the advantage of any $\mathrm {PPT}$ adversary $\mathcal {A}$ against the -game defined in Fig. 2 is negligible:

Similarly we say that it is adaptive $\mathrm {IND\text {-}FE\text {-}CPA}$-secure if

Functional encryption can be defined in a private-key setting: the master secret key $\mathsf {msk}$ is used to encrypt the plaintext $M$, as there is no $\mathsf {mpk}$.

Fig. 2.

The selective and adaptive indistinguishability experiments defined for a functional encryption scheme. The difference between the private-key and the public settings are marked in lines of codes, corresponding to the latter notion.

We define the classical notion of anonymity to the context of functional encryption and its security experiment in Fig. 1 (right). We point out that usually, in an ${\textsf {FE}}$ scheme, a central authority answers key-derivation queries from a potential set of users $\mathcal {U}$, therefore it is unnatural to assume that a user does not know from whom it received the functional key. What we want to ensure is that an adversary $\mathcal {A} \not \in \mathcal {U}$ cannot tell which central authority has issued a ciphertext, without interacting with the key-derivation procedures, otherwise the game becomes trivial. As an easy consequence, anonymity makes sense only in the context of public-key FE, as for a private scheme, the adversary uses encryption oracles to obtain a ciphertext. Thus, anonymity requires that a $\mathrm {PPT}$ bounded adversary can tell which $\mathsf {mpk}$ was used to encrypt a ciphertext only with negligible probability:

3 Robustness: Definitions, Implications and Separations

Robustness guarantees hardness in finding ciphertexts (resp. signatures) generated under adversarial, but well-formed keys, decryptable (resp. verifiable) under multiple secret (resp. public) keys. As stated in the introductory part, this property is often tacitly presumed, but almost as often left without a proof. In this work, we capture two levels of strengths of an adversary: strong robustness models the case where the keys are honestly generated and the adversary is agnostic of their actual values, the interaction being interfaced through decryption/signing oracles. A related, stronger notion, dubbed complete robustness gives an adversary the ability to generate keys (not necessarily honestly). In this work, we restrict to the cases where the keys are malicious, but well-formed².

We commence by presenting the security definition for digital signatures in Sect. 3.1, and then for functional encryption in Sect. 3.2.

3.1 Warm-Up: Robustness for Digital Signatures

The case for digital signatures is treated with respect to two security notions, which we denote strong and complete robustness. The winning condition remains the same in both experiments: that of obtaining a signature/message pair in such a way that it verifies under both public keys. In the $\mathrm {SROB}$ experiment, two signing oracles under $\mathsf {sk}_1, \mathsf {sk}_2$ are given to the adversary, while a $\mathrm {CROB}$ adversary generates its intrinsic keys for accomplishing essentially the same break.

Fig. 3.

Games defining strong robustness $\mathrm {SROB}$ (left) and complete robustness $\mathrm {CROB}$ (right) for a digital signature scheme $\mathsf {DS}$. We assume a negligible probability of sampling $\mathsf {pk}_1=\mathsf {pk}_2$ in the $\mathrm {SROB}$ game.

Definition 4

(SROB and CROB Security). Let $\mathsf {DS}$ be a digital signature scheme. We say $\mathsf {DS}$ achieves complete robustness if the advantage of any $\mathrm {PPT}$ adversary $\mathcal {A}$ against the CROB game depicted in Fig. 3 (right side) is negligible: . $\mathrm {SROB}$-security is defined similarly, the $\mathrm {SROB}^{\mathcal {A}}_{\mathsf {DS}}(\lambda )$ game being defined in Fig. 3 (left side).

Notice the difference to the classical unforgeability game where the adversary obtains signatures issued under the same secret key. We prove any $\mathrm {EUF}$-scheme is implicitly strong-robust, and show there exist signature schemes that fail to achieve complete robustness (thus providing a separation between the two).

Proposition 1

Let $\mathsf {DS}$ be a $\mathrm {CROB}$-secure digital signature scheme. Then $\mathsf {DS}$ is also $\mathrm {SROB}$-secure, the advantage of breaking the strong robustness game being bounded as follows: $\mathsf {Adv}_{\mathcal {A}, \mathsf {DS}}^{\mathrm {SROB}}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}', \mathsf {DS}}^{\mathrm {CROB}}(\lambda ).$

Proof

(Proposition 1). Suppose $\mathsf {DS}$ is not $\mathrm {SROB}$-secure. Let $\mathcal {A}$ be a $\mathrm {PPT}$ adversary that wins the $\mathrm {SROB}$ game with advantage at most $\epsilon _{\mathrm {SROB}}$. We construct a $\mathrm {PPT}$ adversary $\mathcal {A}'$ against the $\mathrm {CROB}$ game as follows: (1) sample two pairs of keys $(\mathsf {sk}_1, \mathsf {pk}_1), (\mathsf {sk}_2, \mathsf {pk}_2)$ using $\mathsf {Gen}(1^\lambda )$; (2) $\mathcal {A}'$ publishes $\mathsf {pk}_1, \mathsf {pk}_2$ and constructs the signing oracles $\mathsf {Sign}_{\mathsf {sk}_1}(\cdot )$ and $\mathsf {Sign}_{\mathsf {sk}_2}(\cdot )$; (3) $\mathcal {A}'$ runs $\mathcal {A}$ w.r.t. signing oracles and public-keys to obtain $( M , \sigma )$; (4) $\mathcal {A}'$ constructs the tuple $(\mathsf {pk}_1,$ $\mathsf {pk}_2,$ $\sigma ,$ $M )$ and outputs it. We obtain that $\mathsf {Adv}_{\mathcal {A}', \mathsf {DS}}^{\mathrm {SROB}}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}, \mathsf {DS}}^{\mathrm {CROB}}(\lambda )$.    $\square$

Fig. 4.

The reduction $\mathcal {A}'$ in Lemma 1.

Of interest, is a minimal level of robustness achieved by any digital signature scheme, and as it turns out, $\mathrm {SROB}$ is accomplished.

Lemma 1

Any $\mathrm {EUF}$-secure digital signature scheme $\mathsf {DS}$ is $\mathrm {SROB}$-secure. The advantage of breaking the $\mathrm {SROB}$ game is bounded by the advantage of breaking the $\mathrm {EUF}$ game: $\mathsf {Adv}_{\mathcal {A}, \mathsf {DS}}^{\mathrm {SROB}}(\lambda ) \le 2 \cdot \mathsf {Adv}_{\mathcal {A}', \mathsf {DS}}^{\mathrm {EUF}}(\lambda ).$

Proof

(Lemma 1). Let $\mathcal {A}$ be a $\mathrm {PPT}$ adversary against the strong robustness game. Let $\mathcal {A}'$ stand for an adversary against the unforgeability of the digital signature. We assume without loss of generality that $\mathcal {A}$: (1) never queries a “winning” message $M$ to the second signing oracle after it has been signed by the first oracle (since it can check it right away) and (2) it never queries a “winning” message $M$ to the first oracle after it has been signed by the second oracle (for the same reason). We present the reduction in Fig. 4 and describe it below:

• 1. The $\mathrm {EUF}$ game proceeds by sampling $(\mathsf {sk}_1, \mathsf {pk}_1)$ and builds a signing oracle $\mathrm {Sign}_{\mathsf {sk}_1}(\cdot )$.

• 2. The reduction $\mathcal {A}'$ is given $\mathsf {pk}_1$ and oracle access to the $\mathrm {Sign}_{\mathsf {sk}_1}(\cdot )$. $\mathcal {A}'$ samples uniformly at random $(\mathsf {sk}_2, \mathsf {pk}_2)$ via $\mathsf {DS}.\mathsf {Gen}$ and constructs a second signing oracle $\mathrm {Sign}_{\mathsf {sk}_2}(\cdot )$.

• 3. $\mathcal {A}'$ runs $\mathcal {A}$ w.r.t. the two $(\mathsf {pk}_1, \mathsf {pk}_2)$ and the corresponding signing oracles $\mathrm {Sign}_{\mathsf {sk}_1}(\cdot ), \mathrm {Sign}_{\mathsf {sk}_2}(\cdot )$. $\mathcal {A}'$ keeps track of the queried messages to each oracle.

• 4. $\mathcal {A}$ returns a pair $(\sigma , M )$ which verifies under both public keys with probability $\epsilon _{\mathrm {SROB}}$, s.t. $M$ has been queried to either $\mathrm {Sign}_{\mathsf {sk}_1}$ or $\mathrm {Sign}_{\mathsf {sk}_2}$ but not to both.

• 5. $\mathcal {A}'$ returns $(\sigma , M )$. If $M \in \mathsf {Sign}_{\mathsf {sk}_1}(\cdot ).$SignedMessages(), $\mathcal {A}'$ aborts and runs $\mathcal {A}$ again. With probability $\frac{1}{2}$, $M$ was not queried before to $\mathsf {Sign}_{\mathsf {sk}_1}(\cdot )$. The tuple $(\sigma , M )$ wins the $\mathrm {EUF}$ game w.r.t. $(\mathsf {pk}_1, \mathsf {sk}_1)$ with probability $\ge \frac{1}{2}\cdot \epsilon _{\mathrm {SROB}}$.

Thus, the reduction (Fig. 4) shows the advantage of breaking $\mathrm {SROB}$ is bounded by advantage breaking $\mathrm {EUF}$, which completes the proof.    $\square$

We also show a separation between the $\mathrm {SROB}$ and $\mathrm {CROB}$, by pointing to a signature scheme that is not $\mathrm {CROB}$ secure (but already $\mathrm {SROB}$).

Proposition 2

There exist DS schemes that are not $\mathrm {CROB}$-secure.

Proof

(Proposition 2). We provide a simple counterexample as follows. Consider the digital signature scheme in [5]:

• $\mathsf {Gen}$: selects uniformly at random and . Set $\mathsf {sk}\leftarrow (x,y)$ and $\mathsf {pk}\leftarrow (g_1, g_2, g_2^x, g_2^y, e(g_1,g_2))$, where $e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$ is a pairing³.

• $\mathsf {Sign}$: given a message $M$, sample and compute $\sigma \leftarrow g_1^{1/(x+ M +yr)}$. Note that with overwhelming probability, $x+ M +yr \ne 0 \bmod p$, where p is the order of $\mathbb {G}_1$. The signature is the pair $(\sigma , r)$.

• $\mathsf {Verify}$: check that $e\left( \sigma , g_2^x \cdot g_2^{ M } \cdot (g_2^y)^r \right) {\mathop {=}\limits ^{?}}e(g_1, g_2)$.

To win the $\mathrm {CROB}$ game, an adversary $\mathcal {A}$ proceeds as follows:

• 1. $\mathcal {A}$ samples a key-pair: and a message $M \in \mathbb {Z}_p$.

• 2. $\mathcal {A}$ samples and computes $\sigma$ under $\mathsf {sk}_1$. Since ${g'}_1$ can be written as $g_1^t$, $\mathcal {A}$ sets $t, x', y'$ such that $1/(x+ M +yr) = t/(x'+ M +y'r)$ (equate the exponents to obtain the same $\sigma$ corresponding to $M$). This can be done by assigning random values to $x',y'$ and setting $t \leftarrow (x'+ M +y'r)/(x+ M +yr)$.

• 3. $\mathcal {A}$ sets $(x',y');$ $\mathsf {pk}' \leftarrow ({g'}_1, {g'}_2, {g'}_2^{x'}, {g'}_2^{y'}, e({g'}_1,{g'}_2))$, for some uniformly sampled generator .

• 4. Finally, observe that $(\sigma ,r)$ verifies under $(\mathsf {sk}_1, \mathsf {pk}_1)$ through the correctness of the signature scheme, but also under $(\mathsf {pk}_2, \mathsf {sk}_2)$, since

  $$ e\left( g_1^{t/(x'+ M +y'r)}, {g'}_2^{x'} \cdot {g'}_2^{ M } \cdot ({g'}_2^{y'})^r \right) = e(g_1^t, {g'}_2). $$

  $\mathcal {A}$ halts and returns $(\mathsf {pk}, \mathsf {pk}', (\sigma ,r), M )$. Note that $\mathcal {A}$ runs in probabilistic polynomial time.    $\square$

3.2 Robustness for Functional Encryption

As discussed in the motivational part of Sect. 1, robustness should be considered as a security notion achieved by a functional encryption scheme. In what follows, we define it for the public/private key settings. We stress about the existence of essentially two major paths one can explore. A first stream of work would study the meaning of robustness in a single-authority context.

A second path is placed in a multi-authority context—that is, assuming there exist multiple pairs $(\mathsf {msk}, \mathsf {mpk})$. Aiming for a correct definition, one property that should be guaranteed is that a ciphertext should not be decryptable under two (or more) functional keys issued via different master secret keys. Stated differently, if $\mathsf {msk}_1$ produces $\mathsf {sk}_{f_1}$ and $\mathsf {msk}_2\ne \mathsf {msk}_1$ produces $\mathsf {sk}_{f_2}$ for two functionalities $f_1, f_2$, we do not want that $\textit{C}$ (say encrypted under $\mathsf {mpk}_1$) to be decrypted under $\mathsf {sk}_{f_2}$ (it already decrypts under $\mathsf {sk}_{f_1}$ with high probability due to the correctness of the scheme). We follow the lines of Definition 4, and propose two new flavours of robustness, corresponding to the cases where the adversary has oracle access to the (encryption, if in a private key setting case), key-derivation and decryption oracles. The security experiments are depicted in Fig. 5. The difference between the two paradigms may seem minor (for our purpose), but in fact having a public master key confers a significant advantage when it comes to deriving a generic transform for achieving complete robustness, as detailed in Sect. 4. In what follows, we will explore the multi-authority path, since it naturally maps to our motivational examples.

Intermediate notions considering robustness under adversarially generated keys introduced in [12]—such as full-robustness or mixed robustness—do not generalize well to functional encryption (or attribute-based encryption). The notion we consider, namely $\mathrm {FEROB}$ is in fact the generalization of $\mathrm {KROB}$ (key-less robustness), as introduced for $\mathsf {PKE}$ by Farshim et al. [12].

Fig. 5.

We introduce $\mathrm {FEROB}$ and $\mathrm {SROB}$ in the context of ${\textsf {FE}}$ schemes defined both in the public and private key setting. For the $\mathrm {SROB}$ games, we give the oracles implementing $\mathsf {Enc}$ and $\mathsf {KDer}$ procedures, mentioning that each query to the latter oracle adds an entry of the form $(f, {\mathsf {sk}_f})$ in the corresponding list $\mathrm {L}_i$—where $i \in \{1,2\}$ stands for the index of the used master keys.

Definition 5

(SROB and FEROB Security for FE). Let ${\textsf {FE}}$ be a functional encryption scheme. We say ${\textsf {FE}}$ achieves functional robustness if the advantage of any $\mathrm {PPT}$ adversary $\mathcal {A}$ against the $\mathrm {FEROB}$ game defined in Fig. 5 (bottom) is negligible: . $\mathrm {SROB}$-security is defined similarly, the $\mathrm {SROB}^{\mathcal {A}}_{\mathsf {Pub}/\mathsf {Prv}{\textsf {FE}}}(\lambda )$ game being defined in Fig. 5 (top).

As stated in the algorithmic description of the security experiment, an adversary against the strongest notion of FEROB attempts to find colliding ciphertexts, which decrypt under two $\mathsf {msk}$-separated keys ${\mathsf {sk}_f}_1, {\mathsf {sk}_f}_2$.

Lemma 2

(Implications). Let ${\textsf {FE}}$ denote a functional encryption scheme. If ${\textsf {FE}}$ is $\mathrm {FEROB}$-secure, then it is also $\mathrm {SROB}$-secure.

Proof

(Lemma 2). We prove the implication holds in both the public and private key settings:

Public-Key FE. We take the contrapositive. For a scheme ${\textsf {FE}}$, we assume the existence of an adversary $\mathcal {A}$ winning the $\mathrm {SROB}$-game with non-negligible advantage $\epsilon _\mathrm {SROB}$. A reduction $\mathcal {A}'$ that wins the $\mathrm {FEROB}$ game is built as follows: (1) $\mathcal {A}'$ samples uniformly at random $(\mathsf {msk}_1, \mathsf {mpk}_1, \mathsf {msk}_2, \mathsf {mpk}_2)$; (2) the corresponding oracles for key-derivation are built; (3) $\mathcal {A}$ runs with access to the aforementioned oracles, returning $(\textit{C}, \mathsf {sk}_{f_1}, \mathsf {sk}_{f_2})$. If $\mathcal {A}$ outputs a winning tuple, then $\mathcal {A}'$ wins the $\mathrm {FEROB}$ game by releasing the messages and the randomness terms used to construct $(\textit{C}, \mathsf {sk}_{f_1}, \mathsf {sk}_{f_2})$. Hence, $\mathsf {Adv}_{\mathcal {A}, {\textsf {FE}}}^\mathrm {SROB}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}',{\textsf {FE}}}^\mathrm {FEROB}(\lambda )$.

We take the contrapositive. For a scheme ${\textsf {FE}}$, we assume the existence of an adversary $\mathcal {A}$ winning the $\mathrm {SROB}$-game with non-negligible advantage $\epsilon _\mathrm {SROB}$. A reduction $\mathcal {A}'$ that wins the $\mathrm {FEROB}$ game is built as follows: (1) $\mathcal {A}'$ samples uniformly at random $(\mathsf {msk}_1, \mathsf {msk}_2)$; (2) $\mathcal {A}'$ constructs the encryption and key-derivation oracles under the two keys; (3) $\mathcal {A}'$ runs $\mathcal {A}$ with these oracles, records the random coins used and obtains $(\textit{C}, \mathsf {sk}_{f_1}, \mathsf {sk}_{f_2})$. Finally $\mathcal {A}'$ wins the $\mathrm {FEROB}$ game by issuing the $\mathrm {FEROB}$ tuple, using the random coins used to derive the functional keys and the ciphertext and therefore we have: $\mathsf {Adv}_{\mathcal {A},{\textsf {FE}}}^\mathrm {SROB}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}', {\textsf {FE}}}^\mathrm {FEROB}(\lambda ).$    $\square$

Proposition 3

(Separations). There exist functional encryption schemes in the public/private-key setting that are not $\mathrm {FEROB}$-secure.

Proof

(Proposition 3). As sketched in Sect. 1, a DDH instantiation for the FE scheme of [2] is not $\mathrm {FEROB}$-secure. The adversary is built upon the idea presented in the introduction and is shown in Fig. 6. Given that any public-key functional encryption scheme can be trivially converted into one in the private-key setting simply by making $\mathsf {mpk}$ private, we obtain an ${\textsf {FE}}$ scheme for the inner product functionality in the private-key setting that is not $\mathrm {FEROB}$-secure.

Fig. 6.

A $\mathrm {FEROB}$ adversary against the DDH instantiation of the bounded-norm inner product scheme in [2].

   $\square$

4 Achieving Robustness via Generic Transforms

4.1 Robust Digital Signatures

We put forward a generic transform similar in spirit to the original work of Abdalla, Bellare, and Neven [1] in the context of digital signatures. For a digital signature scheme, we benefit from the fact that $\mathsf {pk}$ acts as an “immutable" value to which one can easily commit to, while signing a message. Thus, checking if a message verifies under another public key implicitly breaks the binding property of the commitment scheme. For simplicity, we use a hash instead of a commitment scheme.

Fig. 7.

A generic transform that turns any digital signature scheme $\mathsf {DS}$ into one that is, in addition, $\mathrm {CROB}$-secure. The (publicly available) collision-resistant hash function $\mathsf {H}$ can be based on claw-free permutations in the standard model, as shown in the seminal work of Damgård [11]. It is used as a commitment to the public-key.

Lemma 3

Let $\mathsf {DS}$ be an $\mathrm {EUF}$-secure digital signature scheme. Let $\mathsf {H}$ denote a collision-resistant hash function. The digital signature $\overline{\mathsf {DS}}$ obtained through the transform depicted in Fig. 7 is $\mathrm {CROB}$-secure.

Proof

(Lemma 3). We prove both the unforgeability and the complete robustness of the newly obtained construction:

Assume the existence of a $\mathrm {PPT}$ adversary $\mathcal {A}$ against $\overline{\mathsf {DS}}$. We build an adversary $\mathcal {A}'$ against the $\mathrm {EUF}$ of the underlying $\mathsf {DS}$. The unforgeability experiment $\mathrm {EUF}$ for $\mathsf {DS}$ samples $(\mathsf {pk},\mathsf {sk})$ and constructs a signing oracle under $\mathsf {sk}$, which is given to $\mathcal {A}'$. $\mathcal {A}'$ is given a collision resistant hash function $\mathsf {H}$ and builds its own signing oracle $\overline{\mathrm {Sign}}$; when queried, $\overline{\mathrm {Sign}}$ returns the output of $\mathrm {Sign}$ concatenated to the value of $\mathsf {H}(\mathsf {pk})$. When $\mathcal {A}$ replies with $(\overline{\sigma }, M )$, it must be the case that $\mathsf {Ver}(\mathsf {pk}, \sigma , M )$ passes, which breaks $\mathrm {EUF}$ for $\mathsf {DS}$. Thus we conclude that: $\mathsf {Adv}_{\mathcal {A}, \overline{\mathsf {DS}}}^{\mathrm {EUF}}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}', \mathsf {DS}}^{\mathrm {EUF}}(\lambda ).$

To show robustness, we rely on the collision-resistance of $\mathsf {H}$. The $\mathrm {CROB}$ game in Fig. 3 specifies that the adversary $\mathcal {A}$ against the $\mathrm {CROB}$ game finds $\mathsf {pk}_1 \ne \mathsf {pk}_2$ such that $\overline{\mathsf {Ver}}$ passes. The latter implies $\mathsf {H}(\mathsf {pk}_1) = \mathsf {H}(\mathsf {pk}_2)$, trivially breaking the collision-resistance of $\mathsf {H}$, giving us: $\mathsf {Adv}_{\mathcal {A}, \overline{\mathsf {DS}}}^{\mathrm {CROB}}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}', \mathsf {H}}^{\mathrm {CR}}(\lambda ).$    $\square$

4.2 Achieving Robustness for Functional Encryption

The ABN Transform [1] Adapted to Public-Key FE. As for the case of digital signatures, one can reuse the elegant idea rooted in the binding property of a commitment scheme. Concretely, we start from a ${\textsf {FE}}$ scheme, encrypt the plaintext, and post-process the resulting ciphertext through the use of a public-key encryption scheme. The transform consists in committing to the two public keys (corresponding to ${\textsf {FE}}$ and $\mathsf {PK}$) and encrypting the resulting decommitment together with the output of ${\textsf {FE}}.\mathsf {Enc}$ under $\mathsf {pk}$. For decryption, in addition to the functional key, the secret key $\mathsf {sk}$⁴ is needed to recover the decommitment from the “middle" part of the ciphertext. A key difference to the ABN transform is rooted in the innate nature of FE: we cannot encrypt the plaintext under $\mathsf {pk}$, as this would break indistinguishability. For space reasons, we defer such a construction to the full version of this work.

Simple Robustness Transforms in the Public-Key Setting. A simpler idea makes use of a collision-resistant hash function and simply appends the hash of $\mathsf {mpk}||\textit{C}$ to the already existing ciphertext.

Fig. 8.

Generic transform that turns an ${\textsf {FE}}$ scheme into a $\mathrm {FEROB}$ scheme $\overline{{\textsf {FE}}}$.

Lemma 4

Let ${\textsf {FE}}$ be an $\mathrm {IND\text {-}FE\text {-}CPA}$-secure functional encryption scheme in the public setting and let $\mathsf {H}$ denote a collision-resistant hash function. The functional encryption scheme $\overline{{\textsf {FE}}}$ obtained through the transform depicted in Fig. 8 is $\mathrm {FEROB}$-secure, while preserving the $\mathrm {IND\text {-}FE\text {-}CPA}$-security.

Proof

(Lemma 4). To show the transform achieves $\mathrm {FEROB}$, we argue that if an adversary concludes with $({\overline{\mathsf {mpk}_1}}, R _1, M _1, {\overline{\mathsf {mpk}_2}}, R _2, M _2,\ldots )$ such that ${\overline{{\textsf {FE}}}}.\mathsf {Enc}({\overline{\mathsf {mpk}_1}},$ $M _1;$ $R _1) =$ ${\overline{{\textsf {FE}}}}.\mathsf {Enc}({\overline{\mathsf {mpk}_2}},$ $M _2;$ $R _2)$, then the adversary is essentially able to find two tuples such that $\mathsf {H}(\mathsf {mpk}_1||{\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}_1, M _1;$ $R _1)) =$ $\mathsf {H}(\mathsf {mpk}_2||{\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}_2, M _2;$ $R _2))$ which cannot happen with non-negligible probability down to the collision-resistance of $\mathsf {H}$.

The proof follows easily down to the indistinguishability of the underlying scheme ${\textsf {FE}}$: during the challenge phase, the reduction will be given the $\textit{C}^*$ corresponding to $M _b$ (chosen by $\mathcal {A}$); after appending $\mathsf {H}(\textit{C}^*||\mathsf {mpk})$, the adversary will be given ${\overline{\textit{C}^*}}$. Also, that the reduction can answer all the functional key-derivation queries the adversary makes. Hence the advantage in winning the $\mathrm {IND\text {-}FE\text {-}CPA}$ game against ${\overline{{\textsf {FE}}}}$ is bounded by the advantage of winning the $\mathrm {IND\text {-}FE\text {-}CPA}$ game against ${\textsf {FE}}$.

FEROB Transform in the Private-Key FE Setting. In this part, we provide a similar generic transform for turning any ${\textsf {FE}}$ scheme into one that is $\mathrm {FEROB}$-secure, in the private-key framework.

Fig. 9.

A generic transform that turns a ${\textsf {FE}}$ scheme in the private-key setting into a $\mathrm {FEROB}$-secure scheme ${\overline{{\textsf {FE}}}}$.

Lemma 5

Let ${\textsf {FE}}$ be an $\mathrm {IND\text {-}FE\text {-}CPA}$ functional encryption scheme in the private-key setting. Let $\mathsf {PRG}$ denote a right-injective length doubling pseudorandom generator from $\{0,1\}^{|1^\lambda |}$ to $\{0,1\}^{2\cdot |1^\lambda |}$ and $\mathsf {PRF}$ a collision-resistant $\mathsf {PRF}$. The functional encryption scheme ${\overline{{\textsf {FE}}}}$ obtained through the transform depicted in Fig. 9 is $\mathrm {FEROB}$-secure, while preserving $\mathrm {IND\text {-}FE\text {-}CPA}$-security.

Proof

(Lemma 5). Assuming the $\mathrm {FEROB}$ adversary $\mathcal {A}$ outputs $({\overline{\mathsf {msk}_1}}, R _1, M _1, f_1, R _{f_1},$ ${\overline{\mathsf {msk}_2}}, R _2, M _2, f_2, R _{f_2})$ such that ${\overline{{\textsf {FE}}}}.\mathsf {Enc}({\overline{\mathsf {msk}_1}}, M _1; R _1) = {\overline{{\textsf {FE}}}}.\mathsf {Enc}({\overline{\mathsf {msk}_2}}, M _2; R _2)$, we argue that:

• $\textit{C}_2 = \mathsf {PRF}.\mathsf {Eval}(\mathsf {sk}_1, \textit{C}_1) = \mathsf {PRF}.\mathsf {Eval}(\mathsf {sk}_2, \textit{C}_1)$. Down to the collision-resistance (over both keys and inputs) property of the $\mathsf {PRF}$, it results that $\mathsf {sk}_1 = \mathsf {sk}_2$.

• the $\overline{\mathsf {Gen}}$ function makes use of a right injective pseudorandom generator. Since the right half is exactly $\mathsf {sk}_1 (=\mathsf {sk}_2)$, through the injectivity property, it must be the case that the seed $R$ used to feed the $\mathsf {PRG}$ is the same.

• since the randomness $R$ is the same for both cases, it results that the random coins used by ${\textsf {FE}}.\mathsf {Gen}$ are the same, implying that $\mathsf {msk}_1=\mathsf {msk}_2$.

• finally, we obtain that $\overline{\mathsf {msk}_1} = \overline{\mathsf {msk}_2}$, which is not allowed in the robustness game.

Therefore, the advantage of breaking the $\mathrm {FEROB}$ game is bounded by the union bound applied on the collision-resistance of the $\mathsf {PRF}$ and right-injectivity of the PRG: $\mathsf {Adv}_{\mathcal {A}, \overline{{\textsf {FE}}}}^{\mathrm {FEROB}}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}', \mathsf {PRG}}^{\mathsf {INJ}}(\lambda ) + \mathsf {Adv}_{\mathcal {A}'', \mathsf {PRF}}^{\mathrm {CR}}(\lambda ).$

$\underline{\mathrm {IND\text {-}FE\text {-}CPA}\text {-}{\textsc {security}}.}$ The reduction proceeds via one game hop:

• $\mathrm {Game}_0$: is the game, where the adversary runs against the scheme depicted in Fig. 9—the output of the $\mathsf {PRG}$ is the expected one.

• $\mathrm {Game}_1$: based on the pseudorandomness property of the $\mathsf {PRG}$, we change the output to a truly random string, ensuring independence between $\mathsf {msk}$ and $\mathsf {sk}$. The distance to $\mathrm {Game}_0$ is bounded by the pseudorandomness advantage against $\mathsf {PRG}$. We now show the advantage of an adversary winning the $\mathrm {IND\text {-}FE\text {-}CPA}$ experiment against $\overline{{\textsf {FE}}}$ in this setting is negligible.

Assume the existence of a $\mathrm {PPT}$ adversary $\mathcal {A}$ against the $\mathrm {IND\text {-}FE\text {-}CPA}$ of $\overline{{\textsf {FE}}}$. We build an adversary $\mathcal {A}'$ against the $\mathrm {IND\text {-}FE\text {-}CPA}$ of the underlying ${\textsf {FE}}$ scheme. The $\mathrm {IND\text {-}FE\text {-}CPA}$ experiment samples a bit $b'$, the key $\mathsf {msk}$ and constructs a key-derivation oracle $\mathsf {KDer}$ under $\mathsf {msk}$, which is given to $\mathcal {A}'$. The reduction then proceeds as follows:

• 1. $\mathcal {A}'$ chooses uniformly at random $\mathsf {sk}$ to key the $\mathsf {PRF}$ utility.

• 2. $\mathcal {A}'$ builds the $\overline{{\textsf {FE}}}.\mathsf {Enc}$ oracle and the $\overline{{\textsf {FE}}}.\mathsf {KDer}$ oracle by querying the given ${\textsf {FE}}.\mathsf {Enc}, {\textsf {FE}}.\mathsf {KDer}$. The $\mathsf {PRF}$ is evaluated under $\mathsf {sk}$.

• 3. $\mathcal {A}'$ runs $\mathcal {A}$, obtains a tuple $( M _0, M _1)$ and gets back the encryption of $M _{b'}$ (say $\textit{C}^*$) by querying ${\textsf {FE}}.\mathsf {Enc}(\mathsf {msk}, M _{b'})$. $\mathcal {A}'$ computes the corresponding $\overline{\textit{C}^*}$, which is passed to $\mathcal {A}$.

• 4. finally, $\mathcal {A}$ returns a bit b, which constitutes the output of $\mathcal {A}'$.

Analysis of the Reduction. The correctness of the reduction follows trivially. Thus we conclude that in $\mathrm {Game}_1$, the probability of winning is:

$$ \Pr [\mathrm {Game}_1^{\mathcal {A}}(\lambda )\Rightarrow 1] \le \mathsf {Adv}_{\mathcal {A}', {\textsf {FE}}}^{\mathrm {IND\text {-}FE\text {-}CPA}}(\lambda ). $$

For the analysis, we also include the fact that the transition between $\mathrm {Game}_0$ and $\mathrm {Game}_1$ is bounded as follows:

$$ \Pr [\mathrm {Game}_0^{\mathcal {A}}(\lambda )\Rightarrow 1] - \Pr [\mathrm {Game}_1^{\mathcal {A}}(\lambda )\Rightarrow 1] \le \mathsf {Adv}_{\mathcal {A}'', \mathsf {PRG}}^{\mathsf {PRG}}(\lambda ). $$

We apply the Union Bound and conclude:

$$ \mathsf {Adv}_{\mathcal {A}, \overline{{\textsf {FE}}}}^{\mathrm {IND\text {-}FE\text {-}CPA}}(\lambda ) \le \mathsf {Adv}_{\mathcal {A}', {\textsf {FE}}}^{\mathrm {IND\text {-}FE\text {-}CPA}}(\lambda ) + \mathsf {Adv}_{\mathcal {A}'', \mathsf {PRG}}^{\mathsf {PRG}}(\lambda ). $$

   $\square$

5 Anonymity and Robustness

Interestingly, $\mathrm {FEROB}$ does not imply anonymity as defined in Fig. 1 (right) for the public-key case. And based on $\mathrm {FEROB}\Rightarrow \mathrm {SROB}$, it follows that $\mathrm {SROB}$ does not imply anonymity in a generic fashion. Therefore, we have the following separation:

Proposition 4

There exist $\mathrm {FEROB}$ transforms for public-key functional encryption that do not ensure anonymity (as defined in Fig. 1).

Proof

(Proposition 4). We consider the scheme in Fig. 8 and observe that the anonymity game can be easily won as follows: an adversary, given two master public keys and the ciphertext $\overline{\textit{C}} \leftarrow (\textit{C}_1, \textit{C}_2)$, decides the issuer by checking whether $\mathsf {H}(\textit{C}_1 ||\mathsf {mpk}_1){\mathop {=}\limits ^{?}}\textit{C}_2$ or $\mathsf {H}(\textit{C}_1 ||\mathsf {mpk}_2){\mathop {=}\limits ^{?}}\textit{C}_2$, via the publicly available $\mathsf {H}$.    $\square$

Finally, we give a generic construction of an anonymous $\mathrm {FEROB}$ scheme. Reaching both anonymity and robustness for ${\textsf {FE}}$ is non-trivial: on one hand, we expect the ciphertext to be “robust” w.r.t. a sole authority ($\mathsf {mpk}$), but the “link” should not be detectable when included in the ciphertext (anonymity). Therefore, we attempt to embed such a link in the functional key. Our solution ensures $\mathrm {FEROB}$ through the means of a collision-resistant PRF with keys $K$ generated on the fly. An independent functional key to compute the $\mathsf {PRF}$ value is issued via a second ${\textsf {FE}}$ supporting general circuits, while the $\mathsf {PRF}$ key $K$ is encrypted under the additional $\mathsf {mpk}$.

Fig. 10.

A generic transform that converts an ${\textsf {FE}}$ scheme into a $\mathrm {FEROB}$ scheme $\overline{{\textsf {FE}}}$, without ensuring anonymity. Here $\mathcal {C}_\mathsf {PRF}$ denotes the circuit that computes the $\mathsf {PRF}$ value, where $\mathsf {mpk}$ is hard-coded in the circuit.

Theorem 1

Let ${\textsf {FE}}'$ be an $\mathrm {ANON}$-secure functional encryption scheme supporting (at least) one functional-key for general circuits and $\mathsf {PRF}$ denote a collision-resistant $\mathsf {PRF}$. Given an $\mathrm {ANON}$, $\mathrm {IND\text {-}FE\text {-}CPA}$-secure scheme ${\textsf {FE}}$, the functional encryption scheme obtained from the transform in Fig. 10 is $\mathrm {FEROB}$-secure while preserving the original scheme’s security guarantees.

Proof

(Theorem 1). $\mathrm {FEROB}$ follows from the collision resistance of the PRF: if an adversary $\mathcal {A}$ is able to find $( K , \textit{C}_1), ( K ', \textit{C}_1)$ such that $\mathsf {PRF}( K , \textit{C}_1)=\mathsf {PRF}( K ', \textit{C}_1)$, then $\mathcal {A}$ wins the collision resistance game against the $\mathsf {PRF}$.

Follows from the $\mathrm {IND\text {-}FE\text {-}CPA}$-security of the underlying scheme. For any adversary $\mathcal {A}$ against the $\mathrm {IND\text {-}FE\text {-}CPA}$-security of the scheme $\overline{{\textsf {FE}}}$ in Fig. 10, we build the reduction $\mathcal {A}'$ that wins the $\mathrm {IND\text {-}FE\text {-}CPA}$ game against ${\textsf {FE}}$. When $\mathcal {A}$ sends the challenge tuple $( M _0, M _1)$, $\mathcal {A}'$ obtains $\textit{C}_1$ from $\mathrm {IND\text {-}FE\text {-}CPA}$ challenger, samples its own $K$s, $\mathsf {msk}', \mathsf {mpk}'$ and computes $\textit{C}_2, \textit{C}_3$, which are forwarded to $\mathcal {A}$. Whenever $\mathcal {A}$ makes a functional key query for $f$, then $\mathcal {A}'$ forwards two functional queries for $f$ and for $\mathcal {C}_{\mathsf {PRF}(\cdot , \mathsf {mpk})}$, a circuit that is designed to compute $\textit{C}_2$ (the $\mathsf {PRF}$ value) over the encrypted $K$. Thus, whenever $\mathcal {A}$ returns b, $\mathcal {A}'$ returns the same bit and wins under the same advantage.

Follows from the anonymity of the underlying ${\textsf {FE}}$ scheme. We use a hybrid argument. We start from a setting corresponding to $b=0$ in the $\mathrm {ANON}^{\mathcal {A}}_{\overline{{\textsf {FE}}}}$ game ($\mathrm {Game}_0$).

• $\mathrm {Game}_1$: in $\mathrm {Game}_1$, we change $\textit{C}_3$ from ${\textsf {FE}}'.\mathsf {Enc}(\mathsf {mpk}_0, K )$ to ${\textsf {FE}}'.\mathsf {Enc}(\mathsf {mpk}_1, K )$, based on the $\mathrm {ANON}$ property of ${\textsf {FE}}'$, the hop between the two games being bounded by $\mathsf {Adv}_{\mathcal {A},{\textsf {FE}}'}^{\mathrm {ANON}}(\lambda )$.

• $\mathrm {Game}_2$: we change $\textit{C}_1$ from ${\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}_0, M )$ to ${\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}_1, M )$, based on the anonymity of the underlying ${\textsf {FE}}$ scheme, the distance to the previous game being bounded by $\mathsf {Adv}_{\mathcal {A}, {\textsf {FE}}}^{\mathrm {ANON}}(\lambda )$. Implicitly, in $\mathrm {Game}_2$, the reduction updates the value of the $\mathsf {PRF}$ from $\mathsf {PRF}( K ,{\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}_0,\textit{C}_1))$ to $\mathsf {PRF}( K ,{\textsf {FE}}.\mathsf {Enc}(\mathsf {mpk}_1,\textit{C}_1))$.

Finally observe that $\mathrm {Game}_2$ maps to the setting where $b=1$ in the anonymity game for the $\overline{{\textsf {FE}}}$ scheme. Therefore, $\mathsf {Adv}_{\mathcal {A},\overline{{\textsf {FE}}}}^{\mathrm {ANON}} \le \mathsf {Adv}_{\mathcal {A}_1, {\textsf {FE}}'}^{\mathrm {ANON}}(\lambda )+ \mathsf {Adv}_{\mathcal {A}_2, {\textsf {FE}}}^{\mathrm {ANON}}(\lambda ).$    $\square$