Thomas Agrikola

Geoffroy Couteau

Dennis Hofheinz

The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO

Keywords: indistinguishability obfuscation, extremely lossy functions, subexponential assumptions

We consider the problem of removing subexponential reductions to indistinguishability obfuscation (iO) in the context of obfuscating probabilistic programs. Specifically, we show how to apply complexity absorption (Zhandry, Crypto 2016) to the recent notion of probabilistic indistinguishability obfuscation (piO, Canetti et al., TCC 2015). As a result, we obtain a variant of piO which allows to obfuscate a large class of probabilistic programs, from polynomially secure indistinguishability obfuscation and extremely lossy functions. Particularly, our piO variant is able to obfuscate circuits with specific input domains regardless of the performed computation. We then revisit several (direct or indirect) applications of piO, and obtain a fully homomorphic encryption scheme (without circular security assumptions), a multi-key fully homomorphic encryption scheme with threshold decryption, an encryption scheme secure under arbitrary key-dependent messages, a spooky encryption scheme for all circuits, a function secret sharing scheme with additive reconstruction for all circuits, all from polynomially secure iO, extremely lossy functions, and, depending on the scheme, also other (but polynomial and comparatively mild) assumptions. All of these assumptions are implied by polynomially secure iO and the (non-polynomial, but very well-investigated) exponential DDH assumption. Previously, all the above applications required to assume the subexponential security of iO (and more standard assumptions).

Table of Contents 1 Introduction

Obfuscation. Code obfuscation has been formalized already in the early 2000s as a cryptographic building block, by Hada [Had00] and Barak et al. [BGIRSVY01], along with a number of early positive [Can97; LPS04; Wee05; HRsV07; HMS07] and negative [BGIRSVY01; GK05; Wee05] results. However, prior to the candidate obfuscation scheme of Garg et al. [START_REF] Garg | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits[END_REF], only relatively few positive results on obfuscation were known.

The first candidate obfuscator from [START_REF] Garg | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits[END_REF] changed things. Their work identified indistinguishability obfuscation (iO, cf. [BGIRSVY01; GR07]) as an achievable and useful general notion of obfuscation: it presented a candidate indistinguishability obfuscator, along with a first highly non-trivial application. Since then, a vast number of applications have been proposed, ranging from functional [START_REF] Garg | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits[END_REF], deniable [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF], and fully homomorphic [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] encryption, over multi-party computation (e.g., [START_REF] Garg | Two-Round Secure MPC from Indistinguishability Obfuscation[END_REF]), to separation results (e.g., [START_REF] Hofheinz | Standard Security Does Not Imply Indistinguishability Under Selective Opening[END_REF]). In the process, powerful techniques like "puncturing" [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF] have been discovered, which have found applications even beyond obfuscation (e.g., in multi-party computation [BL18; GS18], instantiating the Fiat-Shamir paradigm [START_REF] Canetti | Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption[END_REF], and verifiable random functions [START_REF] Bitansky | Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs[END_REF][START_REF] Goyal | A Generic Approach to Constructing and Proving Verifiable Random Functions[END_REF]). Besides, the notion of iO itself has been refined, and related to other notions of obfuscation [ABGSZ13; BP13; BCP14; BCKP14; CLTV15; IPS15], and various different constructions of obfuscators have been presented [PST14; Zim15; AJ15; BV15; AS17; Lin17; LT17]. Subexponential assumptions. It is currently hard to find a cryptographic primitive that can not be constructed from iO (in combination with another mild assumption such as the existence of one-way functions). However, some of the known iO-based constructions come only with subexponential reductions to iO. For instance, the only known iO-based constructions of fully homomorphic encryption [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF], spooky encryption [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], and graded encoding schemes [START_REF] Farshim | Graded Encoding Schemes from Obfuscation[END_REF] suffer from reductions with a subexponential loss.

Hence, while iO has generally been recognized as an extremely powerful primitive (even to the extent being called a "central hub" for cryptography [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF]), it is not at all clear if this also holds for polynomially secure iO. Indeed, it is conceivable that only polynomially secure iO exists, in which case much of iO's power stands in question.

More generally, subexponential reductions (in particular to iO) are undesirable. Namely, the security of existing iO constructions is still not well-understood, and in particular current state-of-the-art constructions of iO schemes (such as [AS17; Lin17; LT17]) already require subexponential computational assumptions themselves. Hence, assuming subexponential iO is a particularly risky bet. This suspicion is confirmed in part by [START_REF] Pass | Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings[END_REF], who separate polynomial and subexponential security for virtual black-box obfuscation.

Removing subexponential assumptions in general and from iO-based constructions in particular has already explicitly been considered in [LM16; GS16] and [GPS16; GPSZ17; LZ17] respectively. These works offer general techniques and ideas to turn subexponential reductions into polynomial ones. For instance, [GPSZ17; LZ17] offer ways to replace (subexponential) iO-based constructions with (polynomial) constructions based on functional encryption. Of course, this requires a special structure of the primitive to be implemented, and is demonstrated for several primitives, including non-interactive key exchange and short signature schemes.

Our contribution. In this work, we are also concerned with substituting subexponential with polynomial reductions in iO-based constructions. Unlike [GPSZ17; LZ17], however, we do not follow the approach of using functional encryption directly in place of iO, but instead will employ extremely lossy functions (ELFs) [START_REF] Zhandry | The Magic of ELFs[END_REF] to "absorb" subexponential complexity. 4We will implement a variant of probabilistic indistinguishability obfuscation (piO, introduced in [CLTV15]) using polynomially secure iO (and ELFs). piO schemes can be used to obfuscate probabilistic (i.e., randomized) programs, and are currently the only way to obtain, e.g., fully homomorphic encryption (FHE) schemes without circular security assumptions [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. However, the only previous construction of piO schemes required subexponentially secure iO [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. Hence, our construction yields the first FHE scheme from polynomially secure iO (and ELFs). Similarly, we can turn the assumption of subexponentially secure iO into polynomially secure iO (plus ELFs) in the construction of spooky encryption from [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF].

Both FHE and spooky encryption are quite powerful primitives, and we obtain several "spin-off results" by revisiting their implications. For instance, when instantiating the piO-based FHE construction of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] with our piO scheme and a suitable public-key encryption scheme, we obtain a fully key-dependent message (KDM) secure public-key encryption scheme from (polynomially secure) iO and the exponentially secure DDH assumption (and no further assumptions). Under the same assumptions, we obtain multi-key FHE with threshold decryption and function secret sharing schemes from the spooky encryption construction from [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF].

On the plausibility of ELFs. One could argue that we trade one exponential assumption for another, and it is not clear that assuming polynomial iO and exponential DDH is any better than assuming only subexponential iO in the first place. Seconding Zhandry [START_REF] Zhandry | The Magic of ELFs[END_REF] here, we think that exponential DDH is a realistic assumption that is far more popular, better-investigated, and arguably more plausible than subexponential iO. Much of the currently deployed cryptography relies on (in fact a strong variant of) exponential DDH, because parameters are almost always chosen according to the best known attacks.

On the number of assumptions. Another natural observation is that iO for general circuits is already an exponential family of assumptions in itself (one for each obfuscated circuit). It might seem that this lets the challenge of relying on polynomially secure iO instead of subexponentially secure iO appear less appealing. We make two comments on that.

-First, being an exponential family of assumptions and assuming resistance against subexponential adversaries are orthogonal issues. Many cryptographic assumptions have several dimensions of strengths, and relaxing the assumption in any of these dimensions is desirable. 5 In this work, we make progress in one important dimension. By replacing subexponential iO by polynomial iO plus exponential DDH, we effectively trade an exponential number of subexponential hardness assumptions in exchange for a single (plausible, well-studied) exponential hardness assumption (plus an exponential family of polynomial hardness assumptions). -Second, iO being an exponential family of assumptions can be considered an artificial consequence of working on the general notion of iO for arbitrary circuits. When using iO in concrete constructions (e.g. in all the constructions described in this paper), one almost never needs to assume iO for all circuits. It usually suffices to assume iO for a constant number of specific circuits (namely those being obfuscated in the construction and the analysis). Hence, iO is a small number of assumptions when used for building a cryptographic primitive.

Technical overview

The piO construction of Canetti et al. To describe our ideas, it will be helpful to briefly review the work of Canetti et al. [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. In a nutshell, they define the notion of piO as a way to obfuscate probabilistic programs, and show how to use piO to implement the first FHE scheme without any circular security assumption. Intuitively, where the notion of iO captures that the obfuscation iO(P ) of a deterministic program P does not leak anything beyond the functionality of P , piO captures the same for probabilistic programs P .6 They also show how to implement piO with an indistinguishability obfuscator iO and a pseudorandom function (PRF) F . Namely, in order to obfuscate a probabilistic program P , Canetti et al. obfuscate the deterministic program P that, on input x, runs P (x) with random coins r = F (K, x). Here, K is a PRF key hardcoded into P . The security proof uses "puncturing" techniques [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF] and a hybrid argument over all possible P -inputs x. More specifically, for each P -input x, separate reductions to the security of iO and F show that the execution of P (x) is secure. 7This proof strategy is very general and does not need to make any specific assumptions about the structure of P . (In fact, this strategy can be viewed as a specific form of "complexity leveraging", technically similar to the conversion of selective security into adaptive security, e.g., [START_REF] Boneh | Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles[END_REF].) However, the price to pay is a reduction loss which is linear in the size of the input domain (which usually is exponentially large). In particular, even after scaling security parameters suitably, Canetti et al. still require subexponentially secure iO and PRFs.

More on previous works to remove subexponentiality. There are a number of known ways to deal with subexponential reduction losses due to complexity leveraging (or related techniques). For instance, various semi-generic (pre-iO) techniques seek to achieve adaptive security (for different primitives) by establishing an algebraic or combinatorial structure on the used inputs [BB04b; Wat05; HK08; HW09], and can sometimes be adapted to the iO setting [START_REF] Hohenberger | Replacing a Random Oracle: Full Domain Hash from Indistinguishability Obfuscation[END_REF]. But like the already-mentioned, somewhat more general approaches [GPSZ17; LZ17], these works make specific assumptions about the structure of the involved computations.

A somewhat more general approach (that works for more general classes of programs) was outlined by Zhandry [START_REF] Zhandry | The Magic of ELFs[END_REF], who introduces the notion of "extremely lossy functions" (ELFs). Intuitively, an ELF is an injective function G that can be switched into an "extremely lossy mode", in which its range is polynomially small. Such an ELF can sometimes be used to "preprocess" inputs in a cryptographic scheme, with the following benefit: a security reduction can switch the ELF to extremely lossy mode, so that only a polynomial number of (preprocessed) inputs G(x) need to be considered. This simplifies a potential hybrid argument over all (preprocessed) inputs G(x), and can lead to a polynomial (instead of a subexponential) reduction.

However, trying to apply this strategy to the construction and reduction of Canetti et al. (as sketched above) directly fails. Namely, in their application, inputs will be inputs x to an arbitrary (probabilistic) program P ; preprocessing them with an ELF will destroy their structure, and it is not clear how to run P on ELF-preprocessed inputs G(x). Indeed, applying ELFs to realize piO requires fundamentally different techniques.

Main idea: piO with sparsifiable inputs. Instead, we will restrict ourselves to programs P that take as input an element x from a small number of (arbitrary but efficiently samplable) distributions. In other words, all possible inputs x need to be in the range of one of a small number of efficient samplers S i . As an example, for i ∈ {0, 1}, sampler S i could sample ciphertexts C that encrypt plaintext i. Moreover, we require that all inputs to a program P to be obfuscated are at some point actually sampled from some S i according to a certain process.

Obfuscating a given probabilistic program P (that takes as inputs one or more x as above) now consists of two steps:

1. First, we encode all inputs x, in the sense that we compile S i to attach a "certificate" aux to x. This certificate aux guarantees that x has really been sampled using S i . Furthermore, the compiled sampler S i uses preprocessed random coins of the form G(r) (instead of r) for an ELF G. (When G is in injective mode, this does not affect the distribution of sampled x.) The certificate aux additionally guarantees this choice of random coins.8 2. Second, we produce the actual obfuctation of the probabilistic program P as follows. We use an indistinguishability obfuscator iO to obfuscate the following (deterministic) variant P of P : on inputs x 1 , . . . , x with certificates aux 1 , . . . , aux , P first checks the certificates aux i and aborts if one of them is invalid.

Next, P runs P (x 1 , . . . , x ), with random coins F (K, (x i ) i=1 ) for a PRF F and a hardcoded PRF key K.

Finally, P outputs P 's output. Maybe the most important property of this setup is that now the sets of inputs x i are "sparsifiable" in the following sense. If we set G to extremely lossy mode, then only a polynomial number of different random coins r can occur. Hence, each S i will output one of only a small number of possible samples (e.g., encryptions C generated with random coins from a small set). In that sense, the set of possible inputs x i to P has been "sparsified", and a hybrid argument over all possible inputs as in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] is possible with polynomial loss.

We stress that our technique of applying ELFs fundamentally differs from [START_REF] Zhandry | The Magic of ELFs[END_REF]. In [START_REF] Zhandry | The Magic of ELFs[END_REF], the constructed primitive itself ensures that G is applied on all inputs. When approaching the challenge of constructing piO, however, the input to the primitive must externally be sampled using random coins that are preprocessed with G. This process is not under the control of the primitive and therefore requires a mechanism certifying that inputs are generated according to this specific process. We implement this mechanism using the combination of compiling the sampler for the input distribution into a "certifying sampler" (step 1) and restricting correctness of the obfuscated program (step 2). Surprisingly, our piO scheme achieves the notion of "dynamic-input piO" [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF], a very strong variant of piO security. On a high level, dynamic-input piO guarantees indistinguishability between obfuscations of probabilistic programs as long as their output distributions on adversarially chosen inputs are indistinguishable. This constitutes a very strong requirement and, in fact, implies differing-inputs obfuscation [BGIRSVY01; ABGSZ13], a notion for which strong impossibility results exist [START_REF] Garg | On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input[END_REF][START_REF] Bellare | New Negative Results on Differing-Inputs Obfuscation[END_REF]. However, our obfuscator produces circuits which are only required to work on inputs certifiably generated according to a specific process. Hence, our piO scheme enjoys a restricted form of correctness. This enables us to circumvent the impossibility results [GGHW14; BSW16].

Applications. One obvious question is of course how restrictive our assumption on input domains really is. We show that our assumptions apply to two existing piO-based constructions, with a number of interesting consequences.

First, we revisit the piO-based construction of fully homomorphic encryption from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. Here, piO is used to obfuscate the FHE evaluation algorithm that takes two ciphertexts (say, of two bit plaintexts b 0 and b 1 ) as input, and outputs a ciphertext of the NAND of the two plaintexts (i.e., b 0 ∧b 1 ). If we set S b to be a sampler that samples an encryption of b, this setting perfectly fits our scheme. Hence, we obtain first a leveled homomorphic encryption (LHE) scheme, and from this an FHE scheme using the high-level strategy from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. Hence, putting this together with our piO construction, we obtain an FHE scheme from polynomially secure iO and an ELF (and no further assumptions).

We note that the above FHE scheme is also fully key-dependent message (KDM, see [START_REF] Black | Encryption-Scheme Security in the Presence of Key-Dependent Messages[END_REF]) secure when implemented with a suitable basic public-key encryption scheme (such as the DDH-based scheme of [START_REF] Boneh | Circular-Secure Encryption from Decision Diffie-Hellman[END_REF]). In that case, the FHE is secure even when an encryption of its own secret key C sk = Enc(pk, sk) is public. However, such an encryption C sk can be transformed into an encryption Enc(pk, f (sk)) of an arbitrary function of sk thanks to the fully homomorphic properties of the FHE scheme. This leads to a conceptually very simple fully KDM-secure encryption scheme from polynomial assumptions (and ELFs). (We stress that we do not claim novelty for this observation. The connection between FHE and KDM security has already been observed in [START_REF] Barak | Bounded Key-Dependent Message Security[END_REF], and [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] have observed that the FHE construction of Canetti et al. preserves interesting properties of the underlying encryption scheme. However, [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] do not explicitly mention KDM security, and we find these consequences interesting enough to point out.)

As our second application, we consider spooky encryption (with CRS) introduced by Dodis et al. [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]. Intuitively, a spooky encryption scheme features a particular type of homomorphism in a multi-key, multiciphertext setting. More precisely, given ciphertexts {c i = Enc(pk i , x i )} i , a spooky encryption scheme allows to produce ciphertexts {c i } i with y i = Dec(sk i , c i ) such that certain so-called "spooky" relations between between the x i 's and the y i 's hold. An important subclass of spooky relations allows to ensure that the y i 's are random subject to i y i = f (x 1 , . . . , x n ), for any polynomial-time computable function f . Dodis et al. show that spooky encryption implies (among other things) function secret sharing, and they give a piO-based instantiation of spooky encryption (without the need of a CRS). At the heart of their construction is an obfuscated public "spooky evaluation" algorithm with a hardcoded decryption key. Since this algorithm also takes ciphertexts (and a public key) as input, its input domain can be sparsified much like in the FHE case.

In contrast to the FHE application, however, the spooky encryption application contains more technical subtleties. In particular, some inputs to the "spooky evaluation" algorithm may depend on other inputs, and hence sparsifying inputs needs to proceed in a certain order. The main difficulty here is to find a suitably flexible definition of sparsification; we omit the details in this overview. We note that our results of course also yield all applications of spooky encryption, only from polynomially secure iO (and ELFs). In particular, we obtain a simple protocol for function secret sharing for all functions (with additive reconstruction) from these assumptions [START_REF] Boyle | Function Secret Sharing[END_REF].

We believe that our new notion of obfuscation will prove useful in other applications; for example, it would likely allow to improve the recent result of [START_REF] Canetti | Chosen-Ciphertext Secure Fully Homomorphic Encryption[END_REF], which constructed CCA1-secure FHE from subexponentially secure iO.

Follow-up work. In the recent work [START_REF] Döttling | Universal Proxy Re-Encryption[END_REF], Döttling and Nishimaki define the notion universal proxy re-encryption (UPRE). UPRE schemes allow a proxy to convert any ciphertext under any public key of any existing PKE scheme into a ciphertext under any public key of any possibly different existing PKE scheme. [START_REF] Döttling | Universal Proxy Re-Encryption[END_REF] instantiate UPRE based on probabilistic IO due to [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. UPRE for all PKE schemes (including non re-randomizable ones) requires dynamic-input pIO, which implies differing-inputs obfuscation. However, [START_REF] Döttling | Universal Proxy Re-Encryption[END_REF] observe that our notion of doubly-probabilistic IO suffices which yields an instantiation of UPRE for all PKE schemes based on polynomial IO and exponential DDH.

Organization. In Section 2, we introduce our notations and recall standard preliminaries. Section 3 formally introduces our new variant of piO, called dpiO. Section 4 shows how to instantiate dpiO using polynomially secure iO and ELFs. Eventually, in Section 5 and we revisit the construction of leveled homomorphic encryption from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF], using dpiO instead of piO. In , we revisit the construction of spooky encryption from [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] using dpiO and analyze our new construction.

Preliminaries

Notations. Throughout this paper, λ denotes the security parameter. For a natural number n ∈ N, [n] denotes the set {1, . . . , n}. A probabilistic polynomial time algorithm (PPT, also denoted efficient algorithm) runs in time polynomial in the (implicit) security parameter λ. A positive function f is negligible if for any polynomial p there exists a bound B > 0 such that, for any integer k ≥ B, f (k) ≤ 1/|p(k)|. An event depending on λ occurs with overwhelming probability when its probability is at least 1 -negl(λ) for a negligible function negl. Given a finite set S, the notation x $ ← S means a uniformly random assignment of an element of S to the variable x. The notation A O indicates that the algorithm A is given oracle access to O. Let C = {C λ } λ≥0 be a family of sets of (possibly randomized) circuits, where C λ contains circuits of size poly(λ). A circuit sampler for C is a distribution ensemble D = {D λ } λ≥0 , such that D λ ranges over triples (C 0 , C 1 , z) with (C 0 , C 1 ) ∈ C 2 λ of identical size and taking inputs of the same length, and z ∈ {0, 1} poly(λ) . A class of samplers S is a set of circuit samplers for C.

Indistinguishability Obfuscation for General Samplers

Indistinguishability obfuscation (iO) for general samplers was introduced in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. This notion generalizes the classical notion of iO introduced in [START_REF] Barak | On the (Im)possibility of Obfuscating Programs[END_REF]. Informally, an iO scheme for a sampler D allows to obfuscate circuits sampled with D so that, given a sample (C 0 , C 1 ) from D, iO(C 0 ) ≈ iO(C 1 ). The standard notion of iO is recovered by considering samplers over functionally equivalent deterministic circuits of the same size. Stronger notions of obfuscation, denoted piO, can be defined for samplers over probabilistic circuits, satisfying various indistinguishability notions. We recall below the general definition of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] of piO for a class of samplers (using a different notion of correctness defined in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]). The original correctness definition states that an efficient adversary given oracle access to either the original circuit or the obfuscation (with the restriction that no input can be queried twice), can not tell the difference.

