A Research Analysis of Leveled Fully Homomorphic Encryption from Bootstrappable Encryption Generically

Prof.Dr.G.Manoj Someswar 1,  D.Narasimha Raju2

1.Research Supervisor, Dr.APJ Abdul Kalam Technical University, Lucknow,U.P., India
2.Research scholar,  Dr.APJ Abdul Kalam Technical University, Lucknow,U.P., India

Abstract

We propose the principal completely homomorphic encryption plot, tackling a focal open issue in cryptography. Such a plan enables one to figure subjective capacities over encoded information without the decoding key { i.e., given encryptions E(m1); : ; E(mt) of m1; : ; mt, one can proficiently process a smaller cipher text that scrambles f(m1; : ; mt) for any effectively calculable capacity f. This issue was postured by Rivest et al. in 1978.

Completely homomorphic encryption has various applications. For instance, it empowers private inquiries to an internet searcher { the client presents a scrambled inquiry and the web index figures a concise encoded reply while never taking a gander at the question free. It additionally empowers looking on encoded information { a client stores scrambled files on a remote file server and can later have the server recover just files that (when decoded) fulfil some boolean requirement, despite the fact that the server can't unscramble the files all alone. All the more comprehensively, completely homomorphic encryption enhances the efficiency of secure multiparty calculation.

Our development starts with a to some degree homomorphic boost rappable" encryption plot that works when the capacity f is the plan's own unscrambling capacity. We at that point demonstrate how, through recursive self-implanting, boots trappable encryption gives completely homomorphic encryption. The development makes utilization of difficult issues on perfect cross sections.

Keywords: Security of the Abstract Scheme, Bootstrappable Encryption, Computational Complexity and Security, KDM-Secure Boots trappable Encryption, The Ideal Coset

INTRODUCTION

Bootstrappable  Encryption

Assume we have an encryption scheme Ethat compactly evaluates some set of circuits CE. We want to useE to construct a homomorphic encryption scheme that can handle arbitrary circuits. In this Chapter we prove a fundamental result: that if CEcontains (slight augmentations of) E's own decryption circuit DE { i.e., if E compactly evaluates" its (augmented) decryption circuit { then we can use E to construct an efficient scheme that handles circuits of arbitrary depth.

A bit more specifically, for any integer d, we use E to construct a scheme E(d) that can compactly evaluate circuits of depth up to d. The decryption circuit for E(d) is still DE; the secret key and ciphertexts are the same size as in E. The public key in E(d) consists of d + 1 public keys from E, together with a chain of encrypted E secret keys { the first E secret key encrypted under the second E public key, and so on. In short, the family of schemes fE(d) g is leveled fully homomorphic. We base the semantic security of E(d) on that of Eusing a hybrid argument; as usual with hybrid arguments, the reduction loses a factor linear in d. In Chapter 4.3, we describe how one can obtain a fully homomorphic encryption scheme (where the public key size does not depend on the maximum number of levels we want to evaluate) by assuming key-dependent-message (KDM) security, specifically circular-security { i.e., that one can safely encrypt a E secret key under its associated public key.

Since this critical property of E{ that it can compactly evaluate (slight augmentations of) its own decryption circuit { is self-referential and universal, we give it the obvious name: bootstrappability. Why should bootstrappability be such a powerful feature? At a high level, the reason is that bootstrappability allows us periodically to refresh" ciphertexts associated to interior nodes in a circuit; we can refresh for an arbitrary number of levels in the circuit, and thus can evaluate circuits of arbitrary depth. To refresh" a ciphertext that encrypts a plaintext ¼ under E public key pki, we re-encryptit under pki+1and then homomorphically apply the decryption circuit to the result, using the secret key ski that is encrypted under pki+1, thereby obtaining an encryption of ¼under pki+1. Homomorphically evaluating the decryption circuit decrypts the inner ciphertext under pki, but within homomorphic encryption under pki+1. The implicit decryption refreshes" the ciphertext, but the plaintext is never revealed; the plaintext is always covered by at least one layer of encryption. Now that the ciphertext is refreshed, we can continue" correctly evaluating the circuit.[1]

To see how this works mathematically, begin by considering the following algorithm, called Recrypt. For simplicity, suppose the plaintext space P is f0; 1gand DE is a boolean circuit in CE. Let (sk1; pk1) and (sk2; pk2) be two E key-pairs. Let Ã1 be an encryption of 1/4 2 P under pk1. Let sk1j be an encryption of the j-th bit of the first secret key sk1under the second public key pk2. Recrypt takes as these things as input, and outputs an encryption of ¼under pk2.

Recrypt(pk2; DE; hsk1ji; Ã1).

R
Set Ã1j Ã EncryptE (pk2; Ã1j) where Ã1j is the j-th bit of Ã1Set Ã2 Ã EvaluateE(pk2; DE; hhsk1ji; 1jii) Output Ã2

Above, the Evaluate algorithm takes in all of the bits of sk1and all of the bits of Ã1, each encrypted under pk2. Then, Eis used to evaluate the decryption circuit homomorphically. The output Ã2 is thus an encryption under pk2 of DecryptE(sk1; Ã1) ! ¼.  The Recrypt algorithm implies a proxy one-way re-encryption scheme [19]. Roughly speaking, a one-way proxy re-encryption scheme allows the owner of sk1 to generate a tag that enables an untrusted proxy to convert an encryption of ¼under pk1 to an encryption of ¼under pk2, but not the reverse. In our case, the tag is hsk1ji, the encrypted secret key.[2] Strictly speaking, the security model for proxy re-encryption typically requires the security of the delegator's secret key, even against a collusion of delegatee's who also get to see the delegating tags. However, this requirement seems unnecessary, since a delegatee will be able to decrypt ciphertexts directed to the delegator anyway. In the Recrypt algorithm above, the plaintext ¼ is doubly encrypted at one point { under both pk1 and pk2. Depending on the encryption scheme E, however, this double encryption might be overkill. Suppose WeakEncryptE is an algorithm such that the image of WeakEncryptE(pk; ¼) is always a subset of the image of EncryptE (pk; ¼). Then we can replace the first step of RecryptE with:

R
Set Ã1j Ã WeakEncryptE(pk2; Ã1j) where Ã1j is the j-th bit of Ã1

Let us call this relaxation Recrypt0E. The main point of this relaxation is that WeakEncrypt does not need to be semantically secure for Recrypt0Eto be a secure one-way proxy re-encryption scheme, or for Recrypt0E to be useful toward bootstrapping (as we will see below). Thus, depending on E, WeakEncryptE can be very simple { e.g., for some schemes, and in particular for the ideal-lattice-based scheme that we describe later, WeakEncryptE might leave the input bits" entirely unmodified. This will unfortunately not help us much in terms of making the encryption scheme boots trappable; essentially, it will add one circuit level to what Ecan evaluate. However, it will affect the eventual computational complexity of our scheme, since it will require less computation to apply the decryption circuit homo-morphically to cipher texts in which the outer encryption is weak.[3] Another way of viewing this relaxation is that we only need to be able to evaluate non-uniform decryption circuits, where the ciphertext is hard-wired" into the circuit (making this circuit simpler than the normal" decryption circuit that takes the ciphertext (and secret key) as input.

To be bootstrappable, E needs to be able to compactly evaluate not only its decryption circuit, which merely allows recryptions of the same plaintext, but also slightly augmented versions of it, so that we can perform binary operations on plaintexts and make actual progress through a circuit.

Let DE be E's decryption circuit, which takes a secret key and ciphertext as input, each formatted as an element of P`(¸), where P is the plaintext space. Let ¡ be a set of gates with inputs and output in P, which includes the trivial gate (input and output are the same). We call a circuit composed of multiple copiesof DEconnected by a single g gate (the number of copies equals the number of inputs to g) a g-augmented decryption circuit." We denote the set of g-augmented decryption circuits, g 2 ¡, by DE(¡).

As before, let CEdenote the set of circuits that E can compactly evaluate. We say that E is bootstrappable with respect to ¡ if DE (¡) µ CE :For example, if ¡ includes the trivial gate and NAND, E is bootstrappable with respect to ¡ if CEcontains DE and the circuit formed by joining two copies of DEwith a NAND gate. Remarkably, as we will show, if there is a scheme E that can compactly evaluate only these two circuits, then there is a scheme that is leveled fully homomorphic.[4]

We could relax the bootstrappability definition slightly to say that E only needs to be able to homomorphically evaluate its (augmented) decryption circuit when the input ciphertext is weakly encrypted, similar to the relaxation Recrypt0E above. But, this makes the definition of bootstrappable more cumbersome; we will continue with the definition above, and remind the reader occasionally that the relaxation can be used.

From the informal description above, it should already be somewhat clear how to use a bootstrappable encryption scheme to construct a leveled fully homomorphic one; below, we give a more formal description. Let E be bootstrappable with respect to a set of gates For any integer d ¸ 1, we use E to construct a scheme E(d) = (KeyGenE(d) ; EncryptE(d) ; EvaluateE(d) ; DecryptE(d) ) that can handle all circuits of depth dwith gates in ¡. Note that in the description below we encrypt the secret keys in reverse order; the only reason is that this ordering simplifies our description of the recursion in Evaluate. When we refer to the level of a wire in C, we mean the level of the gate for which the wire is an input. We use the notation DE; ±) to refer to the set of circuits that equal a ±-depth circuit with gates in ¡ augmented by DE(copies of DE become inputs to the ±-depth circuit).

KeyGenE(d) (¸; d). Takes as input a security parameter ¸and a positive integer d. For ‘=’(¸) as  it sets:

 R for i 2 [0; d] (ski; pki) Ã KeyGenE(¸) R ; skij) for i 2 [1; d]; j 2 [1; `] skij Ã EncryptE(pki¡1

where ski1; : : : ; ski` is the representation of ski as elements of P. It outputs the secret key

sk(d) Ã sk0 and the public key pk(d) Ã (hpkii; hskiji). Let E(±) refer to the sub-system that uses sk(±) Ã sk0 and pk(±)Ã (hpkiii2[0]; hskijii2[1]) for ± · d.
EncryptE(d) (pk(d); ¼). Takes as input a public key pk(d)and a plaintext ¼ 2 P. It outputs a
R
ciphertext Ã Ã EncryptE (pkd; ¼).
DecryptE(d) (sk(d); Ã). Takes as input a secret key sk(d)and a ciphertext Ã (which should be an encryption under pk0). It outputs DecryptE(sk0; Ã).
EvaluateE(±) (pk(±); C±;ª±). Takes as input a public key pk(±), a circuit C± of depth at most with gates in ¡, and a tuple of input ciphertexts ª± (where each input ciphertext should be under pk±). We assume that each wire in C± connects gates at consecutive levels; if not, add trivial gates to make it so. If ± = 0, it outputs ª0 and terminates. Otherwise, it does the following:

²    Sets (C±y¡1; ªy±¡1) Ã AugmentE(±) (pk(±); C±; ª±).

²    Sets (C±¡1; ª±¡1) Ã ReduceE(±¡1) (pk(±¡1); C±y¡1; ªy±¡1).

²    Runs EvaluateE(±¡1) (pk(±¡1); C±¡1; ª±¡1).

AugmentE(±) (pk(±); C±;ª±). Takes as input a public key pk(±), a circuit C± of depth at most ±  with gates in ¡, and a tuple of input ciphertexts ª± (where each input ciphertext should be under pk±). It augments C± with DE ; call the resulting circuit C±y¡1. Let ªy±¡1be the tuple of ciphertexts formed by replacing each input ciphertext Ã 2ª± by the tuple hhsk±ji; hÃjii, where ÃjÃ WeakEncryptE(±¡1)(pk(±¡1); Ãj) and the Ãj's form the properly-formatted representation of Ãas elements of P. It outputs (C±y¡1; ªy±¡1).
ReduceE(±) (pk(±); C±y;ªy±). Takes as input a public key pk(±), a tuple of input ciphertexts ªy±(where each input ciphertext should be in the image of EncryptE(±) ), and a circuit C±y2 DE; ± + 1). It sets C± to be the sub-circuit of C±y consisting of the first ± levels. It sets ª± to be the induced input ciphertexts of C±, where the ciphertext Ã±(w) associated to wire w at level ± is set to EvaluateE (pk±; C±(w); ª(±w)), where C±(w)is the sub-circuit of C±ywith output wire w, and ª(±w) are the input ciphertexts for C±(w). It outputs (C±; ª±).

High-level review of the Evaluate algorithm. We are given a circuit Cd of, say, d levels with gates in ¡. For each input wire w of Cd, there is an associated input ciphertext Ãwencrypted under pkd. We are also given an encryption scheme Ethat compactly evaluates circuits in DE(¡).

Note that we have not assumed that Ecan evaluate gates in ¡; we have only assumed it can evaluate gates in ¡ that are augmented by the decryption circuit. So, our first step is to augment Cd by placing copies of DE at the leaves of Cd (as in Augment), thereby constructing Cdy¡1. Now, what are the input ciphertexts for our new circuit Cdy¡1? Reconsider the algorithm Recrypt0E. In Recrypt0E, we begin with a ciphertext Ã1encrypt-ing ¼ under pk1for the single wire w, and an empty" circuit C1 (since Recrypt0Edoesn't actually evaluate any gates, it just generates a new encryption of the same plaintext). Our next step was to augment C1 with the decryption circuit DE to obtain C2Ã DE. The input ciphertexts ª2 to C2included the encrypted secret key bits, and the weakly encrypted bits of Ã1. We then showed that the ciphertext generated by Ã2Ã EvaluateE(pk2; C2; ª2), which is also associated to wire w, also encrypts ¼, but now under pk2.

In the full scheme above, the ciphertexts that we associate to the decryption circuit that was attached to wire w are analogous to the ones we used in Recrypt0E: the encrypted secret key (skd under pk1), and the re-encryption ciphertexts of Ãwunder pk1. By the correctness of Recrypt, the ciphertext nowassociated to w (after performing EvaluateE) should encrypt the same plaintext as Ãw, but now under pk1.

The Reduce step simply performs this Evaluate up to the wire w, and one level beyond. We know that Evaluate can correctly continue one level beyond the wire w, because (by assumption) Ecan evaluate not just the decryption circuit attached to w, but can evaluate a circuit containing one ¡-gate above w. Reduce outputs C1 and ciphertexts associated to C1's input wires. We have made progress, since C1is one level shallower than Cd. We perform this entire process d ¡ 1 more times to obtain the final output ciphertexts.
we said that Evaluate takes as input ciphertexts that are \fresh" outputs of Encrypt. However, we note EvaluateE(±) also operates correctly on ciphertexts output by Evaluate. (For ± < d above, this is precisely what EvaluateE(±) does.)

Correctness, Computational Complexity and Security of the Generic Construction

Here we state and prove some theorems regarding the generic construction. Regarding correctness, we have the following theorem.[5]

Let E be bootstrappable with respect to a set of gates ¡. ThenE(d) com-pactly evaluates all circuits of depth d with gates in ¡{ i.e., if ¡ is a universal set of gates, the family E(d) is leveled fully homomorphic. Proof. (Theorem 4.2.1) First, we define a convenient notation: let D(±; w; C; ª) denote the plaintext value for wire w in circuit C induced by the decryptions (under sk±) of the ciphertexts ª associated to C's input wires. If C is empty (has no gates), then the input wires are the same as the output wires, and D(±; w; C; ª) just denotes the decryption of the single ciphertext Ã 2 ª associated to w. To prove correctness, it succes to show that

 D(d; wout; Cd; ªd) = D(0; wout; C0; ª0) (1)

for every output wire wout of C0 (at level 0). First, when (C±y¡1; ªy±¡1) Ã AugmentE(±) (pk(±); C±; ª±), we claim that D(±; w; C±; ª±) = D(±¡1; w; C±y¡1; ªy±¡1) for any wire w at level at most ±¡1. This follows from the correctness of Recrypt (generalized beyond a boolean plaintext space and boolean circuits), and the fact that circuits C± and C±y¡1 are identical up to level ± ¡ 1.

Next, when (C±; ª±) Ã ReduceE(±) (pk(±); C±y; ªy±), we have D(±; w; C±y; ªy±) = D(±; w; C±; ª±) for any wire at level at most ±. This follows from the correctness of EvaluateEover circuits in D (¡), and the fact that circuits Cy and C  are identical up to level ±.
E                                                                     ±               ±

Note that ¡ is arbitrary. For example, each gate in ¡ could be a circuit of (ANDs, ORs, NOTs) of depth m and fan-in 2; for this value of ¡, It implies the scheme correctly evaluates boolean circuits up to depth d ¢ m.

We need to check that the computational complexity of EvaluateE(d) is reasonable { e.g., that recursive applications of Augment do not increase the effective circuit size exponentially.

For a circuit C of depth at most d and size s (defined here as the number of wires), the computational complexity of applying EvaluateE(d) to C is dominated by at most s ¢ ` ¢ d applications of WeakEncryptEand at most s ¢ d applications of EvaluateE to circuits in DE(¡), where ` is as in this research paper. Proof: There is a pre-processing step to ensure that all wires in the circuit connect gates at consecutive levels; clearly, this step increases the number of wires in thecircuit by at most a multiplicative factor of d. It remains to prove that, for the pre-processed circuit, the computational complexity is dominated by at most s0 ¢ ` applications of Encrypt and at most s0applications of EvaluateE to circuits in DE (¡), where s0is the size of the pre-processed circuit. The complexity of AugmentE(±) (pk(±); C±; ª±) is dominated by replacing each ciphertext A2 ª± by the ciphertexts hhsk±ji; hÃjii; generating the hÃji's involves jW±j ¢ ` applications of WeakEncryptE , where W± is the set of wires at level ±. Summing over all ±, there are at most s0 ¢ ` applications of WeakEncryptE.

The complexity of ReduceE(±) (pk(±); C±y;ªy±) is dominated by the evaluation of C±(w) for each w 2 W±, which involves jW±japplications of EvaluateEto circuits in DE (¡). Summing over all ±, there are at most s0 such applications. The theorem follows.

Finally, assuming the semantic security of E, we prove the semantic security of E(d). Theorem 4.2.3. Let A be an algorithm that (t; ²)-breaks the semantic security of E(d). Then, there is an algorithm B that (t0; ²0)-breaks the semantic security of E for t0¼ t ¢ ` and ²0 ¸ ²=`(d + 1), for ` as in. Proof. (Theorem 4.2.3) Let (E)` be equivalent toE, but with plaintext space P ·`, where Encrypt(E)` involves up to `invocations of E and a concatenation of the results. We use a hybrid argument to show that B (t00; ²00)-breaks the semantic security of (E)` for t00 ¼ t and ²00 ¸ ²=(d + 1), from which the result follows.For k2 [0; d], let Game k denote a game against E(d) in which everything is exactly as in the real-world game, except that for all i 2 [1; k] the challenger sets
 (ski0 R R ; skij0) ; pki0) Ã KeyGenE (¸) and  skij Ã EncryptE(pki¡1

In other words, for i 2 [1; k], skij is the encryption (under pk1) of the j-th bit of a random secret key sk0i unrelated to ski. Game d + 1 is identical to Game d, except that the challenger ignores b and (¼0; ¼1), generates a random plaintext ¼ of the appropriate length, and encrypts ¼ to construct the challenge ciphertext. Let ²kdenote the adversary's advantage in Game k.

Since Game 0 is identical to the real world attack, the adversary's advantage is ² by assumption. Also, ²d+1 = 0, since the challenge is independent of b. Consequently, for some k 2 [0; d], it must hold thatk ¡ ²k+1j ¸ ²=(d + 1); ¯x this value of k. B uses A to break (E)` as follows. B receives from the challenger a public key pk. B generates the secret and public values exactly as in Game k, except that it replaces its  0 0              R original value of pkk with pk. Also, if k < d, it generates a dummy key pair (skk+1;pkk+1) Ã KeyGenE(¸), sets ¼0 Ã skk+1and ¼1 Ã sk0k+1, and requests a challenge ciphertext (under `            R pk) encrypting either ¼0; ¼12 P . The challenger generates ¯ Ã f0; 1g and sends a tuple of ciphertexts ji encrypting the bits ¯ji. Breplaces its original tuple hsk(k+1)ji with the tuple ji. One can verify that the public values are generated exactly as in Game k + ¯. B sends the public values to A. R Eventually, A requests a challenge ciphertext on ¼0 or ¼1. B sets b Ã f0;1g. If k < d, R                R B sends the values Ãj Ã EncryptE (pkd; ¼bj). If k = d, B generates random ¼ Ã P and asks R the challenger for a challenge ciphertext on ¼b or ¼. The challenger generates ¯Ã f0; 1g and encrypts ¼b or ¼ accordingly, and Bforwards the challenge to A. A sends a bit b0. B sends bit ¯0 Ã b© b0to the challenger. One can verify that the challenge is generated as in Game k + ¯. Since B's simulation has the same distribution as Game k + ¯, and the probability that outputs 0 is ²k+¯. The result follows.

Fully Homomorphic Encryption from KDM-Secure Boots trappable Encryption

The length of the public key in E(d) is proportional to d (the depth of the circuits that can be evaluated). It would be preferable to have a construction E ¤ where the public key size is completely independent of the circuit depth, a construction that is fully homomorphic rather than merely leveled fully homomorphic. Here is the obvious way to make the public key pk¤of E¤ short: for E key pair (sk; pk), pk¤includes only pk and (the bits" of) sk encrypted under pk. In other words, we have a cycle (in fact, a self-loop in this example) of encrypted secret keys rather than an acyclic chain. It is clear that E¤ is correct: the recursive algorithm EvaluateE¤ works as before, except that the implicit recryptions generate \refreshed" ciphertexts under the same public key.

Why didn't we present this construction in the first place? Using an acyclic chain of encrypted secret keys allowed us to base the security of E(d) on E using a hybrid argument; this hybrid argument breaks down when there is a cycle. In general, a semantically secure encryption scheme is not guaranteed to be KDM-secure { i.e., secure when the adversary can request the encryptions of key-dependent messages, such as the secret key itself. Typ-ically, when we prove an encryption scheme semantically secure, there is not an obvious attack when the adversary is given the encryption of a key-dependent message.[7] However, KDM-security is highly nontrivial to prove. The problem is precisely that the usual hybrid argument breaks down.[6]

It proposed the acyclic, leveled approach as a way to remove the need for KDM-security. Our initial approach had actually been to use E¤ (with the self-loop), and assume, or try to prove, KDM-security.Let us review (a restriction of) the definition of KDM-security. We will say a scheme E is KDM-secure if all polynomial-time adversaries Ahave negligible advantage in the followingKDM-security game.

KDM-Security Game.
R
Setup(¸; n). The challenger sets (ski; pki) Ã KeyGen(¸) for i 2 [0; n ¡1] for integer n =
R
poly(¸). It chooses a random bit b Ã f0; 1g. If b = 0, then for i 2[0; n ¡ 1] and j 2 [1; `],
R
it sets skij Ã EncryptE (pk(1) mod n; skij), where skij is the jth \bit" of ski. If b = 1, it generates the skijvalues as encryptions of random secret keys, unrelated to pk0; : : : ; pk1. It sends the public keys and encrypted secret keys to A.
Challenge and Guess. Basically as in the semantic security game.

This definition of KDM-security is a restriction of the general setting [18, 68, 22], where A can select multiple functions f, and request the encryption of f(sk0; : : : ; sk1). However, when E is a bootstrappable encryption scheme, Acan use the cycle of encrypted secret keys in our game to generate the encryption of f(sk0; : : : ; sk1) under any pki, as long as fcan be computed in polynomial time. Hence, we only need to consider our restricted setting [65]. We have the following theorem.

Suppose E is KDM-secure and also bootstrappable with respect to a uni-versal set of gates ¡. Then, E ¤, obtained from E as described above (with the self-loop), is semantically secure (and fully homomorphic).
The theorem is a straightforward consequence of the fact that, from any loop of public keys and encrypted secret keys that includes (pk0;sk0), one can compute an encryption of sk0under pk0. There does not seem to be any advantage in having pk¤ contain any cycle of encrypted secret keys other than a self-loop.

Absent proof of KDM-security in the plain model, one way to obtain fully homomorphic encryption from bootstrappable encryption is simply to assume that the underlying boot-strappable encryption scheme is also KDM-secure. This assumption, though unsatisfying, does not seem completely outlandish. While an encrypted secret key is very useful in a bootstrappable encryption scheme { indeed, one may view this as the essence of bootstrap-pability { we do not see any actual attack on a bootstrappable encryption scheme that provides a self-encrypted key.

Fully Homomorphic Encryption from Bootstrappable En-cryption in the Random Oracle Model

Above, we constructed a fully homomorphic encryption E¤ from a bootstrappable encryp-tion scheme E basically by adding a self-loop" { a E secret key sk encrypted under its corresponding public key pk { to the E ¤public key pk¤. We showed that E ¤ should inherit the semantic security of E, under the assumption that E is KDM-secure { in particular, under the assumption that it is safe" to reveal a direct encryption of a secret key un-der its own public key (as opposed to some possibly-less-revealing non-identity function of the secret key). Can we provide any evidence that E¤is semantically secure without this assumption?[9] Here we provide some evidence in the random oracle model. First, given a leveled fully homomorphic scheme E(d) and a hash function, we define an intermediate scheme E(d)y. E(d)y is the same as E(d), except for the following. The public key includes a hash function

 `0 ` R `0 R (d) H : P ! P , sets rj ; rj) . Also, in KeyGen, one generates r Ã P Ã EncryptE(d) (pk for j [1; `0], sets ¾ H(r) ? sk0 , and includes ( rj ; ¾) in the public key. (Assume ? is 2 Ã h i
some invertible operation such that a ? b would completely hide b 2 P` if a 2 P` were a one-time pad.) In other words, the E(d)ypublic key includes some additional information: an encryption of the the secret key sk0, where the encryption uses a hash function that will be treated as a random oracle in the security analysis.

Next, we prove the following theorems.

If E(d) is semantically secure, then E(d)y is semantically secure in the random oracle model. Theorem 4.4.2. Suppose E is leveled circuit private (in addition to being bootstrappable) and let E(d)y and E¤ be constructed from E as described above. Then, if E(d) y is semantically secure (in the plain model), and the circuit required to compute the hash function H and invert the ? operation is at most d levels, then E¤is semantically secure.

The result here should be quite surprising. The scheme E¤does not even contain a hash function, and yet we are basically claiming that it is secure in the random oracle model! This is the first instance that we are aware of where one scheme is proven secure in the random oracle model, and then a second scheme's security is based on the first scheme, even though the second scheme does not use a hash function. How is this possible? First, let us consider in this research paper.  This

theorem basically just states the previously known result that it is easy to construct a KDM-secure encryption scheme in the random oracle model. This is because the random oracle allows the reduction to construct a fake" ciphertext purportedly encrypting the secret key, such that the adversary finds out that it was fake only after it has queried the random oracle; this query gives the reduction all of the information that it needs to solve the underlying problem. In our particular case, E(d)yhas a loop among (sk0; pk0); : : : ; (skd; pkd), because E(d) reveals direct encryptions of ski under pk1 fori 2 [1; d], and E(d)y also reveals an indirect encryption (hrji; ¾) of sk0 under pkd (\indirect," because encryption in E does not normally use a hash function). However, the reduction algorithm in the proof of Theorem 4.4.1 will construct ¾ simply as a random string { i.e., it does not actually need to know anything about sk0.

It perhaps the more surprising result. But the result is actually a simple consequence of the fact that: given a correctly constructed E(d) ypublic key, the reduction algorithm can generate an E-encryption of sk0 under pk0, as needed for the E¤ public key. How do we generate the latter ciphertext? The reduction algorithm is given hrji, an encryption of r under pkd. It simply uses the leveled homomorphism and the circuit corresponding to the hash function Hto compute a ciphertext that encrypts H(r) from the ciphertext that encrypts r. Then, given that ciphertext and the value of ¾ = H(r) ? sk0, it computes a ciphertext that encrypts sk0in the natural way { i.e., directly, rather than with the hash function. We assumed that the hash function H and the ? operation can be computed with a circuit of depth at most d; therefore, our leveled homomorphic scheme E(d) has enough levels to evaluate this circuit. Consequently, we obtain a \natural" encryption of sk0 (i.e., under E) under some public key pki for i ¸ 0, and we can use Recrypt operations to obtain a natural encryption of sk0under pk0. This ciphertext is an output of EvaluateE , but circuit privacy guarantees that the ciphertext is distributed as if it were output directly by EncryptE.

Although one can view (hrji; ¾) as an encryption" of sk0, this encryption" function is not the usual encryption function and it might have a very complex decryption circuit, much more complex than DE. In particular, we cannot assume that its decryption circuit is in CE. This why we needed many (d) levels in the leveled scheme to recover sk0, and could not immediately use a self-loop from the outset.[10]

So, if E¤ is secure in the random oracle model despite not using a hash function, does that imply that it is secure in the plain model? Certainly not. The obstacle to this conclusion is obviously that random oracles cannot be instantiated in general. A bit more specifically, however, the obstacle is that the proof of Theorem 4.4.2 depends crucially on the correctness of the ciphertext (hrji; ¾) in E(d) y to construct (homomorphically) an encryption of sk0 under pk0as needed for the E¤ public key; however, in the proof of  the ciphertext is not correct (except with negligible probability): the adversary funds out that it was fake only after it has queried r to the random oracle, giving the reduction all the information it needs.

Proof : Let A be an algorithm that attacks the semantic security of E(d)y; from A, we construct an algorithm Bthat attacks the semantic security of E(d). B will actually request `0+ 1 challenge ciphertexts; thus, the reduction loses a factor of `0 + 1 under the usual hybrid argument.
 The challenger gives B a E(d) R public key.  It also sets a bit b Ã f0; 1g.  B selects two messages r (0) ; r (1) 2 P `0 R and sends them to the challenger. The challenger sets ª Ã f Encrypt(pk ; r(b)) : j 2 [1; `0 ] g and sends back ª. The following is included in the public d j
key that B sends to A: the public key for E(d) sent by the challenger, the set of ciphertexts
R     `
ª, and ¾ Ã P .

A requests a challenge ciphertext on one ¼0; ¼1 2 P. B forwards the query to the challenger, who responds with a ciphertext encrypting ¼b, which B forwards to A. Eventually, either A queries some r0 2 fr(0); r(1)g to the random oracle, or Afinishes with a guess b0. In the former case, B sets b0 so that r0 = r(b0). In either case, B sends b0 as its guess to the challenger.

Let p be the probability that A queries some r0 2 fr(0); r(1)g to the random oracle. B's simulation appears perfect to A if it does not query some r0 2 fr(0); r(1) g; in this case, which occurs with probability 1 ¡p, A's advantage is at least ². Since A's view is independent of r(1¡b), the probability that it queries r(b) to the random oracle is at least p ¡ qH=jPj`0, where qH is the number of random oracle queries make by A. Overall B's advantage in guessing b0 is at least (1 ¡ p)² + p¡ qH=jPj`0 ¸ ²¡ qH=jPj`0.

Proof:  The proof is essentially a simple consequence of the fact that, given a public key for E(d)y, it is easy to generate the public key for E¤homomorphically.

Let A be an algorithm that breaks the semantic security of E¤. We use A to construct an algorithm B that breaks the semantic security of E(d)y.

B  receives a E(d)y public key from the challenger. This public key consists of hpkiii2[0], hskijii2[1], hrjij2[1;`0], and ¾ = H(r) ? sk0. From hrji, B uses the homomorphism of E(d) to compute ciphertexts ª that encrypt H(r). It encrypts ¾, and then uses the homomorphism to recover to obtain an encryption of sk0 from the encryptions of H(r) and ¾ (inverting the ? operation). By assumption, these homomorphic operations take at most dlevels. If it takes only ± < dlevels, and we obtain an encryption of sk0 under pkd¡±, then we can perform Recrypt operations until we have the desired encryption of sk0 under pk0. By circuit privacy, this ciphertext is distributed properly. B includes the encryption of sk0under pk0 as the encrypted secret key contained in the public key for E¤ that it provides to A.
A requests a challenge ciphertext on one ¼0; ¼1 2 P. B forwards the query to the challenger, who responds with a ciphertext encrypting ¼b. B uses Recrypt operations to obtain an encryption of ¼b under pk0 and forwards the result to A. A sends a guess b0, which Bforwards to the challenger.

Clearly, B's advantage is the same as A's.

An Abstract Scheme Based on the Ideal Coset Problem

Our goal now is to construct a bootstrappable encryption scheme, a scheme that can ho-momorphically evaluate a rich set of circuits that includes its own decryption circuit, plus some." In the past, attempts to construct fully homomorphic encryption have focused solely on maximizing the complexity of the circuits that the scheme can evaluate. Our notion of bootstrapability gives us a different way of attacking the problem { by minimizing the complexity of the scheme's decryption circuit.

Our strategy for minimizing the circuit complexity of decryption is to construct our scheme using ideal lattices, since decryption in lattice-based cryptosystems is typically dom-inated by a simple operation, such as an easily parallelizable matrix-vector multiplication (in contrast to, say, RSA, where decryption involves exponentiation, an operation not even known to be in NC). We begin describing the ideal-lattice-based scheme in Chapter 7, after providing some basic background on ideal lattices in Chapter 6.

In this Chapter, we describe our strategy for maximizing the evaluative capacity"[11] of the scheme abstractly, without reference to lattices. Generally speaking, our exposition strategy throughout the paper is to defer technical lattice details for as long as possible. One reason is to make the presentation more modular, and therefore easier to understand. Another reason is that some of our techniques { e.g., bootstrapping, and using techniques from server-aided cryptography to squash the decryption circuit" { maybe applicable to schemes that use different underlying mathematics { e.g., linear codes, or something less similar to lattices.

The Ideal Coset Problem

We saw in  this research paper that many previous homomorphic encryption schemes base security on some ideal membership problem (IMP). For example, in the Polly Cracker" scheme by Fellows and Koblitz, the public key consists of some multivariate polynomials that generate the ideal I of polynomials having a common root x, and ¼ is encrypted by outputting a sample Ã Ã ¼ + I. One can easily see that this is semantically secure if it is hard to distinguish membership in I { in particular, deciding whether Ã ¡¼2 I. Unfortunately, one can also see that homomorphic operations, especially multiplication, expand the ciphertext size potentially exponentially in the depth.

Since we will ultimately use lattices, we apparently need a different abstract approach, since it is easy to distinguish membership in a lattice L: given a basis B of L and t 2 Rn, one simply determines whether t mod B = 0 mod B. Instead, we base security on an idealcoset problem (ICP), which we will state abstractly in terms of rings and ideals. Recall that a ring R is an algebraic object that is closed under addition `+' and multiplication `£' and additive inverse, with an additive identity `0' and multiplicative identity `1'. An ideal I of a ring R is a subset satisfying a + b 2 I and r £ a2 Ifor all a; b 2 I and r 2R. The sum and product of two ideals I and J are, respectively, fi + j : i 2 I; j 2 Jg and the additive closure of fi £j : i 2 I; j 2 Jg. Two ideals I and J are relatively prime if I + J = R. For example, if R = Z, the ideals (2) (the even integers) and (5) (the integers divisible by 5) are relatively prime: (2) + (5) = (1).

Now, the ideal coset problem (ICP) is as follows.
Definition 5.1.1 (Ideal Coset Problem (ICP)). Fix R, BI , algorithm IdealGen, and an al-

 R pk R gorithm Samp1 that e±ciently samples R. The challenger sets b Ã f0; 1g and (BJsk; BJ ) Ã R pk . If b = 1, it samples t IdealGen(R; BI ). If b = 0, it sets r Ã Samp1 (R) and t Ã r mod BJ uniformly from R mod Bpk. The problem: guess b given (t; Bpk). J J

Basically the ICP asks one to decide whether t is uniform modulo J, or whether it was chosen according to a known clumpier" distribution induced by Samp1. Of course, the ICP will be impossible if Samp1 also samples uniformly modulo J, but the security of our encryption scheme will rely on the ICP being hard for a clumpier" instantiation of Samp1; the hardness of the problem depends on the particular instantiation of Samp1. Note that it is possible for the ICP to be hard even when the IMP is easy.

An Abstract Scheme

We start by describing our initial attempt simply in terms of rings and ideals; we bring in ideal lattices later. In our initial scheme E, we use a fixed ring R that is set appropriately according to a security parameter ¸. We also use a fixed basis BI of a ideal I ½R, and an algorithm IdealGen(R; BI) that outputs public and secret bases BpkJ and BskJof some (variable) ideal J, such that I + J = R { i.e., I and J are relatively prime. We assume that if t 2 R and BM is a basis for ideal M ½R, then the value t mod BM is unique and can be computed efficiently { i.e., the coset t + Mhas a unique, efficiently-computable \distinguished representative" with respect to the basis BM . We use the notation R mod BM to denote the set of distinguished representatives of r + M over r 2 R, with respect to the particular basis BM of M. We also use an algorithm Samp(BI; x) that samples from the coset x + I.

In the scheme, Evaluate takes as input a circuit C whose gates perform operations modulo BI . For example, an AddBI gate in C takes two terms in R mod BI , and outputs a third term in R mod BI , which equals the sum of the first two terms modulo I.

sk     pk   R
KeyGen(R; BI ). Takes as input a ring R and basis BI of I. It sets (BJ ; BJ) Ã IdealGen(R; BI ). The plaintext space P is (a subset of) R mod BI . The public key pk includes R, BI , BpkJ, and Samp. The secret key sk also includes BskJ.

Encrypt(pk; ¼). Takes as input the public key pk and plaintext ¼ 2 P. It sets Ã0 Ã Samp(BI ; ¼) and outputs Ã Ã Ã0mod BpkJ. Decrypt(sk; Ã). Takes as input the secret key sk and a ciphertext Ã. It outputs
¼Ã (Ã mod BskJ) mod BI

Evaluate(pk; C; ª). Takes as input the public key pk, a circuit Cin some permitted set CEof circuits composed of AddBIand MultBI gates and a set of input ciphertexts ª. It invokes Add and Mult, given below, in the proper sequence to compute the output ciphertext Ã. (We will describe CE when we consider correctness below. If desired, one could use di®erent arithmetic gates.)

Add(pk; Ã1; Ã2). Outputs Ã1 + Ã2 mod BpkJ.

Mult(pk; Ã1; Ã2). Outputs Ã1 £ Ã2 mod BpkJ.

Concerning IdealGen, it is define the secret basis BskJ de¯nes a lattice L(BskJ) for a (possibly fractional) ideal that contains J, rather than being exactly J.

Now, let us consider correctness, which is a highly nontrivial issue in this paper. The following definitions provide structure for our analysis.

To begin, we observe that the scheme is actually using two di®erent circuits. First, Evaluate takes a mod-BIcircuit C as input. This circuit is implicitly applied to plaintexts. Second, Evaluate applies a circuit related to C, which we call the generalized circuit, to the ciphertexts; this circuit uses the ring operations (not modulo I).[12]

Let C be a mod-BI circuit. We say generalized circuit g(C) of C is the circuit formed by replacing C's AddBI and MultBI operations with addition `+' and multiplication `£' in the ring R. Here are a few more definitions relevant to below, which concerns correctness. (XEnc and XDec). Let XEnc be the image of Samp. Notice that all ciphertexts output by Encrypt are in XEnc +J. Let XDec equal R mod BskJ, the set of distinguished representatives of cosets of J wrt the secret basis BskJ.

Definition 5.2.4 (Permitted Circuits). Let

CE0 = fC : 8(x1; : : : ; xt) 2 XEnct; g(C)(x1; : : : ; xt) 2 XDecg

In other words, CE0is the set of mod-BIcircuits that, when generalized, the output is always in XDec if the inputs are in XEnc. (The value twill of course depend on C.) If CE µ CE0, we say that CE is a set of permitted circuits.

Ã is a valid ciphertext wrt E public key pk and permitted circuits CE if it equals Evaluate(pk; C; ª) for some C 2 CE, where each Ã 2 ª is in the image of Encrypt. The circuit C may be the identity circuit, in which case the output of Evaluate is simply an output of Encrypt.

Finally, we prove correctness with respect to CE . Theorem 5.2.6. Assume CE is a set of permitted circuits containing the identity circuit. E is correct for CE { i.e., Decrypt correctly decrypts valid ciphertexts. CHAPTER 5. AN ABSTRACT SCHEME BASED ON THE IDEAL COSET PROBLEM61

Proof. For ciphertexts ª =1; : : : ; Ãtg, Ãk = ¼k + ik+ jk, where ¼k 2 P, ik 2 I, jk2 J, and ¼k + ik2 XEnc, we have
Evaluate(pk; C; ª) = g(C)(ª) mod BpkJ 2 g(C)(¼1+ i1; : : : ; ¼t + it) + J

If C 2 CE, we have g(C)(XEnc; : : : ; XEnc) 2 XDecand therefore

Decrypt(sk;Evaluate(pk; C; ª))         =     g(C)(¼1 + i1; : : : ; ¼t + it) mod BI

=      g(C)(¼1; : : : ; ¼t) mod BI

=      C(¼1; : : : ; ¼t)

as required.

The bottom line is that we have proven that E is correct for permitted circuits, and our goal now is to maximize this set. The permitted circuits are defined somewhat indirectly; they are the circuits for which the error" g(C)(x1; : : : ; xt) of the output ciphertext is small (i.e., lies inside XDec) when the input ciphertexts are in the image of EncryptE. When we begin to instantiate the abstract scheme with lattices and give geometric interpretations of XEnc and XDec, the problem of maximizing CE will have a geometric °avor.

Again, we note the rather confusing fact that C automatically" reduces the result modulo BI , since it uses mod-BI gates. It does not particularly matter how these mod-BIgates are implemented; in particular, it is more confusing than helpful to imagine a boolean implementation of these gates. Instead, one should just observe that the generalized circuit manages to lazily emulate these gates, reducing its output modulo BIat the end of the computation. C's mod-BI operations are never actually implemented;" they only occur implicitly. Later, when we consider whether our scheme is bootstrappable, and analyze the depth of the decryption circuit in terms of mod-BIgates, it will again be tempting to consider how these gates are \implemented." But in fact these gates are given" in the sense that they are emulated (without any intermediate reduction steps) by the usual ring operations.

Security of the Abstract Scheme

For the following abstract instantiation" of Samp, and where I is a principle ideal generated by some s 2 R (and s is encoded in BI), we provide a simple proof of semantic security based on the ICP. Samp(BI ; x). Run r Ã Samp1(R). Output x + r £ s. Obviously, the output is in x + I since s 2 I.

Suppose that there is an algorithm A that breaks the semantic security of E with advantage ² when it uses Samp. Then, there is an algorithm B, running in about the same time as A, that solves the ICP with advantage ²=2.

Proof. The challenger sends B a ICP instance (t; BpkJ). B sets s, and sets the other compo-nents of pk in the obvious way using the ICP instance. When A requests a challenge cipher- text on one of ¼0; ¼12 P, B sets a bit ¯ Ã f0;1g and sends back Ã Ã¼¯ + t £ s mod BJ . A sends back a guess ¯0, and Bguesses b0 Ã ¯© ¯0.

If b = 0, we claim that B's simulation is perfect; in particular, the challenge ciphertext has the correct distribution. When b = 0, we have that t = r + j, where r was chosen according to Samp1 and j 2 J. So, Ã Ã¼¯ + t £ s = ¼¯ + r £ s mod BpkJ; the ciphertext is thus well-formed. In this case A should have advantage ², which translates into an advantage of ²for B. If b = 1, then t is uniformly random modulo J. Since the ideal I = (s) is relatively prime to J, t£s is uniformly random modulo J, and consequently Ã is a uniformly random element of R mod BpkJthat is independent of ¯. In this case A's advantage is 0. Overall, B's advantage is ²=2.

References:
1. M. Bellare, A. Boldyreva, and S. Micali. Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements. In Proc. of Eurocrypt '00, pages 259{274. Springer, 2000.

2. J. Benaloh. Veri¯able secret-ballot elections. Ph.D. thesis, Yale Univ., Dept. of Comp. Sci., 1988.

3. J. Black, P. Rogaway, and T. Shrimpton. Encryption-scheme security in the presence of key-dependent messages. In Proc. of SAC '02, LNCS 2595, pages 62{75. Springer, 2002.

4. M. Blaze, G. Bleumer, and M. Strauss. Divertible protocols and atomic proxy cryptog-raphy. Eurocrypt '98, LNCS 1403, pp. 127{144.

5. D. Boneh and M. Franklin. E±cient Generation of Shared RSA Keys. J. ACM, vol. 48, no. 4. Pages, 702-722. ACM, 2001. Preliminary version in Crypto 1997.

6. D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF formulas on ciphertexts. TCC '05, LNCS 3378, pp. 325{341.

7. D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky. Circular-Secure Encryption from Decision Di±e-Hellman. In Proc. of Crypto '08, LNCS 5157, pages 108{125.

8. D. Boneh and R. Lipton. Searching for Elements in Black-Box Fields and Applications. In Proc of Crypto '96, LNCS 1109, pages 283{297. Springer, 1996.

9. J. Boyar, R. Peralta, and D. Pochuev. On the Multiplicative Complexity of Boolean Functions over the Basis (^; ©; 1). Theor. Comput. Sci. 235(1), pp. 43{57, 2000.

10. E. Brickell and Y. Yacobi. On Privacy Homomorphisms. In Proc. of Eurocrypt '87, LNCS 304, pages 117{125. Springer, 1988.

11. J.Y. Cai and A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In Proc. of FOCS '97, pages 468{477.

12. R. Canetti. Personal communication, 2008.

13. R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In Proc. of STOC '98, pages 209{218. ACM, 1998.

14. R. Canetti and S. Hohenberger. Chosen-ciphertext secure proxy re-encryption. In Proc. of ACM CCS '07.

15. R. Canetti, H. Krawczyk, and J.B. Nielsen. Relaxing chosen-ciphertext security. In Proc. of Crypto '03, pages 565{582. Springer, 2003.