Structure-Preserving Compilers from New Notions of Obfuscations

Abstract

The dream of software obfuscation is to take programs, as they are, and then generically compile them into obfuscated versions that hide their secret inner workings. In this work we investigate notions of obfuscations weaker than virtual black-box ($\textsf{VBB}$) but which still allow obfuscating cryptographic primitives preserving their original functionalities as much as possible.

In particular we propose two new notions of obfuscations, which we call oracle-differing-input obfuscation ($\textsf{odiO}$) and oracle-indistinguishability obfuscation ($\textsf{oiO}$). In a nutshell, $\textsf{odiO}$ is a natural strengthening of differing-input obfuscation ($\textsf{diO}$) and allows obfuscating programs for which it is hard to find a differing-input when given only oracle access to the programs. An $\textsf{oiO}$ obfuscator allows to obfuscate programs that are hard to distinguish when treated as oracles.

We then show applications of these notions, as well as positive and negative results around them. A few highlights include:

• Our new notions are weaker than $\textsf{VBB}$ and stronger than $\textsf{diO}$.

• As it is the case for $\textsf{VBB}$, we show that there exist programs that cannot be obfuscated with $\textsf{odiO}$ or $\textsf{oiO}$.

• Our new notions allow to generically compile several flavours of secret-key primitives (e.g., SKE, MAC, designated verifier NIZK) into their public-key equivalent (e.g., PKE, signatures, publicly verifiable NIZK) while preserving one of the algorithms of the original scheme (function-preserving), or the structure of their outputs (format-preserving).

1 Introduction

Obfuscation and Its (Dream) Applications. Obfuscation—the ability of running a program hiding its inner working—is a cryptographer’s dream. This is especially true of its most powerful instantiation, virtual black-box ($\textsf{VBB}$) obfuscation: anything a $\textsf{VBB}$-obfuscated program leaks can be simulated through oracle access to the function it computes [8]. It follows that one important application of $\textsf{VBB}$ is to generically transform secret-key cryptographic primitives into their public-key counterparts (an approach sometimes referred to as white-box cryptography). For example, the seminal work of Diffie and Hellman [25] already imagined compiling secret key encryption (SKE) into public key encryption (PKE) by letting the public key consist of the obfuscated encryption program $\textsf{Enc}({\textsf{k}}, \cdot )$. Note that this compiler has the advantage of preserving the format of the underlying ciphertext, as well as the function used to perform decryption.

Transforming Primitives, Nicely. In this paper, we are interested in obfucators that allow generic structure preserving transformation of large classes of cryptographic primitives, i.e., obfuscators that allow to compile cryptographic primitives while preserving parts of the original primitive. In particular, with the term structure-preserving, we refer to two main classes of transformations (from secret-key to public-key primitives), dubbed function-preserving and format-preserving transformations:

• Function-preserving. This first type of transformation does not alter the algorithms (one of which is then obfuscated during the transformation) of the secret-key primitive. An example of such a transformation is the one described by Diffie and Hellman, i.e., compile a SKE into a PKE by obfuscating (without any modification) the encryption algorithm and keep the decryption one unchanged.

• Format-preserving. This other type of transformation modifies the algorithms of the original secret-key primitive but it preserves the format of the output.¹ For example, in order to convert a SKE into a PKE, a format-preserving transformation may require to modify both (before obfuscating) the encryption and decryption algorithm. However, these modifications do not alter the format of ciphertexts (i.e., the ciphertexts of the resulting PKE is of the same format as the original SKE one).

We see this as an interesting design approach to transformation of primitives, worth of study of its own. Structure-preserving compilers are desirable because of: (i) reusability/retrocompatibility and (ii) efficiency. First, with function-preserving transformations we can reuse existing code, programs, libraries, constructions and their cryptanalysis. Cryptographic primitives deployed in hardware could reuse that same hardware for the transformed primitive, instead of having to be redesigned from scratch and possibly replaced in a production environment. Moreover, transformations that preserve the format of their output allow to reuse parsing-related software and to be retrocompatible with older standards (particularly important for legacy systems). Also, function- and format-preserving transformations maintain some of the scheme’s original efficiency guarantees such as preserving the running time of the (possibly heavily optimized) original function and its communication complexity, respectively.

Nice Transformations from Weaker Obfuscation? The seminal work in [7, 8] has shown that the “dream version” of obfuscation, $\textsf{VBB}$, is in general impossible, i.e., there exist programs that cannot be obfuscated through $\textsf{VBB}$. Since then cryptographers have defined new, weaker notions of obfuscations that could hopefully be constructed. One of the plausible weaker candidates in this sense is indistinguishability obfuscation ($\textsf{iO}$) that guarantees the indistinguishability of a pair obfuscated programs, only if the latter have the exact same input-output behavior. It is truly surprising that a notion of obfuscation as weak as $\textsf{iO}$ has managed to generate so many applications [41]. However, most of the applications of $\textsf{iO}$ are out of the spectrum of the “design once; obfuscate later”-approach that was dreamed in the beginning, i.e., generically compile an existing secret-key primitive that it has been designed without the intend of being obfuscated later in time. In fact, most $\textsf{iO}$-based constructions are quite involved and they are not generic since only carefully designed programs can be successfully obfuscated through $\textsf{iO}$. A clear example is [41] that leverages puncturable PRFs and pseudorandom generators (PRG) to build (from scratch) a SKE scheme that satisfies very specific properties (e.g., puncturability) which, in turn, allows $\textsf{iO}$ to convert it into a PKE scheme. Intuitively, this is far from having a generic transformation since the SKE is built with the intent of being obfuscated through $\textsf{iO}$. It is therefore natural to ask the following question:

Can we obtain generic structure-preserving transformations from notions of obfuscation weaker than $\textsf{VBB}$?

Our Results: New Primitives, Compilers, Connections to Prior Notions. In this work we propose two new definitions of obfuscation, oracle-differing-input obfuscation ($\textsf{odiO}$) and oracle-indistinguishability obfuscation ($\textsf{oiO}$), and apply them to structure-preserving transformations for several classes of primitives.

Recall that $\textsf{iO}$ [8] only guarantees indistinguishability of obfuscations between pair of programs that have the exact same input/output behaviour. Differing-input obfuscation ($\textsf{diO}$) [1, 8, 17] is a stronger kind of obfuscation which guarantees the same indistinguishability property of $\textsf{iO}$ but for pair of programs which might have different input/output behaviour, as long as it is computationally hard to find inputs on which the output of the programs differ, even when looking at the code of the programs. Our first notion, $\textsf{odiO}$, enriches the class of programs that can be securely obfuscated including any pair of programs for which it is hard to find differing-inputs, but when the distinguisher is given only oracle access to the programs. $\textsf{oiO}$ then takes it a step further and allows to obfuscate any pair of programs that are indistinguishable when given as oracle.

In the paper we formally study the relationship between our new notions of obfuscation and the existing one. Note that:

$$ \textsf{VBB}> \textsf{oiO}> \textsf{odiO}> \textsf{diO} > \textsf{iO} $$

meaning that a $\textsf{VBB}$-obfuscator is also an $\textsf{oiO}$-obfuscator, and so on. Intuitively, the separation are strict. Again, focusing only on the first inequality: while a $\textsf{VBB}$-obfuscator cannot leak anything about the program that cannot be learned by the oracle version of the program, an $\textsf{oiO}$-obfuscator is allowed to leak any secret contained in its circuit, as long as these secrets do not allow to distinguish between the oracle programs. Focusing on $\textsf{oiO}$, $\textsf{odiO}$, $\textsf{diO}$, and $\textsf{iO}$, we have that all these notions provide the same flavor of security (i.e., two obfuscations are indistinguishable) but for different classes of circuits, each progressively contained into the other. For this reason, we have that $\textsf{oiO}> \textsf{odiO}> \textsf{diO} > \textsf{iO}$.

Note that $\textsf{odiO}$ is stronger than $\textsf{diO}$. Hence, as considered by previous works for $\textsf{diO}$, this work assumes that current candidates of $\textsf{iO}$ obfuscators are candidates obfuscators for $\textsf{odiO}$ and $\textsf{oiO}$.

Still, since $\textsf{oiO}$ and $\textsf{odiO}$ are weaker than $\textsf{VBB}$, it is plausibly easier to build $\textsf{oiO}$ and $\textsf{odiO}$ obfuscators than $\textsf{VBB}$ ones, at least for specific classes of programs: For example, it is known that point functions can be $\textsf{VBB}$-obfuscated, despite the general impossibility results for $\textsf{VBB}$; similarly, programs that differ in a single input (or polynomial number of inputs) can be $\textsf{diO}$-obfuscated, even if we believe that $\textsf{diO}$ is unlikely to exist in general. In the same spirit, our results can be interpreted as showing that we can lift certain symmetric-key primitives to public-key primitives as long as specific functions (e.g., verification algorithms) can be $\textsf{odiO}$-obfuscated.

Fig. 1.

The transformations (1)-(5) of this work: function-preserving on top row; format-preserving on bottom row. By $\textsf{odiO}/\textsf{oiO}$ we denote an algorithm obtained through direct obfuscation of the one on the left; by $\equiv$ one that is completely unchanged; by $\cong$ one with minor changes but still able to take the same input; by $\mathsf {(PPRF)}$ we denote where we modify the algorithm through puncturable PRFs before obfuscation.

We then show that our new notions of obfuscation are enough for generic structure-preserving transformations of important cryptographic primitives. In particular we provide the following transformation (see also Fig. 1):

• 1. A function-preserving transformation from selectively sound succinct designated verifier non-interactive argument systems ($\textsf{dv}\text {-}\textsf{SNARG}$) into publicly verifiable ones ($\textsf{pv}\text {-}\textsf{SNARG}$) (Sect. 5.1); The same transformation allows transforming non-interactive argument systems that satisfy straight-line knowledge soundness, i.e., it is possible to extract (through a trapdoor) a valid witness from verifying proofs without interacting with the adversary;²

• 2. A function-preserving transformation from strong existentially unforgeable MACs into digital signatures that remains strongly unforgeable only in the presence of adversaries that can ask signatures of arbitrary messages in a selective fashion;

• 3. A format-preserving transformation that leverages puncturable PRFs to convert selectively existentially unforgeable MACs into selectively existentially unforgeable digital signatures. In constrast to the previous (MACs to signatures) transformation, this is only format-preserving but achieves existential unforgeability under the standard notion of chosen message attacks (i.e., the adversary has adaptive oracle access to the signature algorithm);

• 4. A format-preserving transformation that leverages puncturable PRFs to convert $\textsf{IV}$-based selectively secure SKEs into selectively IND-CPA secure PKEs. Here, $\textsf{IV}$-based SKEs refer to encryption schemes of the form $\textsf{Enc}({\textsf{k}},m;\textsf{iv}) = (\textsf{iv},c)$ where $\textsf{iv}$ is the initialization vector (i.e., randomness) used to encrypt a message $m$. Note that most SKE used in practice are $\textsf{IV}$-based e.g., those based on block ciphers mode operations such as AES-CBC-mode, AES-CTR-mode, and so on.

• 5. A function-preserving transformation from any semantically secure and key indistinguishable SKE into a selective IND-CPA PKE (Sect. 5.2). Here, the SKE’s key indistinguishability property must hold under chosen message randomness attacks, i.e., it is infeasible to determine under which key a target message has been encrypted even if the adversary has oracle access to $\textsf{Enc}({\textsf{k}},\cdot ;\cdot )$ that accepts adversarially chosen messages and randomnesses.

Note that only the last transformation requires $\textsf{oiO}$ (in order to use the key indistinguishability property of the SKE) whereas $\textsf{odiO}$ is sufficient to achieve the other ones. Also, all the transformations that use puncturable PRFs are (only) format-preserving, i.e., the programs/algorithms of the compiled primitive are (slightly) modified but the format of the output is preserved.³ We anticipate that all our transformations require $\textsf{odiO}/\textsf{oiO}$ and they cannot be implemented using $\textsf{iO}$ (or $\textsf{diO}$). In a nutshell, this is because we focus on generic transformations from secret-key to public-key primitives. In order to be generic, we need to eventually reduce the security of the transformation to the security of the original secret-key primitive. If we wish to accomplish this reduction using either $\textsf{iO}$ or $\textsf{diO}$, we need to put, into the obfuscated circuit, the key $\textsf{sk}$ of the original (secret-key) primitive. However, this is not possible. During the reduction $\textsf{sk}$ is sampled and kept secret by the challenger. We provide more details in Sect. 1.1.