Definition 1 (piO for a Class of Samplers [CLTV15; DHRW16]). A uniform PPT machine piO is an indistinguishability obfuscator for a class of samplers S over a family C = {C λ } λ≥0 of possibly randomized circuits if it satisfies the following conditions:

Correctness. For every security parameter λ, every circuit C ∈ C λ , and every input x, the distributions of C(x) over the random coins of C and of piO(1 λ , C)(x) over the random coins of the obfuscator are identical. µ-Indistinguishability. For every sampler D = {D λ } λ≥0 ∈ S, and for every non-uniform PPT machine A, it holds that

| Pr[(C 0 , C 1 , z) $ ← D λ : A(C 0 , C 1 , piO(1 λ , C 0 ), z) = 1] -Pr[(C 0 , C 1 , z) $ ← D λ : A(C 0 , C 1 , piO(1 λ , C 1 ), z) = 1]| ≤ µ(λ).
We remark that the construction of piO from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] satisfies this notion of correctness if instantiated with a perfect puncturable PRF, see Definition 4. Note that this does not extend to multiple evaluations of the obfuscated circuit. Further, note that this notion of correctness implies that the obfuscated circuit respects the support of the original circuit.

To recover the standard notion of iO, we introduce the class S eq of samplers for functionally equivalent (possibly randomized) circuits, i.e., samplers over triplets (C 0 , C 1 , z) such that |C 0 | = |C 1 |, and for any input x and random coin r, C 0 (x; r) = C 1 (x; r). The standard iO notion is obtained by considering piO over the subclass S det ⊂ S eq of samplers for deterministic functionally equivalent circuits. We denote by Adv iO (A) the advantage of a PPT adversary A in distinguishing between the obfuscation of functionaly equivalent deterministic circuits.

The work of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] introduced four types of samplers over probabilistic circuits, which define four corresponding variants of piO: dynamic-input piO, worst-case piO, memoryless worst-case piO, and X-Ind piO. Informally, a dynamic-input sampler is required to output (possibly randomized) circuits C 0 , C 1 such that the output of these circuits on a dynamically chosen input is computationally indistinguishable. The corresponding notion, dynamic-input piO, is the strongest notion defined in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] and a randomized equivalent of the notion of differing-input obfuscation. Therefore, it inherits the implausibility results of differing-input obfuscation for general circuits [GGHW14; BSW16]. On the other hand, [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] shows that the weaker notion X-Ind piO can be realized from subexponentially secure iO (and subexponentially secure one-way functions). Below, we recall the notion of dynamic-input samplers and dynamic-input piO from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF].

Dynamic-Input Samplers

Definition 2 (Dynamic-Input Indistinguishable Samplers [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]). The class S d-Ind of dynamic-input samplers for a circuit family C contains all circuits samplers D = {D λ } λ∈N for C with the following properties: for every non-uniform PPT A Definition 3 (dynamic-input piO). A uniform PPT machine is a dynamic-input piO scheme if it is a piO for the class of dynamic-input samplers S d-Ind over C that includes all randomized circuits.

