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 selfimplanting,
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, KDMSecure Boots trappable Encryption,
The Ideal Coset
INTRODUCTION
Bootstrappable
Encryption
Assume we have an encryption scheme E
that compactly evaluates some set of circuits C_{E}. We want to use
E to construct a homomorphic encryption scheme that can handle arbitrary circuits. In this Chapter we
prove a fundamental result: that if C_{E}
contains (slight augmentations of) E's
own decryption circuit D_{E} { 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 D_{E};
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 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 keydependentmessage (KDM) security, specifically circularsecurity { 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 selfreferential 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_{i}, we reencrypt
it under pk_{i}_{+1}
and then homomorphically apply the
decryption circuit to the result, using the secret key sk_{i} that is 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_{i}, but within homomorphic
encryption under pk_{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 f0; 1g
and D_{E} is a boolean
circuit in C_{E}. Let (sk_{1}; pk_{1}) and (sk_{2}; pk_{2}) be two E keypairs. Let Ãƒ_{1} be an encryption of 1/4 2 P under
pk_{1}. Let sk_{1j} be an encryption of the jth 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}
; hsk_{1j}i; Ãƒ_{1}).
R
Set Ãƒ_{1j} Ãƒ Encrypt_{E} (pk_{2}; Ãƒ_{1j}) where Ãƒ_{1j} is the jth bit of Ãƒ_{1}
Set Ãƒ_{2} Ãƒ Evaluate_{E}(pk_{2};
D_{E}; hhsk_{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_{E}(sk_{1}; Ãƒ_{1}) ! ¼. The Recrypt algorithm implies a proxy oneway
reencryption scheme [19]. Roughly speaking, a oneway proxy reencryption
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 hsk_{1j}i, the encrypted secret key.[2] Strictly speaking,
the security model for proxy reencryption 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_{E} is an
algorithm such that the image of WeakEncrypt_{E}
(pk; ¼) is always a subset of the
image of Encrypt_{E} (pk; ¼). Then we can replace the first step
of Recrypt_{E} with:
R
Set Ãƒ_{1j} Ãƒ WeakEncrypt_{E}
(pk_{2}; Ãƒ_{1j}) where Ãƒ_{1j} is the jth bit of Ãƒ_{1}
Let us call this relaxation Recrypt^{0}_{E}.
The main point of this relaxation is that WeakEncrypt does not need to be
semantically secure for Recrypt^{0}_{E}
to be a secure oneway proxy reencryption scheme, or for Recrypt^{0}_{E} to be useful
toward bootstrapping (as we will see below). Thus, depending on E, WeakEncrypt_{E} can be very simple { e.g., for some schemes, and in
particular for the ideallatticebased 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
can evaluate. However, it will affect the eventual computational complexity of our scheme, since it will require less
computation to apply the decryption circuit homomorphically 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 nonuniform decryption circuits,
where the ciphertext is hardwired" 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_{E} 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 D_{E}
connected by a single g gate (the
number of copies equals the number of inputs to g) a gaugmented
decryption circuit." We denote the set of gaugmented decryption circuits, g 2 ¡, by D_{E}(¡).
As before, let C_{E}
denote the set of circuits that E can
compactly evaluate. We say that E is bootstrappable with respect to ¡ if D_{E} (¡) Âµ C_{E} :For example, if ¡ includes the trivial gate and
NAND, E is bootstrappable with
respect to ¡ if C_{E}
contains D_{E} and the
circuit formed by joining two copies of D_{E}
with 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 Recrypt^{0}_{E} 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)} = (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_{E}
(copies of D_{E} become
inputs to the ±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_{i}; pk_{i}) Ãƒ KeyGen_{E}(¸)


R

; sk_{ij})

for

i 2

[1; d]; j 2 [1; `]


sk_{ij} Ãƒ Encrypt_{E}(pk_{i¡}_{1}

where sk_{i}_{1}; : : : ; sk_{i`} is the representation of sk_{i} as elements of P.
It outputs the secret key
sk^{(d)} Ãƒ sk_{0} and the public key pk^{(d)} Ãƒ (hpk_{i}i; hsk_{ij}i). Let E^{(±)} refer to the subsystem that uses sk^{(±)} Ãƒ sk_{0} and pk^{(±)}
Ãƒ (hpk_{i}i_{i2}_{[0;±]}; hsk_{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 a
R
ciphertext Ãƒ Ãƒ Encrypt_{E} (pk_{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_{E}(sk_{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_{E} ; call the resulting
circuit C_{±}^{y}_{¡}_{1}.
Let Âª^{y}_{±¡}_{1}
be the tuple of ciphertexts formed by replacing each input ciphertext Ãƒ 2
Âª_{±} by the tuple hhsk_{±j}i;
hÃƒ_{j}ii, where Ãƒ_{j}
Ãƒ WeakEncrypt_{E}(±¡1)
(pk^{(±¡1)}; Ãƒ_{j}) and the Ãƒ_{j}'s form the
properlyformatted representation of Ãƒ
as elements of P. It outputs (C_{±}^{y}_{¡}_{1}; Âª^{y}_{±¡}_{1}).
Reduce_{E}(±) (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 Encrypt_{E}(±) ), and a circuit C_{±}^{y}
2 D_{E}(¡; ± + 1). It sets C_{±} to be the subcircuit 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 Evaluate_{E} (pk_{±};
C_{±}^{(w)}; Âª^{(}_{±}^{w}^{)}), where C_{±}^{(w)}
is the subcircuit of C_{±}^{y}
with output wire w, and Âª^{(}_{±}^{w}^{)} are
the input ciphertexts for C_{±}^{(w)}. It outputs (C_{±}; Âª_{±}).
Highlevel review of the Evaluate algorithm. We
are given a circuit C_{d} of,
say, d levels with gates in ¡. For
each input wire w of C_{d}, there is an associated
input ciphertext Ãƒ_{w}encrypted under pk_{d}.
We are also given an encryption scheme 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_{d} by placing copies of D_{E} at the leaves of C_{d} (as in Augment), thereby
constructing C_{d}^{y}_{¡}_{1}.
Now, what are the input ciphertexts for our new circuit C_{d}^{y}_{¡}_{1}? Reconsider the
algorithm Recrypt^{0}_{E}.
In Recrypt^{0}_{E},
we begin with a ciphertext Ãƒ_{1}
encrypting ¼ under pk_{1}
for the single wire w, and an
empty" circuit C_{1} (since
Recrypt^{0}_{E}
doesn't actually evaluate any gates, it just generates a new encryption of the
same plaintext). Our next step was to augment C_{1} with the decryption circuit D_{E} to obtain C_{2}
Ãƒ D_{E}.
The input ciphertexts Âª_{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_{E}(pk_{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^{0}_{E}: the encrypted secret key (sk_{d} under pk_{d¡}_{1}), and the
reencryption ciphertexts of Ãƒ_{w}
under pk_{d¡}_{1}. By
the correctness of Recrypt, the ciphertext now
associated to w (after performing
Evaluate_{E}) should encrypt
the same plaintext as Ãƒ_{w},
but now under pk_{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_{d}.
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 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)} compactly 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_{out} of 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}; Âª^{y}_{±}), we have D(±;
w; C_{±}^{y}; Âª^{y}_{±})
= D(±; w; C_{±}; Âª_{±})
for any wire at level at most ±. This
follows from the correctness of Evaluate_{E}
over circuits in D (¡), and the fact
that circuits C^{y} 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
fanin 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 preprocessing
step to ensure that all wires in the circuit connect gates at consecutive
levels; clearly, this step increases the number of wires in the
circuit by at most a multiplicative factor of d. It remains to prove that, for
the preprocessed 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 preprocessed 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};
Âª^{y}_{±}) is
dominated by the evaluation of C_{±}^{(w)} for each w 2 W_{±}, which involves jW_{±}j
applications of Evaluate_{E}
to circuits in D_{E} (¡).
Summing over all ±, there are at most
s^{0} 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 (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^{00}; ²^{00})breaks
the semantic security of (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 realworld 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_{E}(pk_{i¡}_{1}

In other words, for i 2 [1;
k], sk_{ij} is the
encryption (under pk_{i¡}_{1})
of the jth bit of a random secret key sk^{0}_{i} unrelated to sk_{i}. 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 ²_{k}
denote 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 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_{k} with pk. Also, if 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 ¯ Ãƒ
f0; 1g and sends a tuple of ciphertexts hÃƒ_{j}i encrypting the bits h¼_{¯j}i. B
replaces its original tuple hsk_{(k+1)j}i with the tuple hÃƒ_{j}i. 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} Ãƒ Encrypt_{E} (pk_{d}; ¼_{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 B
forwards the challenge to A. A sends a bit b^{0}. B sends
bit ¯^{0} Ãƒ b
© b^{0}
to 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 KDMSecure
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 selfloop in this example) of encrypted
secret keys rather than an acyclic chain. It is clear that E^{¤} is correct: the recursive algorithm Evaluate_{E}¤ 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 KDMsecure { i.e., secure when the
adversary can request the encryptions of keydependent
messages, such as the secret key itself. Typically, when we prove an
encryption scheme semantically secure, there is not an obvious attack when the adversary is given the
encryption of a keydependent message.[7] However, KDMsecurity 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 KDMsecurity. Our initial approach had actually been to use E^{¤} (with the selfloop), and
assume, or try to prove, KDMsecurity.Let us review (a restriction of) the
definition of KDMsecurity. We will say a scheme E is KDMsecure
if all polynomialtime adversaries A
have negligible advantage in the following
KDMsecurity game.
KDMSecurity Game.
R
Setup(¸; n). The challenger sets (sk_{i}; pk_{i}) Ãƒ 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 sk_{ij} Ãƒ Encrypt_{E} (pk_{(i¡1)
mod} _{n}; sk_{ij}), where sk_{ij} is the jth \bit" of sk_{i}. If b = 1,
it generates the sk_{ij}
values as encryptions of random secret keys, unrelated to pk_{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 KDMsecurity 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_{i}, as long as 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 KDMsecure and also bootstrappable with respect to a
universal set of gates ¡. Then, E ^{¤}, obtained from E as described
above (with the selfloop), 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 selfloop.
Absent proof of KDMsecurity in the plain model, one way to obtain fully
homomorphic encryption from bootstrappable encryption is simply to assume that the underlying
bootstrappable encryption scheme is also KDMsecure. 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 bootstrappability { we do not see any actual attack on
a bootstrappable encryption scheme that provides a selfencrypted key.
Fully Homomorphic Encryption from Bootstrappable
Encryption in the Random Oracle Model
Above, we constructed a fully homomorphic encryption E^{¤} from a bootstrappable
encryption scheme E basically by
adding a selfloop" { 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
KDMsecure { in particular, under the assumption that it is safe" to
reveal a direct encryption of a secret key under its own public key (as
opposed to some possiblylessrevealing nonidentity 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

; r_{j})


. Also, in KeyGen, one generates r
Ãƒ P

Ãƒ Encrypt_{E}(d) (pk


for
j

[1; `^{0}], sets ¾

H(r)
? sk_{0}

, and includes (

; ¾)
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
onetime 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. This
theorem basically just states the previously known result that it is
easy to construct a KDMsecure 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_{d}; pk_{d}),
because E^{(d)} reveals direct
encryptions of sk_{i} under
pk_{i¡}_{1} for
i 2 [1; d], and E^{(d)y} also reveals an indirect encryption (hr_{j}i;
¾) of sk_{0} under pk_{d} (\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 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)} ^{y}
public key, the reduction algorithm can generate an Eencryption 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 hr_{j}i, an encryption of
r under pk_{d}. It simply uses the leveled homomorphism and the
circuit corresponding to the hash function 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_{i} for 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_{E} , but circuit privacy
guarantees that the ciphertext is distributed as if it were output directly by
Encrypt_{E}.
Although one can view (hr_{j}i;
¾) as an encryption" of sk_{0}, this encryption" function
is not the usual encryption function and it might have a very complex
decryption circuit, much more complex than D_{E}
. In particular, we cannot assume that its decryption circuit is in C_{E}. This why we needed many (d) levels in the leveled scheme to
recover sk_{0}, and could not immediately use a selfloop 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 (hr_{j}i; ¾) in E^{(d)} ^{y} to
construct (homomorphically) an encryption of sk_{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 `^{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 r^{0} 2 fr^{(0)}; r^{(1)}g to the random oracle, or A
finishes with a guess b^{0}.
In the former case, B sets b^{0} so that r^{0} = r^{(b0)}. In
either case, B sends b^{0} as its guess to the
challenger.
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^{`0}, where q_{H} is the number of random
oracle queries make by A. Overall B's advantage in guessing b^{0} is at least (1 ¡ 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 hpk_{i}i_{i2}_{[0;±]}, hsk_{ij}i_{i2}_{[1;±]}, hr_{j}i_{j2}_{[1;`}0_{]},
and ¾ = H(r) ? sk_{0}. From hr_{j}i, 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_{d¡±}, then we can perform
Recrypt operations until we have the desired encryption of sk_{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 ¼_{b} under
pk_{0} and forwards the result to A.
A sends a guess b^{0}, which 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 homomorphically 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 latticebased cryptosystems is typically dominated by a
simple operation, such as an easily parallelizable matrixvector multiplication
(in contrast to, say, RSA, where decryption involves exponentiation, an
operation not even known to be in NC). We begin describing the
ideallatticebased 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
serveraided 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^{n}, one
simply determines whether t mod B = 0 mod 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_{I} , algorithm IdealGen,
and an al
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_{I} ). If 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_{I} of a ideal I ½
R, and an algorithm IdealGen(R; B_{I}
) that outputs public and secret bases B^{pk}_{J} and B^{sk}_{J}
of 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 B_{M} is a basis for ideal M ½
R, then the value t mod B_{M} is unique and can be
computed efficiently { i.e., the coset t + M
has a unique, efficientlycomputable \distinguished representative" with
respect to the basis B_{M} .
We use the notation R mod B_{M} to denote the set of
distinguished representatives of r + M over r 2 R, with respect to the particular basis B_{M} of 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_{I} . For example, an Add_{BI} gate in C takes
two terms in R mod B_{I} , and outputs a third term
in R mod B_{I} , which equals the sum of the first two terms modulo I.
sk pk R
KeyGen(R; B_{I} ). Takes as input a ring R and basis B_{I} of I. It
sets (B_{J} ; B_{J}
) Ãƒ IdealGen(R; B_{I} ). The
plaintext space P is (a subset of) R mod B_{I} . The public key pk includes R, B_{I} , B^{pk}_{J}, and Samp. The secret key
sk also includes B^{sk}_{J}.
Encrypt(pk; ¼). Takes as input
the public key pk and plaintext ¼ 2 P. It sets Ãƒ^{0} Ãƒ Samp(B_{I} ; ¼) and outputs Ãƒ Ãƒ Ãƒ^{0}
mod B^{pk}_{J}.
Decrypt(sk; Ãƒ). Takes as input the
secret key sk and a ciphertext Ãƒ. It
outputs
¼
Ãƒ (Ãƒ mod B^{sk}_{J}) mod B_{I}
Evaluate(pk; C; Âª). Takes as
input the public key pk, a circuit C
in some permitted set C_{E}
of circuits composed of Add_{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_{E} when
we consider correctness below. If desired, one could use di®erent arithmetic
gates.)
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}_{J} de¯nes a lattice L(B^{sk}_{J}) 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 modB_{I}
circuit 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 modB_{I} circuit. We say generalized
circuit 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}_{J}, the set of distinguished representatives of cosets of
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_{E}^{0}
is the set of modB_{I}
circuits that, when generalized, the output is always in X_{Dec} if the inputs are in X_{Enc}. (The value t
will of course depend on C.) If C_{E} Âµ C_{E}^{0}, we say that C_{E} is a set of permitted circuits.
Ãƒ is a valid ciphertext wrt E public key pk and permitted circuits C_{E} if it equals Evaluate(pk; C; Âª) for some C 2 C_{E}, 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 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_{k}, where ¼_{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_{E}, we have g(C)(X_{Enc}; : : : ; X_{Enc}) 2 X_{Dec}
and therefore
Decrypt(sk;
Evaluate(pk; C; Âª)) = g(C)(¼_{1} + i_{1}; : : : ; ¼_{t} + i_{t}) mod B_{I}
=
g(C)(¼_{1}; : : : ; ¼_{t}) mod 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_{t}) of the output
ciphertext is small (i.e., lies inside X_{Dec})
when the input ciphertexts are in the image of Encrypt_{E}. When we begin to instantiate the abstract scheme with
lattices and give geometric interpretations of X_{Enc} and X_{Dec}, the problem of
maximizing C_{E} will have a
geometric °avor.
Again, we note the rather confusing fact that C automatically" reduces the result modulo B_{I} , since it uses modB_{I} gates. It does not
particularly matter how these modB_{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. C's
modB_{I} 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 modB_{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.
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_{I}
), we provide a simple proof of semantic security based on the ICP. Samp(B_{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 components 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 ¯ Ãƒ f0;
1g and sends back Ãƒ Ãƒ
¼_{¯} + t £ s mod B_{J} . A sends back a guess ¯^{0}, and 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}_{J}; the
ciphertext is thus wellformed. 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 B^{pk}_{J}
that 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. PublicKey Encryption in a
Multiuser Setting: Security Proofs and Improvements. In Proc. of Eurocrypt '00, pages 259{274. Springer, 2000.
2. J. Benaloh. Veri¯able secretballot elections. Ph.D. thesis, Yale
Univ., Dept. of Comp. Sci., 1988.
3. J. Black, P. Rogaway, and T. Shrimpton. Encryptionscheme security in
the presence of keydependent 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 cryptography. 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, 702722. ACM, 2001. Preliminary version in Crypto
1997.
6. D. Boneh, E.J. Goh, and K. Nissim. Evaluating 2DNF formulas on
ciphertexts. TCC '05, LNCS 3378, pp. 325{341.
7. D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky. CircularSecure
Encryption from Decision Di±eHellman. In Proc.
of Crypto '08, LNCS 5157, pages 108{125.
8. D. Boneh and R. Lipton. Searching for Elements in BlackBox 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 worstcase to averagecase
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. Chosenciphertext secure proxy
reencryption. In Proc. of ACM CCS '07.
15. R. Canetti, H. Krawczyk, and J.B. Nielsen. Relaxing
chosenciphertext security. In Proc. of
Crypto '03, pages 565{582. Springer, 2003.