Although both $\textsf{odiO}$ and $\textsf{oiO}$ are weaker than $\textsf{VBB}$, this does not tell us anything about the plausibility of these new notions of obfuscation (and their applications). As a last contribution, we investigate whether $\textsf{VBB}$’s impossibility results of Barak et al. [7, 8] extends to either $\textsf{odiO}$ or $\textsf{oiO}$ (or both). In particular, Barak et al. [7, 8] shows the following two impossibility results regarding $\textsf{VBB}$. (i) The first states an universal $\textsf{VBB}$ obfuscator does not exist, i.e. there exists (not necessarily natural) computations that cannot be obfuscated through $\textsf{VBB}$. (ii) The second states that even the specific applications/transformations of $\textsf{VBB}$ we can naturally hope for are impossible (e.g., converting any SKE into a PKE).

What about the above and $\textsf{odiO}$/$\textsf{oiO}$? We answer this question as follows:

• Result (i) does apply to $\textsf{odiO}$ and $\textsf{oiO}$. This does not say much about how useful they are, so in the paper we explore result (ii) as well (see Sect. 6.1).

• Result (ii) applies only to transformation (5) for $\textsf{oiO}$. Moreover, we need to rework the original result (ii) from [7, 8] to extend it to transformation (5) since it does not apply as it is (see Sect. 6.2).

• Result (ii) does not apply at all to the applications/transformations we have for $\textsf{odiO}$ and there seems no natural way to extend it to them. Hence, all our $\textsf{odiO}$-based transformations remain plausible.

Summing up, while the first result (i) applies to both our proposed notions, $\textsf{odiO}$ is not at all subject to the second result (ii) (impossibility of applications), which is the most limiting one.

Expanding more about the above results, we provide two different negative results by adapting the techniques of [7, 8] to the case of $\textsf{odiO}$ and $\textsf{oiO}$. First, we show that there exists an ensemble of circuits that neither $\textsf{odiO}$ nor $\textsf{oiO}$ cannot obfuscate, unconditionally (Sect. 6.1). Second, we show that the $\textsf{oiO}$-based function-preserving transformation (5) from any semantically secure and key indistinguishable SKEs into selective IND-CPA secure PKEs is inherently impossible (no matter what type of obfuscator is used to implement it).⁴ We elaborate further on this in the technical overview (Sect. 1.1) and in the related Sect. 6.

Why Study these New Notions if they are Still Subject to the [7, 8] Impossibility Results? There are multiple responses to that (some of which we expand below):

• 1. The work of Barak et al. [7, 8] does not really say much about how useful $\textsf{odiO}$/$\textsf{oiO}$ are (see also technical overview). Indeed, [7, 8] shows two types of impossibility results, i.e., impossibility of an universal obfuscator and impossibility of applications. As we mentioned above, these impossibilities do not equally extend to both notions, e.g., impossibility of applications do not extend to our $\textsf{odiO}$-based transformations.

• 2. It is still important to study foundational aspects of obfuscation. We think ours are natural questions and natural notions to propose and to turn our attention to. As it is often the case in theoretical research, these notions may be connected to others in the future in unexpected ways. They might also motivate further work on notions that will turn out to be achievable (the [7, 8] prompted the quest for $\textsf{iO}$ and other notions related to $\textsf{VBB}$).

• 3. Related to the above, both $\textsf{odiO}$ and $\textsf{oiO}$ might be useful for many “proof-of-concept” type of results that rely on $\textsf{VBB}$-obfuscation. In cases where these weaker definitions might suffice, the proposed notions could shed light on what security property is actually needed from the obfuscator to imply security of the overall construction.⁵ As an example, our results can be interpreted as follows: If a particular circuit (e.g., secret-key verification/encryption algorithm) can be $\textsf{odiO}$-obfuscated (resp. $\textsf{oiO}$-obfuscated) then we can lift a particular secret-key primitive into its public-key flavor (e.g., MAC to signatures, SKE to PKE).

• 4. $\textsf{VBB}$ and $\textsf{odiO}$/$\textsf{oiO}$ are still distinct notions and with distinct flavors of security (simulation- vs indistinguishability-based). Moreover, nonetheless the known impossibility results, research on $\textsf{VBB}$ is still active such as identifying specific and interesting class of circuits that can be securely $\textsf{VBB}$-obfuscated [33, 43, 45]. The same can be investigated for the case of $\textsf{odiO}/\textsf{oiO}$. For example, there could exist a specific class of circuits that can be $\textsf{oiO}$-/$\textsf{odiO}$-obfuscated but not $\textsf{VBB}$-obfuscated. Or there could exist circuit classes that are $\textsf{VBB}$-obfuscatable, but that can still be $\textsf{odiO}$/$\textsf{oiO}$-obfuscated more efficiently or from significantly weaker assumptions.

Lastly, we stress that $\textsf{odiO}/\textsf{oiO}$ may have other interesting applications. This work focuses on secret-key to public-key transformations since these are most prominent applications of $\textsf{VBB}$ and, we believe that studying $\textsf{odiO}/\textsf{oiO}$ in the same context provides a better understanding about the relations between $\textsf{odiO}/\textsf{oiO}$ and $\textsf{VBB}$, including their limitations.

1.1 Technical Overview

Oracle-Differing-Input Obfuscation ($\boldsymbol{\textsf{odiO}}$). The notion of $\textsf{odiO}$ is a variant of the notion of differing-input obfuscation, or $\textsf{diO}$. What is common with $\textsf{diO}$, for example, is that: (i) we are given a sampler $\textsf{S}$ that outputs two circuits $C_0 \text { and } C_1$ and some auxiliary information $\alpha$; (ii) the output of the sampler should satisfy some property P (we call such sampler “permissible”); (iii) if the sampler sastisfies property P then the obfuscated circuits $\textsf{Obf}(C_0)$ and $\textsf{Obf}(C_1)$ should look indistinguishable to a PPT adversary given also in input $\alpha$. Also, in both $\textsf{diO}$ and $\textsf{odiO}$, the property P corresponds to “no PPT $\textsf{D}$ can find a differing input x for $C_0$ and $C_1$ (given in input $\alpha$)”, that is an input $x \text { such that } C_0(x) \ne C_1(x)$. Where the two definitions diverge is that in $\textsf{diO}$ algorithm $\textsf{D}$ takes as input the actual representation (the code) of the two circuits, whereas in $\textsf{odiO}$ $\textsf{D}$ only has oracle access to the functions computed by $C_0$ and $C_1$.

An example of sampler that is permissible for $\textsf{odiO}$ but not $\textsf{diO}$ is the following: consider two programs $C_0$ and $C_1$ where their only (high-entropy) differing input is encoded as a comment in their code. Given their code it is easy to find such input, but not with oracle access to them. We provide more examples when we discuss our transformations below.

Public-key “Forgery-based” Transformations through $\boldsymbol{\textsf{odiO}}$. We show that $\textsf{odiO}$ is particularly suitable for transforming a general class of primitives—which we informally dub forgery-based—from their secret-key to their public-key version. By forgery-based we mean a primitive where the security is defined roughly as follows: “No adversary can produce (forge) a string passing a given test without knowledge of a certain secret (or if a certain condition does not hold)”. Straightforward examples of this type of primitives include message-authentication codes (MACs) and digital signature, but non-interactive proof systems and signatures of knowledge [24] also capture this intuition.

The properties of $\textsf{odiO}$ are sufficient for compiling the forgery-based primitives (1)-(3) listed above. We now give the main intuitions behind our transformations and their security. Our goal is to transform a primitive allowing us to verify a string through knowledge of secret into one that can do the same without such knowledge. Let us denote the first generic verification algorithm by $\textsf{Verify}(\textsf{sk}, \dots )$;⁶ we aim to transform it into a public key equivalent $\textsf{Verify}'(\textsf{pk}, \dots )$. Our construction is straightforward: We define $\textsf{pk}$ as the $\textsf{odiO}$-obfuscation of $\textsf{Verify}(\textsf{sk}, \dots )$, and the program $\textsf{Verify}'(\textsf{pk}, \dots )$ simply runs the program encoded in $\textsf{pk}$.

We now argue that the above is secure in a selective-security-flavored setting. In general, in such a setting, the adversary first claims some input (e.g., a message or an NP statement) for which it would like to forge a valid string (e.g., a signature or a proof). The rest of the intuition is better conveyed being specific. We thus focus on the setting of non-adaptive (selective) security in non-interactive proof systems where the verifier has the syntax $\textsf{Verify}(\textsf{vrs}, x, \pi )$ and $\textsf{vrs}$ is the (secret) verification key, x is a public statement (allegedly in a language $\mathcal {L}$), $\pi$ is the proof. In this security game, for any input $\hat{x} \not \in \mathcal {L}$, the adversary should not be able to forge a corresponding valid proof after seeing the public parameters (aka, common reference string or $\textsf{crs}$). We now show how to reduce the security of the publicly verifiable construction to that of the original (designated verifier) one applying $\textsf{odiO}$ security. Recall that the security property of $\textsf{odiO}$ must refer to a given sampler returning pairs of circuits. We require that our $\textsf{odiO}$ obfuscator is secure against a sampler that returns $(C_0, C_1)$ (we ignore the auxiliary input here) where:

• $C_0$ takes as input $x \text { and } \pi$ and returns $\textsf{Verify}(\textsf{vrs}, x, \pi )$.

• $C_1$ behaves like $C_0$ except that it immediately returns 0 whenever $x = \hat{x}$.

The two circuits clearly satisfy the $\textsf{odiO}$ permissibility notion since finding a differing input through oracle access to them would violate the original hypothesis of soundness (the only differing inputs are valid proofs for $\hat{x}$).⁷

Thus we can move to an hybrid where the $\textsf{crs}$ is an obfuscation of $C_1$, and indistinguishability of the hybrids follows from the security of the $\textsf{odiO}$ obfuscator. But now note that by construction of $C_1$, when $\textsf{crs}= \textsf{Obf}(C_1)$, an adversary by definition cannot produce a valid for $\hat{x}$. Moreover, we obtain (for free) that our transformation preserves zero-knowledge since it is function-preserving and the $\textsf{Prove}$ algorithm is not modified (see Remark 5.3).

The blueprint for the construction and security proof above can be adapted (with the appropriate care) to the other forgery-settings (2)-(3) for which we propose transformations. For transformation (2)—which yields selectively-secure strongly unforgeable signatures—one technical challenge is that we need to simulate the queries to the signing oracle. Since these queries are selective we can embed them in one of the circuits we obfuscate during the hybrid arguments. Transformation (3) requires additional care since it yields a signature scheme secure against an adversary with adaptive queries to the signing oracle. To do so we slightly modify the signature algorithm and use a (puncturable) PRF to generate a fresh one-time symmetric-key used to sign a single message. The verification algorithm is similarly adapted and then obfuscated. Due to the use of the PRF, the transformation is not function-preserving but only format-preserving.

Compiling Extractable Argument Systems. We are able to extend our result for argument schemes satisfying soundness to arguments that satisfy knowledge soundness. This is achieved by the exact same function-preserving construction from $\textsf{odiO}$.⁸ We are able to compile an adaptively-secure straight-line extractable designated verifier argument into an adaptively-secure straight-line extractable publicly verifiable argument. Note that, when considering straight-line extractability, proofs are not succinct anymore; hence, in this case we cover $\textsf{dv}\text {-}\textsf{NIZK} {}$ and $\textsf{pv}\text {-}\textsf{NIZK} {}$. In contrast to soundness—which achieves only selective security—here we are able to preserve adaptive security. Again, the transformation is function-preserving and it does not alter the $\textsf{Prove}$ algorithm. Hence, zero-knowledge is preserved (see also Remark 5.3). To the best of our knowledge ours is the first work applying obfuscation in the context of extractability in proof schemes.

Using $\boldsymbol{\textsf{odiO}}$ for Public-key Encryption through Puncturable PRFs. So far we discussed how $\textsf{odiO}$ is particularly useful for forgery-flavored primitives. We observe, however, that we are able to prove security of another type of primitive, encryption. In the full version of this work [21], we show how to compile $\textsf{IV}$-based selectively secure SKEs (whose ciphertexts have the form $\textsf{Enc}({\textsf{k}},m;\textsf{iv}) = (\textsf{iv},c)$) into selectively IND-CPA secure PKEs. Our obfuscated circuit (that will be our $\textsf{pk}$) uses two puncturable PRFs: The first to generate the initialization vector $\textsf{iv}$ from the randomness given to the PKE’s $\textsf{Enc}$ and, the second to generate a one-time fresh symmetric-key (used to encrypt) from $\textsf{iv}$.⁹ The decryption algorithm has access to the key for the second PRF and takes as input the ciphertext $(\textsf{iv}, c)$. It can then regenerate the key and thus decrypt. Note that this transformation is only format-preserving since we slightly modify both encryption and decryption algorithm to embed the evaluation of the PRF.

