__A Research Analysis of Leveled Fully Homomorphic Encryption from Bootstrappable Encryption Generically__**Prof.Dr.G.Manoj Someswar**

^{1}, D.Narasimha Raju^{2}**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

*E*that compactly evaluates some set of circuits*C*. We want to use_{E}*E*to construct a homomorphic encryption scheme that can handle*arbitrary circuits. In this Chapter we prove a fundamental result: that if**C*contains (slight augmentations of)_{E}*E*'s*own decryption circuit**D*{ i.e., if_{E}*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*D*; the secret key and ciphertexts are the same size as in_{E}*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*E*using 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 pk*, we*_{i}*re-encrypt*it under pk_{i}_{+1}and then*homomorphically apply the decryption circuit*to the result, using the secret key sk*that is*_{i}*encrypted under pk*_{i}_{+1}, thereby obtaining an encryption of*¼*under pk_{i}_{+1}. Homomorphically evaluating the decryption circuit decrypts the*inner*ciphertext under pk*, but within homomorphic encryption under pk*_{i}_{i}_{+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*f*0*;*1*g*and*D*is a boolean circuit in_{E}*C*. Let (sk_{E}_{1}*;*pk_{1}) and (sk_{2}*;*pk_{2}) be two*E*key-pairs. Let*Ã*_{1}be an encryption of 1/4*2 P*under pk_{1}. Let sk_{1j}*be an encryption of the**j*-th bit of the*first secret key*sk_{1}under*the**second public key*pk_{2}. Recrypt takes as these things as input, and outputs an encryption of*¼*under pk_{2}.Recrypt(pk

_{2}*; D*_{E}*;**h*sk_{1j}*i; Ã*_{1}).R

Set

*Ã*_{1j}*Ã*Encrypt*(pk*_{E}_{2}*; Ã*_{1j}) where*Ã*_{1j}is the*j*-th bit of*Ã*_{1}Set*Ã*_{2}*Ã*Evaluate*(pk*_{E}_{2}*; D*_{E};*hh*sk_{1j}*i;**hÃ*_{1j}*ii*) Output*Ã*_{2}Above, the Evaluate algorithm takes in all of the bits of sk

_{1}and all of the bits of*Ã*_{1}, each encrypted under pk_{2}. Then,*E*is used to evaluate the decryption circuit homomorphically. The output*Ã*_{2}is thus an encryption under pk_{2}of Decrypt*(sk*_{E}_{1}*; Ã*_{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 sk_{1}to generate a tag that enables an untrusted proxy to convert an encryption of*¼*under pk_{1}to an encryption of*¼*under pk_{2}, but not the reverse. In our case, the tag is*h*sk_{1j}*i*, 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 pk_{1}and pk_{2}. Depending on the encryption scheme*E*, however, this double encryption might be overkill. Suppose WeakEncrypt*is an algorithm such that the image of WeakEncrypt*_{E}*(pk*_{E}*; ¼*) is always a subset of the image of Encrypt*(pk*_{E}*; ¼*). Then we can replace the first step of Recrypt*with:*_{E}R

Set

*Ã*_{1j}*Ã*WeakEncrypt*(pk*_{E}_{2}*; Ã*_{1j}) where*Ã*_{1j}is the*j*-th bit of*Ã*_{1}Let us call this relaxation Recrypt

*. The main point of this relaxation is that WeakEncrypt does not need to be semantically secure for Recrypt*^{0}_{E}*to be a secure one-way proxy re-encryption scheme, or for Recrypt*^{0}_{E}*to be useful toward bootstrapping (as we will see below). Thus, depending on*^{0}_{E}*E*, WeakEncrypt*can be very simple { e.g., for some schemes, and in particular for the ideal-lattice-based scheme that we describe later, WeakEncrypt*_{E}*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*_{E}*E*can 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

*D*be_{E}*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*D*connected by a single_{E}*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*D*(¡)._{E}As before, let

*C*denote the set of circuits that_{E}*E*can compactly evaluate. We say that*E*is*bootstrappable*with respect to ¡ if*D*(¡)_{E}*µ C*For example, if ¡ includes the trivial gate and NAND,_{E}:*E*is bootstrappable with respect to ¡ if*C*contains_{E}*D*and the circuit formed by joining two copies of_{E}*D*with a NAND gate. Remarkably, as we will show, if there is a scheme_{E}*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 Recrypt*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.*^{0}_{E}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)}= (KeyGen*(*_{E}*d*)*;*Encrypt*(*_{E}*d*)*;*Evaluate*(*_{E}*d*)*;*Decrypt*(*_{E}*d*) ) that can handle all circuits of depth*d*with 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*D*(¡_{E}*; ±*) to refer to the set of circuits that equal a*±*-depth circuit with gates in ¡ augmented by*D*(copies of_{E}*D*become inputs to the_{E}*±*-depth circuit).KeyGen

*(*_{E}*d*) (*¸; d*). Takes as input a security parameter*¸*and a positive integer*d*. For ‘=’(*¸*) as it sets*:*

R | for | i 2 | [0 ; d] | ||

(sk pk_{i};) _{i}Ã KeyGen(_{E}¸) | |||||

R | ; sk)_{ij} | for | i 2 | [1 ; d]; j 2 [1; `] | |

sk _{ij}Ã Encrypt(pk_{E}_{i¡}_{1} |

where sk

_{i}_{1}*; : : : ;*sk*is the representation of sk*_{i`}*as elements of*_{i}*P*. It outputs the secret keysk