= (A 1 , A 2 ), the advantage Adv d-Ind (A) := Pr[Exp-d-Ind A (λ) = 1] -1 2 of A in the experiment Exp-d-Ind represented in Figure 1 is negligible. Experiment Exp-d-IndA(λ) (C0, C1, z) $ ← Dλ (x, st) $ ← A1(C0,
Note that the class S eq of samplers for functionally equivalent circuits that we defined previously, is a subclass of S d-Ind : any sampler for triples (C 0 , C 1 , z) where C 0 and C 1 are functionally equivalent is trivially a dynamic-input sampler.

Puncturable Pseudorandom Function

A pseudorandom function (PRF) originally introduced in [GGM84] is a tuple of PPT algorithms F = (F.KeyGen, F.Eval). Let K denote the key space, X denote the domain, and Y denote the range. The key generation algorithm F.KeyGen on input of 1 λ , outputs a random key from K and the evaluation algorithm F.Eval on input of a key K and x ∈ X , evaluates the function F : K × X → Y. The core property of PRFs is that, on a random choice of key K, no probabilistic polynomial-time adversary should be able to distinguish F (K, •) from a truly random function, when given black-box access to it. Puncturable PRFs (pPRFs) have the additional property that some keys can be generated punctured at some point, so that they allow to evaluate the PRF at all points except for the punctured point. As observed in [BW13; BGI14; KPTZ13], it is possible to construct such punctured keys for the original construction from [START_REF] Goldreich | How to Construct Random Functions (Extended Abstract)[END_REF], which can be based on any one-way functions [START_REF] Håstad | A Pseudorandom Generator from any One-way Function[END_REF].

Definition 4 (Puncturable Pseudorandom Function [BW13; BGI14; KPTZ13]). A puncturable pseudorandom function (pPRF) with punctured key space K p is a triple of PPT algorithms (F.KeyGen, F.Punct, F.Eval) such that -F.KeyGen(1 λ ) outputs a random key K ∈ K, -F.Punct(K, x), on input K ∈ K, x ∈ X , outputs a punctured key K{x} ∈ K p , -F.Eval(K , x ), on input a key K (punctured or not), and a point x , outputs an evaluation of the PRF. We require F to meet the following conditions:

Functionality preserved under puncturing. For all λ ∈ N, for all x ∈ X ,

Pr[K $ ← F.KeyGen(1 λ ), K{x} $ ← F.Punct(K, x) : ∀x ∈ X \ {x} : F.Eval(K, x ) = F.Eval(K{x}, x )] = 1. Pseudorandom at punctured points. For all PPT adversaries A, Adv s-cPRF (A) := Pr[Exp-s-pPRF A (λ) = 1] - 1 2 is negligible, where Exp-s-cPRF is represented Figure 2. We call a pPRF F perfect, if the distribution {F.Eval(K, x) | K $ ← F.KeyGen(1 λ )} is identical to the uniform distribution over Y, for all inputs x ∈ X . 9
Definition 4 corresponds to a selective security notion for puncturable pseudorandom functions; adaptive security can also be considered, but will not be required in our work. For ease of notation we often write

F (•, •) instead of F.Eval(•, •). Experiment Exp-s-pPRF A (λ) (x * , state) $ ← A(1 λ ) K $ ← F.KeyGen(1 λ ), K{x * } $ ← F.Punct(K, x * ) b $ ← {0, 1}, y0 ← F.Eval(K, x * ), y1 $ ← Y b $ ← A(state, K{x * }, yb) return b = b

Extremely Lossy Function

In this section we present extremely lossy functions (ELFs) introduced in [START_REF] Zhandry | The Magic of ELFs[END_REF]. ELFs are an extremely powerful primitive for complexity absorption allowing to replace subexponential or even exponential security assumptions with polynomial ones. Informally, an ELF is a function that can be generated in two different modes: an injective mode and an extremely lossy mode. In injective mode, the range of the ELF has exponential size whereas the range comprises only polynomially many elements in extremely lossy mode.

Definition 5 (Extremely Lossy Function [START_REF] Zhandry | The Magic of ELFs[END_REF]). An extremely lossy function ELF is an algorithm ELF.Gen which, on input (M, r), where M is an integer and r ∈ [M ], outputs the description of a function

G : [M ] → [N ] such that -G can be computed in time poly(log M ) -If r = M , G is injective with overwhelming probability (in log M ) over the randomness of ELF.Gen(M, M ); -For any r ∈ [M ], |G([M ])| < r
with overwhelming probability (in log M ) over the randomness of ELF.Gen(M, r); -Indistinguishability: For any large enough M , any polynomial P , and any inverse polynomial function δ, there exists a polynomial Q such that for any adversary A running in time at most P (log M ) and any

r ∈ [Q(log M ), M ], the advantage of A in distinguishing ELF.Gen(M, M ) from ELF.Gen(M, r) is bounded by δ(log M ).
In addition, we will consider extremely lossy functions satisfying strong regularity, as defined below.

9 Given any pPRF F , we can build a perfect pPRF F by sampling two keys K1 $ ← F .KeyGen(1 λ ) and K2 $ ← Y in the key generation algorithm and defining the evaluation algorithm to output F .Eval(K1, x) ⊕ K2 on input of x, see [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF].

Definition 6 (Strong regularity). An ELF is strongly regular if for any (polynomial) r, the distribution {x

$ ← [M ] : G(x)} is statistically close to uniform over G([M ]), with overwhelming probability over the choice of G $ ← ELF.Gen(M, r).
We note that, if an ELF is strongly regular, it is possible to efficiently enumerate its image: the set of values obtained by evaluating an ELF on λr log r random inputs, where r is a bound on the size of its image, contains the entire image of the ELF with overwhelming probability.

Instantiating ELFs. A construction of strongly regular extremely lossy function is given in [START_REF] Zhandry | The Magic of ELFs[END_REF]. It can be based on the exponential hardness of the decision Diffie-Hellman assumption (or any of its variants, such as the decision linear assumption), which we denote eDDH. The eDDH assumption for a group generator GroupGen (which generates a tuple (G, p, g) where G is a group, p is its order, and g is a generator of G) states that there exists a polynomial q such that for any time bound t and probability ε, denoting κ ← log q(t, 1/ε), any adversary A running in time at most t has advantage at most ε in distinguishing the following distributions:

{(G, p, g) $ ← GroupGen(1 κ ), (a, b, c) $ ← Z 3 p : (G, g, g a , g b , g c )}, {(G, p, g) $ ← GroupGen(1 κ ), (a, b) $ ← Z 2 p : (G, g, g a , g b , g ab )}.
As noted in [START_REF] Zhandry | The Magic of ELFs[END_REF], groups based on elliptic curves are plausible candidates for groups where this assumption holds: in practical instantiations of DDH over elliptic curves, the size of the group is chosen assuming that the best attack takes time O( √ p), hence disproving eDDH (which amounts to showing that there is an attack which takes time less than p c for any constant c) would have considerable practical implications. Furthermore, relying on some form of exponential hardness assumption seems necessary, as a construction from polynomial hardness only would have surprising complexity-theoretic implications. More precisely, given access to only some super-logarithmic amount of non-determinism (i.e. ω(log log M ) bits, where [M ] is the domain of the ELF), it is easy to distinguish between injective and lossy mode of the ELF. This is due to the fact that in lossy mode, the codomain of G has only polynomial size which means that the restriction of G to the set D = [2 ω(log log M ) ] (having super-polynomial cardinality) is guaranteed to have a collision (which is not the case in injective mode), and using only ω(log log M ) bits of non-determinism this collision can be guessed.

Non-interactive Zero-Knowledge proof system

A non-interactive zero-knowledge (NIZK) proof system for a language L with witness relation R enables to prove in a non-interactive manner that some statements are in L without leaking information about corresponding witnesses. NIZK proof systems were originally introduced in [START_REF] Blum | Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract)[END_REF].

Definition 7 (Non-interactive zero-knowledge proof system [START_REF] Groth | Perfect Non-interactive Zero Knowledge for NP[END_REF]). A non-interactive zeroknowledge (NIZK) proof system for a language L ∈ NP (with witness relation R) is a tuple of PPT algorithms NIZK = (NIZK.Setup, NIZK.Prove, NIZK.Verify) such that NIZK.Setup is a common reference string generation algorithm, NIZK.Prove is a proving algorithm NIZK.Verify is a (deterministic) verification algorithm.

-NIZK.Setup(1 λ ) outputs a common reference string crs.

-NIZK.Prove(crs, x, w), on input crs, a statement x and a witness w, outputs a proof π.

-NIZK.Verify(crs, x, π), on input crs, a statement x and a proof π, outputs either 1 or 0. We require NIZK to meet the following properties: Perfect completeness. For every (x, w) ∈ R, we have that

Pr[crs $ ← NIZK.Setup(1 λ ), π $ ←NIZK.Prove(crs, x, w) :
NIZK.Verify(crs, x, π) = 1] = 1. Statistical soundness. For every x ∈ L with |x| = λ and every (possibly unbounded) adversary A, we have that Pr[crs

$ ← NIZK.Setup(1 λ ), π $ ← A(crs, x) : NIZK.Verify(crs, x, π) = 1] < 2 -λ .
Computational zero-knowledge. There exists a PPT algorithm Sim = (Sim 0 , Sim 1 ) such that for every PPT adversary A,

Adv ZK (A) := | Pr crs $ ← NIZK.Setup(1 λ ) : A NIZK.Prove(crs,•,•) (crs) = 1 -Pr (crs, τ ) $ ← Sim 0 (1 λ ) : A Sim 1 (crs,τ,•,•) (crs) = 1 | is negligible in λ, where Sim 1 (crs, τ, x, w) returns Sim 1 (crs, τ, x) only if (x, w) ∈ R.
For simplicity in the analysis we use a NIZK proof system that satisfies the following property: with overwhelming probability over the coins of NIZK.Setup(1 λ ), there does not exist any pair (x, π) such that x / ∈ L and NIZK.Verify(crs, x, π) = 1. We call a NIZK that satisfies this property almost perfectly sound. We note that there is a simple folklore method which allows to construct an almost perfectly sound NIZK proof system starting from any statistically sound NIZK proof system. Consider a 2 -λ -statistically sound NIZK proof system, for statements x ∈ {0, 1} n , for some polynomial n = n(λ). Using parallel repetitions, the soundness of the proof system can be amplified to 2 -λ-n .10 Then, it necessarily holds that for all possible crs except a 2 -λ fraction of them, there does not exist any pair (x, π) where x / ∈ L and π is an accepting proof. To realize this, let E crs

x denote the event that there exists a proof π such that NIZK.Verify(crs, x, π) = 1. Then, by a union bound argument,

Pr crs [∃x ∈ {0, 1} n \ L : E crs x ] ≤ x∈{0,1} n \L Pr crs [E crs x ] ≤ 2 n • 2 -λ-n .
Hence, the NIZK proof system obtained via parallel repetitions is almost perfectly sound.

In [START_REF] Bitansky | ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation[END_REF] Bitansky et al. showed that statistically sound NIZK proof systems can be obtained from polynomially secure indistinguishability obfuscation in conjunction with polynomially secure one-way functions.

Indistinguishability Obfuscation of Probabilistic Circuits over Distributions of Inputs

We first define the notion of a sampler with input. A sampler with input is a family of PPT algorithms which, on input x, sample from some distribution D x . This notion is convenient to capture the fact that, in many scenarios, the inputs to an obfuscated (probabilistic) circuit are sampled from some distribution D x , where x is some private input of a player.

Definition 8 (Sampler with Input). We say that SI = {SI λ } λ∈N is a family of samplers with input, with input domain I = {I λ } λ∈N , if for any λ ∈ N, SI λ is a set of probabilistic algorithms running in polynomial time (in 1 λ ) with input domain I λ such that for any S ∈ SI λ , and x ∈ I λ , S(x) samples from {0, 1} λ .

Doubly-Probabilistic Indistinguishability Obfuscation

Below, we define a variant of indistinguishability obfuscation, that takes into account the fact that in many applications, obfuscated (probabilistic) circuits might only have to be evaluated on inputs coming from specific distributions. This is formalized by defining an encoding procedure for a sampler with input, which additionally produces auxiliary material that an obfuscated circuit can use to verify that its inputs were produced correctly, and by restricting the correctness of the obfuscated circuit to only hold for such well-formed inputs. We also refer to this auxiliary material as "certificate". However, this approach faces two issues. First, the inputs to an obfuscated circuit might not be sampled "all at once" from a single distribution; rather, they can come from different and independent sources. We capture this behavior by defining -source obfuscation, to account for the fact that different inputs might have been sampled independently. Second, when inputs are sampled by different parties, there might still be interdependencies which must be accounted for. For example, a party might sample an input (e.g. a public key of an encryption scheme), pass it to a second party, who then samples a second input from a distribution that is parametrized by the first input (e.g. a ciphertext under that public key). We handle this possibility by ordering the inputs to the obfuscated circuit, and by considering a stateful sampler with input S: when S is used to generate the i'th sample y i , it receives in addition to its input a state stf(y 1 , . . . , y i-1 ), where stf is some fixed efficiently computable state function (which depends on the particular application), and the y j are outputs sampled by the first i -1 sources. The state function captures the fact that a particular Additionally, we admit the possibility that a sampler produces some additional correlated output, that will not serve as input to an obfuscated circuit. Hence, there is no need to "certify" this input using the auxiliary information, and we call this output unauthenticated output. Continuing the use case from above, given a sampler producing some public key, the unauthenticated part of that sampler's output could be a corresponding secret key.

Exp 0-enc A (1 λ ) pp $ ← Setup(1 λ ) return b ← A O enc 0 [pp] (pp) Exp 1-enc A (1 λ ) (pp, trap) $ ← Sim0(1 λ ) return b ← A O enc 1 [pp,trap] (pp) Oracle O enc 0 [pp]
Definition 9 (Doubly-Probabilistic Indistinguishability Obfuscation (dpiO)). Let be an integer. Let {stf λ : ({0, 1} λ ∪{⊥}) -1 → T λ } λ∈N be a family of efficiently computable functions. Let SI = {SI λ } λ∈N be a family of samplers with inputs, with input domain {T λ ×I} λ∈N . Let C = {C λ } λ∈N be a family of (probabilistic) circuits, and let CS be a class of circuit samplers over C. An -source dpiO scheme for (stf, SI, C, CS) is a triple of PPT algorithms (Setup, Encode, Obfuscate) such that -Setup(1 λ ), on input the security parameter (in unary), outputs public parameters pp; -Encode(pp, S), on input the public parameters pp, and a sampler with input S ∈ SI λ , outputs an encoded sampler S ; -Obfuscate(pp, S, C), on input public parameters pp, a sampler with input S ∈ SI λ , and a circuit C ∈ C λ , outputs a circuit C of size poly(λ, |C|). We call C an obfuscation of C with respect to S.

We further assume that the outputs of S on any input (state, x) is of the form (y; y ) (looking ahead, we will call y the authenticated output, and y the unauthenticated output). The scheme should satisfy the three properties given below.

Informally, the first security requirement ensures that, on any (adversarially chosen) input x, state state, and sampler with input S, the sampler S obtained by encoding S outputs samples of the form (y, aux; y ) where (y; y ) is distributed as an output of S(state, x), and aux does not leak any non-trivial information about the inputs. This is formalized by requiring the existence of a simulator that can simulate aux given only y.

Definition 10 (Simulatability of Encodings). An -source dpiO scheme for (stf, SI, C, CS) satisfies simulatability of encodings if for any large enough λ and any (stateful) PPT adversary A, there exists a PPT simulator Sim = (Sim 0 , Sim 1 ) such that the advantage of A in distinguishing the experiments Exp 0-enc and Exp 1-enc represented on Figure 3 is negligible. We denote by Adv enc (A) the advantage of A in this experiment.

We now introduce the restricted correctness requirement. Intuitively, it states the following: in an honest scenario, the inputs (y 1 , . . . , y ) should be constructed using the sampler with input S. The restricted correctness property guarantees that if the inputs have indeed been constructed "according to S", then the obfuscated circuit will behave correctly, and its output distribution (taken over the coins of the obfuscator) will be (statistically) indistinguishable from the output distribution of the circuit C (taken over its internal random coins). Note that this statistical indistinguishability does not extend to multiple evaluations. Additionally, when evaluated on such inputs, the obfuscated circuit respects the support of the original circuit. To make this definition meaningful, we need a way to let the obfuscated circuit verify that the inputs are well-formed. Note that we do not want to ensure that they were generated through S with uniformly random coins, but only that they were generated through S with some random coins (and some input). To make this verification possible, we let the parties generate their input using the encoded sampler S instead. This encoded sampler should correctly sample as S, but it will in addition produce auxiliary information which can be used by the obfuscated program to verify that the inputs were honestly constructed (more formally, for a given y, that there exists an input x, coins r, and an unauthenticated part y such that (y; y ) = S(x; r)).