Oracle-Indistinguishability Obfuscation ($\boldsymbol{\textsf{oiO}}$). The notion of $\textsf{oiO}$ represents a natural strengthening of $\textsf{odiO}$. It has similar features to $\textsf{diO}$ and $\textsf{odiO}$ in that it requires samplers that output pairs of circuits satisfying some permissibility predicate P. While the permissibility predicate in $\textsf{diO}$ and $\textsf{odiO}$ requires hardness of finding a differing-input, in $\textsf{oiO}$ we have a weaker permissibility predicate (which in turn makes $\textsf{oiO}$ stronger than $\textsf{odiO}$): in $\textsf{oiO}$ the sampler must output pairs of circuits such that an adversary (given also as input related auxiliary string $\alpha$) cannot distinguish the circuits while having only oracle oracle access to them. An example of a sampler that is permissible for $\textsf{oiO}$ but not $\textsf{odiO}$ is the one where $C_0$ and $C_1$ are both PRFs but with different keys, since they differ on (almost) every input but their output distributions are indistinguishable.

Public-key “Indistinguishability-based” Transformations through $\boldsymbol{\textsf{oiO}}$. While $\textsf{odiO}$ is suitable for transforming forgery-based primitives, $\textsf{oiO}$ has synergies with indistinguishability-based primitives, i.e. where “No adversary can distinguish between two distributions without knowledge of a certain secret”. Natural examples are encryption schemes where the distributions to distinguish are the encryption of different messages (e.g., IND-CPA security).

Through $\textsf{oiO}$ we are able to prove the security of a more general transformation (compared to (4)) from SKEs to PKEs. Starting from a symmetric encryption algorithm $\textsf{Enc}({\textsf{k}},\cdot ;\cdot )$, our aim is to transform it into something with the following syntax $\textsf{Enc}(\textsf{pk},\cdot ;\cdot )$, where $\textsf{pk}$ is a public key. Our transformation is identical to the one proposed by Diffie and Hellman [25]: We define $\textsf{pk}$ as the $\textsf{oiO}$-obfuscation of $\textsf{Enc}({\textsf{k}},\cdot ;\cdot )$ for some honestly chosen symmetric key ${\textsf{k}}$. To claim the IND-CPA security of the above transformation, we need to assume that the initial SKE is key indistinguishable under (adversarially) chosen message randomness attacks. The latter allows us to build a sampler that satisfies the permissibility predicate of $\textsf{oiO}$. In particular, the sampler returns $(C_0,C_1)$ (again, we ignore the auxiliary input here) where:

• $C_0$ takes as input $m\text { and } r$ and returns $\textsf{Enc}({\textsf{k}}, m; r)$.

• $C_1$ is identical to the above except that it uses a different (honestly generated) symmetric key ${\textsf{k}}'$.

Intuitively, the circuits satisfy the $\textsf{oiO}$ permissibility notion since any adversary that is able to distinguish between oracles $C_0$ and $C_1$ would also violates the key indistinguishability security of the SKE. Now, since the obfuscations of these two circuits are indistinguishable, we can reduce the security of the PKE to the security of the original SKE. Consider the standard IND-CPA experiment of PKE where $\textsf{pk}$ is set to the obfuscation of $C_0$ and the challenge ciphertext $c$ is computed as $c= \textsf{pk}(m_b;r) = \textsf{Enc}({\textsf{k}},m_b;r)$ for r randomly chosen. We can now do an hybrid where $\textsf{pk}$ is set to the obfuscation of $C_1$ whereas the challenge ciphertext is still computed as $c= \textsf{Enc}({\textsf{k}},m_b;r)$ where ${\textsf{k}}$ is the key hardcoded in $C_0$. Since the ciphertext $c$ is computed using a key ${\textsf{k}}$ that is not the obfuscated one (recall $C_1$ uses an independent key ${\textsf{k}}'$), we can now conclude the proof by doing a reduction to the semantic security of the original SKE. We highlight that this proof technique works only if we consider selective IND-CPA security. This is because the sampler needs to output an auxiliary input that is an honest encryption of $m_b$ under the key ${\textsf{k}}$ (hardcoded into $C_0$). This is fundamental to simulate the challenge ciphertext (of the selective IND-CPA experiment) and concludes the hybrid argument.

Why aren’t $\boldsymbol{\textsf{diO}}$/$\boldsymbol{\textsf{iO}}$ Sufficient for these Transformations Above? We observe that each of the compilation described above would not be feasible with either $\textsf{iO}$ or $\textsf{diO}$. Intuitively, this is because we would eventually need to reduce the security of our transformations ($\textsf{pv}\text {-}\textsf{SNARG}$, signature, PKE) to the security of the original secret-key primitive ($\textsf{dv}\text {-}\textsf{SNARG}$, MAC, SKE). However, in the latter experiment the secret-key $\textsf{sk}$ (e.g., a $\textsf{vrs}$ or a symmetric-key), that we need to obfuscate in order to conclude the reduction, is sampled and kept secret by the challenger. This makes $\textsf{iO}$ and $\textsf{diO}$ insufficient since we are not able to satisfy their permissibility notion during this reduction. For the case of $\textsf{iO}$, during the reduction, the only thing we could do is to to obfuscate different circuit $C_1$ that does not use the secret-key $\textsf{sk}$ sampled by the challenger. However, this $C_1$ will have (with overwhelming probability) a different input/output behavior compared to $C_0$ (the original obfuscated circuit of the transformation that, in turn, contains $\textsf{sk}$).

A similar discussion applies to $\textsf{diO}$. For the sake of concreteness, consider transforming a $\textsf{dv}\text {-}\textsf{SNARG}$ into a $\textsf{pv}\text {-}\textsf{SNARG}$ by publishing an obfuscation of the circuit $C_0$ which implements the $\textsf{dv}\text {-}\textsf{SNARG}$ verification algorithm using an hardcoded verification key $\textsf{vrs}$. During the reduction to the security of the underlying scheme we are not allowed to use the secret verification key $\textsf{vrs}$. Thus, during the reduction, we can only move to a hybrid where we obfuscate a circuit $C_1$ that does not use the $\textsf{vrs}$. But then we cannot argue that it is hard to find differing-inputs for $C_0,C_1$. In this specific case, the distinguisher could simply produce proofs $\pi$ for true statements x and submit them to the circuits. While $C_0$ (using the $\textsf{vrs}$) returns 1, $C_1$ (without the $\textsf{vrs}$) is unable to verify the proof and cannot return a consistent output. Similar arguments apply to the other transformations.

The Landscape of Limitations of $\boldsymbol{\textsf{odiO}}$/$\boldsymbol{\textsf{oiO}}$. The seminal work of [7, 8] explores the boundaries of obfuscation in several directions. As it is well known they show that there are (not necessarily natural) computations which are impossible to obfuscate using $\textsf{VBB}$. Moreover, [7, 8] also shows that $\textsf{VBB}$-obfuscation cannot be used for securely performing certain structure-preserving transformations. In this direction, they show a (contrived but secure) SKE that turns into an insecure PKE scheme when compiled using obfuscation. We show that the results of [7, 8] can be extended to the setting of $\textsf{odiO}$ and $\textsf{oiO}$. In particular, we show that there (unconditionally) exist samplers that are $\textsf{odiO}$/$\textsf{oiO}$ permissible but are not obfuscatable. Specifically we sample (somewhat contrived) circuits $C_s$ with an embedded secret s that remains “hidden enough” when only oracle access is allowed (thus being $\textsf{odiO}$/$\textsf{oiO}$ permissible). We then show that, once given access to the obfuscated circuit, it becomes possible to “partially extract” this secret s. Finally, we show that (since this sampler cannot be obfuscated) our $\textsf{oiO}$-based transformation (5) (from semantically secure and key indistinguishable SKE to selectively IND-CPA PKE) is inherently impossible, regardless of the strength of the obfuscator used. This is done by using the unobfuscatable circuits to build a contrived SKE (satisfying semantic security and key indistinguishability) that, once compiled, yields an insecure PKE. As mentioned, a similar impossibility result was given in [8, Theorem 4.10]. However their contrived SKE does not satisfy key indistinguishability and, for this reason, it cannot be directly used to show the infeasibility of our transformation (5). Thus, our negative result strengthens the one of [8] since ours apply to a smaller class of SKEs (i.e., SKEs with stronger notions of security) that satisfy key indistinguishability under chosen message randomness attacks. Note that while we just argued that the $\textsf{oiO}$-based transformation in (5) is inherently impossible, our $\textsf{odiO}$-based transformations (1)-(4) remain plausible as the impossibility results do not seem to extend. We elaborate further in Sect. 6.2.

1.2 Future Directions

Our work opens up several interesting future directions. How to generally formalize structure-preserving transformations? Can we characterize what type of games can be transformed (from “secret” to “public” key) through $\textsf{odiO}$? Several, but not all those we achieve, seem to have a “forgery” flavor to them (MAC, NIZKs, etc.). What are further connections between our proposed notions of obfuscation and $\textsf{VBB}$, $\textsf{iO}$ and $\textsf{diO}$? While the techniques in [8] seem to fail to show that some of our transformations are paradoxical, what are other techniques that could shed light on further limitations of $\textsf{odiO}$ $\textsf{oiO}$? Can we leverage our techniques for going from secret-key to public-key variants of different cryptographic primitives than those we consider here, e.g., proofs of retrievability [42]?

2 Related Work

Barak et al. [7, 8] investigate the feasibility of obfuscation. They focus on virtual black-box ($\textsf{VBB}$) obfuscation, where an obfuscated program/circuit should leak no information except for its input-output behaviour. They show: 1) that a general $\textsf{VBB}$ obfuscator cannot exist since there are circuits that cannot be unconditionally obfuscated in the $\textsf{VBB}$ paradigm; 2) that most of the intriguing applications of $\textsf{VBB}$ are impossible (including the suggestion of Diffie and Hellman’s of building a PKE by obfuscating the SKE encryption algorithm with an embedded symmetric key). On the positive side, several works have shown that some restricted classes of circuits can be securely $\textsf{VBB}$-obfuscated [23, 33, 43, 45] . Goldwasser and Kalai [30, 31] and Bitansky et al. [13] extended $\textsf{VBB}$’s impossibility results to the case of auxiliary information demonstrating that other “natural” circuits cannot be $\textsf{VBB}$ obfuscated when some (dependent or independent) auxiliary information are available. In addition, [13] demonstrated that the availability of auxiliary information is equivalent to $\textsf{VBB}$ with universal simulation. Goldwasser and Rothblum [32] proposed the notion of best-possible obfuscation that guarantees that the obfuscation of a circuit leaks as little information as any other circuit implementing the same functionality. They show that a separation between $\textsf{VBB}$ and best-possible obfuscation and an impossibility result (for both) in the random oracle model. Other works [6, 20, 22, 37, 38, 40] studied the (in)feasibility of $\textsf{VBB}$ in different idealized models.

To avoid the $\textsf{VBB}$ paradigm (and its impossibility results), [8] suggested two weaker security definitions of obfuscation: indistinguishability obfuscation ($\textsf{iO}$) and differing-input obfuscation ($\textsf{diO}$). The former has obtained a lot of interest thanks to its applications, as initially shown by Sahai and Waters [41]. The first work that proposed a candidate $\textsf{iO}$ construction is by Garg et al. [26] that built $\textsf{iO}$ via multilinear maps. Subsequent works [2,3,4, 15, 16, 19, 28, 29, 36, 39] focused on both the relations of $\textsf{iO}$ and other primitives (e.g., functional encryption) and new candidates construction from weaker assumptions. These works led to the recent works of Jain et al. [35] and Wee and Wichs [44]. [35] built (sub-exponentially secure) $\textsf{iO}$ from the sub-exponential hardness of LWE, learning parity with noise, and boolean pseudorandom generators in $\textsf{NC}^0$. On the other hand, [44] proposed the first construction based solely on lattices and LWE. Their construction relies on a new falsifiable LWE assumption.

As for $\textsf{diO}$, [1, 10, 17, 17] proposed different formalization of $\textsf{diO}$ (for both circuits and Turing machines) and showed different applications. On the negative side, [11, 18, 27] showed that, in the presence of (some) auxiliary information (e.g., samplers), a general $\textsf{diO}$ obfuscator may not exist. Notably, Bellare et al. [11] showed that if sub-exponentially secure one-way functions exist then a sub-exponentially secure general $\textsf{diO}$ obfuscator for Turing machines does not exist, i.e., there exists a sampler that outputs two Turing machines and some auxiliary information that cannot be obfuscated through $\textsf{diO}$. Moreover, they show that the impossibility result extends to $\textsf{diO}$ for circuits, if SNARKs exist. Garg et al. [27] showed a similar result for $\textsf{diO}$ for circuits under the conjecture that a special-purpose obfuscator exists (i.e., an obfuscator that does not follow from $\textsf{diO}$). All the negative results of [11, 18, 27] rely on the fact that the sampler can silently provide a trapdoor that allows an adversary to distinguish between two obfuscations whereas the trapdoor does not help in finding a differing-input., Because of this, Ishai et al. [34] proposed the weaker notion of public-coin $\textsf{diO}$ where the random coins of the sampler are public, i.e., a sampler cannot hide any trapdoor in the auxiliary information.