^{(d)}*Ã*sk_{0}and the public key pk^{(d)}*Ã*(*h*pk_{i}i;*h*sk*). Let*_{ij}i*E*^{(±)}refer to the sub-system that uses sk^{(±)}*Ã*sk_{0}and pk^{(±)}*Ã*(*h*pk_{i}i_{i2}_{[0;±]}*;**h*sk_{ij}i_{i2}_{[1;±]}) for*±**·**d*.Encrypt

*(*_{E}*d*) (pk^{(d)}*; ¼*). Takes as input a public key pk^{(d)}and a plaintext*¼**2 P*. It outputs aR

ciphertext

*Ã**Ã*Encrypt*(pk*_{E}*).*_{d}; ¼Decrypt

*(*_{E}*d*) (sk^{(d)}*; Ã*). Takes as input a secret key sk^{(d)}and a ciphertext*Ã*(which should be an encryption under pk_{0}). It outputs Decrypt*(sk*_{E}_{0}*; Ã*).Evaluate

*(*_{E}*±*) (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})*Ã*Augment*(*_{E}*±*) (pk^{(±)}*; C*ª_{±};*).*_{±}² Sets (

*C*_{±¡}_{1}*;*ª_{±¡}_{1})*Ã*Reduce*(*_{E}*±¡*1) (pk^{(±¡1)}*; C*_{±}^{y}_{¡}_{1}*;*ª^{y}_{±¡}_{1}).² Runs Evaluate

*(*_{E}*±¡*1) (pk^{(±¡1)}*; C*_{±¡}_{1}*;*ª_{±¡}_{1}).Augment