A small technicality is that we must allow the sampler with input to depend on state information, to capture the possible interdependencies between the inputs. This means that the auxiliary information will have to certify that an input was generated correctly, with respect to some state that the obfuscated circuit might not have access too (which would prevent it from verifying the certificate). However, this issue disappears by restricting the interdependencies to only involve a state computed from the previous samples (as opposed to more complex interdependencies which would involve, for example, the coins used to produce these samples). In this case, the obfuscated circuit can check the certificates in an incremental way: it first checks that y 1 was correctly constructed with respect to the state st λ (⊥, . . . , ⊥), then it checks that y 2 was correctly constructed with respect to the state st λ (y 1 , ⊥, . . . , ⊥), and so on.

Definition 11 (Statistical Restricted Correctness

). An -source dpiO scheme for (stf, SI, C, CS) satisfies restricted correctness if for any large enough λ ∈ N, any S ∈ SI λ , (x 1 , . . . , x ) ∈ I λ , and C ∈ C λ , the advantage of any (possibly unbounded) adversary A in distinguishing the experiments Exp 0-rcorr and Exp 1-rcorr represented on Figure 4 is negligible. We denote by Adv rcorr (A) the advantage of A in this experiment. Additionally, we require that the encoded sampler and the obfuscated circuit respect the support of the original sampler and the original circuit, respectively. That is for all pp ← Setup(1 λ ) and all S ← Encode(pp, S) and all C ← Obfuscate(pp, S, C), we have that for all inputs (state, x), S (state, x) ∈ Supp(S(state, x)) and for all (y 1 , aux 1 , . . . , y , aux ) produced as in Exp 0-rcorr , C (y 1 , aux 1 , . . . , y , aux ) ∈ Supp(C(y 1 , . . . , y )).

We now introduce the indistinguishability notion. It is close in spirit to the standard indistinguishability notion for obfuscation of probabilistic circuits of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. However, in our scenario, the security notion must account for the fact that a set of public parameters pp is generated in a setup phase; the indistinguishability property of obfuscated circuits must therefore hold when (polynomially) many circuits are obfuscated with respect to a single string of public parameters. This suggests an oracle-based security notion.

Definition 12 (Indistinguishability with Respect to CS). An -source dpiO scheme for (stf, SI, C, CS) satisfies indistinguishability with respect to CS if for every circuit sampler D = {D λ } λ∈N ∈ CS, for any large enough λ, the advantage of any PPT adversary A in distinguishing the experiments Exp 0-ind and Exp 1-ind represented on Figure 5 is negligible. We denote by Adv ind (A) the advantage of A in this experiment.

Construction

In this section, we will construct an -source dpiO scheme (for any constant ), for samplers with input over an input domain I of polynomial size11 , and dynamic-input indistinguishable circuit-samplers. Our construction relies on polynomially-secure indistinguishability obfuscation, a perfect puncturable pseudorandom function, an almost perfectly sound non-interactive zero-knowledge proof system, and an extremely lossy function.

Exp b-ind A (1 λ ) pp $ ← Setup(1 λ ) return b ← A O ind b [pp,D λ ](•) (pp) Oracle O ind b [pp, Dλ]

Overview

We start by providing a high-level overview of our construction. The Setup procedure generates parameters for the ELF and for the NIZK proof system. To encode a sampler with input S, we define the encoded sampler S as follows: on input (state, x; r), S computes (y; y ) $ ← S(state, x; G(r)) and aux $ ← NIZK.Prove(y, L G,S state , (y , x, r)), and outputs (y, aux; y ). Here, G is the ELF defined by the public parameters, and the language L G,S state contains all values y for which there exists (y , x, r) such that (y; y ) = S(state, x, G(r)). We call valid input a value y ∈ L G,S state . Note that when G is in injective mode, L G,S state will in general be a trivial language. The simulatability of the encodings directly follows from the injectivity of G, and the zero-knowledge property of the proof system.

We construct the Obfuscate algorithm for a circuit C as follows (we assume a single source in this overview for simplicity). It first samples a pPRF key K for the pPRF F. Then, it returns an obfuscation of the following circuit: on input (y, aux), run NIZK.Verify on aux to check that y is a valid input (and output ⊥ otherwise). Set r ← F (K, y), and output C(y; r). Restricted correctness follows from the correctness of the NIZK scheme. For indistinguishability between obfuscations of two dynamic-input indistinguishable circuits (C 0 , C 1 ), we follow the standard puncturing strategy of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]: we proceed through a sequence of hybrids, with successive modifications of the obfuscated circuit. For every possible input y, we construct a sequence of hybrids where the outputs C 0 (y; r) are gradually replaced by C 1 (y; r). Each replacement relies on the security of the iO scheme, the PRF security, and the dynamic-input indistinguishability of C 0 and C 1 .

The main issue of this approach is that the number of possible inputs y (hence the number of hybrids) is exponential -indeed, this is the reason why the piO scheme of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] requires subexponentially secure primitives (iO and PRF). To get around this issue, we first switch G to an appropriate extremely lossy mode, that the adversary cannot distinguish from the injective mode. Now, the soundness of the NIZK proof system ensures that all valid inputs y are of the form S(state, x; G(r)) for some (x, r) (omitting y for simplicity). For a given state, the quantity of such values is bounded by the size of the range of G (which is polynomial), times the size of the input domain I. Therefore, in all applications where the inputs to the obfuscated circuit are sampled using private inputs from a small domain, we can base security on polynomially secure iO.

Construction

For our construction, we employ a perfectly sound NIZK proof system for the following (parametrized) language L G,S state := {y | ∃(y , x, r) : (y; y ) = S(state, x; G(r))}. Let ∈ N be a constant, let {stf λ : ({0, 1} λ ∪ {⊥}) -1 → T λ } λ be a family of efficiently computable state functions, and let C = {C λ } λ be a family of (randomized) circuits with random space {0, 1} M (where M = M (λ) is polynomial). Let SI be a family of samplers with input domain I of polynomial size. Further, let S d-Ind be the class of dynamic-input indistinguishable samplers (over C).

Theorem 13. If ELF is a strongly regular extremely lossy function, iO is a perfectly correct polynomially secure IO scheme, F is a polynomially secure perfect puncturable PRF, and NIZK is a perfectly sound polynomially zero-knowledge NIZK proof system for the family of languages {L G,S state } state,G,S , then dpiO = (Setup, Encode, Obfuscate) defined in Figure 6 is an -source dpIO scheme for (stf, SI, C, S d-Ind ).

As noted in Section 2.5, almost perfectly correct NIZKs can be constructed from polynomially-secure indistinguishability obfuscation and extremely lossy functions. ELFs also imply the existence of one-way functions, hence of perfect puncturable PRFs [GGM84; HILL99]. Therefore, we get as corollary: Corollary 14. Assuming polynomially-secure indistinguishability obfuscation and extremely lossy functions, there exists (for any constant ) an -source doubly-probabilistic indistinguishability obfuscation scheme for the class of dynamic-input circuit-samplers, and input-samplers with a polynomial size input domain.

Proof (of Theorem 13). We prove that dpiO as defined in Figure 6 satisfies simulatability of encodings (cf. Definition 10), statistical restricted correctness (cf. Definition 11), and indistinguishability (cf. Definition 12). Simulatability of encodings. We prove that there exists a PPT simulator Sim = (Sim 0 , Sim 1 ) such that for every PPT adversary A, the advantage Adv enc (A) is negligible. By the zero-knowledge property of NIZK, there exists a simulator (NIZK.Sim 0 , NIZK.Sim 1 ). We construct a simulator Sim = (Sim 0 , Sim 1 ) as follows:

-Sim 0 produces the CRS using (crs, τ ) $ ← NIZK.Sim 0 (1 λ ), samples the parameters of the ELF G in injective mode, and outputs pp := (crs, G) together with trap := τ .

-Sim 1 on input (pp, trap), a sampler S, a state state, and a value y sampled via (y; y ) $ ← S(state, x), Sim 1 produces a simulated proof via π $ ← NIZK.Sim 1 (crs, τ, (G, S, state, y)) and outputs aux := π.

Let A be a PPT adversary on the simulatability property of dpiO. We prove indistinguishability between the real and the simulated distribution via a series of hybrids starting from the simulated game Exp 1-enc

A (1 λ ).
Game G 0 : This game is identical to Exp 1-enc A (1 λ ). We remark that in this game, the tuple (y; y ) is produced using the adversarially chosen sampler S on input of the adversarially chosen state state and input x supplied with true randomness. Game G 1 : This game is identical to G 0 except for the fact that for each query (S, state, x), the sampler S is supplied with randomness G(r) for uniform r (instead of true randomness). Due to the strong regularity of G and by a standard hybrid argument over all queries, the statistical distance between G 0 and G 1 is negligible. Game G 2 : This game is the same as G 1 with the difference that crs is produced honestly using NIZK.Setup(1 λ ). Additionally, for each adversarial query (S, state, x), the proof π is produced honestly by NIZK.Prove(crs, (G, S, state, y), (y , x, r)), where G(r) are the random coins supplied to the sampler S. The view of A in game G 2 is distributed exactly as in the real game Exp 0-enc A (1 λ ). We construct a PPT adversary B on the zero-knowledge property of NIZK. Given a CRS crs, B samples an ELF G in injective mode and invokes A on input of pp := (crs, G). Each time A queries its oracle on (S, state, x), B draws random coins r and invokes the sampler S on input of (state, x) with random coins G(r) to obtain (y; y ). In order to produce π, B calls its prove oracle on input (G, S, state, y) with witness (y , x, r). Therefore, if B is supplied with an honest CRS and honestly generated proofs, B perfectly simulates G 2 for A, else B perfectly simulates G 1 . Hence, |Pr[out 2 = 1] -Pr[out 3 = 1]| ≤ Adv ZK (B). This concludes the proof.

Restricted Correctness. Let S ∈ SI λ be an arbitrary sampler with input, let y 1 , . . . , y be arbitrary values from the input domain I λ , and let C be a circuit from the family C λ . To prove the correctness of dpiO, we proceed over a series of hybrids.

Game G 0 : This game is the ideal game Exp 1-rcorr A (1 λ ). As the sampler S is called using true randomness whereas in Exp 0-rcorr A (1 λ ) samples are generated using G(r), where r is truly random, we need an intermediate hybrid.

Game G 1 : This game is identical to G 0 with the difference that each call of the sampler S is supplied with G(r) as randomness (where r is sampled uniformly for each call). Due to the strong regularity of G, and by a hybrid argument over all calls of S, the statistical distance between G 0 and G 1 is negligible. Game G 2 : This game is the real game Exp 0-rcorr A (1 λ ). We now argue that the view of A in game G 1 is distributed identically to its view in G 2 . G 2 samples public parameters pp via Setup(1 λ ) and S an encoded sampler via S ← Encode(pp, S). Further, (y j , aux j ) are sampled as state j ← stf(y 1 , . . . , y j-1 , ⊥, . . . , ⊥) and (y j , aux j , y j ) $ ← S (state j , x j ), for j ∈ [ ]. Let Λ be the obfuscation Λ $ ← Obfuscate(pp, S, C) of the circuit C with respect to sampler S. Due to the perfect correctness of iO, Λ has the same functionality as C[stf, (crs, G), S, C, K], where K is a freshly generated key for the PRF F. Hence, by the perfect completeness of NIZK, on input of ((y 1 , aux 1 ), . . . , (y , aux )), Λ evaluates the circuit C on input of (y 1 , . . . , y ) with random coins F (K, (y 1 , . . . , y )). Therefore, the view of A in the games G 1 and G 2 only differs in the fact that G 1 supplies C with true random coins whereas G 2 supplies C with F (K, (y 1 , . . . , y )) as randomness. As F is a perfect PRF, the distribution {F (K, (y 1 , . . . , y )) | K $ ← F.KeyGen(1 λ )} is identical to the uniform distribution over the image of F . Therefore, the view of A in G 1 and G 2 is distributed identically.

By construction, all S ← Encode(pp, S) respect the support of S. Furthermore, by construction, perfect completeness of NIZK and perfect correctness of iO, for all C ← Obfuscate(pp, S, C) and all (y 1 , aux 1 , . . . , y , aux ) produced as in Exp 0-rcorr , C (y 1 , aux 1 , . . . , y , aux ) ∈ Supp(C(y 1 , . . . , y )). Security. Let D ∈ S d-Ind be an arbitrary dynamic-input indistinguishable circuit sampler over C. To prove that dpiO satisfies indistinguishability (Definition 12), we proceed over a series of hybrids. Toward contradiction, assume that there is a PPT adversary A distinguishing Exp 0-ind A (1 λ ) from Exp 1-ind A (1 λ ) with non-negligible advantage ε over the random guess after making a polynomial number Q of queries to the oracle. Game G 1 . In this game, the challenger samples G as G $ ← ELF.Gen(M, t), where t is a polynomial such that any PPT algorithm of circuit size s has advantage at most ε/2 in distinguishing ELF.Gen(M, M ) from ELF.Gen(M, t). The advantage of A in this game is therefore lower bounded by ε/2: Pr[out 1 = 1] ≥ ε/2. Game G 1 . This game proceeds exactly as G 1 , except that after sampling b $ ← {0, 1}, the challenger always sets up the experiment Exp 1-ind A (1 λ ). The challenger still returns 1 iff b = b. By using a standard hybrid argument over the oracle queries, we prove that |Pr[out

1 = 1] -Pr[out 1 = 1]| ≤ Q • negl(λ), where Q is a polynomial in λ.
Game G 1.q This game is identical to G 1 except for the fact that the first q oracle queries are answered using an obfuscation

Λ q of C 1 instead of C b . Hence, Pr[out 1.0 = 1] = Pr[out 1 = 1] and Pr[out 1.Q = 1] = Pr[out 1 = 1],
where Q is the number of adversarial oracle queries.