Among weaker notions of obfuscation, we also find virtual gray-box obfuscation ($\textsf{VGB}$) [12, 14]. This notion is close to that of $\textsf{VBB}$ but models the simulator as semi-bounded, i.e., unbounded in running time but limited to a polynomial number of oracle queries. $\textsf{VGB}$ is equivalent to another notion, strong $\textsf{iO}$ ($\textsf{siO}$), where it holds that $\textsf{Obf}(C_0) \approx _c \textsf{Obf}(C_1)$ whenever the pair $(C_0, C_1)$ is sampled from a concentrated distribution $\textbf{D}$: For every input x, the probability that $C_0(x)$ and $C_1(x)$ do not return to common output $maj_{\textbf{D}}(x)$ is negligible (where $maj_{\textbf{D}}(\cdot )$ is defined with respect to the concentrated distribution $\textbf{D}$ taken into account). Observe that concentrated distributions are a generalization of evasive functions [5]. Intuitively, $\textsf{siO}$ is weaker than $\textsf{odiO}$ (and $\textsf{oiO}$) since circuits (sampled from concentrated distributions) are oracle-diffing-input even against semi-bounded adversaries. Also, note that $\textsf{siO}$ is not powerful enough to achieve structure-preserving transformations. Intuitively, because $\textsf{siO}$ is able to obfuscate distributions of circuits that “pass” an information theoretical test. This is a obstacle when trying to implement our structure-preserving transformations since our objective is to compile/obfuscate primitives whose security follows from computational assumptions.

3 Preliminaries on Obfuscation

We assume the reader to be familiar with standard cryptographic notation and definitions. Our notation and all the standard definitions used in the paper can be found in the full version.

Indistinguishability Obfuscation and Differing-input Obfuscation. Let $\mathcal {C}= \{\mathcal {C}_\lambda \}_{\lambda \in \mathbb {N}}$ be an ensemble of functionally equivalent circuits (of same size), i.e., $\forall \lambda \in \mathbb {N}, \forall C_0,C_1 \in \mathcal {C}_\lambda , \forall x \in \{0,1\}^{\ell _{in}}$, $C_0(x) = C_1(x)$ and $|C_0| = |C_1|$. Indistinguishability obfuscation ($\textsf{iO}$) [7] guarantees that the obfuscation of any two functionally equivalent circuits $C_0,C_1 \in \mathcal {C}_\lambda$ are computationally indistinguishable. The stronger notion of differing-input obfuscation ($\textsf{diO}$) [1, 8, 17] considers the larger class of differing-input circuits, i.e., circuits that differ on hard to find inputs. Below, we introduce the definition of $\textsf{diO}$ with respect to samplers responsible of sampling two differing-input circuits and (some) auxiliary information.

Definition 3.1

A sampler $\textsf{S}$ for an ensemble of circuits $\mathcal {C}= \{\mathcal {C}_\lambda \}_{\lambda \in \mathbb {N}}$ is a PPT algorithm that, on input the security parameter $1^\lambda$, it outputs two circuits $C_0,C_1 \in \mathcal {C}_\lambda$ such that $|C_0| = |C_1|$ and (possibly) some auxiliary information $\alpha$.

Definition 3.2

($\textsf{diO}$-sampler) We say a sampler $\textsf{S}$ (Definition 3.1) is a $\textsf{diO}$-sampler if for every PPT adversary $\textsf{A}$ we have

$$\begin{aligned} \mathbb {P}\left[ C_0(x) \ne C_1(x) \Big | (C_0,C_1,\alpha )\,{\leftarrow \!\!{\$}}\,\textsf{S}(1^\lambda ), x \,{\leftarrow \!\!{\$}}\,\textsf{A}(1^\lambda ,C_0,C_1,\alpha ) \right] \le \textsf{negl}(\lambda ). \end{aligned}$$

Definition 3.3

[Differing-input obfuscation] Let $\mathcal {S}$ be an ensemble of $\textsf{diO}$-samplers (Definition 3.2). For every $\textsf{S}\in \mathcal {S}$, let $\mathcal {C}^{\textsf{S}} = \{\mathcal {C}^\textsf{S}_\lambda \}_{\lambda \in \mathbb {N}}$ be the ensemble of circuits output by $\textsf{S}$. A PPT algorithm $\textsf{Obf}$ is a $(\mathcal {S})$-$\textsf{diO}$-obfuscator for the ensemble $\mathcal {S}$ if the following conditions are satisfied:

• Correctness. $\forall \textsf{S}\in \mathcal {S}$, $\forall \lambda \in \mathbb {N}$, $\forall C\in \mathcal {C}^\textsf{S}_\lambda$, $\forall x \in \{0,1\}^{\ell _{in}}$, we have $C'(x) = C(x)$ where $C' \,{\leftarrow \!\!{\$}}\,\textsf{Obf}(1^\lambda ,C)$.

• Polynomial slowdown. There exists a polynomial p such that $\forall \textsf{S}\in \mathcal {S}$, $\forall C\in \mathcal {C}^\textsf{S}_\lambda$, we have $|\textsf{Obf}(1^\lambda ,C)| \le p(|C|)$.

• Indistinguishability. For every $\textsf{S}\in \mathcal {S}$, every PPT adversary $\textsf{D}$, we have that

  $$ \left| \mathbb {P}\left[ \textsf{D}(1^\lambda ,\textsf{Obf}(1^\lambda ,C_0),\alpha ) =1 \right] - \mathbb {P}\left[ \textsf{D}(1^\lambda ,\textsf{Obf}(1^\lambda ,C_1),\alpha ) =1 \right] \right| \le \textsf{negl}(\lambda ), $$

  where $(C_0,C_1,\alpha )\,{\leftarrow \!\!{\$}}\,\textsf{S}(1^\lambda )$.

The above definition is parametrized by an ensemble of $\textsf{diO}$-samplers since some negative results for $\textsf{diO}$ are known [11, 27] (see next). Because of this, an universal (general) $\textsf{diO}$-obfuscator may not exists, i.e., a $\textsf{diO}$-obfuscator that obfuscates any $\textsf{diO}$-sampler.

Negative Results. In the setting of Turing machines (not covered by this paper), Bellare et al. [11] show that if sub-exponentially secure one-way functions exist then a sub-exponentially secure $\textsf{diO}$-obfuscator $\textsf{Obf}$ for any sampler for Turing machines does not exist (i.e., there exists a particular sampler that cannot be $\textsf{diO}$-obfuscated). We stress that the main impossibility result covers Turing machines but, as described by [11], if SNARKs exist the negative result can be extended to $\textsf{diO}$ for circuits. Garg et al. [27] show that under the conjecture that a special-purpose obfuscator exists (i.e., an obfuscator that does not follow from the existence of a $\textsf{diO}$-obfuscator) then a $\textsf{diO}$-obfuscator $\textsf{Obf}$ for any sampler for circuits does not exist. We highlight that both [11, 27] show that only “some” $\textsf{diO}$-samplers cannot be obfuscated. Indeed, both works rely on samplers that output complex auxiliary information $\alpha$ ($\alpha$ is itself an obfuscation of contrived circuit/Turing machine). Hence, this does not rule out the possibility of obfuscating the same class of circuits/Turing machines under simpler auxiliary information.

Virtual Black-box Obfuscation. Virtual black-box obfuscation ($\textsf{VBB}$) [7], is the strongest known notion of obfuscation. In a nutshell, a $\textsf{VBB}$-obfuscator guarantees that having an obfuscation of a circuit $C$ is “equivalent” to having oracle access to $C$. We consider the weakest notion of $\textsf{VBB}$ that requires the adversary (and the simulator) to output a single bit. This is equivalent to asking the adversary/simulator to compute/determine an arbitrary predicate $\pi (C)$ of the original circuit [7]. Similarly to $\textsf{diO}$, we consider $\textsf{VBB}$ with respect to samplers responsible to sample a circuit and (some) auxiliary information. This will allow us to provide a meaningful comparison between $\textsf{VBB}$ and $\textsf{diO}$, $\textsf{odiO}$, $\textsf{oiO}$.

Definition 3.4

($\textsf{VBB}$-sampler) A $\textsf{VBB}$-sampler $\textsf{S}$ for an ensemble of circuits $\mathcal {C}= \{\mathcal {C}_\lambda \}_{\lambda \in \mathbb {N}}$ is a PPT algorithm that, on input the security parameter $1^\lambda$, it outputs a circuit $C\in \mathcal {C}_\lambda$ and some auxiliary information $\alpha$.

Definition 3.5

(Virtual black-box obfuscation). Let $\mathcal {S}$ be an ensemble of $\textsf{VBB}$-samplers (Definition 3.4). For every $\textsf{S}\in \mathcal {S}$, let $\mathcal {C}^{\textsf{S}} = \{\mathcal {C}^\textsf{S}_\lambda \}_{\lambda \in \mathbb {N}}$ be the ensemble of circuits output by $\textsf{S}$. A PPT algorithm $\textsf{Obf}$ is a $(\mathcal {S})$-$\textsf{VBB}$-obfuscator for the ensemble $\mathcal {S}$ if the following conditions are satisfied:

• Correctness. $\forall \textsf{S}\in \mathcal {S}$, $\forall \lambda \in \mathbb {N}$, $\forall C\in \mathcal {C}^\textsf{S}_\lambda$, $\forall x \in \{0,1\}^{\ell _{in}}$, we have $C'(x) = C(x)$ where $C' \,{\leftarrow \!\!{\$}}\,\textsf{Obf}(1^\lambda ,C)$.

• Polynomial slowdown. There exists a polynomial p such that $\forall \textsf{S}\in \mathcal {S}$, $\forall C\in \mathcal {C}_\lambda$, we have $|\textsf{Obf}(1^\lambda ,C)| \le p(|C|)$.

• Virtual black-box simulation. For every PPT adversary $\textsf{A}$, there exists a PPT simulator $\textsf{Sim}$ such that for every $\textsf{S}\in \mathcal {S}$, we have

  $$\begin{aligned} \left| \mathbb {P}\left[ \textsf{A}(1^\lambda ,\textsf{Obf}(1^\lambda ,C), \alpha ) =1 \right] - \mathbb {P}\left[ \textsf{Sim}^{C(\cdot )}(1^\lambda , 1^{|C|}, \alpha ) =1 \right] \right| \le \textsf{negl}(\lambda ), \end{aligned}$$

  where $(C,\alpha ) \,{\leftarrow \!\!{\$}}\,\textsf{S}(1^\lambda )$.

Note that $\textsf{VBB}$ is a much stronger flavor of obfuscation than $\textsf{diO}$ and $\textsf{iO}$ for two reasons. First, $\textsf{VBB}$ defines the concept of ideal/oracle obfuscation, i.e., an obfuscated circuit behaves as an oracle. Second, $\textsf{VBB}$ is a simulation-based definition (whereas both $\textsf{iO}$ and $\textsf{diO}$ are indistinguishability-based), i.e., any bit of leakage (that can be retrieved from the obfuscation of a circuit) can be simulated (except with negligible probability) having only oracle access to the unobfuscated circuit.

Impossibility Results. $\textsf{VBB}$ is a very interesting notion of obfuscation since it has several important applications (e.g., it permits to convert a SKE into PKE). However, $\textsf{VBB}$-obfuscation turned out to be impossible for several and reasonably simple class of circuits/samplers [7, 8, 13]. Moreover, also several applications of $\textsf{VBB}$ are impossible to achieve. As an example, Barak et al. [8, Theorem 4.10] have shown that there exist a SKE that cannot be transformed into a PKE by (simply) obfuscating the SKE’s encryption algorithm (a similar impossibility result applies also to PRFs, MACs, and signatures). Still, $\textsf{VBB}$-obfuscation is still possible for other class of circuits/samplers. Examples are compute-and-compare programs [45] (also known as lockable obfuscation [33]) and point functions [43].

4 Oracle-Differing-Input and Oracle-Indistinguishability Obfuscation