*(*_{E}*±*) (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_{±}*D*; call the resulting circuit_{E}*C*_{±}^{y}_{¡}_{1}. Let ª^{y}_{±¡}_{1}be the tuple of ciphertexts formed by replacing each input ciphertext*Ã**2*ª*by the tuple*_{±}*hh*sk*, where*_{±j}i; hÃ_{j}ii*Ã*WeakEncrypt_{j}Ã*(*_{E}*±¡*1)(pk^{(±¡1)}*; Ã*) and the_{j}*Ã*'s form the properly-formatted representation of_{j}*Ã*as elements of*P*. It outputs (*C*_{±}^{y}_{¡}_{1}*;*ª^{y}_{±¡}_{1}).Reduce

*(*_{E}*±*) (pk^{(±)}*; C*ª_{±}^{y};*). Takes as input a public key pk*^{y}_{±}^{(±)}, a tuple of input ciphertexts ª*(where each input ciphertext should be in the image of Encrypt*^{y}_{±}*(*_{E}*±*) ), and a circuit*C*_{±}^{y}*2**D*(¡_{E}*; ±*+ 1). It sets*C*to be the sub-circuit of_{±}*C*consisting of the first_{±}^{y}*±*levels. It sets*ª**to be the induced input ciphertexts of*_{±}*C*, where the ciphertext_{±}*Ã*_{±}^{(w)}associated to wire w at level*±*is set to Evaluate*(pk*_{E}_{±}; C_{±}^{(w)}*;*ª^{(}_{±}^{w}^{)}), where*C*_{±}^{(w)}is the sub-circuit of*C*with output wire_{±}^{y}*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

*C*of, say,_{d}*d*levels with gates in ¡. For each input wire*w*of*C*, there is an associated input ciphertext_{d}*Ã*encrypted under pk_{w}*. We are also given an encryption scheme*_{d}*E*that compactly evaluates circuits in*D*(¡)._{E}_{}Note that we have not assumed that

*E*can 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*C*by placing copies of_{d}*D*at the leaves of_{E}*C*(as in Augment), thereby constructing_{d}*C*_{d}^{y}_{¡}_{1}. Now, what are the input ciphertexts for our new circuit*C*_{d}^{y}_{¡}_{1}? Reconsider the algorithm Recrypt*. In Recrypt*^{0}_{E}*, we begin with a ciphertext*^{0}_{E}*Ã*_{1}encrypt-ing*¼*under pk_{1}for the single wire*w*, and an empty" circuit*C*_{1}(since Recrypt*doesn't actually evaluate any gates, it just generates a new encryption of the same plaintext). Our next step was to augment*^{0}_{E}*C*_{1}with the decryption circuit*D*to obtain_{E}*C*_{2}*Ã**D*. The input ciphertexts ª_{E}_{2}to*C*_{2}included the encrypted secret key bits, and the weakly encrypted bits of*Ã*_{1}. We then showed that the ciphertext generated by*Ã*_{2}*Ã*Evaluate*(pk*_{E}_{2}*; C*_{2}*;*ª_{2}), which is also associated to wire*w*, also encrypts*¼*, but now under pk_{2}.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 Recrypt*: the encrypted secret key (sk*^{0}_{E}*under pk*_{d}_{d¡}_{1}), and the re-encryption ciphertexts of*Ã*under pk_{w}_{d¡}_{1}. By the correctness of Recrypt, the ciphertext*now*associated to*w*(after performing Evaluate*) should encrypt the same plaintext as*_{E}*Ã*, but now under pk_{w}_{d¡}_{1}.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)*E*can evaluate not just the decryption circuit attached to*w*, but can evaluate a circuit containing one ¡-gate above*w*. Reduce outputs*C*_{d¡}_{1}and ciphertexts associated to*C*_{d¡}_{1}'s input wires. We have made progress, since*C*_{d¡}_{1}is one level shallower than*C*. We perform this entire process_{d}*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 Evaluate

*(*_{E}*±*) also operates correctly on ciphertexts output by Evaluate. (For*± < d*above, this is precisely what Evaluate*(*_{E}*±*) 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*¡

*. Then*

*E*

^{(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; wª_{out}; C_{d}; ) =_{d} D(0; w_{out}; C_{0}; ª_{0}) | (1) |

for every output wire

*w*of_{out}*C*_{0}(at level 0). First, when (*C*_{±}^{y}_{¡}_{1}*;*ª^{y}_{±¡}_{1})*Ã*Augment*(*_{E}*±*) (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*ª_{±};*)*_{±}*Ã*Reduce*(*_{E}*±*) (pk^{(±)}*; C*ª_{±}^{y};*), we have*^{y}_{±}*D*(*±; w; C*ª_{±}^{y};*) =*^{y}_{±}*D*(*±; w; C*ª_{±};*) for any wire at level at most*_{±}*±*. This follows from the correctness of Evaluate*over circuits in*_{E}*D*(¡), and the fact that circuits*C*and^{y}*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 Evaluate

*(*_{E}*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 Evaluate

_{E}(d) to C is dominated by at most s ¢ ` ¢ d applications of WeakEncrypt_{E}and at most s ¢ d applications of Evaluate_{E}to circuits in D_{E}(¡), 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 s^{0}¢ ` applications of Encrypt and at most s^{0}applications of Evaluate_{E}to circuits in D_{E}(¡), where s^{0}is the size of the pre-processed circuit. The complexity of Augment_{E}(±) (pk^{(±)}; C_{±}; ª_{±}) is dominated by replacing each ciphertext A2 ª_{±}by the ciphertexts hhsk_{±j}i; hÃ_{j}ii; generating the hÃ_{j}i's involves jW_{±}j ¢ ` applications of WeakEncrypt_{E}, where W_{±}is the set of wires at level ±. Summing over all ±, there are at most s^{0}¢ ` applications of WeakEncrypt_{E}.The complexity of Reduce

*(*_{E}*±*) (pk^{(±)}*; C*ª_{±}^{y};*) is dominated by the evaluation of*^{y}_{±}*C*_{±}^{(w)}for each*w**2**W*, which involves_{±}*jW*applications of Evaluate_{±}j*to circuits in*_{E}*D*(¡). Summing over all_{E}*±*, there are at most*s*such applications. The theorem follows.^{0}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*(*t*)^{0}; ²^{0}*-breaks the semantic security of E for t*(^{0}¼ t ¢ ` and ²^{0}¸ ²=`*d*+ 1)*, for ` as in. Proof.*(Theorem 4.2.3) Let (*E*)*be equivalent to*^{`}*E*, 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*(*t*)-breaks the semantic security of (^{00}; ²^{00}*E*)*for*^{`}*t*^{00}*¼**t*and*²*(^{00}¸ ²=*d*+ 1), from which the result follows.For*k**2*[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(sk _{i}^{0} | R | R | ; sk)_{ij}^{0} | ||

; pk)_{i}^{0} Ã KeyGen(_{E} ¸) | and sk _{ij}Ã Encrypt(pk_{E}_{i¡}_{1} |

In other words, for

*i**2*[1*; k*], sk*is the encryption (under pk*_{ij}_{i¡}_{1}) of the*j*-th bit of a*random*secret key sk*unrelated to sk*^{0}_{i}*. Game*_{i}*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*²*denote the adversary's advantage in Game_{k}*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 that*j²*_{k}¡ ²_{k}_{+1}*j ¸ ²=*(*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 pk*with pk. Also, if*_{k}*k < d*, it generates a dummy key pair (sk_{k}_{+1}*;*pk_{k}_{+1})*Ã*KeyGen*(*_{E}*¸*), sets*¼*_{0}*Ã*sk_{k}_{+1}and*¼*_{1}*Ã*sk^{0}_{k}_{+1}, and requests a challenge ciphertext (under*`*^{R }pk) encrypting either*¼*_{0}*; ¼*_{1}*2 P*. The challenger generates*¯**Ã f*0*;*1*g*and sends a tuple of ciphertexts*hÃ*encrypting the bits_{j}i*h¼*._{¯j}i*B*replaces its original tuple*h*sk_{(k+1)j}*i*with the tuple*hÃ*. One can verify that the public values are generated exactly as in Game_{j}i*k*+*¯*.*B*sends the public values to*A*. R Eventually,*A*requests a challenge ciphertext on*¼*_{0}or*¼*_{1}.*B*sets*b**Ã f*0*;*1*g*. If*k < d*, R R*B*sends the values*Ã*Encrypt_{j}Ã*(pk*_{E}*). If*_{d}; ¼_{bj}*k*=*d*,*B*generates random*¼ Ã P*and asks R the challenger for a challenge ciphertext on*¼*or_{b}*¼*. The challenger generates*¯**Ã f*0*;*1*g*and encrypts*¼*or_{b}*¼*accordingly, and*B*forwards the challenge to*A*.*A*sends a bit*b*.^{0}*B*sends bit*¯*^{0}*Ã**b**©**b*to the challenger. One can verify that the challenge is generated as in Game^{0}*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 Evaluate^{¤}*works as before, except that the implicit recryptions generate \refreshed" ciphertexts under the same public key.*_{E}¤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*A*have negligible advantage in the followingKDM-security game.**KDM-Security Game.**

R

Setup(

*¸; n*). The challenger sets (sk*pk*_{i};*)*_{i}*Ã*KeyGen(*¸*) for*i**2*[0*; n**¡*1] for integer*n*=R

poly(

*¸*). It chooses a random bit*b**Ã f*0*;*1*g*. If*b*= 0, then for*i**2*[0*; n**¡*1] and*j**2*[1*; `*],R

it sets sk

_{ij}*Ã*Encrypt*(pk*_{E}_{(i¡1) mod}*sk*_{n};*), where sk*_{ij}*is the*_{ij}*j*th \bit" of sk*. If*_{i}*b*= 1, it generates the sk*values as encryptions of random secret keys, unrelated to pk*_{ij}_{0}*; : : : ;*pk_{n¡}_{1}. 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*(sk_{0}*; : : : ;*sk_{n¡}_{1}). However,*when**E*is a bootstrappable encryption scheme,*A*can use the cycle of encrypted secret keys in our game to generate the encryption of*f*(sk_{0}*; : : : ;*sk_{n¡}_{1}) under any pk*, as long as*_{i}*f*can 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 (pk_{0}*;*sk_{0}), one can compute an encryption of sk_{0}under pk_{0}. 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 _{j} | ; r)_{j} | |||||||||||||

. Also, in KeyGen, one generates r Ã P | Ã Encrypt(_{E}d) (pk | |||||||||||||||

for j | [1 ; `], sets ^{0}¾ | H(r) ? sk_{0} | , and includes ( _{j} | ; ¾) 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)y}public key includes some additional information: an encryption of the the secret key sk_{0}, 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. Thistheorem 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)y}has a loop among (sk_{0}*;*pk_{0})*; : : : ;*(sk*pk*_{d};*), because*_{d}*E*^{(d)}*reveals direct encryptions of sk**under pk*_{i}_{i¡}_{1}*for**i 2*[1*; d*], and*E*^{(d)y}*also reveals an**indirect*encryption (*h*~~r~~i; ¾) of sk_{j}