As |Pr[out

1 = 1] -Pr[out 1 = 1]| ≤ Q q=1 |Pr[out 1.q = 1] -Pr[out 1.q+1 = 1]|,
it suffices to upper bound the distinguishing gap between G 1.q and G 1.q+1 . We observe that due to the (almost) perfect soundness of NIZK, the obfuscated circuit in the q-th oracle answer simulates the randomized computation of the circuit C q,0 only on well-formed inputs, i.e. on outputs of S q using random coins from the range of G. As ELF is in extremely lossy mode, this set of well-formed inputs is extremely sparsified. Therefore, by the strong regularity of ELF, we can enumerate over all possible outputs at all input positions j ∈ [ ]. Let B q,j be the set of all well-formed inputs for input position j: B q,j := {S q (stf(y 1 , . . . , y j-1 ), x; G(r)) |

x ∈ I λ , r ∈ {0, 1} M , y k ∈ B k for k ∈ [j -1]}.
The set B q,j contains at most |I|•t j-1 elements. Further, let γ q,1 < • • • < γ q, t be the ordered enumeration of all -tuples in B q := j=1 B q,j .12 Hence, the total number of well-formed inputs

t = j=1 |B q,j | ≤ (|I| • t -1 ) ≤ |I| • t ( 2 )
is polynomial in λ (given that is a constant, and |I| and t are polynomial). Towards proving indistinguishability between G 1.q and G 1.q+1 , we conduct a hybrid argument over all well-formed inputs for the obfuscation Λ q and gradually replace the evaluation of circuit C q,b with C q,1 . From here on, our proof strategy is similar to the one employed in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. However, we only need to consider polynomially many hybrids (as we assume |I| to be polynomial), hence we only lose a polynomial factor to the underlying assumptions. Game G 1.q.i . In game G 1.q.i the oracle answers the q-th query using an obfuscation of the circuit

C [stf, (crs, G), S q , C q,b , C q,1 , K q , γ q,i ]
that is defined in Figure 7 using iO.

Circuit C [stf, (crs, G), S, C0, C1, K, γi]( The circuits C[stf, (crs, G), S q , C q,b , K q ] and C [stf, (crs, G), S q , C q,0 , C q,1 , K q , γ q,1 ] are functionally equivalent (on input x = ((y 1 , aux 1 ), . . . , (y , aux )), both return C q,b (y 1 , . . . , y ) with randomness F (K q , (y 1 , . . . , y ))).

Hence, this game hop is justified by the indistinguishability property of iO, more formally there exists a PPT adversary B such that |Pr[out 1.q = 1] -Pr[out 1.q.1 ] = 1| ≤ Adv iO (B).

We aim to reduce the game hop from G b 1.q.i to G b 1.q.i+1 to the dynamic-input indistinguishability of the circuit sampler D λ . For this purpose, we first need to supply C q,b with true randomness. Hence, we define an other series of hybrids between G 1.q.i and G 1.q.i+1 . Game G 1.q.i.1 . This game is identical to G 1.q.i except for the fact that we use a punctured PRF key K q {γ q,i } $ ← F.Punct(K q , γ q,i ) and obfuscate the circuit

C [stf, (crs, G), C q,0 , C q,1 , K q {γ q,i }, Y := C q,b (γ q,i ; F (K q , γ q,i )), γ q,i ]
defined in Figure 8 using iO. As F preserves the functionality under punctured keys, the circuits C [stf, (crs, G), S q , C q,0 , C q,1 , K q , γ q,i ] and C [stf, (crs, G), S q , C q,0 , C q,1 , K q {γ q,i }, Y := C q,b (γ q,i ; F (K q , γ q,i )), γ q,i ] are functionally equivalent. Hence, there exists a PPT adversary B such that |Pr[out 1.q.i = 1] -Pr[out 1.q.i.1 = 1]| ≤ Adv iO (B). We note that the view of A in game G 1.q.i.1 does not depend on the PRF key K. This enables to exploit the selective security of F. Game G 1.q.i.2 . In this game we replace the randomness F (K q , (γ q,i )) by true randomness, i.e. we produce Y as follows: Y := C q,b (γ q,i ; R). This game hop is justified by the selective PRF property, more formally |Pr[out 1.q.i.1 = 1] -Pr[out 1.q.i.2 = 1]| ≤ Adv s-cPRF (B) for some PPT adversary B.

Leveled Homomorphic Encryption

In this section we show that our notion of dpIO from Section 3 can be applied to construct leveled homomorphic encryption in a similar way as in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. This construction leads to a transformation which operates on an encryption scheme E, satisfying IND-CPA security (and possibly other security properties, e.g., KDM security), and produces a leveled homomorphic encryption scheme that retains the security properties of E. We recall the definition of IND-CPA secure encryption schemes in .

Definition 15 (Leveled Homomorphic Encryption [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF]). A leveled homomorphic encryption scheme LHE is a family of encryption schemes {Enc L : L ≥ 0} such that each Enc L is homomorphic for all polysize depth-L circuits ( i.e., it allows to homomorphically and compactly evaluate any polysize depth-L circuit) with an algorithm Eval of size polynomial in (λ, L), and all the Enc L use the same decryption circuit. We require LHE to meet the following properties:

Correctness. We say that LHE is correct if for every λ ∈ N, for every polysize depth-L circuits C and respective inputs m 1 , . . . , m k ∈ {0, 1}, we have that

Pr [LHE.Dec(sk, (LHE.Eval(ek, C, c 1 , . . . , c k ))) = C(m 1 , . . . , m k )]
is negligible in λ, where (pk, ek, sk)

$ ← LHE.KeyGen(1 λ ) and m j $ ← LHE.Enc(pk, m j ) for j ∈ [k].
Security. We say that LHE is IND-CPA secure if for every PPT adversary A the advantage

Adv IND-CPA (A) := | Pr [A(pk, ek, LHE.Enc(pk, 0))] -Pr [A(pk, ek, LHE.Enc(pk, 1))]| is negligible in λ, where (pk, ek, sk) $ ← LHE.KeyGen(1 λ ).
Let stf λ be the trivial state function, i.e. stf : (y 1 , y 2 ) → ⊥ for each (y 1 , y 2 ) ∈ ({0, 1} λ ∪ {⊥}) 2 . Let E = (E.KeyGen, E.Enc, E.Dec) be an IND-CPA-secure public-key encryption scheme. Let the class SI contain all samplers S pk that on input of a state state and an input x ∈ I := {0, 1}, produce an encryption y := E.Enc(pk, x) and y := ⊥ ignoring state, where pk is a public key in the range of E.KeyGen(1 λ ). Let C be the class of polynomially sized randomized circuits and let S d-Ind be the class of dynamic-input indistinguishable samplers over C.

Theorem 16. Let (Setup, Encode, Obfuscate) be a 2-source dpiO scheme for (stf, SI, C, S d-Ind ) and let E be an IND-CPA secure public-key encryption scheme. Then, LHE as defined in Figure 9 is an IND-CPA secure LHE scheme. The proof strategy is similar as in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. On a high level, we want to reduce the security of LHE to the security of the underlying encryption scheme E. However, the evaluation key ek contains information (even though obfuscated) on the secret keys of each level. For the purpose of invoking the security of E on the challenge ciphertext, we need to remove this dependency on sk 0 . Therefore, we gradually (starting from level L) replace the obfuscations of the circuits C with an obfuscation of trapdoor circuits tC that simply output samples produced by the encoded sampler S on input of 0 (hence, not needing any information on decryption keys). These two circuits only differ in the fact that they sample from the same encoded sampler S using (possibly) different inputs. Due to the simulatability of encodings and the IND-CPA security of E, the two circuits are dynamic-input indistinguishable. Hence, by the indistinguishability property of dpiO for S d-Ind , an honest evaluation key and an evaluation key consisting only of trapdoor circuits are indistinguishable.

LHE.KeyGen(1 λ , 1 L ) for i ∈ {0, . . . , L} do (pk i , ski) $ ← E.KeyGen(1 λ ) pp i $ ← Setup(1 λ ) S pk i ← Encode(pp i , S pk i ) for i ∈ {1, . . . , L} do Λi $ ← Obfuscate pp i-1 , S pk i-1 , C[S pk i , ski-1] pk := S pk
Given these modifications, the challenge ciphertext c * consists of an encryption of a bit b under pk 0 accompanied by some auxiliary information produced by the corresponding encoded sampler. This auxiliary information might leak information on the bit b and thereby prevents to directly employ the IND-CPA security of E. However, as dpiO satisfies simulatability of encodings, this auxiliary information can be simulated without knowledge of b and, hence, contains no information about b. Therefore, by the IND-CPA security of E, LHE is IND-CPA secure. Given our construction of dpiO from Section 4, we obtain the following corollary: Proof (of Theorem 16). We prove that LHE satisfies correctness and IND-CPA security.

Correctness. Let C be a polysized circuit of depth L that consists only of ∧-gates. We prove that on every level i every gate g in C is evaluated as the original gate given the decrypted inputs (except for an negligible error). By a union bound argument over the number of gates, the probability that an error occurs when evaluating circuit C is negligible. Let i ∈ [L] be a level and let g be a gate on level i. Further, let (x α , aux α , •) be in the scope of S pk i-1 (⊥, α) and (x β , aux β , •) be in the scope of S pk i-1 (⊥, β). By the perfect correctness of E, the circuit C[S pk i , sk i-1 ] on input of (x α , aux α ) and (x β , aux β ) always outputs an element from the scope of S pk i (⊥, α ∧ β). 13 Furthermore, due to the statistical correctness of dpiO, the distribution C[S pk i , sk i-1 ]((x α , aux α ), (x β , aux β )) is statistically close to the output of Λ i (over the random coins of Setup, Obfuscate, and S ). Hence, the probability that gate g is not evaluated correctly is negligible. Therefore, the probability (over the random coins of LHE.KeyGen and LHE.Enc) that the circuit C is not evaluated correctly is negligible. 14With the objective of exploiting the IND-CPA security of E to the challenge ciphertext c * , we need to ensure that the auxiliary information that accompanies the ciphertext from S pk 0 (b) does not leak any information about b. This is formalized via another game transition. Game G b 2 . This game is identical to G b 1 except for the fact that the public parameters pp 0 are simulated by Sim 0 (additionally yielding a trapdoor trap 0 ). Furthermore, the challenge ciphertext c * is produced by drawing a sample (y; y ) from S pk 0 (b) and simulating the auxiliary information aux using Sim 1 (pp 0 , trap 0 , S pk 0 , y, ⊥). We recall that for any PPT adversary A such a simulator Sim = (Sim 0 , Sim 1 ) exists as dpiO satisfies simulatability of encodings. Hence, by simulatability of encodings, the distinguishing gap |Pr[out

b 1 = 1] -Pr[out b 2 = 1]| is negligible in λ.
It remains to argue, that the games G 0 2 and G 1 2 are computationally indistinguishable. This can be reduced to the IND-CPA security of E with respect to pk 0 as in G b 2 neither the corresponding secret key sk 0 nor the plaintext b are necessary for simulation.

Claim. For every PPT adversary A, the distinguishing gap |Pr[out

0 1 = 1] -Pr[out 1 1 = 1]| is negligible.
Proof. Let A be a PPT adversary on distinguishing G 0 2 and G 1 2 . We construct a PPT adversary B on the IND-CPA security of E. On input of pk, B defines pk 0 := pk, samples key pairs (pk j , sk j ) $ ← E.KeyGen(1 λ ) for j ∈ {1, . . . , L} and produces ek as in G 1 2 . B outputs the messages 0 and 1 to the IND-CPA game and in turn receives a ciphertext c * . Furthermore, B simulates the auxiliary information by aux * $ ← Sim 1 (pp 0 , trap 0 , S pk 0 , c * , ⊥). Finally, B invokes A on input of (pk 0 , ek, (c * , aux * ) and forwards its output to the IND-CPA experiment. Hence, |Pr[out

0 1 = 1] -Pr[out 1 1 = 1]| is negligible by the IND-CPA security of E.
Given our construction of dpiO from Section 4, we obtain the following corollary:

Corollary 18. Assuming polynomially secure indistinguishability obfuscation and extremely lossy functions, there exists a leveled homomorphic encryption scheme.

Note that IND-CPA secure cryptosystems, as required in our construction, can be constructed from (polynomially secure) IO and one-way function (the latter being implied by ELFs). Previously, constructions of LHE were only known from the learning with error assumption, or from subexponentially secure indistinguishability obfuscation (together with lossy encryption, which can be based e.g. on DDH). Using the generic transformation from leveled homomorphic encryption to fully homomorphic encryption from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF], we also get:

Corollary 19. Assuming slightly-superpolynomially secure indistinguishability obfuscation and extremely lossy functions, there exists a fully homomorphic encryption scheme.

Previously, constructions of FHE were only known from circular-security assumptions over lattice-based cryptosystems, or subexponentially secure indistinguishability obfuscation and lossy encryption. Below, we sketch an improvement to Corollary 19, which removes the need for superpolynomially-secure iO.

Fully Homomorphic Encryption from Polynomial iO and ELFs. Applying the [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] transform of LHE into FHE requires to use superpolynomially secure iO. However, using the same techniques as we used to build dpiO, we can actually base this transformation on polynomially secure iO (and ELFs). We briefly sketch the strategy. The LHE-to-FHE transform of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] stems from the following observation: if an LHE scheme can handle a (slightly) superpolynomial number of levels L, then it is fully homomorphic for all polynomial size circuits. However, this would require generating and storing a superpolynomial number of evaluation keys (ek 1 , . . . , ek L ).

To overcome this issue, the strategy of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] is to obfuscate a master key generation program MProg, which generates the evaluation keys on the fly: on input i, MProg returns ek i . It was observed in [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] that probabilistic iO cannot be directly used to obfuscate this program, because the coins used by MProg must be correlated between two consecutive levels (for example, in our LHE construction, ek i is an obfuscated program with a secret key sk i and a public key pk i+1 hardcoded; hence, ek i+1 must contain the matching secret key for pk i+1 ). Nevertheless, "derandomizing" this program, using the standard technique of generating the coins using a pseudorandom function F (the coins for sk i are generated as F(K, i), and the coins for pk i+1 are generated as F(K, i + 1), which guarantees the appropriate correlation between the coins used in ek i and ek i+1 ), and obfuscating with standard iO, allows to prove security of this approach.