In this section, we propose two new notions of obfuscation, dubbed oracle-differing-input obfuscation and oracle-indistinguishability obfuscation ($\textsf{odiO}$ and $\textsf{oiO}$ in short). Both $\textsf{odiO}$ and $\textsf{oiO}$ are the result of two natural extensions of $\textsf{diO}$ (resp. $\textsf{iO}$): they introduce the notion of oracle circuits (as in $\textsf{VBB}$) while keeping the indistinguishability property of $\textsf{diO}$ (resp. $\textsf{iO}$). In a nutshell, $\textsf{odiO}$ requires that the obfuscations of two circuits $C_0,C_1$ are computationally indistinguishable if the latter two are differing-input circuits when treated as oracles, i.e., an adversary cannot find an input x such that $C_0(x) \ne C_1(x)$ when given oracle access to both $C_0$ and $C_1$. On the other hand, $\textsf{oiO}$ provides the same indistinguishability guarantee with respect to circuits $C_0,C_1$ that are computationally indistinguishable when treated as oracles.

As usual, we define $\textsf{odiO}$ and $\textsf{oiO}$ with respect to an ensemble of samplers responsible of generating the circuits $C_0,C_1$ and (possibly) some auxiliary information $\alpha$.

Definition 4.1

($\textsf{odiO}$- and $\textsf{oiO}$-sampler) Let $\textsf{type}\in \{\textsf{odiO},\textsf{oiO} \}$. We say a sampler $\textsf{S}$ (Definition 3.1) is an $\textsf{type}$-sampler if for every PPT adversary $\textsf{A}$ we have

• If $\textsf{type}= \textsf{odiO}$: $\mathbb {P}\left[ C_0(x) \ne C_1(x) \Big | x \,{\leftarrow \!\!{\$}}\,\textsf{A}^{C_0(\cdot ),C_1(\cdot )}(1^\lambda ,1^{|C_0|},\alpha ) \right] \le \textsf{negl}(\lambda )$,

• If $\textsf{type}= \textsf{oiO}$: $\left| \mathbb {P}\left[ \textsf{A}^{C_0(\cdot )}(1^\lambda ,1^{|C_0|},\alpha ) =1 \right] - \mathbb {P}\left[ \textsf{A}^{C_1(\cdot )}(1^\lambda ,1^{|C_1|},\alpha ) =1 \right] \right| \le \textsf{negl}(\lambda )$,

where $(C_0,C_1,\alpha )\,{\leftarrow \!\!{\$}}\,\textsf{S}(1^\lambda )$.¹⁰

Definition 4.2

(Oracle-differing-input and oracle-indistinguishability obfuscation). For $\textsf{type}\in \{\textsf{odiO},\textsf{oiO} \}$, let $\mathcal {S}$ be an ensemble of $\textsf{type}$-samplers (Definition 4.1). For every $\textsf{S}\in \mathcal {S}$, let $\mathcal {C}^{\textsf{S}} = \{\mathcal {C}^\textsf{S}_\lambda \}_{\lambda \in \mathbb {N}}$ be the ensemble of circuits output by $\textsf{S}$. A PPT algorithm $\textsf{Obf}$ is a $(\mathcal {S})$-$\textsf{type}$-obfuscator for the ensemble $\mathcal {S}$ if the following conditions are satisfied:

• Correctness. $\forall \textsf{S}\in \mathcal {S}$, $\forall \lambda \in \mathbb {N}$, $\forall C\in \mathcal {C}^\textsf{S}_\lambda$, $\forall x \in \{0,1\}^{\ell _{in}}$, we have $C'(x) = C(x)$ where $C' \,{\leftarrow \!\!{\$}}\,\textsf{Obf}(1^\lambda ,C)$.

• Polynomial slowdown. There exists a polynomial p such that $\forall \textsf{S}\in \mathcal {S}$, $\forall C\in \mathcal {C}^\textsf{S}_\lambda$, we have $|\textsf{Obf}(1^\lambda ,C)| \le p(|C|)$.

• Indistinguishability. For every $\textsf{S}\in \mathcal {S}$, every PPT adversary $\textsf{D}$, we have that

  $$ \left| \mathbb {P}\left[ \textsf{D}(1^\lambda ,\textsf{Obf}(1^\lambda ,C_0),\alpha ) =1 \right] - \mathbb {P}\left[ \textsf{D}(1^\lambda ,\textsf{Obf}(1^\lambda ,C_1),\alpha ) =1 \right] \right| \le \textsf{negl}(\lambda ), $$

  where $(C_0,C_1,\alpha )\,{\leftarrow \!\!{\$}}\,\textsf{S}(1^\lambda )$.

Comparing $\textsf{diO}$-, $\textsf{odiO}$-, $\textsf{oiO}$-, and $\textsf{VBB}$-obfuscation. We now study the relations between $\textsf{diO}$, $\textsf{odiO}$, $\textsf{oiO}$, and $\textsf{VBB}$. In order to provide a meaningful comparison, we work in terms of best-possible universal obfuscators, i.e., we compare the classes of circuits/samplers that each flavor of obfuscation is able to handle. We start by defining the notion of best-possible universal $\textsf{type}$-obfuscator $\textsf{Obf}$ (for $\textsf{type}\in \{\textsf{diO},\textsf{odiO},\textsf{oiO},\textsf{VBB} \}$) whose definition is tied with the (universal) set $\mathcal {S}_{\textsf{type}}$ composed of all the $\textsf{type}$-samplers that can be securely $\textsf{type}$-obfuscated (as defined in Definitions 4.2 to 3.4).

Definition 4.3

(Best-possible universal $\textsf{type}$-obfuscator). Let $\textsf{type}\in \{\textsf{diO},\textsf{odiO},\textsf{oiO},\textsf{VBB} \}$. Consider the ensemble $\mathcal {S}_{\textsf{type}}$ composed of every $\textsf{type}$-sampler $\textsf{S}$ (Definitions 4.1, 3.2 and 3.4) that can be securely $\textsf{type}$-obfuscated (Definitions 4.2, 3.3 and 3.5), i.e.,

$$ \mathcal {S}_{\textsf{type}} = \{\textsf{type}\text {-sampler } \textsf{S}\ | \ \exists \ \textsf{Obf}\text { s.t.}~\textsf{Obf}\text { is a } (\{\textsf{S}\})\text {-}\textsf{type}\text {-obfuscator} \}. $$

A PPT algorithm $\textsf{Obf}$ is a best-possible universal $\textsf{type}$-obfuscator if $\textsf{Obf}$ is a $(\mathcal {S}_{\textsf{type}})$-$\textsf{type}$-obfuscator (Definitions 3.3, 4.2 and 3.5).

Remark 4.4

There are two technical reasons behind the need of considering only best-possible universal obfuscators, while comparing $\textsf{diO}$, $\textsf{odiO}$, $\textsf{oiO}$, and $\textsf{VBB}$. First, for any notion of $\textsf{type}$-obfuscation, it is possible to find two contrived $\textsf{type}$-obfuscators $\textsf{Obf}_0$ and $\textsf{Obf}_1$ that result to be incomparable, even within the same flavor of obfuscation. As an example, we could have that $\textsf{Obf}_0$ (resp. $\textsf{Obf}_1$) is able to $\textsf{type}$-obfuscate $\textsf{S}_0$ (resp. $\textsf{S}_1$) but not $\textsf{S}_1$ (resp. $\textsf{S}_0$) where $\textsf{S}_0,\textsf{S}_1$ are two $\textsf{type}$-samplers.¹¹ The same argument holds between different notions. For example, if we consider $\textsf{diO}$ and $\textsf{odiO}$, we could have that $\textsf{Obf}_0$ $\textsf{diO}$-obfuscates a $\textsf{diO}$-sampler $\textsf{S}$ (that in turn, as we will see, is also a $\textsf{odiO}$-obfuscator) but $\textsf{Obf}_1$ does not $\textsf{odiO}$-obfuscate $\textsf{S}$. Also, we can have the symmetric case: there exist two obfuscators $\textsf{Obf}'_0$ and $\textsf{Obf}'_1$ such that $\textsf{Obf}'_1$ $\textsf{odiO}$-obfuscates $\textsf{S}$ but $\textsf{Obf}'_0$ does not $\textsf{diO}$-obfuscate $\textsf{S}$. Hence by changing the obfuscator we could reach any conclusions: (i) $\textsf{odiO}$ and $\textsf{diO}$ are incomparable, (ii) $\textsf{odiO}$ implies $\textsf{diO}$, or (iii) $\textsf{diO}$ implies $\textsf{odiO}$. This clearly does not allow for a meaningful comparison. Definition 4.3 naturally solves the above problem since a best-possible universal $\textsf{type}$-obfuscator uniquely represents the power of a particular notion of obfuscation, i.e., the set $\mathcal {S}_{\textsf{type}}$ of samplers that can be securely $\textsf{type}$-obfuscated. This allows us to have a meaninful (and unique) formal comparison between $\textsf{diO}$, $\textsf{odiO}$, $\textsf{oiO}$, and $\textsf{VBB}$.

Second, Definition 4.3 allows us to exclude from the comparison the known impossibility results of $\textsf{VBB}$ [7, 13] (and $\textsf{odiO}$, $\textsf{oiO}$ as we will show in Sect. 6). This is because, instead of quantifying over any possible $\textsf{type}$-sampler, best-possible universal $\textsf{type}$-obfuscation is defined over any possible $\textsf{type}$-sampler that can be $\textsf{type}$-obfuscated.

In the setting of best-possible universal obfuscation, $\textsf{odiO}$ (resp. $\textsf{oiO}$) is stronger than $\textsf{diO}$ since (i) any $\textsf{diO}$-sampler is also an $\textsf{odiO}$-sampler (resp. $\textsf{oiO}$-sampler) and (ii) both $\textsf{diO}$ and $\textsf{odiO}$ (resp. $\textsf{oiO}$) have the same indistinguishability-based security definition. The same argument applies to $\textsf{odiO}$ and $\textsf{oiO}$, i.e., $\textsf{oiO}$ is stronger than $\textsf{odiO}$.

Theorem 4.5

($\textsf{oiO} \Rightarrow \textsf{odiO} \Rightarrow \textsf{diO}$). For $\textsf{type}\in \{\textsf{diO},\textsf{odiO},\textsf{oiO} \}$, we have that $\mathcal {S}_{\textsf{diO}} \subseteq \mathcal {S}_{\textsf{odiO}} \subseteq \mathcal {S}_{\textsf{oiO}}$ where $\mathcal {S}_{\textsf{type}}$ as defined in Definition 4.3.

The proof of this theorem is deferred to full version.

About (best-possible universal) $\textsf{odiO}$-, $\textsf{oiO}$-, and $\textsf{VBB}$-obfuscation, we have that $\textsf{VBB}$ is stronger than $\textsf{odiO}$ (resp. $\textsf{oiO}$) for two main reasons:

• 1. $\textsf{VBB}$ leverages a simulation-based definition: any bit of information that can be leaked from an obfuscated circuit $C$ can be simulated by only having oracle access to $C$. On the other hand, $\textsf{odiO}$ (resp. $\textsf{oiO}$) provides a much weaker security guarantee: the obfuscation of two circuits $C_0,C_1$ (output by an $\textsf{odiO}$-sampler (resp. $\textsf{oiO}$-sampler)) are computationally indistinguishable. This implies that a $\textsf{odiO}$-obfuscator (resp. $\textsf{oiO}$-obfuscator) could leak significant information about the circuit, as long as the leaked information does not help in distinguishing (except with negligible probability) between the obfuscations of $C_0$ and $C_1$.

• 2. Both $\textsf{VBB}$ and $\textsf{odiO}$ (resp. $\textsf{oiO}$) incorporate the notion of oracle circuits in their definitions. However, oracles are used to define two different concepts. $\textsf{VBB}$ uses oracle circuits to define the amount of information a $\textsf{VBB}$-obfuscator may leak. Since oracles leak no information (except their input-output behavior), this implies that a $\textsf{VBB}$-obfuscator does not leak any information, except with negligible probability. Conversely, $\textsf{odiO}$ and $\textsf{oiO}$ leverage the notion of oracle circuits to characterize the class of circuits (or samplers) that an $\textsf{odiO}$-/$\textsf{oiO}$-obfuscator can handle. The definition of security (i.e., the indistinguishability property of Definition 4.2) is independent from the oracles. Both $\textsf{odiO}$ and $\textsf{oiO}$ “only” guarantee that the information leaked by the obfuscation of two circuits are the same. This does not imply that the $\textsf{odiO}$-/$\textsf{oiO}$-obfuscated circuits must “behave” as oracles (as required by $\textsf{VBB}$ (Definition 3.5)).

The relation between $\textsf{VBB}, \textsf{oiO}$, and $\textsf{odiO}$ is formalized by the following theorem, whose proof is deferred to full version.

Theorem 4.6