_{0}*under pk**(\indirect," because encryption in*_{d}*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 sk_{0}.It perhaps the more surprising result. But the result is actually a simple consequence of the fact that: given a correctly constructed

*E*^{(d)}*public key, the reduction algorithm can generate an*^{y}*E*-encryption of sk_{0}under pk_{0}, as needed for the*E*public key. How do we generate the latter ciphertext? The reduction algorithm is given^{¤}*h*~~r~~i, an encryption of_{j}

*r*under pk*. It simply uses the leveled homomorphism and the circuit corresponding to the hash function*_{d}*H*to compute a ciphertext that encrypts*H*(*r*) from the ciphertext that encrypts*r*. Then, given that ciphertext and the value of*¾*=*H*(*r*)*?*sk_{0}, it computes a ciphertext that encrypts sk_{0}*in 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 sk_{0}(i.e., under*E*) under some public key pk*for*_{i}*i**¸*0, and we can use Recrypt operations to obtain a natural encryption of sk_{0}under pk_{0}. This ciphertext is an output of Evaluate*, but circuit privacy guarantees that the ciphertext is distributed as if it were output directly by Encrypt*_{E}*.*_{E}Although one can view (

*h*~~r~~i; ¾) as an encryption" of sk_{j}

_{0}, this encryption" function is not the usual encryption function and it might have a very complex decryption circuit, much more complex than*D*. In particular, we cannot assume that its decryption circuit is in_{E}*C*. This why we needed many (_{E}*d*) levels in the leveled scheme to recover sk_{0}, 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 (^{¤}*h*~~r~~i; ¾) in_{j}

*E*^{(d)}*to construct (homomorphically) an encryption of sk*^{y}_{0}under pk_{0}as 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

*B*that attacks the semantic security of

*E*

^{(d)}.

*B*will actually request

*`*+ 1 challenge ciphertexts; thus, the reduction loses a factor of

^{0}*`*+ 1 under the usual hybrid argument.

^{0} 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 ciphertextsR

_{`}ª, 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*

*¼*, which

_{b}*B*forwards to

*A*. Eventually, either

*A*queries some

*r*

^{0}*2 fr*

^{(0)}

*; r*

^{(1)}

*g*to the random oracle, or

*A*finishes with a guess

*b*. In the former case,

^{0}*B*sets

*b*so that

^{0}*r*=

^{0}*r*

^{(b0)}. In either case,

*B*sends

*b*as its guess to the challenger.

^{0}Let

*p*be the probability that*A*queries some*r*^{0}*2 fr*^{(0)}*; r*^{(1)}*g*to the random oracle.*B*'s simulation appears perfect to*A*if it does not query some*r*^{0}*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**¡**q*_{H}*=jPj*, where^{`0}*q*is the number of random oracle queries make by_{H}*A*. Overall*B*'s advantage in guessing*b*is at least (1^{0}*¡**p*)*²*+*p**¡**q*_{H}*=jPj*^{`0}*¸**²**¡**q*_{H}*=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*h*pk_{i}i_{i2}_{[0;±]},*h*sk_{ij}i_{i2}_{[1;±]},*h*~~r~~i_{j}

_{j2}_{[1;`}*0*_{]}, and*¾*=*H*(*r*)*?*sk_{0}. From*h*~~r~~i,_{j}

*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 sk_{0}from the encryptions of*H*(*r*) and*¾*(inverting the*?*operation). By assumption, these homomorphic operations take at most*d*levels. If it takes only*± < d*levels, and we obtain an encryption of sk_{0}under pk*, then we can perform Recrypt operations until we have the desired encryption of sk*_{d¡±}_{0}under pk_{0}. By circuit privacy, this ciphertext is distributed properly.*B*includes the encryption of sk_{0}under pk_{0}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

*¼*under pk

_{b}_{0}and forwards the result to

*A*.

*A*sends a guess

*b*, which

^{0}*B*forwards to the challenger.

Clearly,

*B*'s advantage is the same as*A*'s.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*R*, one simply determines whether t mod B = 0 mod*^{n}*B*. Instead, we base security on an*ideal**coset 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**£**a**2**I*for all*a; b**2**I*and*r**2**R*. 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*, B*, algorithm IdealGen, and an al-*_{I}R | pk | R | |

gorithm Samp _{1} that e±ciently samples R. The challenger sets b Ã f0; 1g and (B_{J}^{sk}; B_{J} | ) Ã | ||

R | pk | . If b = 1, it samples t | |

IdealGen( R; B ). If _{I}b = 0, it sets r Ã Samp_{1} | ( R) and t Ã r mod B_{J} | ||

uniformly from R mod B^{pk}. The problem: guess b given (t; B^{pk}). | |||

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 Samp_{1}. Of course, the ICP will be impossible if Samp_{1}also samples uniformly modulo*J*, but the security of our encryption scheme will rely on the ICP being hard for a clumpier" instantiation of Samp_{1}; the hardness of the problem depends on the particular instantiation of Samp_{1}. 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 B*of a ideal*_{I}*I**½**R*, and an algorithm IdealGen(*R;*B*) that outputs public and secret bases B*_{I}^{pk}*and B*_{J}^{sk}*of some (variable) ideal*_{J}*J*, such that*I*+*J*=*R*{ i.e.,*I*and*J*are relatively prime. We assume that if t*2**R*and B*is a basis for ideal*_{M}*M**½**R*, then the value t mod B*is unique and can be computed efficiently { i.e., the coset t +*_{M}*M*has a unique, efficiently-computable \distinguished representative" with respect to the basis B*. We use the notation*_{M}*R*mod B*to denote the set of distinguished representatives of*_{M}*r*+*M*over*r**2**R*, with respect to the particular basis B*of*_{M}*M*. We also use an algorithm Samp(B_{I}*;*x) that samples from the coset x +*I*.In the scheme, Evaluate takes as input a circuit

*C*whose gates perform operations modulo B*. For example, an Add*_{I}_{BI}gate in*C*takes two terms in*R*mod B*, and outputs a third term in*_{I}*R*mod B*, which equals the sum of the first two terms modulo*_{I}*I*.sk pk R

KeyGen(

*R;*B*). Takes as input a ring*_{I}*R*and basis B*of*_{I}*I*. It sets (B_{J}*;*B*)*_{J}*Ã*IdealGen(*R;*B*). The plaintext space*_{I}*P*is (a subset of)*R*mod B*. The public key pk includes*_{I}*R*, B*, B*_{I}^{pk}*, and Samp. The secret key sk also includes B*_{J}^{sk}*.*_{J}Encrypt(pk

*; ¼*). Takes as input the public key pk and plaintext*¼**2 P*. It sets*Ã*^{0}*Ã*Samp(B_{I}*; ¼*) and outputs*Ã**Ã**Ã*mod B^{0}^{pk}*. Decrypt(sk*_{J}*; Ã*). Takes as input the secret key sk and a ciphertext*Ã*. It outputs¼

*Ã*(*Ã*mod*B*^{sk}*) mod*_{J}*B*_{I}Evaluate(pk

*; C;*ª). Takes as input the public key pk, a circuit*C*in some permitted set*C*of circuits composed of Add_{E}_{BI}and Mult_{BI}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*C*when we consider correctness below. If desired, one could use di®erent arithmetic gates.)_{E}Add(pk

*; Ã*_{1}*; Ã*_{2}). Outputs*Ã*_{1}+*Ã*_{2}mod B^{pk}*.*_{J}Mult(pk

*; Ã*_{1}*; Ã*_{2}). Outputs*Ã*_{1}*£**Ã*_{2}mod B^{pk}*.*_{J}Concerning IdealGen, it is define the secret basis B

^{sk}*de¯nes a lattice*_{J}*L*(B^{sk}*) for a (possibly fractional) ideal that*_{J}*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-B

*circuit*_{I}*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-B*circuit. We say generalized circuit*_{I}*g*(*C*) of*C*is the circuit formed by replacing*C*'s Add_{BI}and Mult_{BI}operations with addition `+' and multiplication `*£*' in the ring*R*. Here are a few more definitions relevant to below, which concerns correctness. (*X*_{Enc}and*X*_{Dec}). Let*X*_{Enc}be the image of Samp. Notice that all ciphertexts output by Encrypt are in*X*_{Enc}+*J*. Let*X*_{Dec}equal*R*mod B^{sk}*, the set of distinguished representatives of cosets of*_{J}*J*wrt the secret basis B^{sk}*.*_{J}Definition 5.2.4 (Permitted Circuits). Let

*C*=

_{E}^{0}*fC*:

*8*(

*x*

_{1}

*; : : : ; x*)

_{t}*2 X*

_{Enc}

*(*

^{t}; g*C*)(

*x*

_{1}

*; : : : ; x*)

_{t}*2 X*

_{Dec}

*g*

In other words,

*C*is the set of mod-B_{E}^{0}*circuits that, when generalized, the output is always in*_{I}*X*_{Dec}if the inputs are in*X*_{Enc}. (The value*t*will of course depend on*C*.) If*C*_{E}*µ C*, we say that_{E}^{0}*C*is a set of permitted circuits._{E}*Ã*is a

*valid ciphertext*wrt

*E*public key pk and permitted circuits

*C*if it equals Evaluate(pk

_{E}*; C;*ª) for some

*C*

*2 C*, where each

_{E}*Ã*

*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 C

_{E}. Theorem 5.2.6. Assume C_{E}is a set of permitted circuits containing the identity circuit. E is correct for C_{E}{ i.e., Decrypt correctly decrypts valid ciphertexts. CHAPTER 5. AN ABSTRACT SCHEME BASED ON THE IDEAL COSET PROBLEM61*Proof.*For ciphertexts ª =

*fÃ*

_{1}

*; : : : ; Ã*,

_{t}g*Ã*=

_{k}*¼*+

_{k}*i*+

_{k}*j*, where

_{k}*¼*,

_{k}2 P*i*,

_{k}2 I*j*,

_{k}2 J*and*

*¼*+

_{k}*i*

_{k}*2*

*X*

_{Enc}, we have

Evaluate(pk

*; C;*ª) =*g*(*C*)(ª) mod B^{pk}_{J}*2**g*(*C*)(*¼*_{1}+*i*_{1}*; : : : ; ¼*+_{t}*i*) +_{t}*J*If

*C**2 C*, we have_{E}*g*(*C*)(*X*_{Enc}*; : : : ; X*_{Enc})*2**X*_{Dec}and thereforeDecrypt(sk

*;*Evaluate(pk*; C;*ª)) =*g*(*C*)(*¼*_{1}*+**i*_{1}*; : : : ; ¼*+_{t}*i*) mod_{t}*B*_{I}=

*g*(*C*)(*¼*_{1}*; : : : ; ¼*) mod_{t}*B*_{I}=

*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*)(*x*_{1}*; : : : ; x*) of the output ciphertext is small (i.e., lies inside_{t}*X*_{Dec}) when the input ciphertexts are in the image of Encrypt*. When we begin to instantiate the abstract scheme with lattices and give geometric interpretations of*_{E}*X*_{Enc}*and**X*_{Dec}, the problem of maximizing*C*will have a geometric °avor._{E}Again, we note the rather confusing fact that

*C*automatically" reduces the result modulo B*, since it uses mod-B*_{I}*gates. It does not particularly matter how these mod-B*_{I}*gates 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 B*_{I}*at the end of the computation.*_{I}*C*'s mod-B*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-B*_{I}*gates, 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.*_{I}**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 B*), we provide a simple proof of semantic security based on the ICP. Samp(B*_{I}_{I}*;*x). Run r*Ã*Samp_{1}(*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

*;*B

^{pk}

*).*

_{J}*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}

*; ¼*

_{1}

*2 P*,

*B*sets a bit

*¯*

*Ã f*0

*;*1

*g*and sends back

*Ã*

*Ã*

*¼*+ t

_{¯}*£*s mod B

*. A sends back a guess*

_{J}*¯*, and

^{0}*B*guesses

*b*

^{0}*Ã*

*¯*

*©*

*¯*.

^{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 Samp_{1}and j*2**J*. So,*Ã**Ã**¼*+ t_{¯}*£*s =*¼*+ r_{¯}*£*s mod B^{pk}*; the ciphertext is thus well-formed. In this case*_{J}*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 B^{pk}*that is independent of*_{J}*¯*. 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.