To apply the techniques developped in this work, we must make the input to MProg "sparsifiable", so as to puncture at every possible input with a polynomial loss in the security reduction. We outline a natural approach to achieve this. Instead of directly taking the index i as input, the program MProg takes as input a pair (c i , π), where c i is a counter defined as follows: c 0 = 0, and c i+1 = G(c i ), where G is an extremely lossy function in injective mode, and π is a proof (with a statistically sound NIZK proof system) that c i is in the image of G. On input (c i , π), the program MProg checks the proof, and outputs ⊥ if the check fails. If the check passes, it computes c i+1 ← G(c i ), "draws" random coins r i ← F(K, c i ) and r i+1 $ ← F(K, c i+1 ), and uses these random coins to generate the evaluation key ek i . The exact same proof strategy as [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] applies, except that in the security analysis, we first switch G to an extremely lossy mode, and enumerate over all pairs of the form (x, G(x)) where x is in the image of G; this enumeration is done in polynomial time, hence the reduction only looses a polynomial factor. Therefore, we get:

Corollary 20. Assuming polynomially-secure indistinguishability obfuscation and extremely lossy functions, there exists a fully homomorphic encryption scheme.

By replacing the IND-CPA secure encryption scheme E in the construction of Figure 9 by a KDM-secure encryption scheme for the identity function, which remains secure even when the adversary is allowed to obtain ciphertexts of the form E(pk, sk) (i.e., encryptions of the secret key), we obtain a fully-homomorphic encryption scheme which satisfies KDM-security for the identity function. As already noted in the introduction, this directly implies a fully-KDM secure encryption scheme (which remains secure even when the adversary can receive encryptions of arbitrary functions of its secret key). Plugging in the DDH-based KDM-secure encryption scheme of [START_REF] Boneh | Circular-Secure Encryption from Decision Diffie-Hellman[END_REF], we obtain:

Corollary 21. Assuming polynomially-secure indistinguishability obfuscation and eDDH, there exists a fully KDM-secure encryption scheme.

Spooky Encryption

In this section, we recall the definition of spooky encryption from [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], describe a new construction of spooky encryption from dpiO, and discuss some applications.

Tools and Definitions

Definition 22 (Spooky Encryption [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]). Let C be a class of (possibly randomized) circuits with n inputs and n outputs. An n-key C-spooky encryption scheme SE is a five-tuple of PPT algorithms (SE.Setup, SE.KeyGen, SE.Enc, SE.Eval, SE.Dec) such that -(SE.Setup, SE.KeyGen, SE.Enc, SE.Dec) is an IND-CPA-secure bit encryption scheme; -SE.Eval(C, (pk 1 , c 1 ), . . . , (pk n , c n )), on input a circuit C ∈ C, and n pairs of public key and ciphertext, outputs n ciphertexts; which additionally satisfies the following condition: for every λ, every C ∈ C, every input

x = (x 1 , . . . , x n ) to C, the distribution {∀i, (pk i , sk i ) $ ← SE.KeyGen(1 λ ), c i $ ← SE.Enc(pk i , x i ), (c 1 , . . . , c n ) ← SE.Eval(C, (pk i , c i ) i≤n ) : (SE.Dec(sk i , c i )) i≤n } is statistically close (in λ) to the distribution C(x 1 , . . . , x n ).
Note that we allow the encryption scheme to have a universal setup algorithm, that generates common parameters used (implicitly) in all other algorithms (in particular in the key generation). This corresponds to a "common reference string" flavor of spooky encryption, as for the LWE-based construction in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]. The piO-based construction given in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], however, does not require any such setup, but the definition of dpiO requires a universal setup, which we therefore assume for our construction of spooky encryption below.

An important class of spooky relations are the circuits that, on input (x 1 , . . . , x n ), output random additive (bitwise) shares of a function f (x 1 , . . . , x n ). A spooky encryption scheme handling this type of relation is called AFS-spooky. Two-Key Spooky Encryption of Re-Sampleable Circuits. The work of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] constructs two-key spooky encryption schemes, for probabilistic circuits satisfying efficient re-sampleability, assuming piO (as well as other primitives, which can be instanciated from DDH). Below, we revisit their construction, and show that we can replace the underlying piO scheme by a dpiO scheme for samplers with input over a small domain. We first recall the necessary notions and primitives.

Definition 23 (Efficient Re-Sampleability). A probabilistic circuit C : {0, 1} 1 × {0, 1} 2 → {0, 1} 1 × {0, 1} 2 of polynomial size is efficiently re-sampleable if there exists a polynomial-size resampling circuit RS C such that for any

(x 1 , x 2 ) ∈ {0, 1} 1 × {0, 1} 2 , the distribution C(x 1 , x 2 ) is identical to the distribution {(y 1 , y 2 ) $ ← C(x 1 , x 2 ), y 2 $ ← RS C (x 1 , x 2 , y 1 ) : (y 1 , y 2 )}.
Let M : {0, 1} 2 → {0, 1} 2 be a probabilistic circuit which performs a spooky multiplication: on input (b 1 , b 2 ), it outputs random bit-shares of their product b 1 b 2 . It is clear that M is efficiently re-sampleable. We write M (b 1 , b 2 ; r) 1 to denote the first output of M on input (b 1 , b 2 ) with randomness r.

Maliciously Circuit-Private (Non-Compact) Homomorphic Encryption Scheme. A public key encryption scheme E = (E.KeyGen, E.Enc, E.Dec) is homomorphic for a class of circuits C if there exists an algorithm E.Eval such that for every key pair (pk, sk), circuit C ∈ C, and ciphertext c ← E.Enc(pk, x), it holds that E.Dec(sk, E.Eval(pk, C, c)) = C(x).

Definition 24 (Perfect Malicious Circuit Privacy [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]). A homomorphic encryption scheme E = (E.KeyGen, E.Enc, E.Dec, E.Eval) for a class of circuits C has perfect malicious circuit privacy if for every alleged public key pk (possibly outside of the support of KeyGen) and ciphertext c * (possibly maliciously computed), there exists an "effective plaintext" x such that for every two circuits (C 1 , C 2 ) ∈ C with C 1 (x) and C 2 (x), it holds that E.Eval(pk, C 1 , c * ) and E.Eval(pk, C 2 , c * ) are identically distributed.

Our construction will employ an homomorphic encryption scheme with perfect malicious circuit privacy. As noted in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], a perfect malicious circuit private encryption scheme homomorphic for NC 1 (which suffices for the construction) can be constructed from the DDH assumption.

Overview of the dpIO-Based Construction

At an intuitive level, our construction of spooky encryption from dpiO mimics the piO-based construction of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], in the same way that our construction of LHE from dpiO in the previous section follows the same path as the piO-based construction of LHE from [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. However, this strategy faces a number of technical challenges. Below, we provide a high level overview of our construction, the challenges which must be overcome, and our solutions.

Overview. The construction of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] proceeds in two steps: first, it constructs a two-key spooky encryption scheme for bit inputs that supports evaluation of spooky multiplication. This evaluation procedure is performed by an obfuscated circuit. Second, it enhances this two-key spooky encryption scheme into a scheme that supports d hops of (interleaved) two-key spooky multiplications, and single-key homomorphic addition (for any polynomial d(λ)). This second step is done by applying Canetti et al's piO-based transformation of an encryption scheme into a d-leveled encryption scheme [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]. Eventually, the authors observed that a scheme that supports both single key homomorphic addition and two-key spooky multiplication leads to a leveled AFS-spooky encryption scheme for all circuits, drawing upon an elegant connection to the GMW protocol for multiparty computation.

We therefore start by building a dpiO-based two-key spooky encryption scheme for bit inputs and evaluation of spooky multiplication. The inputs to the obfuscated evaluation circuit P are tuples of the form (pk 1 , pk 2 , c 1 , pk, c), where pk 1 , pk 2 , pk are public keys, c 1 is a ciphertext under pk 1 , and c is a ciphertext under pk. P will decrypt c 1 with sk 1 to some x, encrypt with pk 2 a plaintext computed from x, and homomorphically evaluate (using pk) the corresponding second part of the M -spooky evaluation on c. Toward obfuscating P with a dpiO scheme, we define a sampler with input S which has five possible states. With the first four states, it generates the appropriate input (pk 1 , pk 2 , c 1 , pk, c) for P . With the last state, it generates the output of P . Note that unlike in the LHE construction of the previous section, S must be stateful to allow for sampling, e.g., c 1 as a fresh ciphertext under the public key pk 1 , which is itself sampled with S.

While this would suffice to construct a dpiO-based two-key M -spooky encryption scheme, we cannot apply the second step of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] to transform it into an n-key spooky encryption scheme for all circuits. Indeed, the transformation requires to enhance the M -spooky scheme into a leveled-homomorphic M -spooky scheme. It was done in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] using the piO-based approach of [START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF]; here, we would like to follow the same approach, but using our dpiO-based construction of LHE from the previous section. However, for this to work, we need to ensure that all inputs to the (dpiO-obfuscated) leveled homomorphic evaluation circuits are appropriately authenticated samples from the encryption algorithm (with respect to some hardcoded public key). This is not the case, as ciphertexts obtained by evaluating P are not distributed as fresh ciphertexts. To overcome this issue, we therefore add to the public key of our two-key scheme a dpiO-obfuscated circuit that performs a re-encryption procedure. More precisely, it takes all the inputs of P , plus the output of P , and checks that they were correctly constructed as samples with S. Then, it decrypts the outputs of P , and re-encrypt them freshly.

With this last modification, the outputs of a spooky evaluation procedure are generated as fresh ciphertexts and authenticated as such. By replacing the encryption scheme E in the LHE construction of the previous section with our two-key M -spooky encryption scheme, the correctness argument follows as before and we get a 2-key M -spooky encryption scheme that supports leveled (single-key) homomorphic evaluation. We can therefore invoke Theorem 9 from [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], which states that such a scheme directly implies an n-spooky encryption scheme for all circuits.

Two-Key Spooky Encryption for Bit-Inputs

We proceed with a construction of a two-key M -spooky encryption scheme for bit-inputs.

Sampler with Input for Spooky Encryption. Let E = (E.KeyGen, E.Enc, E.Dec, E.Eval) be a maliciously circuit-private homomorphic encryption scheme for NC 1 . Fix any security parameter λ ∈ N. Let T λ ← [3] × ({0, 1} λ ∪ {⊥}) 3 . We denote by st λ : ({0, 1} λ ∪ {⊥}) 5 → T λ the following state function:

on input (y 1 , ⊥, ⊥, ⊥, ⊥) with any y 1 ∈ {0, 1} λ ∪ {⊥}, st λ output (1, ⊥, ⊥, ⊥); on input (y 1 , y 2 , ⊥, ⊥, ⊥) with y 2 = ⊥, st λ output (2, y 1 , ⊥, ⊥); on input (y 1 , y 2 , y 3 , ⊥, ⊥) with y 3 = ⊥, st λ output (1, ⊥, ⊥, ⊥); on input (y 1 , y 2 , y 3 , y 4 , ⊥) with y 4 = ⊥, st λ output (2, y 4 , ⊥, ⊥); on input (y 1 , y 2 , y 3 , y 4 , y 5 ) with y 4 = ⊥, st λ output (3, y 2 , y 4 , y 5 ).

We now describe the sampler with input S, with input domain T λ × {0, 1}. On input (state, x), S parses state as (i, y, y , y ), and does the following:

if i = 1, run (pk, sk) $ ← E.KeyGen(1 λ ), and output (pk; sk).

if i = 2, run c $ ← E.Enc(y, x), and output (c; ⊥); if i = 3, pick random coins (r, r , r 1 ), define M [x, r, r ](•) ≡ RS M (x, •, M (x, 0; r) 1 ; r ), set c 1 ← E.Enc(y, M (x, 0; r) 1 ; r 1 ) and c 2 ← E.Eval(y , M [x, r, r ], y ), and output ((c 1 , c 2 ); ⊥). Description of the Scheme. Let SI = {SI λ } λ∈N be the family of samplers with input as defined in the previous paragraph, with input domain T λ × {0, 1}, where each SI λ contains a single sampler with input S, with state function st λ . Let (Setup, Encode, Obfuscate) be a 5-source dpiO scheme for (st λ , SI, C, CS), where C contains all circuits of the following form:

the programs P [sk 1 , pk 1 , pk 2 , pp 2 , S] represented on Figure 11 for all strings (sk 1 , pk 1 , pk 2 , pp 2 ); the programs Q j [sk 3-j , pk 3 , pp 3 , S] represented on Figure 11 for all strings (sk 3-j , pk 3 , pp 3 ) for j = 1, 2; the programs P [pk 1 , pk 2 , pp 2 , trap 2 , S] represented on Figure 13 for all strings (pk 1 , pk 2 , pp 2 , trap 2 ); the programs Qj [pk 3 , pp 3 , S, trap 3 ] represented on Figure 12 for all strings for j = 1, 2, and the circuit sampler CS randomly samples keys (sk i , pk i ) sampled with S 1 ((1, ⊥, ⊥, ⊥), 0), public parameters pp 2 , pp 3 with Setup (or with the simulator algorithm for the Setup when it must generate (pp 2 , trap 2 ) or (pp 3 , trap 3 )), and outputs either (C 0 , C 1 , z) = (P [sk 1 , pk 1 , pk 2 , pp 2 , S], P [pk 1 , pk 2 , pp 2 , trap 2 , S], (pk 1 , pk 2 , pp 2 )) or (C 0 , C 1 , z) = (Q j [sk 3-j , pk 3 , pp 3 , S], Qj [pk 3 , pp 3 , S, trap 3 ], (pk 3 , pp 3 )) for j = 1 or j = 2. We will prove that this circuit sampler outputs pairs of circuits satisfying dynamic-input indistinguishability in the security analysis of our protocol. We represent on Figure 11 our construction of a two-key M -spooky encryption scheme for bit inputs.