($\textsf{VBB} \Rightarrow \textsf{oiO}$ and $\textsf{VBB} \Rightarrow \textsf{odiO}$). Let $\textsf{S}$ be a sampler (Definition 3.1). For $b\in \{0,1\}$, let $\textsf{S}_b$ be a sampler such that $(C_b,\alpha ) = \textsf{S}_b(1^\lambda ;r)$ where $r \in \{0,1\}^*$, and $(C_0,C_1,\alpha ) = \textsf{S}(1^\lambda ;r)$. If $\textsf{S}_0,\textsf{S}_1 \in \mathcal {S}_{\textsf{VBB}}$ then $\textsf{S}\in \mathcal {S}_{\textsf{type}}$ where $\mathcal {S}_{\textsf{VBB}}$ and $\mathcal {S}_{\textsf{type}}$ are defined in Definition 4.3.

By leveraging a similar argument to that used to prove Theorem 4.5, we can demonstrate that any negative result for $\textsf{diO}$ extends to $\textsf{odiO}$. This because any $\textsf{diO}$-sampler $\textsf{S}$ is also an $\textsf{odiO}$-sampler and, since $\textsf{diO}$ and $\textsf{odiO}$ leverage the same indistinguishability-based definition, if $\textsf{S}\not \in \mathcal {S}_{\textsf{diO}}$ then $\textsf{S}\not \in \mathcal {S}_{\textsf{odiO}}$.¹² The same applies between $\textsf{odiO}$ and $\textsf{oiO}$, and between $\textsf{oiO}$ and $\textsf{VBB}$ (with respect to samplers as defined in Thoerem 4.6).

Corollary 4.7

For $\textsf{type}\in \{\textsf{diO},\textsf{odiO},\textsf{oiO},\textsf{VBB} \}$, let $\mathcal {S}_{\textsf{type}}$ be an ensemble of $\textsf{type}$-samplers as defined in Definition 4.3. The following conditions holds:

• 1. For every $\textsf{diO}$-sampler $\textsf{S}$ such that $\textsf{S}\not \in \mathcal {S}_{\textsf{diO}}$ then $\textsf{S}\not \in \mathcal {S}_{\textsf{odiO}}$.

• 2. For every $\textsf{odiO}$-sampler $\textsf{S}$ such that $\textsf{S}\not \in \mathcal {S}_{\textsf{odiO}}$ then $\textsf{S}\not \in \mathcal {S}_{\textsf{oiO}}$.

• 3. For every $\textsf{oiO}$-sampler $\textsf{S}$ and every pair of $\textsf{VBB}$-samplers $(\textsf{S}_0,\textsf{S}_1)$ such that $(C_b,\alpha ) = \textsf{S}_b(1^\lambda ;r)$ where $r \in \{0,1\}^*$, $(C_0,C_1,\alpha ) = \textsf{S}(1^\lambda ;r)$ and $b \in \{0,1\}$ (as defined in Theorem 4.6), if $\textsf{S}\not \in \mathcal {S}_{\textsf{oiO}}$ then $\textsf{S}_0 \not \in \mathcal {S}_{\textsf{VBB}}$ or $\textsf{S}_1 \not \in \mathcal {S}_{\textsf{VBB}}$.

Lastly, $\textsf{odiO}$ (resp. $\textsf{oiO}$) does not imply $\textsf{VBB}$, i.e., both $\textsf{odiO}$ and $\textsf{oiO}$ are strictly weaker than $\textsf{VBB}$. This follows by leveraging two observations. First, Barak et al. [7, Lemma 3.5, Corollary 3.8] have demonstrated that there (unconditionally) exists a distribution of circuits that cannot be $\textsf{VBB}$-obfuscated (see also Sect. 6.1). This, in turn, implies that there exists a $\textsf{VBB}$-sampler $\textsf{S}_0\not \in \mathcal {S}_{\textsf{VBB}}$, i.e., $\textsf{S}_0$ outputs $(C,\bot )$ where $C$ comes from the distribution of [7, Lemma 3.5]. Second, we have that any sampler $\textsf{S}_1$, that outputs $(C_0,C_1,\bot )$ such that $C_0 = C_1$, is an $\textsf{odiO}$-sampler (resp. $\textsf{oiO}$-sampler) that can be easily $\textsf{odiO}$-obfuscated (resp. $\textsf{oiO}$-obfuscated).¹³ By combining these two observations, we conclude that if $\textsf{S}_1$ outputs $(C_0,C_1,\bot )$ where $C_0 = C_1$ and $(C_0,\bot ) \,{\leftarrow \!\!{\$}}\,\textsf{S}_0(1^\lambda )$, it follows that neither $C_0$ nor $C_1$ (sampled by $\textsf{S}_0$) can be $\textsf{VBB}$-obfuscated but $\textsf{S}_1$ can be $\textsf{odiO}$-obfuscated (resp. $\textsf{oiO}$-obfuscated). While this counterexample might be trivial at first sight, it indeed captures the fact that an $\textsf{odiO}$-/$\textsf{oiO}$-obfuscator is allowed to reveal any information which is common to the two circuits, as long as this information does not allow to win the respective distinguishing game between the oracles.

Theorem 4.8

($\textsf{odiO} \not \Rightarrow \textsf{VBB}$ and $\textsf{oiO} \not \Rightarrow \textsf{VBB}$). Let $\textsf{S}_0$ be a $\textsf{VBB}$-sampler (Definition 3.4). Consider the $\textsf{odiO}$-sampler (resp. $\textsf{oiO}$-sampler) $\textsf{S}_1$ defined as $(C_0,C_1,\alpha ) = \textsf{S}_1(1^\lambda ;r)$ where $C_0 = C_1$ and $(C_0,\alpha ) = \textsf{S}_0(1^\lambda ;r)$ for $r \in \{0,1\}^*$. For $\textsf{type}\in \{\textsf{odiO},\textsf{oiO} \}$, there exists a $\textsf{VBB}$-sampler $\textsf{S}_0$ such that $\textsf{S}_0 \not \in \mathcal {S}_{\textsf{VBB}}$ and $\textsf{S}_1 \in \mathcal {S}_{\textsf{type}}$ where $\mathcal {S}_{\textsf{VBB}}$ and $\mathcal {S}_{\textsf{type}}$ as defined in Definition 4.3.

5 Applications of $\textsf{odiO}$ and $\textsf{oiO}$

In this section, we show that $\textsf{odiO}$ and $\textsf{oiO}$ are able to compile several symmetric key primitives into their corresponding public key versions and designated verifier non-interactive argument systems into their public verifiable version. These transformations achieve (and use) different flavors of security whose definitions can be found in the full version of this paper. In more details, we demonstrate the following transformations:

• Function-Preserving PV-NIZK from DV-NIZK: $\textsf{odiO}$ is able to compile any designated verifier non-interactive argument system (that satisfies either selective soundness or straight-line knowledge soundness) into its public verifiable version (Sect. 5.1).

• Function-Preserving Signatures from MACs: $\textsf{odiO}$ is able to compile any $(q)$-sEUF-sel-CMA MAC into a $(q)$-sEUF-sel-CMA signature scheme (full version).

• Format-Preserving Signatures from MACs: $\textsf{odiO}$ is able to compile EUF MAC into a sel-EUF-CMA digital signature scheme, using puncturable PRF (full version).

• Format-Preserving PKE from $\textsf{IV}$-based SKE: $\textsf{odiO}$ is able to compile semantically secure $\textsf{IV}$-based SKE (i.e., SKE whose encryption algorithm has the following sintax $\textsf{Enc}({\textsf{k}},m;\textsf{iv}) = (\textsf{iv},c)$) into a sel-IND-CPA PKE, using puncturable PRF (full version).

• Function-Preserving PKE from SKE: $\textsf{oiO}$ is able to compile any semantically and sel-IND-CPRA-key secure SKE into a sel-IND-CPA PKE (Sect. 5.2).

Note that transformations that use the puncturable PRFs are only format-preserving whereas the others are fully function-preserving.

We show the first and the last of our applications in detail in the main body; proofs and the remaining applications are deferred to the full version of this work.

5.1 From Designated Verifier to Public Verifiable Non-interactive Argument Systems

Fig. 2.

The circuits $C^\textsf{Verify}_\textsf{vrs}$, $C^\textsf{Verify}_{\textsf{vrs},x^*}$, $C^{\textsf{Verify}}_{\textsf{vrs},\textsf{td},r}$, and the samplers $\textsf{S}_{x}$,$\textsf{S}_{\textsf{Ext}^*}$. $C^\textsf{Verify}_\textsf{vrs}$ and $C^\textsf{Verify}_{\textsf{vrs},x^*}$ (resp. $C^\textsf{Verify}_\textsf{vrs}$ and $C^{\textsf{Verify}}_{\textsf{vrs},\textsf{td},r}$) are padded to match the size $\gamma =\textsf{max}\{|C^\textsf{Verify}_\textsf{vrs}|, |C^\textsf{Verify}_{\textsf{vrs},x^*}|\}$ (resp. $\gamma = \textsf{max}\{|C^\textsf{Verify}_\textsf{vrs}|, |C^{\textsf{Verify}}_{\textsf{vrs},\textsf{td},r}|\}$).

Construction 1

Let $\varPi ^* = (\textsf{Setup}^*,\textsf{Prove}^*,\textsf{Verify}^*)$ and $\textsf{Obf}$ be a DV non-interactive argument system for a relation $\mathcal {R}$ and an obfuscator, respectively. We compile $\varPi ^*$ into a PV non-interactive argument system $\varPi =(\textsf{Setup},\textsf{Prove},\textsf{Verify})$ for the same relation $\mathcal {R}$ as follows:

• $\textsf{Setup}(1^\lambda ,\mathcal {R})$: On input the security parameter $1^\lambda$ and a relation $\mathcal {R}$, the setup algorithm computes $(\textsf{crs}^*,\textsf{vrs}^*) \,{\leftarrow \!\!{\$}}\,\textsf{Setup}^*(1^\lambda , \mathcal {R})$ and outputs $\textsf{crs}= \textsf{crs}^*$ and $\textsf{vrs}= \widetilde{C}$ where $\widetilde{C} \,{\leftarrow \!\!{\$}}\,\textsf{Obf}(1^\lambda ,C^{\textsf{Verify}}_{\textsf{vrs}^*})$ and $C^\textsf{Verify}_\textsf{vrs}$ is depicted in Fig. 2.

• $\textsf{Prove}(\textsf{crs},x,\omega )$: On input the common reference string $\textsf{crs}= \textsf{crs}^*$, a statement $x$, and a witness $\omega$, the prover algorithm outputs $\pi \,{\leftarrow \!\!{\$}}\,\textsf{Prove}^*(\textsf{crs}^*,x,\omega )$.

• $\textsf{Verify}(\textsf{vrs},x,\pi )$: On input the verification key $\textsf{vrs}= \widetilde{C}$, a statement $x$, and a proof $\pi$, the verification algorithm returns $b = \widetilde{C}(x,\pi )$.

Below we establish the following result.

Theorem 5.1

Let $\varPi ^*$ and $\textsf{Obf}$ as defined in Construction 1. For every $x\not \in \mathcal {L}$, consider the sampler $\textsf{S}_x$ depicted in Fig. 2.

• 1. If $\varPi ^*$ satisfies selective soundness then, for every $x\not \in \mathcal {L}$, $\textsf{S}_x$ is an $\textsf{odiO}$-sampler (Definition 4.1), and

• 2. if $\textsf{Obf}$ is a $(\{\textsf{S}_x\}_{x\not \in \mathcal {L}})$-$\textsf{odiO}$-obfuscator (Definition 4.2) then the publicly verifiable non-interactive argument system $\varPi$ of Construction 1 satisfies selective soundness.

We extend the above result to the case of straight-line knowledge soundness.

Theorem 5.2

Let $\varPi ^*$ and $\textsf{Obf}$ as defined in Construction 1.

• 1. If $\varPi ^*$ satisfies straight-line knowledge soundness then the sampler $\textsf{S}_{\textsf{Ext}^*}$ of Fig. 2 is an $\textsf{odiO}$-sampler (Definition 4.1) where $\textsf{Ext}^* = (\textsf{Ext}^*_0,\textsf{Ext}^*_1)$ is the PPT extractor of $\varPi ^*$, and

• 2. if $\textsf{Obf}$ is a $(\{\textsf{S}_{\textsf{Ext}^*}\})$-$\textsf{odiO}$-obfuscator (Definition 4.2) then the publicly verifiable non-interactive argument system $\varPi$ of Construction 1 satisfies straight-line knowledge soundness.

Remark 5.3

(On zero-knowledge). Observe that Construction 1 preserves zero-knowledge if the underlying designated verifier non-interactive argument system $\varPi ^*$ is zero-knowledge. This is straightforward and follows intuitively because Construction 1 only obfuscates $\textsf{vrs}$ (that it is known by a malicious verifier against zero-knowledge) and it does not alter $\varPi ^*$’s $\textsf{Prove}$. A proof sketch of the zero-knowledge property would be as follows. The simulator for the publicly verifiable case is the same as the one for the designated verifier case. Now assume there exists an adversary $\textsf{A}_{\text {pv}}$ distinguishing simulated proofs from honest ones. We could then design adversary $\textsf{A}_{\text {dv}}$ breaking zero-knowledge of the original scheme. This adversary can in fact internally run $\textsf{A}_{\text {pv}}$ passing to it the obfuscation $\textsf{Obf}(1^\lambda , C^\textsf{Verify}_{\textsf{vrs}})$. It can do that because the designated-verifier zero-knowledge has access to $\textsf{vrs}$.

5.2 From Semantically and sel-IND-CPRA-key SKEs to sel-IND-CPA PKEs

Fig. 3.

The circuit $C^\textsf{Enc}_{\textsf{k}}$ and the sampler $\textsf{S}_{m}$. $C^\textsf{Enc}_{{\textsf{k}}_0}$ and $C^\textsf{Enc}_{{\textsf{k}}_1}$ (output by $\textsf{S}_{m}$) are padded to match the size $\gamma = \textsf{max}\{|C^\textsf{Enc}_{{\textsf{k}}_0}|,|C^\textsf{Enc}_{{\textsf{k}}_1}|\}$)

Construction 2

Let $\varPi ^* = (\textsf{KGen}^*,\textsf{Enc}^*,\textsf{Dec}^*)$ and $\textsf{Obf}$ be a SKE with message space $\mathcal {M}$ and an obfuscator, respectively. We compile $\varPi ^*$ into a PKE scheme $\varPi =(\textsf{KGen},\textsf{Enc},\textsf{Dec})$ with message space $\mathcal {M}$ as follows:

• $\textsf{KGen}(1^\lambda )$: On input the security parameter $1^\lambda$, the key generation algorithm computes ${\textsf{k}}^* \,{\leftarrow \!\!{\$}}\,\textsf{KGen}^*(1^\lambda )$ and outputs $\textsf{pk}= \widetilde{C}$ and $\textsf{sk}= {\textsf{k}}^*$ where $\widetilde{C} \,{\leftarrow \!\!{\$}}\,\textsf{Obf}(1^\lambda ,C^{\textsf{Enc}}_{{\textsf{k}}^*})$ and $C^\textsf{Enc}_{\textsf{k}}$ is depicted in Fig. 3.

• $\textsf{Enc}(\textsf{pk},m;r)$: On input the public key $\textsf{pk}= \widetilde{C}$, a message $m\in \mathcal {M}$, and randomness $r\in \{0,1\}^*$, the encryption algorithm outputs $c= \widetilde{C}(m,r)$.

• $\textsf{Dec}(\textsf{sk},c)$: On input the secret key $\textsf{sk}= {\textsf{k}}^*$ and a ciphertext $c$, the deterministic decryption algorithm returns $m= \textsf{Dec}^*({\textsf{k}}^*,c)$.

Below we establish the following result.

Theorem 5.4

Let $\varPi ^*$ and $\textsf{Obf}$ as defined in Construction 2. For every $m\in \mathcal {M}$, consider the sampler $\textsf{S}_m$ depicted in Fig. 3.

• 1. If $\varPi ^*$ is sel-IND-CPRA-key then, for every $m\in \mathcal {M}$, $\textsf{S}_m$ is an $\textsf{oiO}$-sampler (Definition 4.1), and

• 2. If $\varPi ^*$ is semantically secure and $\textsf{Obf}$ is a $(\{\textsf{S}_m\}_{m\in \mathcal {M}})$-$\textsf{oiO}$-obfuscator (Definition 4.2) then the PKE scheme $\varPi$ of Construction 2 is sel-IND-CPA.

Fig. 4.

The circuit $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ where $(\textsf{s},{\textsf{k}},a,b,\textsf{y},e)\in \{0,1\}^{5\lambda +1}$ and $\odot$ is the binary representation of a $2\times 2$ table of an arbitrary binary operator (e.g., AND, OR, NOT).

6 Extending the Impossibility Results of Barak et al. [7, 8] to the Setting of $\textsf{odiO}$ and $\textsf{oiO}$

In Sect. 4, we have demonstrated that both $\textsf{odiO}$ and $\textsf{oiO}$ are weaker than $\textsf{VBB}$ and, despite this, these new notions are enough to implement several of the most important applications of $\textsf{VBB}$ (Sect. 5). At this point, the natural question is how weak $\textsf{odiO}$ and $\textsf{oiO}$ are, compared to $\textsf{VBB}$. In order to give an answer to this question, we investigate whether the impossibility results for $\textsf{VBB}$ (of Barak et al. [7, 8]) extend to either $\textsf{odiO}$ or $\textsf{oiO}$ (or both). Unfortunately, this turned out to be true: As we show in Sect. 6.1, for $\textsf{type}\in \{\textsf{odiO},\textsf{oiO} \}$, there exist a $\textsf{type}$-sampler that cannot be $\textsf{type}$-obfuscated (unconditionally).

In addition, Barak et al. [8, Theorem 4.10] have shown that converting an arbitrary SKE into a PKE (by simply obfuscating the SKE’s encryption algorithm together with a symmetric key) is not possible: Indeed, there exists a contrived SKE $\varPi$ that cannot be obfuscated (as described above) into a PKE. However, such an impossibility result does not apply to our $\textsf{oiO}$-based transformation from semantically secure and sel-IND-CPRA-key secure SKEs into sel-IND-CPA PKEs (Sect. 5.2) since the contrived SKE $\varPi$ of [8] is not sel-IND-CPRA-key. Following the same spirit, we study whether a similar argument applies to our format-preserving (deferred to full version) and function-preserving transformations (Construction 2). In this case, we have a negative answer but only for the $\textsf{oiO}$-based function-preserving transformation (Construction 2): We demonstrate that there exists a SKE $\varPi$ that is semantically and sel-IND-CPRA-key secure that cannot be converted into a sel-IND-CPA PKE by simply obfuscating the SKE’s encryption algorithm together with a symmetric key, as done by our $\textsf{oiO}$-based Construction 2. On the other hand, it remains unclear how we can prove a similar impossibility result for our $\textsf{odiO}$-based format-preserving transformation from SKEs to PKEs (through puncturable PRFs). See full version of this work for more details.

We stress that both our impossibility results leverage similar techniques to that of Barak et al. [7, 8] that we describe in the next sections.

Also, to meet space constraints, the formal proofs of the theorems that appear in next sections are deferred to full version.

6.1 Unobfuscatable $\textsf{odiO}$-samplers (Resp. $\textsf{oiO}$-samplers) Exist Unconditionally

We build an ensemble of circuits $\mathcal {C}= \{C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}\}$ (indexed by $(\textsf{s},{\textsf{k}},a,b,\textsf{y},e) \in \{0,1\}^{5\lambda + 1}$) that (i) $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ leaks no information when treated as oracles, and (ii) the obfuscation of any $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)} \in \mathcal {C}$ allows to extract the hardcoded values $({\textsf{k}},a,b,\textsf{y},e)$. We anticipate that the value $e\in \{0,1\}$ will allow us to prove that a circuit $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ cannot be $\textsf{odiO}$-obfuscated (resp. $\textsf{oiO}$-obfuscated) (see Sect. 6.1). On the other hand, the value $\textsf{y}$ is a key of a PRF that is fundamental to build a contrived semantically and sel-IND-CPRA-key secure SKE that cannot be obfuscated (as described in Construction 2) into a sel-IND-CPA PKE (Sect. 6.2). We build such an ensemble $\mathcal {C}$ (depicted in Fig. 4) by using a similar technique to that of [7, 8] (for more details, we refer the reader to [7, 8]).

In a nutshell, $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ (depicted in Fig. 4) is the composition of four circuits $(C^0_{{\textsf{k}},a,b}, C^1_{{\textsf{k}},a}, C^2_{{\textsf{k}}}, C^{3}_{{\textsf{k}},a,b,y,e})$ and it is defined with respect to a SKE scheme $\varPi _0 = (\textsf{KGen}_0,\textsf{Enc}_0,\textsf{Dec}_0)$ and a PRF $\varPi _1 = (\textsf{Gen}_1,\textsf{F}_1)$ (required to generate “fresh” randomnesses). On input $(\ell ,v,r)$ where $v = (x,i,c_1,c_2,\odot ,d_1,\ldots ,d_\lambda )$, $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ uses $\ell$ to select which circuit to execute:

• 1. If $\ell =0$, $C^0_{{\textsf{k}},a,b}(x,\textsf{F}_1(\textsf{s},(\ell ,v,r)))$ is executed. This circuit presents a trigger input a. If $x = a$, $C^0_{{\textsf{k}},a,b}(x,\textsf{F}_1(\textsf{s},(\ell ,v,r)))$ returns b. Otherwise, it returns $\textsf{Enc}_0({\textsf{k}},0;\textsf{F}_1(\textsf{s},(\ell ,v,r)))$.

• 2. If $\ell = 1$, $C^1_{{\textsf{k}},a}(i,\textsf{F}_1(\textsf{s},(\ell ,v,r)))$ is executed. This circuit simply outputs the encryption of the i-th bit of a, i.e., $\textsf{Enc}_0({\textsf{k}},a_i;\textsf{F}_1(\textsf{s},(\ell ,v,r)))$.

• 3. If $\ell = 2$, $C^2_{{\textsf{k}}}(c_1,c_2,\odot ,\textsf{F}_1(\textsf{s},(\ell ,v,r)))$ is executed. This circuit allows an evaluator to perform (gate by gate) computations over encrypted inputs. In more detail, it outputs the encryption of the evaluation of $w \odot z$ (i.e., $\textsf{Enc}_0({\textsf{k}},w \odot z; \textsf{F}_1(\textsf{s},(\ell ,v,r)))$) where $\odot$ is a binary operator, and w and z are the bits encrypted by $c_1$ and $c_2$, respectively.

• 4. If $\ell = 3$, $C^3_{{\textsf{k}},a,b,\textsf{y},e}(d_1,\ldots ,d_\lambda ,\textsf{F}_1(\textsf{s},(\ell ,v,r)))$ is executed. This is another circuit that presents a trigger input b. In more detail, if each $d_i$ is the encryption of the i-th of b, the circuit returns $({\textsf{k}},a,\textsf{y},e)$. Otherwise, it returns $\textsf{Enc}_0({\textsf{k}},0;\textsf{F}_1(\textsf{s},(\ell ,v,r)))$.

Following [7, 8], if the SKE scheme $\varPi _0$ is IND-CCA1 and $\varPi _1$ is a secure PRF, then oracle access to $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ is computationally indistinguishable to oracle access to a circuit $\widetilde{C}_{{\textsf{k}}}$ that, on every input $(\ell ,v,r)$, it always outputs a fresh encryption of 0. This is because an adversary only sees ciphertexts and, as a consequence, it cannot distinguish between $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ and $\widetilde{C}_{{\textsf{k}}}$ unless it guesses the trigger inputs $a,b \in \{0,1\}^\lambda$. As a consequence, this implies that (i) an adversary cannot leak the hardcoded values $({\textsf{k}},a,b,\textsf{y},e)$ and, (ii) the pair of circuits $(C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},0)},C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},1)})$ are both oracle-differing-input and oracle-indistinguishable circuits (Definition 4.1).

On the other hand, on input $\widetilde{C} \,{\leftarrow \!\!{\$}}\,\textsf{Obf}(1^\lambda ,C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)})$, an adversary can easily extract $({\textsf{k}},a,b,\textsf{y},e)$, i.e., the circuit is partially reversible. This can be done as follows:

• Evaluate $\widetilde{C}(1,\cdot ,\cdot )$ to get the encryptions $(c_1,\ldots ,c_\lambda )$ of the a’s bits (see Item 2).

• Use $(c_1,\ldots ,c_\lambda )$ to compute $(d_1,\ldots ,d_\lambda )$ where $d_i$ is the encryption of b’s i-th bit. Observe that this can be done by leveraging $\widetilde{C}(2,\cdot ,\cdot )$ to evaluate (gate by gate) $\widetilde{C}(0,\cdot ,\cdot ) = C^0_{{\textsf{k}},a,b}(\cdot ,\cdot )$ on a (see Item 3), and

• Compute $({\textsf{k}},a,b,\textsf{y},e)$ by $\widetilde{C}(3,\cdot ,\cdot )$ on $(d_1,\ldots ,d_\lambda )$ (see Item 4).