Theorem 25. Let dpiO be a 5-source dpIO scheme for (st, SI, C, CS), and let E be an IND-CPA-secure circuit-private (non-compact) homomorphic encryption scheme for one-bit functions. Then SE defined in Figure 11 is a two-key M -spooky encryption scheme for bit inputs.

spooky evaluation procedure at level i are encrypted under pk 3i , but given an encryption of x under pk 3i , one can always encrypt 0 under pk 3i and homomorphically XOR x with 0, obtaining an encryption of x under the key pk 3i+1 .

From there, we can invoke Theorem 9 of [DHRW16]:

Theorem 28 (2-Spooky to n-Spooky [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]). Let d = d(λ) and assume that there exists a publickey bit encryption cheme that supports 2d (interleaving) hops of (1) single-key compact additive homomorphism and (2) two-key spooky multiplication. Then, that same scheme is a d-level AFS-spooky encryption for all circuits.

The proof of Theorem 9 can be found in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]. It follows from an elegant connection with the GMW protocol: it evaluates an arbitrary circuit gate by gate, given n encrypted shares under n different public keys (pk 1 , . . . , pk n ) of the value on a gate. If the gate is a XOR, it performs an homomorphic XOR operations on each pair of shares encrypted with the same public key. If its an AND gate, it performs a two-key spooky multiplication for each pair of public keys, between the shares encrypted under these two keys, obtaining shares of the products. Then, it homomorphically XOR all outputs which are encrypted under the same public keys (if there are n keys, this requires log n levels of 2-input homomorphic XOR). It follows by inspection that the resulting n ciphertexts encrypt additive shares of the output of the gate, under the n different public keys (pk 1 , . . . , pk n ).

Using our construction of a dpiO scheme (Corollary 14) together with Theorem 28, we obtain:

Theorem 29. Assuming polynomially-secure indistinguishability obfuscation and eDDH, there exists an n-key spooky encryption scheme for all circuits.

As observed in [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], this implies a de-centralized function secret sharing scheme for all circuits, and a counter-example to the [ABOR00] heuristics (which transforms multi-prover protocols to single-prover protocols), under the same assumptions.

$←Fig. 1 .

 1 Fig. 1. Experiment Exp-d-Ind for the indistinguishability property of dynamic-input samplers.

Fig. 2 .

 2 Fig. 2. Selective security game for puncturable pseudorandom functions.

←Fig. 3 .

 3 Fig. 3. Experiments Exp 0-enc A (1 λ ) and Exp 1-enc A (1 λ ) for the simulatability of encodings in an -source dpiO. The PPT algorithm A can interact polynomially many times with either O enc 0 [pp] or O enc 1 [pp, trap]. A wins the experiment when it outputs b = b in Exp b-enc A (1 λ ) application might define an arbitrary communication pattern, and specifies which samples a party should have access to when generating his sample.Additionally, we admit the possibility that a sampler produces some additional correlated output, that will not serve as input to an obfuscated circuit. Hence, there is no need to "certify" this input using the auxiliary information, and we call this output unauthenticated output. Continuing the use case from above, given a sampler producing some public key, the unauthenticated part of that sampler's output could be a corresponding secret key.

←Fig. 4 .

 4 Fig. 4. Experiments Exp 0-rcorr A (1 λ ) and Exp 1-rcorr A (1 λ ) for the restricted correctness property an -source dpiO. A wins the experiment when it outputs b = b in Exp b-rcorr A (1 λ ) when b $ ← {0, 1}.

←Fig. 5 .

 5 Fig. 5. Experiment Exp b-ind A (1 λ ) for the indistinguishability with respect to CS in an -source dpiO. The PPT algorithm A can interact polynomially many times with O ind b [pp, D λ ]. The oracle O ind b [pp, D λ ] is stateful and has (pp, D λ ) hardcoded in its description. A wins the experiment when it outputs b = b in Exp b-ind A (1 λ ) when b $ ← {0, 1}.

←$←Fig. 6 .

 6 Fig. 6. Construction of -source dpIO scheme dpiO = (Setup, Encode, Obfuscate).

Game G 0 .

 0 In this game, the challenger samples b $ ← {0, 1}, and sets up the experiment Exp b-ind A (1 λ ). More precisely, A has access to the public parameters pp and an oracle O ind b [pp, D λ ], that on input of a sampler with input S, draws a sample (C 0 , C 1 , z) from D and outputs (C 0 , C 1 , z) together with an obfuscation Obfuscate(pp, S, C b ). A outputs a guess b and the challenger returns 1 if b = b. By assumption, Pr[out 0 = 1] = ε.

Fig. 7 .

 7 Fig. 7. Definition of the circuit C .

  Fig. 9. Description of the LHE scheme LHE. The circuit C is defined in Figure 10.

Fig. 10 .

 10 Fig. 10. Definition of the circuits C and tC. Before we start the analysis of our construction, we briefly recall the definition of an IND-CPA secure public-key encryption scheme. Definition 17 (Public-key bit-encryption scheme). A public-key bit-encryption scheme is a triple of PPT algorithms E = (E.KeyGen, E.Enc, E.Dec) that satisfies the following properties: Perfect correctness. E is perfectly correct, if for every λ ∈ N and every message m ∈ {0, 1} Pr[E.Dec(sk, E.Enc(pk, m)) = m|(pk, sk) $ ← E.KeyGen(1 λ )] = 1. IND-CPA security. We say that E is IND-CPA secure if for every PPT adversary A, the advantage Adv IND-CPA (A) := | Pr [A(pk, LHE.Enc(pk, 0))] -Pr [A(pk, LHE.Enc(pk, 1))]| is negligible in λ, where (pk, sk) ← E.KeyGen(1 λ ).

That means that our final schemes depend on ELFs, which are currently only known to be instantiable from exponential assumptions. However, we stress that ELFs can be built from exponential variants of very standard assumptions, such as the decisional Diffie-Hellman (DDH) assumption.

For example, if a protocol relies on the subexponential hardness of LWE with exponential modulus-to-noise ratio, it would be desirable to achieve the same while relying only on polynomially secure LWE, even if the modulus-to-noise ratio remains exponential.

This is of course an oversimplification. Also,[START_REF] Canetti | Obfuscation of Probabilistic Circuits and Applications[END_REF] define several types of piO security that provide a tradeoff between security and achievability.

Again, we are not very specific about the form of desired or assumed security. However, we believe that for this exposition, these specifics do not matter.

Looking ahead, this "certificate" will be implemented using a NIZK in our construction.

That is, for any statement x ∈ L, the probability Prcrs[∃π : NIZK.Verify(crs, x, π) = 1] ≤ 2 -λ-n .

We note that the output domain of such samplers can be of exponential size.

We remark that the values of each set Bj can be computed efficiently by evaluating S on all possible inputs from I × ( j-1 k=1 Bj) and all possible images in the range of G. Furthermore, it is possible to enumerate the image of G in polynomial time because G is strongly regular.

We implicitly use that the scopes of S (⊥, 0) and S (⊥, 1) are disjoint.

Our construction from Section 4 even guarantees perfect correctness.

homomorphic evaluation of XOR gate is sufficient for the transformation of[START_REF] Dodis | Spooky Encryption and Its Applications[END_REF].

Acknowledgments

We would like to thank the anonymous reviewers for many helpful comments.

Supported by ERC Project PREP-CRYPTO 724307.

Circuit C [stf, (crs, G), S, C0, C1, K{γi}, Y, γi](x) parse x =: ((y1, aux1), . . . , (y , aux )) statej := stf(y1, . . . , yj-1, ⊥, . . . , ⊥) if ¬ (∀j ∈ [ ] : NIZK.Verify(crs, (G, S, statej, yj), auxj) = 1) then return ⊥ γ := (y1, . . . , y ) if γ < γi then r := F (K{γi}, γ); return C1(γ; r) if γ = γi then return Y if γ > γi then r := F (K{γi}, γ); return Cb(γ; r) Game G 1.q.i.3 . Game G 1.q.i.3 is the same as G 1.q.i.2 except for the fact that Y is produced using the circuit C q,1 , i.e. Y := C q,1 (γ q,i ; R). This game hop is justified by the fact that the circuit sampler D λ is a dynamic-input indistinguishable sampler. Game G 1.q.i.4 . This game is the same as G 1.q.i.3 with the difference that we again use pseudorandom coins to compute Y , i.e. Y := C q,1 (γ q,i ; F (K q , γ q,i )). For every PPT adversary A there exists a PPT adversary B such that |Pr[out 1.q.i.3 = 1] -Pr[out 1.q.i.4 = 1]| ≤ Adv s-cPRF (B). As the pPRF F preserves functionality under punctured keys, the two circuits C [stf, (crs, G), S q , C q,0 , C q,1 , K q {γ q,i }, Y := C q,1 (γ q,i ; F (K q , γ q,i )), γ q,i ] and C [stf, (crs, G), S q , C q,0 , C q,1 , K q , γ q,i+1 ] are functionally equivalent. Therefore, we have that |Pr[out 1.q.i.4 = 1] -Pr[out 1.q.i+1 = 1]| ≤ Adv iO (B).

Summing up, the advantage to distinguish G 1 and G 1.Q is bounded by |I| • t 2 • negl(λ). As is constant and |I|, t are polynomial, this quantity is negligible. As the circuit obfuscated in G 1.Q is now functionally equivalent to the circuit obfuscated in G 1 1 , the game hop to G 1 is justified by the indistinguishability property of iO. More formally there exists a PPT adversary B such that |Pr[out 1.Q = 1] -Pr[out 1 ] = 1| ≤ Adv iO B (λ). This implies that the advantage of A in game G 1 is lower bounded by ε/2 -negl(λ), which is non-negligible. However, the view of A in G 1 is perfectly independent of b, hence its advantage in this game cannot be non-zero; therefore, we reach a contradiction, which concludes the proof.

Extension

We sketch a straightforward extension of our above construction. It follows easily by inspection that the same proof strategy would work even if the sources, which sample inputs accorded to an encoding of a sampler S with respect to public parameters pp, are not required anymore to use the same public parameters. The sources could even each use different public parameters (pp 1 , . . . , pp ). The modified proof for this scenario would proceed by first switching the ELFs in (pp 1 , . . . , pp ) to an extremely-lossy mode, through a sequence of hybrids. Each extremely-lossy mode is chosen so that A as advantage at most ε/2 in distinguishing it from the injective mode. By a union bound, A has therefore advantage at most ε/2 in distinguishing the all-injective modes from the all-lossy modes. Then, enumerating over all possible valid inputs to an obfuscated circuit takes polynomial time as before, as each input of a source comes from a set of polynomial size. Therefore, the exact same sequence of hybrids proves security, with a polynomial loss in the underlying primitives. To adapt the security properties of our definition of dpiO to this multi-parameter setting, it suffices to let all experiments initially sample and send to the adversary public parameters (pp 1 , . . . , pp ) instead of one. In the simulatability of encodings definition (resp. in the indistinguishability definition), the adversary is allowed to specify under which public parameters it wants to receive a (real or simulated) sample (y, aux; y ) (resp. under which public parameters it wants C b to be obfuscated in the indistinguishability experiment).

It can prove convenient to simplify the construction in some applications to allow different sources to use different public parameters. Let us illustrate the syntax we adopt on an example: if (Setup, Encode, Obfuscate) is a 5-source dpiO scheme, we denote by Obfuscate(pp 1 [1 -3], pp 2 [4, 5], , S, C) an obfuscation of a circuit C, whose first three inputs should be sampled with respect to pp 1 , and whose last two inputs should be sampled with respect to pp 2 . We will also sometimes slightly abuse our notation, noting that an -source dpiO scheme directly implies an i-source dpiO scheme for i ≤ , and allow an -source scheme to obfuscate a circuit C that takes i < inputs.

Security. To prove that LHE is IND-CPA secure, we proceed over a series of hybrids. Let A be a PPT adversary. Game G b 0 . This game is exactly the IND-CPA game for LHE, where the challenge ciphertext c * contains the bit b.

Game G b

1 . This game is the same as G b 0 with the difference that the evaluation key consists of obfuscations tΛ i of the circuit tC[S pk i ]. Claim. For every PPT adversary A, we have that |Pr

for some negligible function negl. Proof. We define a series of L + 1 hybrid games G b 0.i for i ∈ {0, . . . , L} as follows: Game G b 0.i . This game is identical to G b 0.i-1 with the difference that we replace the obfuscated circuit Λ L-i+1 with the obfuscation tΛ L-i+1 := Obfuscate(pp L-i , S pk L-i , tC[pk L-i+1 ]). Hence, in G b 0.i the evaluation key ek has the form ek := (Λ 1 , . . . , Λ L-i , tΛ L-i+1 , . . . , tΛ L ) .

We

Let D be a circuit sampler, that samples public parameters pp $ ← Setup(1 λ ) and two public key pairs (pk, sk), (pk , sk ) $ ← E.KeyGen(1 λ ), produces the encoded sampler S pk ← Encode(pp, S pk ) and outputs the circuits C 0 := C[S pk , sk ] and C 1 := tC[S pk ] together with its state z := (pk, pk , sk , pp). Claim. The circuit sampler D as defined above is a dynamic-input indistinguishable sampler. Proof. We prove this using two hybrids. Let A be an adversary for the dynamic-input indistinguishability game for the circuit sampler D. Game H 0 . This is the dynamic-input indistinguishability game as defined in Figure 1. In detail, given the descriptions of the sampled circuits C 0 and C 1 together with the state z, A chooses an input x (dynamically). Game H 0 evaluates the circuit C b (for a random bit b) at x using fresh random coins and sends the output to A. Game H 1 . By the simulatability of encodings property of dpiO, there exists a simulator Sim = (Sim 0 , Sim 1 ). Game H 1 is the same as H 0 with the difference that the public parameters are sampled as (pp, trap)