The properties of the ensemble $\mathcal {C}$ are formalized in Theorem 6.1. We highlight that our technique of generating $\textsf{Enc}_0$’s randomness as $\textsf{F}_1(\textsf{s},(\ell ,v,r))$ (instead of $\textsf{F}_1(\textsf{s},(\ell ,v))$ as done by Barak et al. [7, 8]) permits to have multiple randomnesses for a fixed pair $(\ell ,v)$. This is allows us to prove a new property (not achieved by [7, 8]) named input-indistinguishability that, in turn, is fundamental to prove the impossibility (Sect. 6.2) of converting semantically and sel-IND-CPRA-key secure SKE into sel-IND-CPA PKE. We stress that the ensemble of circuits built by Barak et al. [7, Lemma 3.5] does not satisfy input-indistinguishability.

Theorem 6.1

Let $\varPi _0 = (\textsf{KGen}_0,\textsf{Enc}_0,\textsf{Dec}_0)$, $\varPi _1 = (\textsf{Gen}_1,\textsf{F}_1)$, and $C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}$ be a SKE scheme with key space $\{0,1\}^\lambda$, a PRF scheme with key space $\{0,1\}^\lambda$, and the circuit defined in Fig. 4 with respect to $\varPi _0$ and $\varPi _1$, respectively. Then, the ensemble $\mathcal {C}= \{C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}\}_{\textsf{s},{\textsf{k}},a,b,\textsf{y}\in \{0,1\}^\lambda ,e\in \{0,1\}}$ satisfies the following properties:

• Oracle-differing-input: If $\varPi _0$ is IND-CCA1 and $\varPi _1$ is secure then for every PPT adversary $\textsf{D}$, we have

  $$\begin{aligned} \mathbb {P}\left[ C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},0)}(\ell ,v,r) \ne C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},1)}(\ell ,v,r) \right] \le \textsf{negl}(\lambda ), \end{aligned}$$

  where $(\ell ,v,r) \,{\leftarrow \!\!{\$}}\,\textsf{A}^{C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},0)}(\cdot ,\cdot ,\cdot ),C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},1)}(\cdot ,\cdot ,\cdot )}(1^\lambda )$, ${\textsf{k}}\,{\leftarrow \!\!{\$}}\,\textsf{KGen}_0(1^\lambda )$, $\textsf{s}\,{\leftarrow \!\!{\$}}\,$ $\textsf{Gen}_1(1^\lambda )$, $\textsf{y}\,{\leftarrow \!\!{\$}}\,\textsf{Gen}_1(1^\lambda )$, and $(a,b) \,{\leftarrow \!\!{\$}}\,\{0,1\}^{2\lambda }$.

• Input-indistinguishability: If $\varPi _0$ is IND-CCA1 and IND-CPA-key, and $\varPi _1$ is secure, then for every $\ell ,v \in \{0,1\}^*$, every PPT adversary $\textsf{D}$, we have

  $$\begin{aligned}&\left| \mathbb {P}\left[ \textsf{D}^{C^*_{\textsf{s}_0({\textsf{k}}_0,a_0,b_0,\textsf{y}_0,0)}(\cdot ,\cdot ,\cdot ), C^*_{\textsf{s}_1,({\textsf{k}}_1,a_1,b_1,\textsf{y}_1,1)}(\cdot ,\cdot ,\cdot )}(1^\lambda , m_0) =1 \right] - \right. \\&\qquad \left. \mathbb {P}\left[ \textsf{D}^{C^*_{\textsf{s}_0,({\textsf{k}}_0,a_0,b_0,\textsf{y}_0,0)}(\cdot ,\cdot ,\cdot ), C^*_{\textsf{s}_1,({\textsf{k}}_1,a_1,b_1,\textsf{y}_1,1)}(\cdot ,\cdot ,\cdot )}(1^\lambda , m_1) =1 \right] \right| \le \textsf{negl}(\lambda ), \end{aligned}$$

  where $(a_0,b_0,a_1,b_1) \,{\leftarrow \!\!{\$}}\,\{0,1\}^{4\lambda }$, ${\textsf{k}}_j \,{\leftarrow \!\!{\$}}\,\textsf{KGen}_0(1^\lambda )$ for $j \in \{0,1\}$, $\textsf{s}_j \,{\leftarrow \!\!{\$}}\,$ $\textsf{Gen}_1(1^\lambda )$ for $j \in \{0,1\}$, $\textsf{y}_j \,{\leftarrow \!\!{\$}}\,\textsf{Gen}_1(1^\lambda )$ for $j \in \{0,1\}$, and $m_d = C^*_{\textsf{s}_d,({\textsf{k}}_d,a_d,b_d,\textsf{y}_d,d)}(\ell ,v,r_d)$ for $r_d \,{\leftarrow \!\!{\$}}\,\{0,1\}^*$ and $d \in \{0,1\}$.

• Partial reversibility: There exists a PPT algorithm $\textsf{Ext}$ such that for every $(\textsf{s},{\textsf{k}},a,b,\textsf{y},e) \in \{0,1\}^{5\lambda +1}$ and every circuit $\widetilde{C}$ such that $\widetilde{C}(\ell ,v,r) = C^*_{\textsf{s},({\textsf{k}},a,b,\textsf{y},e)}(\ell ,v,r)$ for all $\ell ,v,r \in \{0,1\}^*$, $\mathbb {P}\left[ ({\textsf{k}},a,b,\textsf{y},e) \,{\leftarrow \!\!{\$}}\,\textsf{Ext}(1^\lambda , \widetilde{C}) \right] = 1$.

Theorem 6.1 implies that there exists an $\textsf{odiO}$-sampler (resp. $\textsf{oiO}$-sampler) $\widehat{\textsf{S}}$ that cannot be $\textsf{odiO}$-obfuscated (resp. $\textsf{oiO}$-obfuscated), if OWFs exist (indeed, OWF implies both IND-CCA1 and IND-CPA-key security of SKE. See full version for more details).

Corollary 6.2

For $\textsf{type}\in \{\textsf{odiO},\textsf{oiO} \}$, if OWFs exist then there exists a $\textsf{type}$-sampler $\widehat{\textsf{S}}$ (Definition 4.1) such that $\widehat{\textsf{S}} \not \in \mathcal {S}_{\textsf{type}}$ where $\mathcal {S}_{\textsf{type}}$ is defined in Definition 4.3.

Fig. 5.

The circuit $C^\textsf{owf}_{r,b}$ and the sampler $\textsf{S}_{\textsf{owf}}$.

Similarly to $\textsf{VBB}$, both $\textsf{odiO}$ and $\textsf{oiO}$ imply the existence of OWFs. As a consequence, for $\textsf{type}\in \{\textsf{odiO},\textsf{odiO} \}$, a $\textsf{type}$-unobfuscatable $\textsf{type}$-sampler exists unconditionally.

Theorem 6.3

s Let $\textsf{Obf}$ and $\textsf{S}_{\textsf{owf}}$ be an obfuscator and the sampler as defined in Fig. 5. Let $p(\cdot )$ and $\mathcal {F}= \{\textsf{F}_\lambda \}_{\lambda \in \mathbb {N}}$ be a polynomial and an ensemble of functions such that $\textsf{F}_\lambda$ is defined as $\textsf{F}_\lambda (b,r_0,r_1) = \textsf{Obf}(1^\lambda , C^{\textsf{owf}}_{r_0,b};r_1)$ where $(b,r_0,r_1) \in \{0,1\}\times \{0,1\}^{\lambda } \times \{0,1\}^{p(\lambda )}$. Then, the following statements hold:

• 1. $\textsf{S}_{\textsf{owf}}$ is an $\textsf{odiO}$-sampler (resp. $\textsf{oiO}$-sampler), and

• 2. if $\textsf{Obf}$ is a $(\{\textsf{S}_{\textsf{owf}}\})$-$\textsf{odiO}$-obfuscator (resp. $(\{\textsf{S}_{\textsf{owf}}\})$-$\textsf{oiO}$-obfuscator) then $\textsf{F}_\lambda \in \mathcal {F}$ is a OWF.

Corollary 6.4

For $\textsf{type}\in \{\textsf{odiO},\textsf{oiO} \}$, there exists (unconditionally) a $\textsf{type}$-sampler $\textsf{S}$ such that $\textsf{S}\not \in \mathcal {S}_{\textsf{type}}$ where $\mathcal {S}_{\textsf{type}}$ as defined in Definition 4.3.

The above corollary follows by combining Corollary 6.2 and Theorem 6.3, i.e., either $\textsf{S}_{\textsf{owf}} \not \in \mathcal {S}_{\textsf{type}}$ or $\widehat{\textsf{S}} \not \in \mathcal {S}_{\textsf{type}}$ (for $\textsf{type}\in \{\textsf{odiO},\textsf{odiO} \}$) where $\textsf{S}_{\textsf{owf}}$ and $\widehat{\textsf{S}}$ defined in Fig. 5 and Corollary 6.2, respectively.

6.2 Impossibility of Obfuscating Semantically and sel-IND-CPRA-key Secure SKE into sel-IND-CPA Secure PKE Schemes

We now demonstrate that it is inherently impossible to convert a semantically secure and sel-IND-CPRA-key SKEs into sel-IND-CPA PKEs by simply obfuscating the SKE’s encryption algorithm, as described in our $\textsf{oiO}$-based Construction 2. We prove this by leveraging a similar technique to that of [8]: We construct a SKE $\varPi ^*$ that satisfies semantic and sel-IND-CPRA-key security that, when obfuscated into a PKE (as described in Sect. 5.2), the latter results to be completely insecure. By leveraging the ensemble $\mathcal {C}$ of Theorem 6.1, a PRF $\overline{\varPi }=(\overline{\textsf{Gen}},\overline{\textsf{F}})$, and a semantically and sel-IND-CPRA-key secure SKE scheme $\widetilde{\varPi } = (\widetilde{\textsf{KGen}},\widetilde{\textsf{Enc}},\widetilde{\textsf{Dec}})$, we build the contrived SKE $\varPi ^*$ as follows:

$$\begin{aligned} \textsf{Enc}^*({\textsf{k}}^*,(\ell ,v);r) = (\widetilde{\textsf{Enc}}(\widetilde{{\textsf{k}}},(\ell ,v);r), C^*_{\textsf{s},(\widehat{{\textsf{k}}},a,b,\textsf{y},e)}(\ell ,v,r), \overline{\textsf{F}}(\textsf{y},(\ell ,v,r)) \oplus \widetilde{{\textsf{k}}}) \end{aligned}$$

(1)

where ${\textsf{k}}^* = (\widehat{{\textsf{k}}}, \widetilde{{\textsf{k}}}, \textsf{s},a,b,\textsf{y},e)$.

$\varPi ^*$ is a semantically and sel-IND-CPRA-key secure SKE for the following reasons. First, as described in Sect. 6.1, oracle access to the circuit $C^*_{\textsf{s},(\widehat{k},a,b,\textsf{y},e)} \in \mathcal {C}$ is computationally indistinguishable from having oracle access to a circuit $\widetilde{C}_{\textsf{k}}$ that always returns encryptions of 0. Hence, this implies that $C^*_{\textsf{s},(\widehat{k},a,b,\textsf{y},e)}$ does not leak the message $(\ell ,v)$ and that an adversary cannot leak any information about $(\widehat{{\textsf{k}}},a,b,\textsf{y},e)$. Second, conditioned to the above observation, the semantic security of $\varPi ^*$ easily follows from the semantic security of $\widetilde{\varPi }$ and the security of $\overline{\varPi }$. Third, as for the sel-IND-CPRA-key security of $\varPi ^*$, it follows from sel-IND-CPRA-key security of $\widetilde{\varPi }$, the security of $\overline{\varPi }$, and the fact that $\mathcal {C}$ satisfies input-indistinguishability (see Theorem 6.1).

On the other hand, when $\textsf{Enc}^*$ is obfuscated (as in Construction 2), an adversary can exploit the partial reversibility of $\mathcal {C}$ (Theorem 6.1) to extract $\textsf{y}$ and, in turn, the key $\widetilde{{\textsf{k}}}$ that is used to encrypt the message $m= (\ell ,v)$. Below, we report the formal result.

Theorem 6.5

If OWFs exist then the following statements hold:

• 1. there exist a SKE $\varPi ^*$ such that $\varPi ^*$ is semantically secure, sel-IND-CPRA-key, and

• 2. the PKE scheme $\varPi = (\textsf{KGen},\textsf{Enc},\textsf{Dec})$ (output by applying to $\varPi ^*$ the transformation defined in Construction 2) is not sel-IND-CPA (Theorem 5.4).

We stress that the above result improves the impossibility result of Barak et al. [8] since ours apply to the smaller class of SKEs (i.e., SKEs with stronger notions of security) that satisfy sel-IND-CPRA-key security.

Also, all our $\textsf{odiO}$-based transformations remain plausible as the impossibility result do not seem to extend. We provide more details in the full version of this work.