Given the input x = (y 1 , y 2 ) for the circuits, compute (m 0 , m 1 ) := (α ∧ β, 0) using the secret key sk . Furthermore, instead of evaluating C b at x honestly, game H 1 produces (y, •) $ ← S pk (⊥, m b ) and aux $ ← Sim 1 (trap, S pk , y, ⊥). Due to the simulatability of encodings, the difference |Pr[out H0 = 1] -Pr[out H1 = 1]| between these two games is negligible. The advantage of A in game H 1 is negligible. To realize that, we construct an adversary B on the IND-CPA security of E with respect to the public key pk. On input of pk, B samples (C 0 , C 1 , z) in the same way as in H 1 (embedding pk) and calls A on input of (C 0 , C 1 , z) to obtain (x, state). B decrypts x = (y 1 , y 2 ) to obtain α, β using sk , and outputs (m 0 , m 1 ) := (α ∧ β, 0) to the IND-CPA game. In return B receives a ciphertext c * , simulates the corresponding auxiliary information aux $ ← Sim 1 (pp, trap, S pk , c * , ⊥), and invokes A on input of its previous state state and

In order to upper bound the distinguishing gap between G 0.i and G 0.i+1 , we construct a PPT adversary B on the indistinguishability property of dpiO. B gets as input public parameters pp , the circuits C 0 , C 1 together with auxiliary information z produced by D, and an obfuscation Λ $ ← Obfuscate(pp , S pk , C b) for some b ∈ {0, 1}. Initially, B samples parameters as LHE.KeyGen embedding its input as pp L-i-1 := pp , pk L-i-1 := pk , and pk L-i := pk, and defines the public key to be pk := S pk 0 for S pk 0 ← Encode(pp 0 , S pk ). B produces the obfuscations Plugging in our construction of dpiO of the previous section, and the DDH-based construction of a circuit-private encryption scheme [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF], we get the following corollary:

Corollary 26. Assuming polynomially-secure indistinguishability obfuscation and eDDH, there exists a two-key M -spooky encryption scheme for bit inputs.

Proof. We first show that the scheme SE is complete and M -spooky. Consider the following simplification of the scheme of the Figure 11: the algorithm SE.Setup is removed, all invocations of (S 1 , S 2 , S 3 ) are replaced by invocations of S (hence all auxiliary values are removed), the obfuscated programs Q1 , Q2 are removed (and SE.Eval outputs ((2, c 1 ), (1, c 2 )) directly), and the program P is obfuscated using a standard piO scheme. The new scheme SE obtained this way is exactly the piO-based spooky encryption scheme of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]; we refer the reader to [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] for a thorough analysis of its properties.

Here, we focus on showing that our modifications do not alter the completeness and M -spooky properties. Let us first show completeness of the encryption and decryption algorithms. Let x ∈ {0, 1}. Let crs $ ← SE.Setup(1 λ ). For any j ∈ {1, 3}, let (pk j , aux j ; sk j ) $ ← S j ((1, ⊥, ⊥, ⊥), 0), let (c, aux) $ ← S j ((2, pk j , ⊥, ⊥), x) and let x ← E.Dec(sk j , c). It necessarily holds that x = x: otherwise, this would distinguish the output distribution of S j from the output distribution of S (as S((1, ⊥, ⊥, ⊥), 0) outputs a random key pair (pk, sk) for E, and S((2, pk, ⊥, ⊥), x) outputs a random encryption of x under E).

It remains to show the correctness of the spooky evaluation procedure. First, we show that the outputs (c 1 , c 2 ) of P 0 are encryptions (under pk 0 2 and pk 1 1 respectively) of the spooky evaluation of M on the plaintexts of (c 0 , c 1 ). Observe that the inputs to P 0 satisfy the requirements of the statistical restricted correctness of the dpiO scheme. It follows immediatly from the definition of SE.KeyGen and SE.Enc that the inputs (pk 0 1 , pk 0 2 , c 0 , pk 1 1 , c 1 ) are appropriately authenticated inputs sampled using S 1 = Encode(pp 1 , S), with the appropriate auxiliary inputs, with respective states

Therefore, by the restricted correctness of dpiO, the correctness analysis of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF] applies and allows to conclude that (c 1 , c 2 ) of P 0 are encryptions (under pk 0 2 and pk 1 1 respectively) of the spooky evaluation of M on the plaintexts of (c 0 , c 1 ). We now argue that the outputs c 1 and c 2 are encryptions (under pk 0 3 and pk 1 3 respectively) of the spooky evaluation of M on the plaintexts of (c 0 , c 1 ). As Q 1 and Q 2 do only perform decryption (of c 1 and c 2 respectively) and re-encryption with pk 3 , it suffices to show that the inpus to ( Q1 , Q2 ) satisfy the requirements of the statistical restricted correctness of the dpiO scheme. This follows immediatly by our previous observation that the inputs (pk 0 1 , pk 0 2 , c 0 , pk 1 1 , c 1 ) are appropriately P [sk1, pk 1 , pk 2 , pp 2 , S](y1, y2, c1, y, c)

Qj[sk3-j, pk 3 , pp 3 , S](y1, y2, c1, y, c, (c 1 , c 2 ))

parse crs as (pp 1 , pp 2 , pp 3 ) for j ∈ {1, 3}, Sj ← Encode(pp j , S)

pk ← (pk 1 , aux1, pk 2 , aux2, pk 3 , aux3, P , Q1, Q2) return (pk, sk) SE.Enc(crs, pk, x)

parse crs as (pp 1 , pp 2 , pp 3 ), and parse pk as (pk 1 , aux1, pk 2 , aux2, pk 3 , aux3, P , Q1, Q2)

return (1, c, aux) SE.Dec((sk1, sk2, sk3), i, c) return E.Dec(ski, c) SE.Eval(pk 0 , c 0 , aux 0 , pk 1 , c 1 , aux 1 ) parse pk 0 as (pk 0 1 , aux 0 1 , pk 0 2 , aux 0 2 , pk 0 3 , aux 0 3 , P 0 , Q1 0 , Q2 0 )

Fig. 11. dpiO-based construction of a two-key M -spooky encryption scheme for bit inputs. authenticated inputs sampled using S 1 = Encode(pp 1 , S), with the appropriate auxiliary inputs, and by observing that (c 1 , c 2 ) are appropriately authenticated inputs sampled using S 2 = Encode(pp, 2), with state Game G 1 : In this game, we use the simulatability of encodings property of the dpiO scheme. Let Sim = (Sim 0 , Sim 1 ) be the simulator whose existence is guaranteed by Definition 10. The challenger computes (pp 1 , trap 1 )

and sends crs ← (pp 1 , pp 2 , pp 3 ). It computes (pk, c) as before. This game is indistinguishable from the previous one, by the simulatability of encodings property of the dpiO scheme. Game G 2 : In this game, we modify the generation of pk by the challenger. We divide this game into two successive hybrids, for j = 1 and j = 2, where the challenger generates pk as follows: instead of building Qj as Obfuscate(pp 1 [1 -5], pp 2 [6], S, Q j [sk 3-j , pk 3 , pp 3 , S]) in SE.KeyGen(crs), the challenger sets Qj ← Obfuscate(pp 1 [1 -5], pp 2 [6], S, Qj [pk 3 , pp 3 , trap 3 , S]) instead, with the program Qj represented on Figure 12. The indistinguishability argument proceeds by showing that Q j and Qj are dynamic-input indistinguishable. The argument proceeds in 4 steps.

1. Consider the program Q 0 j represented on Figure 12. Its only difference with Q j is that it generates c j through S instead of S 3 , and generate the auxiliary input using Sim 1 . By the simulatability of encodings property of the dpiO scheme, the output distribution of Q j and Q 0 j are computationally indistinguishable (even on adversarially chosen inputs), hence Q j and Q 0 j are dynamic-input indistinguishable. 2. Consider the program Q 1 j represented on Figure 12. By definition of S, c j is now a uniformly random encryption (with E) of 0 under the key pk 3 . Note that the corresponding secret key sk 3 is not used in any program. Therefore, under the IND-CPA security property of E, Q 1 j is dynamic-input indistinguishable from Q 0 j . 3. Consider the program Q 2 j represented on Figure 12. It is identical to Q 1 j , except that it does not have sk 3-j hardcoded in its description anymore (note that Q 1 j does not use this hardcoded key). Therefore, Q 1 j and Q 2 j are functionally equivalent. 4. Observe now that the only difference between Q 2 j and Qj , represented on Figure 12, is that Qj generates (c j , aux) using S 3 , while Q 2 j uses S and Sim 1 . Therefore, by the simulatability of encodings property of the dpiO scheme, Q 2 j and Qj are dynamic-input indistinguishable. From there, the indistinguishability property of the dpiO scheme allows to conclude that the obfuscation of Q j and the obfuscation of Qj are computationally indistinguishable, hence this game is indistinguishable from the previous one.

)

) Game G 3 : In this game, we further modify the generation of pk by the challenger. Instead of generating P as Obfuscate(pp 1 , S, P [sk 1 , pk 1 , pk 2 , pp 2 , S]), the challenger sets P ← Obfuscate(pp 1 , S, P [pk 1 , pk 2 , pp 2 , trap 2 , S]) instead, with the program P represented on Figure 13. The proof proceeds by showing that P and P are dynamic-input indistinguishable. This is done in the same way as in the previous game, by exhibiting a sequence of programs P, P 0 , P 1 , P 2 2, P which are all dynamic-input indistinguishable. The programs are represented on Figure 13. Indistinguishability between P and P 0 follows by the same argument as in step 1 of the previous game. P 1 is constructed by replacing all occurences of x 1 by 0 in P 0 .

Lemma 27. The circuits P 0 and P 1 are dynamic-input indistinguishable.

Proof. The indistinguishability argument is essentially identical to the proof of the claim 4.10.3 of [START_REF] Dodis | Spooky Encryption and Its Applications[END_REF]. We recall it briefly for the sake of completeness. Observe that in P 0 , c 1 is distributed as a random encryption of x 1 , and c 2 is the output of an homomorphic evaluation on c. We consider an intermediate programs P 0.1 . Tt proceeds as P 0 , except that it uses instead of S a sampler S 0.1 which, on input the state (3, y 2 , y, c) and x 1 , samples the output c 1 as a random encryption of 0 instead (it proceeds as S otherwise). Note that the encryption of c 1 is under pk 2 , whose corresponding secrey key is not known to the program. Therefore, under the IND-CPA-security property of E, P 0.1 is dynamic-input indistinguishable from P 0 . Now, the only difference between P 0.1 and P 1 is that c 2 is obtained by homomorphically evaluating M [x 1 , r, r ] on c in P 0.1 , and M [0, r, r ] on c in P 1 . By the malicious circuit privacy of E, c 2 is therefore distributed as an encryption with fresh random coin (of some plaintext under pk) in both P 0.1 and P 1 . Therefore, by the IND-CPA-security property of E, P 0.1 and P 1 are dynamic-input indistinguishable.

Then, the circuit P 2 represented on Figure 13 is obtained by not harcoding sk 1 in P 1 anymore; as in step 3 of the previous game, P 2 is functionally equivalent to P 1 . Eventually, P 2 and P are dynamic-input indistinguishable by the simulatability of encodings property of the dpiO scheme, using the same argument as step 4 of the previous game. From there, the indistinguishability property of the dpiO scheme allows to conclude that the obfuscation of P and the obfuscation of P are computationally indistinguishable, hence this game is indistinguishable from the previous one.

P 0 [sk1, pk 1 , pk 2 , pp 2 , trap 2 , S](y1, y2, c1, y, c) . By definition of SE.Enc, c is now computed as (c, aux) ← S 1 ((2, pk 1 ), x), with x = b in the previous game, and x = 0 in this game. By definition of S, it follows that c is a random encryption under E of x, with key pk 1 . Observe that the key sk 1 is not hardcoded anymore in any of the obfuscated circuits of the public key pk. Therefore, this game is indistinguishable from the previous game under the IND-CPA security property of E. Observe now that in the current game, the output of the challenger does not depend on b anymore, hence the advantage of A in this game is 0. This concludes the proof that (SE.Setup, SE.KeyGen, SE.Enc, SE.Dec) is an IND-CPA-secure bit encryption scheme.

6.4 From Two-Key M -Spooky Encryption to n-Key Spooky Encryption for all Circuits By plugging our construction of two-key M -spooky encryption scheme in the transformation of the previous section, we obtain a two-key M -spooky and (single-key) leveled homomorphic encryption scheme. More precisely, let us sketch how to integrate our scheme to the LHE construction of the previous section. Our two-key M -spooky scheme SE requires three public keys of E, (pk 1 , pk 2 , pk 3 ). Fresh ciphertexts are samples with S corresponding to encryptions with E under pk 1 , and outputs of a spooky-evaluation are samples with S corresponding to encryptions with E under pk 3 . To simplify the integration, we add to the public key of SE an (obfuscated) re-encryption circuit, which takes fresh ciphertexts under pk 1 as input (sampled with S), performs decryption with sk 1 , and outputs fresh re-encryption with E sampled with S under pk 3 .

The obfuscated circuit for homomorphic operations takes as input two ciphertexts under pk 3 (sampled with S), decrypts them with sk 3 , computes a XOR gate, 15 and re-encrypts the result under a new key pk 4 . We can generalize this to d levels of interleaved two-key spooky evaluations and single-key homomorphic evaluations by using 3d public keys for E. The computation at each level i will output the result of either a spooky evaluation or an homomorphic evaluation, under the public key pk 3i+1 . Note that the output of a