Cryptographic Program Obfuscation
Sanjam Garg
University of California, Berkeley
February 2016

Chapter 1

Executive Summary
Cryptography is the “black magic,” of theoretical computer science, enabling tasks that often seemparadoxical or simply impossible. For example, consider the goal of enciphering data in a way
such that only the designated recipient can make sense of it. Even this seemingly simple taskof encryption has eluded mankind for centuries. Wars have been lost because of weaknesses inencryption methods, thought to be secure. Modern cryptography has provided us with encryption
schemes based on sound mathematical principles giving very strong assurances of security. In fact,
now we have a multitude of cryptographic primitives enabling far more ambitious goals than justencryption.
Beyond encryption, cryptographers have long wondered if it possible to obfuscate computer
programs. More specifically, can we make computer programs “unintelligible” while preserving theirfunctionality? Here, “unintelligibility” requirement means that the obfuscated program should hide
the secrets that were embedded inside the original program. This is a very stringent requirement
requiring that no automated “deobfuscator” can derive the secrets that we intend to hide inside
the program. On the other hand, “preserving its functionality” means that the obfuscated program
should be fully executable and have the same input-output behavior as the original program.
Next we explain the “unintelligibility” requirement with the example of how obfuscation canbe used to convert a private key encryption scheme to a public key one. This classical applicationof obfuscation was first envisioned by Diffie and Hellman [DH76] with the goal of realizing the firstpublic key encryption scheme. In a private key encryption scheme it is the same private key thatenables both the tasks of encryption and decryption. So given the secret key one can encrypt aplaintext and obtain a ciphertext. The same secret key can then be used to decrypt the generated
ciphertext and recover the original plaintext. On the other hand, in the case of a public key
encryption, encryption is done using a public key, enabling encryption by anyone while decryption
is done using the corresponding private key. Diffie and Hellman noticed that an obfuscation of the
program that does the encryption, with the secret key embedded inside it, can be published as the
public key. This would enable encryption by all while still preserving decryption to the holder ofthe secret key. This allows for a generic method for converting a private key encryption scheme
into a public key one. In this example, obfuscation attempts to hide the private key inside theprogram.
As another example consider the goal of secure software patching, something that is typicallynot considered to be in the domain of cryptography. Consider for instance the security software
Norton. Let’s say that one day Norton’s team of software security engineers, finds a bug in theirsoftware and releases a patch to fix this bug. An attacker could reverse-engineer this newly released
patch and figure out what the original bug was. Widespread deployment of software patches takes
1

a lot of time, certainly a few days and sometimes even weeks. Knowledge of this bug allows an
attacker to attack such unpatched machines on the Internet. This actually turns to be a real
security problem that exists when software patches are released today. Obfuscation offers a very
elegant solution to this problem. If instead of releasing the patch in its unobfuscated form, Norton
was to release the patch in its obfuscated form; then that would keep the patch “unitelligible.” Herethe security bug is the secret which the obfuscation will now be protecting. Of course, once large
scale deployment of the obfuscated patch has completed, Norton could move to a more efficient
unobfuscated version of the patch.
Defining obfuscation rigorously turns out to be somewhat involved. For example, the requirement of maintaining functionality implicitly places some limitations on what obfuscation can accomplish. In particular, consider a program that on a specified input prints its own code. No
obfuscation method that preserves functionality can successfully hide the code of this program.
The most natural way to define unintelligibility of obfuscation is to require that giving theobfuscated program is as good as giving black-box oracle access to the program [BGI+ 01]. Morespecifically, whatever an attacker could learn from the obfuscated program could have been learned
using just oracle access to the program implementing that function. However, this notion of obfuscation, has been shown to be impossible albeit only for some unnatural class of circuits. An alternative
weaker notion of obfuscation is indistinguishability obfuscation [BGI+ 01, GR07, GGH+ 13b]. This
notion only requires computational indistinguishability of obfuscations of two circuits computing
the exact same functionality. In particular, if two circuits C1 and C2 are such that C1 (x) = C2 (x)for all x then this definition requires that the obfuscation of C1 , namely O(C1 ), is computationallyindistinguishable from O(C2 ).
Given the impossibility results of Barak et al. [BGI+ 01], cryptographers were very skeptical
about the existence of general obfuscation results. However, recent works [GGH+ 13b] provide
plausible candidate constructions based on multilinear maps [BS02, GGH13a]. These works provide
the indistinguishability obfuscation notion. At first sight, this might seem week. Goldwasser
and Rothblum [GR07], provide strong philosophical argument supporting the meaningfulness of
this notion. In particular they show that (efficiently computable) indistinguishability obfuscators
achieve the notion of Best-Possible Obfuscation: Informally, a best-possible obfuscator guarantees
that its output hides as much about the input circuit as any other circuit (of a certain size).
Current obfuscation methods are prohibitively inefficient. Furthermore, our understanding of
the security of these constructions is limited. Next we provide an overview of the techniques used
to construct multilinear maps, obfuscation and the resulting applications. Details will be provided
in the main body of this report.

1.1

Technical Insights - Multilinear Maps

In his breakthrough result, Gentry [Gen09] constructed a fully-homomorphic encryption schemethat enabled arbitrary computation on encrypted data without allowing for decryption. However
for many applications, the ability to perform arbitrary computation on encrypted data along withthe ability to check if two ciphertexts encrypt the same message is essential. In his scheme, Gentry
relied on “noise” to hide messages. The presence of noise, which helps hide messages without
restricting arbitrary computation on them, seems to be in conflict with the goal of equality checking.
Recent candidate constructions [GGH13a, CLT13, GGH15] overcome this obstacle by introducing
techniques that enable equality testing even in the presence of noise. Next we present an overview
of how this is achieved in the GGH construction [GGH13a].
The GGH constructions work in polynomial rings and use principal ideals in these rings (and2their associated lattices). In a nutshell, an instance of the GGH construction has a secret short ringelement g ∈ R, generating a principal ideal I = hgi ⊂ R. In addition, it has an integer parameterq and another secret z ∈ R/qR, which is chosen at random (and hence is not small).
Think of a term like g x in a discrete-log system as an “encoding” of the “plaintext exponent” x.
In GGH, the role of the “plaintext exponents” is played by the elements in R/I (i.e. cosets of I),
which is “encoded” via division by z in Rq . In a few more details, GGH system provides many levelsof encoding, where a level-i encoding of the coset eI = e + I is an element of the form c/zi mod q
where c ∈ eI is short. It is easy to see that such encodings can be both added and multiplied,
so long as the numerators remain short. This enables the goal of allowing for computation on
the hidden “plaintext exponents.” Additionally, GGH scheme publishes a “zero testing parameter”
that enables to test if two elements encode the same coset at a given level, without violating security(e.g., it should still be hard to compute x from an encoding of x at higher levels). Namely, GGH add
to the public parameters an element of the form pzt = h · z κ /g mod q for a not-too-large h, whereκ is the level of multilinearity. Multiplying an encoding of zero (at the κth level) by pzt (mod q)
yields a small element, while multiplying an encoding of a non-zero by pzt (mod q) yields a large
element. Hence one can distinguish zero from non-zero, and by subtraction one can distinguish two
encodings of the same element from encodings of two different elements.
Building on the GGH multilinear maps [CLT13, CLT15, GGH15] alternate constructions ofmultilinear maps have been obtained. The security of these constructions also relies on new assumptions. The suggested candidate constructions of multilinear map constructions also supported
randomization of encodings. Several attacks have been shown in this setting [CHL+ 15, CLR15,
CLLT15, CFL+ 16]. However, typical obfuscation candidate constructions, besides [GLSW15], do
not reply on encodings of zero. Therefore, obfuscation constructions remain unaffected by these
attacks and so we do not include discussion about these zeroing attacks in this report. We remark that very recent attacks [JHC16, MA16] are applicable for the setting where zero’s are notprovided. These attacks can be prevented using the parameters carefully. Finally, a very recent
attack [MSZ16] provides an attack that works directly on certain obfuscation candidates specifically for the GGH construction. We note that this attack isn’t actually known to break the known
candidates but points to something that we should worry about. Furthermore, we need to develop
defences that would avoid these attacks in a provable sense. We don’t consider this attack in thisreport.

1.2

Technical Insights - Obfuscation

As stated, multilinear maps enable arbitrary computing on encrypted data along with ability tocheck if two ciphertexts encrypt the same message. Obfuscation is more general and requires
revealing specific functions of encrypted data already which program obfuscation [BGI+ 01, BGI+ 12].
Positive results for obfuscation, without multilinear maps, have been limited to simple classes ofprograms such as point functions [Can97, CMR98, LPS04, Wee05, CD08, BC10], testing hyperplane
membership [CRV10] and a few other simple programs [HRsV07, HMLS07, Had10, CCV12]. On
the other hand, multilinear maps based construction work for a arbitrary programs [GGH+ 13b].
This new construction, the focus of this report, provides a realization of the indistinguishability
obfuscation notion. Many follow up works have improved these candidate construction in several
ways [BR14b, BGK+ 14, AGIS14, MSW14, BV15, AJ15, BMSZ15, AJS15]
Technically speaking the obfuscation construction is obtained by encrypting the program insuch a manner such that computing the encrypted program on an input is same as evaluating an
input specific polynomial on the encrypted values and checking if it evaluates to zero or not. In
3this setting the polynomial for each input is different and this is what enables computation for any
input choice. Security itself is based on the fact that any other (bounded degree) polynomial thatcan be computed on the encrypted data evaluates to something random and hence doesn’t reveal
anything.
Note on VBB obfuscation. Even though Virtual black box obfuscation [BGI+ 01] (VBB in
short) is impossible in general it various flavors of it have been realized for special functions suchas conjunctions [BR13, BR14a, BVWW16] and for general circuits in idealized models [BR14b,
BGK+ 14]. Our inability to provide more general results can be explained by the negative resultsof [BGI+ 01], who showed that there exist families of “unobfuscatable” functions for which the VBB
definition is impossible to achieve in the plain model. However this result does not apply to thesetting of generic multilinear attacks, in which case the VBB notion can actually be realized [BR14b,
BGK+ 14]. These works provide evidence that no algebraic attacks (that respect multilinear maps)
against these candidate constructions leak anything beyond what could be leaked in a black-box
manner and provide heuristic evidence that these obfuscation mechanisms offer strong security for“natural” functions.

1.3

Technical Insights - Applications

Obfuscation radically enhances our tool set and opens a floodgate of applications. One-roundmulti-party key-exchange is a classical example. Diffie and Hellman in their seminal paper [DH76]
provided the first construction of a one-round two-party key-exchange protocol which was thengeneralized to the three party setting by Joux [Jou00] using Weil and Tate pairings. Obfuscation
can be used realize a result that works for arbitrary number of parties [BZ14, GPSZ16]. Anothervery interesting application of obfuscation has been in demonstrating the hardness of finding Nash
Equilibrium [BPR15, GPS15]. Next we describe at length the various applications of obfuscation
to the problem of enabling flexible encryption.
How flexible can we make access to encrypted data? Enabling encryption by arbitrary
parties motivated the invention of public key encryption [DH76, RSA78]. However, enabling finegrained decryption capabilities has remained an elusive goal![Sha84, SW05, GPSW06]. Shamir [Sha84]
proposed the problem of non-interactively associating identities with encrypted data, and later Sahai and Waters [SW05] asked if an encrypter at the time of encryption can non-interactively embedany arbitrary decryption policy into his ciphertext. All primitive described above enabled encrypters with the ability to specify who can decrypt. However at the same time these tools do
not provide for a mechanism to specific what a decrypter can learn. A decrypter learns either theentire message or nothing about it. More specifically, in functional encryption [BSW11, O’N10],
ciphertexts encrypt inputs x and keys are issued for functions f . The striking feature of this systemis that given an encryption of x, the key corresponding to f can be used to obtain f (x) but nothingelse about x. Furthermore, any arbitrary collusion of key holders relative to many functions fi
does not yield any more information about x beyond what is “naturally revealed” by each of them
individually (i.e. fi (x) for all i). Using obfuscation, [GGH+ 13b] give a construction of functional
encryption for general circuits.1
1

We note that the [GGH+ 13c] construction gets a weaker indistinguishability notion of security for functional
encryption. However this can be upgraded to natural simulation-based definitions of security using the work of De
Caro et al. [CIJ+ 13].

4

Witness Encryption. Encryption in all its myriad flavors has always been imagined with someknown recipient in mind. But, what if the intended recipient of the message is not known and may
never be known to the encrypter? For example, consider the task of encrypting to someone who
knows a solution to a crossword puzzle that appeared in the The New York Times. Or, in general,a solution to some NP search problem which he might know or might acquire over a period of time.
The encrypter on the other hand may even be unaware of the existence of a solution.
[GGSW13] proposed the concept of witness encryption which captures this intuition and realized it based on our noisy multilinear maps. It was later shown in [GGH+ 13b] that it can bebased on indistinguishability obfuscation as well. Witness Encryption is closely related to the notion of computational secret sharing for NP-complete access structures, first posed by Rudich in1989 [Rud89] (see [Bei11]). As observed by Rudich, this primitive already suffices for converting
private-key cryptosystems to public-key ones. Witness encryption has found applications elsewhereas well. Most prominently, Goldwasser et al. [GKP+ 13] used (a variant of) witness encryption for
constructing a variant of attribute-based encryption scheme for polynomial-time Turing machines,
where the sizes of secret keys depend only on the size of the Turing machine (rather than its runtime). Furthermore in these constructions, the decryption algorithm has an input-specific runtime
rather than worst-case runtime (at the price of revealing this runtime).
Obfuscation has many other applications and we refer the reader to [SW14, GGHR14] for the
first works on the topic.

1.4

Roadmap

In Sections 2.1 and 2.2 we recall some of the preliminary definitions and concepts needed for explaining multilinear maps, as needed for constructing obfuscation. The construction for multilinear
maps in provided in Section 2.3. These three sections have been largely taken verbatim from theauthors doctoral thesis. Next we provide a construction of obfuscation for NC1 as in [BGK+ 14] inSection 3.2 and provide extension to general circuits in Section 3.3 as in [GGH+ 13b].

5

Chapter 2

Multilinear Maps
2.1

Preliminaries I : Lattices

We denote set of complex number by C, real numbers by R, the rationals by Q and the integers
by Z. For a positive integer n, [n] denotes the set {1, . . . , n}. By convention, vectors are assumed
to be in column form and are written using bold lower-case letters, e.g. x. The ith componentof x will be denoted by xi . We will use xT to denotes the transpose of x. For a vector x in
P
1/p
p
Rn or Cn and p ∈ [1, ∞], we define the `p norm as kxkp =where p < ∞, andi∈[n] |xi |kxk∞ = maxi∈[n] |xi | where p = ∞. Whenever p is not specified, kxk is assumed to represent the`2 norm (also referred to as the Euclidean norm).
Matrices are written as bold capital letters, e.g. X, and the ith column vector of a matrix X isdenoted xi . Finally we will denote the transpose and the inverse (if it exists) of a matrix X with
X T and X −1 respectively.
The natural security parameter throughout the report is λ, and all other quantities are implicitly
assumed to be functions of λ. We use standard big-O notation to classify the growth of functions,and say that f (λ) = Õ(g(λ)) if f (λ) = O(g(λ) · log c λ) for some fixed constant c. We let poly(λ)
denote an unspecified function f (λ) = O(λc ) for some constant c. A negligible function, denoted
generically by negl(λ), is an f (λ) such that f (λ) = o(λ−c ) for every fixed constant c. We say thata function is overwhelming if it is 1 − negl(λ).
The statistical distance between two distributions X and Y over a domain D is defined to be
1Pd∈D | Pr[X = d] − Pr[Y = d]|. We say that two ensembles of distributions {Xλ } and {Yλ } are2statistically indistinguishable if for every λ the statistical distance between Xλ and Yλ is negligiblein λ.
Two ensembles of distributions {Xλ } and {Yλ } are computationally indistinguishable if for every
probabilistic poly-time (in λ) machine A, | Pr[A(1λ , Xλ ) = 1] − Pr[A(1λ , Yλ ) = 1]| is negligible inλ. The definition is extended to non-uniform families of poly-sized circuits in the standard way.

2.1.1

Lattices

A lattice Λ is an additive discrete sub-group of Rn , i.e., it is a subset Λ ⊂ Rn satisfying the following
properties:(subgroup) λ is closed under addition and subtraction,(discrete) there is an  > 0 such that any two distinct lattice points x 6= y ∈ Λ are at distance atleast kx − yk ≥ .
6

Let B = {b1 , . . . , bk } ⊂ Rn consist of k linearly independent vectors in Rn . The lattice generated
by the B is the setkX
L(B) = {Bz =zi bi : z ∈ Zk },i=1

of all the integer linear combinations of the columns of B. The matrix B is called a basis for thelattice L(B). The integers n and k are called the dimension and rank of the lattice. If n = k then
L(B) is called a full-rank lattice. We will only be concerned with full-rank lattices, hence unlessotherwise mentioned we will assume that the lattice considered is full-rank.
The minimum distance λ1 (Λ) of a lattice Λ is the length (in the Euclidean `2 norm, unlessotherwise indicated) of its shortest nonzero vector: λ1 (Λ) = minx6=0,x∈Λ kxk. More generally, theith successive minimum λi (Λ) is the smallest radius r such that Λ contains i linearly independentvectors of norm at most r. We write λ∞1 to denote the minimum distance measured in the `∞ norm
(which as mentioned earlier, is defined as kxk∞ = max |xi |).
For lattices Λ0 ⊆ Λ, the quotient group Λ/Λ0 (also written as Λ mod Λ0 ) is well-defined as the
additive group of distinct cosets v + Λ0 for v ∈ Λ, with addition of cosets defined in the usual way.

2.1.2

Gaussians on Lattices

Review of Gaussian measure over lattices presented here follows the development by prior works [Reg04,
AR05, MR07, GPV08, AGHS12]. For any real s > 0, define the (spherical) Gaussian function
ρs : Rn → (0, 1] with1 parameter s as:∀x ∈ Rn , ρs (x) = exp(−πhx, xi/s2 ) = exp(−πkxk2 /s2 ).
For any real s > 0, and n-dimensional lattice Λ, define the (spherical) discrete Gaussian distribution over Λ as:ρs (x)∀x ∈ Λ, DΛ,s (x) =.
ρs (Λ)
Smoothing Parameter. Micciancio and Regev [MR07] introduced a lattice quantity called thesmoothing parameter, and related it other lattice parameters.
Definition 2.1.1 (Smoothing Parameter, [MR07, Definition 3.1]). For an n-dimensional lattice Λ,and positive real  > 0, we define its smoothing parameter denoted η (Λ), to be the smallest s suchthat ρ1/s (Λ∗ \ {0}) ≤ .
Intuitively, for a small enough , the number η (Λ) is sufficiently larger than a fundamental
parallelepiped of Λ so that sampling from the corresponding Gaussian “wipes out the internal
structure” of Λ. The following Lemma 2.1.3 and Corollary 2.1.4 formally provide this claim. The
bounds on η (Λ) are specified by Lemma 2.1.2. Finally Lemma 2.1.5 provides bounds on the lengthof a vector sampled from a Gaussian.
Lemma 2.1.2 ([MR07, Lemma 3.3]). For any n-dimensional lattice Λ and positive real  > 0, we
have thatrln(2n(1 + 1/))η (Λ) ≤· λn (Λ).
π
1
The Gaussian function can be defined more generally as being centered around a specific vector c instead of 0 as
done here. The simpler definition considered here suffices for our purposes.

7

The following lemma explains the name “smoothing parameter.”Lemma 2.1.3 ([MR07, Lemma 4.1]). For any lattice Λ,  > 0, s ≥ η (Λ), and c ∈ Rn , thestatistical distance between Ds + c mod Λ and the uniform distribution modulo Λ is at most /2.
Corollary 2.1.4 ([GPV08, Corollary 2.8]). Let Λ, Λ0 be n-dimensional lattices, with Λ0 ⊆ Λ. Thenfor any  ∈ (0, 12 ), any s ≥ η (Λ0 ), the distribution of (DΛ,s mod Λ0 ) is within a statistical distanceat most 2 of uniform over (Λ mod Λ0 ).
Lemma 2.1.5 ([MR07, Lemma 4.4] and [BF11b, Proposition 4.7]). For any n-dimensional lattice
Λ, and s ≥ η (Λ) for some negligible , then for any constant δ > 0 we have
r
r 

n
n
Pr
(1 − δ)s≤ kxk ≤ (1 + δ)s≥ 1 − negl(n).
x←DΛ,s2π2π2.2Preliminaries II : Algebraic Number Theory Background

Algebraic number theory is the study of number fields. Here we review the background essential
for understanding our encoding scheme. We consider the special case of cyclotomic number fields
as a special example of particular interest. Much of our description here follows [LPR10], and werefer the reader to [Jan96, Ste04, Oss08, Wes99] for detailed background reading.

2.2.1

Number Fields and Ring of Integers

An algebraic number field (or simply number field) K is a finite (and hence algebraic) field extensionof the field of rational numbers Q. In this section we will recall definition of some of these elementary
notions.
Definition 2.2.1 (Algebraic Number and Algebraic Integer). We say that ζ ∈ C is an algebraic
number if it is a root of a polynomial f (x) ∈ Q[x]. Furthermore, we say that that ζ is an algebraic
integer if additionally f (x) is a monic (a polynomial whose leading coefficient is 1) polynomial inZ[x].
Definition 2.2.2 (Minimal Polynomial). The minimal polynomial of ζ is the monic polynomial
f (x) ∈ Q[x] of least positive degree such that f (ζ) = 0.
The conjugates of ζ are defined by all the roots of its minimal polynomial.
Proposition 2.2.3 ([Ste04, Lemma 5.1.3]). If ζ is an algebraic integer, then the minimal polynomial of ζ is in Z[x].
Proposition 2.2.4 ([Ste04, Proposition 5.1.5]). The set of all algebraic integers form a ring, i.e.,the sum and product of two algebraic integers is again an algebraic integer.
Now we are ready to define the notion of a number field and its ring of integers.
Definition 2.2.5 (Number Field and Ring of Integers). A number field is a field extension K =Q(ζ) obtained by adjoining an algebraic number ζ to the field of rationals Q. The ring of integers
of a number field K is the ringOK = {x ∈ K : x is an algebraic integer.}
Let the minimal polynomial f (x) of ζ have degree n. Then because f (ζ) = 0, there is a natural
isomorphism between Q[x] mod f (x) and K, given by x 7→ ζ, and the number field K can be seen
as an n-dimensional vector space over Q with basis {1, ζ, . . . , ζ n−1 }. This is called the power basis
of K.
8

√

The case of Cyclotomic Number Fields. Let ζm = e2π −1/m ∈ C denote a primitive m-th
root of unity. (Recall that an mth root of unity is said to be a primitive root if it is not a kth root
for some 0 < k < m.)Definition 2.2.6 (Cyclotomic Polynomial). The m-th cyclotomic polynomial, denote by Φm (x),is defined as the productYk(x − ζm).
Φm (x) =k∈Z∗m

Observe that the values ζ k run over all the primitive mth roots of unity in C, thus Φm (x) has
degree n = ϕ(m), where ϕ(m) denotes the Euler’s totient or phi function. Recall that if m is apositive integer, then ϕ(m) is the number of integers in the set {1, 2, . . . , m} that are relatively
prime to m.
It is easy to see that Φm (x) is monic. It is also known (a nontrivial result due to Gauss) thatΦm (x) is in Z[x] and is irreducible over Q. Therefore ζm is an algebraic integer with the minimal
polynomial Φm (x).
The cyclotomic polynomial Φm (x) may be computed by (exactly) dividing xn − 1 by the cyclotomic polynomials of the proper divisors of n previously computed recursively (setting, Φ1 (x) =x − 1) by the same method:xm − 1Φm (x) = Q.
d|m Φd (x)
d<m
m

−1
Two useful facts about cyclotomic polynomials are that Φm (x) = xx−1
= xm−1 + . . . + x + 1 forprime m, and Φm (x) = Φm0 (xm/m0 ) where m0 is the radical of m, i.e., the product of all primes
diving m. For instance, Φ8 (c) = x4 + 1 and Φ9 (x) = x6 + x3 + 1. We will be most interested in thecase when m ≥ 2 is a power of 2 in which case Φm (x) = xm/2 + 1. (However, not all cyclotomic
polynomials have 0-1, or even small coefficients: e.g., Φ6 (x) = x2 − x + 1, Φ3·5·7 has a −2 coefficient,and Φ3·5·7·11·13 (x) has coefficients with magnitudes as large as 22.)

Definition 2.2.7. The mth cyclotomic field Q(ζm ) (with m > 2) is obtained by adjoining ζm to
Q.
Proposition 2.2.8 ([Jan96, p 48, Proposition 4.3]). The ring of integers in Q(ζm ) is Z(ζm ). Thisring Z(ζm ) is called the cyclotomic ring.

2.2.2

Embeddings and Geometry

In this section we will recall various geometric interpretations of a number field and most importantly define different notion of norm essential for our study.
Canonical Embedding. A number field K = Q(ζ) of degree2 n has [Wes99, p 9, Proposition 2.1] exactly n field homomorphisms σi = K ,→ C that fix every element of Q. Concretely,
these embeddings map ζ to each of its conjugates; it can be verified that these are the only field
homomorphisms from K to C because ζ’s conjugates are the only roots of ζ’s minimal polynomial
f (x). An embedding whose image lies in R (corresponding to a real root of f (x)) is called a real
2

Recall that a number field K = Q(ζ) is isomorphic to Q[x]/f (x) where f (x) is the minimal polynomial of ζ.
The degree of K defined to be the value [K : Q], is same as [Ste04, p 28] the degree of the polynomial f (x). (Moregenerally, if K ⊂ L are number fields, we let [L : K] denote the dimension of L viewed as a K-vector space.)9embedding; otherwise (for a complex root of f (x)) it is called a complex embedding. Because complex roots of f (x) come in conjugate pairs, so too do the complex embeddings. The number of realembeddings is denoted s1 and the number of pairs of complex embeddings is denoted by s2 , so wehave n = s1 + 2s2 . The pair (s1 , s2 ) is called the signature of K. By convention, we let {σj }j∈[s1 ]be the real embeddings, and order the complex embeddings so that σs1 +s2 +j = σs1 +j for j ∈ [s2 ].
The canonical embedding σ : K → Rs1 × C2s2 is defined as
σ(x) = (σ1 (x), . . . , σn (x)).
The canonical embedding σ is a field homomorphism from K to Rs1 ×C2s2 , where multiplication
and addition in Rs1 ×C2s2 are component-wise (since σ is a ring homomorphism). Due to the pairingof the complex embeddings, σ maps into the following space H ⊆ Rs1 × C2s2 ⊂ Cn :H = {(x1 , . . . , xn ) ∈ Rs1 × C2s2 : xs1 +s2 +j = xs1 +j , ∀j ∈ [s2 ]}.
By identifying elements of K with their canonical embeddings in H, we can speak of geometriccanonical norms on K. Specifically, we define the `p canonical norm of x, denoted as kxkcan
as
p
P
1
p p for p < ∞, and as max
kσ(x)kp =i∈[n] |σi (x)| for p = ∞. (As always we assumei∈[n] |σi (x)|the `2 norm when p is omitted.)
Q
Field Norm. The (field) norm of an element a ∈ K is defined as N(a) = NK/Q (a) = i∈[n] σi (a).3
Note that the [Wes99, p 43, proof of Lemma 3.2] norm of an algebraic integer is in Z.
Coefficient Embedding. There is also a coefficient embedding τ : K → Qn . As mentioned
earlier, since f (ζ) = 0, there is an isomorphism between Q[x] mod f (x) and K given by x → ζ. So,
K can be represented as a n-dimensional vector space over Q using the power basis {1, ζ, . . . , ζ n−1 },and τ maps an element of K to its associated coefficient vector. When identifying an element a ∈ K
as a coefficient vector, i.e., τ (a) we denote it as a boldface vector a. Note that the addition of vectors
is done component-wise, while the multiplication is done as polynomials modulo f (x). We define
the coefficient norm of a as the norm of the vector a. Specifically, we define the `p coefficient norm
P
1
p p
of a, denoted as kakp or kakp as
for p < ∞, and as maxi∈[n] |ai | for p = ∞. (Asi∈[n] aialways we assume the `2 norm when p is omitted.)
Relationship between Coefficient and Canonical Embeddings. The conversion of an element in K = Q[ζm ] (n = φ(m)) from its coefficient representation to the canonical one can be seenas the multiplication of the coefficients of the polynomial by a specific Vandermonde matrix. Morespecifically, if a is an element of K in the coefficient representation then Vm · a is exactly the canon(n−1)ji
ji 2ji
ical representation where Vm ∈ Cn×n such that its ith row is the vector (1, ζm, ζm , . . . , ζm)for all ji ∈ Z∗m . The matrix Vm when m is a power of 2 is special in the sense that the matrix
1n Vm is unitary. This means that conversions between the canonical embedding and the coefficient
representation corresponds to just a rigid rotation and a scaling.
3

More generally, the relative norm NK/L (a) of an element a ∈ K over a subfield L ⊂ K is
consists of the K-embeddings σi that fix every element in L.

10Q

σi ∈S σi (a), where S

Multiplicative Expansion Factor. We define the multiplicative expansion factor γMult to deka×bk
note (as in [Gen09, p. 71]) the maximal value of kak·kbk
for any a, b ∈ K. (See [LM06] for adifferent definition of the expansion factor for multiplication.) The dependence of γMult value on
the underlying field K is understood.
Next we will argue (also see [Gen09, Lemma 7.4.3] and [GH10, Section 2.2]) that for the field√
K = Q[x]/(xn + 1), γMult can be upper bounded by n.
Lemma 2.2.9. Let K = Q[x]/(xn + 1), for any positive integer n. ∀a, b ∈ K and c = a × b wehave that√kck ≤ n · kak · kbk.
Proof. Consider the ith coefficient ci of c. First observe that for each i, ci is obtained as a dot
product of a and some reordering of entries of b (additionally the signs of some entries can also be√reversed). Therefore we have ci ≤ kak·kbk. This allows us to conclude that kck ≤ n·kak·kbk.
Example. Continuing with our example of the mth cyclotomic number field where K = Q(ζm )for m > 2, there are 2s2 = n = ϕ(m) complex canonical embeddings (and no real ones), which are
i for i ∈ Z∗ . (It is convenient to index the embeddings by elements of Z∗
given by σi (ζm ) = ζmmm
instead of [n].) For an element x = ζ j ∈ K in the power basis of K, all the embeddings of x have√magnitude 1, and hence kxkcan= n and kxkcan∞ = 1. Also considering the coefficient embedding2
kxk2 = 1.

2.2.3

Ideals in the Ring of Integers

The ring of integers OK , of a number field K of degree n, is a free Z-module (see [Wes99,
p 39, Theorem 2.22]) of rank n, i.e., the set of all Z-linear combinations of some integral basis{b1 , . . . , bn } ⊂ OK . Such a set is called an integral basis, and it is also a Q-basis for K. As usual,
there are infinitely many such bases when n > 1.
Continuing with our example of the mth cyclotomic number field K = Q(ζm ) of degree n =n−1 } of K also happens to be an integral basis of the cyclotomic
ϕ(m), the power basis {1, ζm , . . . , ζmring OK = Z[ζm ]. (In general, it is unusual for the power basis of a number field to generate theentire ring of integers.)
Definition 2.2.10 (Ideal). An (integral) ideal I ⊆ OK is a nontrivial (i.e., nonempty andnonzero4 ) additive subgroup that is closed under multiplication by OK – that is, r · g ∈ I for
any r ∈ OK and g ∈ I. A fractional ideal I ⊂ K is a set such that d · I is an integral ideal forsome d ∈ OK . The inverse I −1 of an ideal I is the set {a ∈ K : a · I ⊆ OK }.
An ideal I in OK is finitely generated as the set of all K-linear combinations of some generators g1 , g2 , . . . ∈ OK , denoted I = hg1 , g2 , . . .i. (In fact, it is know that two generators [Ste04,
Proposition 9.1.7] always suffice.)
Definition 2.2.11. An ideal I is principal if I = hgi for g ∈ OK – that is, if one generator suffices.
More useful to us is the fact [Oss08, Proposition 1.6.1] that an ideal (integral or fractional) is
also a free Z-module of rank n, i.e., it is generated as the set of all Z-linear combinations of somebasis {b1 , . . . , bn } ⊂ OK .
4

Some texts also define the trivial set {0} as an ideal, but in this work it is more convenient to exclude it.

11Definition 2.2.12. Let I, J be ideal of a ring R. Their sum is the ideal
I + J = {a + b : a ∈ I, b ∈ J }and their product IJ is ideal generated by all products of elements in I with elements in J , or
IJ = ha · b : a ∈ I, b ∈ J i.
Two ideals I, J ⊆ OK are said to be coprime (or relatively prime) if I + J = OK .

2.2.4

Prime Ideals - Unique Factorization and Distributions

In this section we will define the notion of prime ideals and recall some of their properties. A prime
ideal shares many important properties of a prime number in Z.
Definition 2.2.13. An ideal p ( OK is prime if whenever a, b ∈ OK and ab ∈ p then either a ∈ p
or b ∈ p.
Unique Factorization. As per unique-prime-factorization theorem, we have that every integer
greater than 1 is either prime itself or is the product of prime numbers. Similar in any ring ofintegers OK of the number field K has unique factorization of ideals into prime ideals.
Proposition 2.2.14 (Unique Factorization of Ideals [Ste04, Theorem 6.1.9]). Suppose I is an
integral ideal of OK . Then I can be written as a productI = p1 . . . pnof prime ideals of OK , and this representation is unique up to order.
Ideal Norm and some of its properties. Now we will define the norm of an ideal and mention
some of the properties about the norms of prime ideals.
Definition 2.2.15. If I is an ideal of a ring of integers OK , we define the norm of I to be
N(I) = |OK /I|
where |OK /I| dentes the size of the quotient ring OK /I.
It is know that [Wes99, p 60, Lemma 2.2] N(IJ ) = N(I)N(J ).
In OK , an [Ste04, Proposition 6.1.4] ideal p is prime if and only if it is maximal, i.e., if the only
proper superideal of p is OK itself, which implies that the quotient ring OK /p is a finite field oforder N(p).
Proposition 2.2.16 ([Oss08, Corollary 1.6.9]). For a in a ring of integers OK , let p = hai be theprincipal ideal generated by a, then we have that N(I) = |N(a)|.
Suppose p is an ideal of a ring of integers OK , and N(p) = p for some prime integer p ∈ Z.
Then we have that [Oss08, Lemma 1.6.7] p is prime in OK . Note that, many prime ideals do nothave prime norms. In fact [Oss08, Lemma 4.6.1] if p is a prime ideal in a ring of integers OK , thenN(p) = pn for some prime p ∈ Z and n ∈ N.

12

Distribution of Prime ideals. The distribution of prime ideals in number fields is quite analogous to the distribution of primes in the integers. Just as the prime number theorem states thatthe number of primes less than x is approximately x/ ln x, we have Landau’s prime ideal theorem.
Theorem 2.2.17 (Landau’s prime number theorem [BS96, Theorem 8.7.2]). Let K be an algebraic
number field of degree n. Let πK (x) denote the number of prime ideals whose norm is ≤ x. Let
ξ(x) = (ln x)3/5 (ln ln x)−1/5 . There is a c > 0 (depending on K) such that
πK (x) = Li(x) + O(xe−cξ(x) ) ∼where Li(x) =

x
,
ln x

R t dt2 ln t .

Furthermore the prime ideals in the above theorem are dominated by the ideals of norm aprime number. Assuming the Generalized Riemann Hypothesis (GRH) [BS96, Conjecture 8.7.3],
a stronger statement [BS96, Theorem 8.7.4] can be made but the above mentioned unconditional
statement suffices for our purposes.
In our constructions we will need results on the distribution of prime ideals that are also principal. From prime number theorem for arithmetic progressions, we know that the number of primes
less that or equal to x and congruent to a mod n (where a and n are co-prime), is x/(φ(n) ln x).
Similarly one of the consequences of Chebotarëv’s density5 theorem (see for example [Ste10, Proofof Lemma 4]) is that the among all the prime ideals in a number field K, h1 of them are principal,
where h is the class number of K.
We refer the reader to [Lan90, p 77] for a general analytic formula for computing the classnumber of any number field K. The class number6 of the n-th cyclotomic field K, factors as h+times h− , where h+ is the class number of the maximal real subfield of K. The Brauer-Siegel
theorem (see [Was97, Theorem 4.20]) implies that log(h− ) grows roughly as 14 φ(n) log n as n → ∞.
However, h+ tends to be rather small. For n a power of 2, it is conjectured that h+ =1. This istrue for n = 2k with k ≤ 7, and also for k = 8 if we assume GRH. This provides for theoreticalevidence that principal prime ideals exist. However since the class number is already exponential
this does not suffice for our purposes.
Nevertheless restricting the Landau’s prime number theorem to principal ideals we can heuristically expect that with noticeable probability a random principal ideal will have a prime norm.
Conjecture 2.2.18. Let K be the n-th cyclotomic field for n a power of 2. For every σ = poly(n)there is a constant c > 1 such that for sufficiently large n we have thatPrf ←DZ n ,σ[N(f ) ≥ 2O(n) and is prime] ≥1.
ncSmart and Vercauteren [SV10] and Boneh and Freeman [BF11a] follow a similar heuristic in
their applications. Experimental results supporting this heuristic have been provided by Smart andVercauteren [SV10].
5

Just like Landau’s prime number theorem is a generalization of the prime number theorem, we have the Chebotarëv’s density theorem [BS96, Theorem 8.7.9] with generalizes the prime number theorem for arithmetic progressions[BS96, Theorem 8.4.2] to number fields. Chebotarëv’s density theorem is a very technical result building on field
theory and we do not delve into stating it formally. We refer the reader to [SL96] for a very down to earth introduction
to Chebotarëv’s Density Theorem.
6
We would like to thank Alice Silverberg and Lawrence Washington for pointing [SW13] these facts about classnumber of cyclotomic fields to us.

13

2.2.5

Ideal Lattices

Recall that a number field K = Q(ζ) is isomorphic to Q[x]/f (x) where f (x) is the minimal
polynomial of ζ. Also recall that any ideal I of OK is a free Z-module, i.e., it is generated as the setof all Z-linear combinations of some basis B = {b1 , . . . , bn } ⊂ OK . Therefore under the coefficientembedding τ , the ideal I of OK yields a rank-n lattice τ (I) having basis {b1 , . . . , bn }, where eachbi = τ (bi ). Obviously, addition is done component-wise in the coefficients, and multiplication ispolynomial multiplication modulo the polynomial f (x). We call I an ideal lattice to stress its dual
interpretation as both an ideal and a lattice. When visualizing it as a lattice we speak of, e.g., theminimum distance λ1 (I) of an ideal, etc.
As pointed out earlier the mth cyclotomic ring with n = ϕ(m) happens to be exactly Z[ζm ]which corresponds to the lattice Zn .
Proposition 2.2.19 ([LPR12, p 22]). For any ideal I of the mth cyclotomic ring (with n = ϕ(m))
we have λn (I) = λ1 (I).
We will sketch the argument here. Consider the mth cyclotomic field such that n = ϕ(m).
Observe that multiplying a shortest nonzero element v ∈ I by 1, ζ, . . . , ζ n−1 gives n linearly independent elements of the same length. This allows us to conclude the above proposition.
Invertibility of ring elements. Let R denote the 2nth cyclotomic ring and let Rq denote R/qR
for a prime q. We note that Rq is also a ring and not all elements in it are invertible. Let Rq× denotethe set of elements in Rq that are invertible. We next provide a lemma of Stehlé and Steinfeld thatpoints out that a (large enough) random element is Rq is also in Rq× with large probability.
Lemma 2.2.20 ([SS11, Lemma 4.1]). p
Let n ≥ 8 be a power of 2 such that xn + 1 splits into nlinear factors modulo q ≥ 5. Let σ ≥ n ln(2n(1 + 1/δ))/π · q 1/n , for an arbitrary δ ∈ (0, 1/2).
Then
Pr [f mod q ∈/ Rq× ] ≤ n(1/q + 2δ).
f ←DZ n ,σ2.3

GGH Multilinear Maps

In this section we describe the GGH multilinear maps for the “symmetric setting” Later we explain
how to handle the “asymmetric setting,” which will be needed for our obfuscation construction.
We provide only those details that are essential for understanding the obfuscation construction.
An instance of the GGH construction is parameterized by the security parameter λ and therequired multi-linearity level κ ≤poly(λ). Based on these parameters, choose the 2nth cyclotomic
ring R = Z[x]/(xn + 1) where n is a power of 2 (n is set large enough to ensure security), and a
modulus q that defines Rq = R/qR (with q large enough to support functionality). The specificconstraints that these parameters must satisfy are discussed in Section 2.3.2, an approximate setting
to keep in mind is n = Õ(κλ2 ), and q = 2κλ .

2.3.1

The Encoding Scheme

We start by giving the intuition behind the scheme. An instance of the GGH scheme relative tothe parameters above encodes elements of a quotient ring QR = R/I, where I is a principal prime
ideal I = hgi ⊂ R, generated by a “short” vector g. Namely, the “ring elements” that are encodedin our scheme are cosets of the form e + I for some vector e. The short generator g itself is kept

14

secret, and no “good” description of I is made public in our scheme. In addition, GGH systemdepends on another secret element z, which is chosen at random in Rq (and hence is not short).
A level-zero (“plaintext”) encoding of a coset e + I ∈ R/I is just a short vector in that
coset (which must exist, since the generator g is short and therefore the basic cell of I is quite
small). For higher-level encodings, a level-i encoding of the same coset is a vector of the form
c/zi ∈ Rq with c ∈ e + I short. Specifically, for i ∈ {0, 1, . . . , κ} the set of all level-i encodings is
Si = {c/zi ∈ Rq : kck < q 1/8 }, and the set of level-i encodings of the “plaintext element” e + I
(e+I)
is Si
= {c/zi ∈ Rq : c ∈ e + I, kck < q 1/8 }. Throughout the construction we use the sizeof the numerator as the “noise level” in the encoding. Namely, with each level-i encoding c/zi we
produce also an upper bound on kck.
Instance generation: (params, pzt ) ← InstGen(1λ , 1κ ). GGH instance-generation procedure chooses
at random the ideal-generator g and denominator z, as well as several other vectors that are used in
the other procedures and are described later in the section. The denominator z is chosen uniformly
at random in Rq , and hence is not “small” with overwhelming probability. Using Lemma 2.2.20 wehave that z is invertible in Rq with overwhelming probability.
√
Simply draw g from a discrete Gaussian over Zn , say g ← DZn ,σ with σ = λn repeatedly till:√(i) kgk ≤ σ n and g is invertible in Rq .
(ii) kg−1 k ≤ nc+1.5 (in K) for an appropriate constant c. (Recall that we denote K = Q[x]/(xn +1). The reason that we need g−1 ∈ K to be short is explained when we describe the zerotesting procedure.)(iii) N(g) is a prime ≥ 2O(n) .
From Lemma 2.3.1 we can conclude that the above described rejection sampling procedure succeeds
in polynomially many trials. Condition (iii) from above, Proposition 2.2.16 and the discussion there
after imply that I = hgi is a principal prime ideal.
An element pzt that is used as a zero-testing parameter is also generated. This generation
process is described later. The instance-generation procedure outputs params = (n, q, g, z) and pzt .
Lemma 2.3.1. If g ← DZn ,σ , then assuming Conjecture 2.2.18 there exists a constant c such that(i), (ii) and (iii) from above are simultaneously satisfied with a noticeable probability.
Proof. We will proceed by obtaining bounds on probabilities that each of the above conditions (i),(ii) and (iii) individually holds. Subsequently the lemma follows by a union bound argument.
(i) It follows directly from Lemma 2.1.5 and Lemma 2.2.20 that condition (i) is satisfied withoverwhelming probability.
(ii) Now we argue that with good probability g−1 in the field of fractions K is also rather short.
We will argue this by looking at g in terms of the canonical embedding. As pointed in
Section 2.2.2, the canonical embedding representation can be obtained by multiplying thecoefficient representation with the matrix V2n . And this transformation for a power of 2
cyclotomic corresponds to just a rigid rotation and a scaling (thus the spherical Gaussian
distribution is not affected by the transformation). Therefore we have that sampling g from
DZn ,σ and considering the canonical embedding is the same as sampling directly the canonicalrepresentation for an appropriately scaled gaussian parameter σ 0 , which in our case is at leastω(1). This implies that roughly with probability 1 − o(1/nc+1 ), evaluating g at any complex
2n’th root of unity ζ ∈ C yields g(ζ) which is greater than 1/nc+1 .
15

Next by taking a union bound, with probability 1 − o(1/nc ) we have g−1 (ζ) = 1/g(ζ) < nc+1
c+1 . This implies anfor all the primitive 2n’th roots of unity ζ, which means that kg−1 kcan
∞ <n
−1
c+1
upper bound of kg k∞ < nas well (because for every a ∈ K we have that kak∞ ≤ kakcan∞ ;see for example [DPSZ11, Theorem 7 and Discussion on p. 39] for a detailed proof). Hence abound of kg−1 k < nc+1.5 .
(iii) Conjecture 2.2.18 implies that there exists a constant c such that condition (iii) is satisfied
with probability at least n1c .
Putting the above bounds together and taking a union bound implies the claimed lemma.
Sampling level-zero encodings: d ← samp(params). To sample a level-zero encoding of a ran√
dom coset, just draw a random short element in R, d ← DZn ,σ0 , where σ 0 = σn λ (for σ that wasused to sample g). In Lemma 2.3.2 we argue that the sampled value d corresponds to a random
coset of I. Finally note that by Lemma 2.1.5 the size of this level-zero encoding is bounded by√
σ 0 n (and we use this as our noise-bound for this encoding).
√
Lemma 2.3.2. Let I = hgi and σ 0 ≥ λnkgk, then we have that the distribution d mod I whered ← DZn ,σ0 is close to uniform over Zn mod I, up to negligible distance.
Proof. We can safely assume that λ1 (I) ≤ kgk. Next according to Proposition 2.2.19 we havethat λn (I) = λ1 (I). This along with Lemma 2.1.2 allows us to conclude that with overwhelming
probabilityrln(2n(1 + 1/))· kgk
η2−λ (I) ≤πrln(2n(1 + 1/))
· kgk
≤
π
√
≤ λnkgk
Finally since we have that σ 0 ≥ η2−λ (I), therefore by Corollary 2.1.4 we can conclude that theinduced distribution over the cosets of I is close to uniform, up to a negligible distance.
Encodings at higher levels: ui ← enc(params, i, d). To allow encoding of cosets at higher levels,
draw d ← DZn ,σ0 , for some parameter σ 0 , then compute the encoding as [d/zi ]q (A more secureversion of sampling is described in [GGH13a]. We use the notation [·]q to denote operations in Rq .)Adding and multiplying encodings. It is easy to see that the encoding as above is additively
homomorphic, in the sense that adding encodings yields an encodingof the sum. This follows
P
sinceP
if we have
many
short
c
’s
then
their
sum
is
still
short,kckq, and therefore the sum
j
j j
P
P
c = j cj = [ j cj ]q ∈ Rq belong to the coset j (cj + I). Hence,
if we denote uj = cj /z ∈ Rq
P
then each uj is an encoding of the coset cj + I, and the sum [ j uj ]q is of the form c/z where cis still a short element in the sum of the cosets.
Moreover, since I is an ideal then multiplying upto κ encodings can be interpreted as an
encoding of the product, by raising the denominator to the appropriate power. Namely, for uj =cj /z ∈ Rq as above, we have



Q
κ
Y
cj
j
.
u=
uj  =
zκ q
j=1

q

16

Q
As
long
as
the
c
’s
are
small
enough
to
begin
with,
we
still
have
k
j
Q
Q
Q
Qj cj k  q, which means that[ j cjQ]q = j cj (where the product j cj is computed in R), hence [ j cj ]q belongs to the productcoset j (cj + I).
Thus, if each uj is a level-1 encoding of the coset cj +I with short-enough numerator, then theirproduct is a level-κ encoding of the product coset. We note that just like level-1 encoding, level-κ
encoding (and in fact any of the intermediate level encoding) also offers additive homomorphism.
?

Zero testing: isZero(params, pzt , uκ ) = 0/1. Since the encoding is additively homomorphic, GGH
can test equality between encodings by subtracting them and comparing to zero. To enable zerotesting, GGH generate the zero-testing parameter as follows: Draw a “somewhat small” ring element/ I and set the zero-testing parameter as pzt = [hzκ /g]q . (A moreh ← DZn ,√q , such that h ∈secure version of sampling is described in [GGH13a].) To test if a level-κ encoding u = [c/zκ ]qis an encoding of zero, we just multiply it in Rq by pzt and check whether the resulting element
w = [pzt · u]q is short (e.g., shorter than q 3/4 ). Namely, we use the test
1 if k[pzt u]q k∞ < q 3/4
isZero(params, pzt , u) =(2.1)
0 otherwise
In Lemma 2.3.3 we will argue that encodings of zero (such that the numerator is less than q 1/8 )always pass the zero test. Next in Lemma 2.3.5 we argue that encodings of non-zero cosets pass
the zero test only with a negligible probability.
1/8

Lemma 2.3.3. For any u = [c/zκ ]q such that kck < q 1/8 and c ∈ I = hgi, such that kg−1 k < nq 3/2(in K) we have that k[pzt u]q k∞ < q 3/4 where h ← DZn ,√q , and pzt = [hzκ /g]q .
Proof. To see why this works, we note thatw = pzt · u =hzκ c·= h · c/g (all the operations in Rq ).
g zκ

If u is an encoding of zero then c is a short vector in I (containing elements gr for r ∈ R), whichmeans that it is divisible by g in R. Hence the element c/g ∈ R is the same as the elementc · g−1 ∈ K. Next we have that c · g−1 is at most kck · kg−1 k · γMult (recall that using Lemma 2.2.9√
2γMult can be bounded n). Next we have that kwk ≤ khk · kck · kg−1 k · γMult, which for our
√
1/2
1/8
−1
3/4
choice of parameter is q · n · q · kg k · n < q(Note that by Lemma 2.1.5 we have that√khk ≤ q 1/2 · n with overwhelming probability). This immediately also gives an upper bound on
the `∞ norm of w.
If u is an encoding of a non-zero coset, then c is a short vector in some coset of I. In thiscase we have w = [c · h/g]q , where c, g are small (and h is “somewhat small”). Intuitively, since[h/g]q is large with high probability then for a “random enough” c we expect the size of w to belarge. More formally, we argue below (Lemma 2.3.4) that when choosing a uniformly random cosetof I = hgi, there are no short elements c in that coset such that [c · h/g]q is small. This will allow
up to conclude Lemma 2.3.5.
Lemma 2.3.4. Let w = [c · h/g]q and suppose kg · wk and kc · hk are each at most q/2. Suppose
hgi is a prime ideal. Then, either c or h is in the ideal hgi.
Proof. Since g · w = c · h mod q, and since kg · wk and kc · hk are each at most q/2, we haveg · w = c · h exactly. We also have an equality of ideals hgi · hwi = hci · hhi, and, since hgi is aprime ideal and our cyclotomic ring is a unique factorization domain (see Proposition 2.2.14), we
have that hgi divides either hci or hhi (or both). The result follows.
17

Lemma 2.3.5. Let q = nω(1) , and hgi be a prime ideal such that kgk = poly(n). Sample h ←DZn ,√q such that h ∈/ hgi. Then, there is no  > 0 and c ∈/ I such that kck < q 1/8 and k[c·h/g]q k <
1−
q .
√
Proof. We are give than kck < q 1/8 and have khk < q · n (with overwhelming probability using
Lemma 2.1.5). Hence, using Lemma 2.2.9 we have that kc · hk < q 1/8+1/2 · n < q/2. Also for thesake of contradiction assume that that w = [c · h/g]q is such that kwk < q 1− . Then again we have√that kw · gk < q 1− · kgk n < q/2 as kgk = poly(n) and q = nω(1) . Now using Lemma 2.3.4, wehave that either c or h is in the ideal hgi, which is a contradiction.

2.3.2

Setting the parameters

In this section we provide the parameters for the basic setting that should be set so that all theconstraints required by the scheme are met. A overview is presented in Table 2.3.2.
Parameterσσ0qConstraints√
By Lemma 2.3.1, kgk ≤√σ n, kg−1 k ≤ nc+1.5 .
By Lemma 2.3.2, σ 0 ≥ nλ · kgk.
Multiplication of κ encoding shouldhave small numerator.
By Lemma 2.3.5, q > nω(1) .
1/8
By Lemma 2.3.3, kg−1 k < nq 3/2 .

Value
√ Set
nλ
λn3/2
q ≥ 28κλ nO(κ)

Table 2.1: Parameters for our graded encoding scheme.
• The basic Gaussian parameter σ that we use to draw the ideal generator,√ g ← DZn ,σ , needsnto be set to satisfy σ ≥ η2−λ (Z ), which means that we have σ = λn. Then as argued
in Lemma 2.3.1√we have that the size of g is bounded with overwhelming probability by√
kgk ≤ σ n = n λ.
• Once we have √the ideal lattice I = hgi, the Gaussian parameter σ 0 by Lemma 2.3.2 we shouldhave σ 0 ≥ kgk λn. Given the bound from above bound on the size of g, it is sufficient to set
σ 0 = λn3/2 , which means that the size of level-zero elements is bounded with overwhelming
probability by λn2 .
• A level-κ encoding is obtained by multiplying κ level-one encodings (which will always be
re-randomized). Hence it is of the form [c/zκ ]q with c of size bounded with high probability
by kck ≤ (2λ · poly(n))κ = 2κλ · nO(κ) . To use Lemma 2.3.5 for level-κ encodings, we needkck ≤ q 1/8 , so it is sufficient to set q ≥ 28κλ · nO(κ) . With this choice the constraints from
1/8
Lemma 2.3.5 (q > nω(1) ) and Lemma 2.3.3 (kg−1 k < nq 3/2 ) are easily satisfied.
• Finally, in order to get λ-level security against lattice attacks, we roughly need to set thedimension n large enough so that q < 2n/λ , which means that n > Õ(κλ2 ).

2.3.3

Asymmetric Variant

We now describe the asymmetric variant of multilinear maps. In this variant we still choose justr
one ideal generator g, but several different denominators zj ← Rq , j = 1, . . . , τ . Then, a vector18

of the form c/zj ∈ Rq with c short is a level-one encoding of the coset c + I relative to the “j’thdimension”. In this case we use vectors rather than integers to represent the different levels, where
for an index w = hw1 , . . . , wτ i ∈ Nτ and a coset c0 + I, the encodings of c0 + I relative to the index
w are
(
)
τ
Y
(c0 +I)
wi
∗
0
1/8
∗
Sw
=
c/z : c ∈ c + I, kck < q , z =
zi
.
i=1

To enable encoding in this asymmetric variant, we provide the public parameters yj = [aj /zj ]q and{xi,j = [bi,j /zj ]q }i for all j = 1, 2, . . . , κ, with short ai ∈ 1 + I and bi,j ∈ I. To
zero-test
Qenableτviτ
relative to index hv1 , . . . , vτ i ∈ N we provide the zero-test parameter pzt = (h · i=1 zi )/g ∈PRq .
The parameters for this variant will have Pto be set in order to provide functionality up to i vi
levels. In particular, we will need q > 28κλ

i vi

P

nO(κ) and n > Õ(κλ1+

19

i vi

).

Chapter 3

Obfuscation
3.1

Preliminaries

In this section we define the notion of “virtual black-box” obfuscation and indistinguishability
obfuscation. Additionally we recall the definition of branching programs and describe a “dualinput” variant of branching programs used in our construction.

3.1.1“Virtual Black-Box” Obfuscation

We roughly the “Virtual Black-Box” Obfuscation (or, VBB for short) definition requires that having
access to the obfuscated circuit is as good as having only oracle access to the circuit.
Definition 3.1.1 (“Virtual Black-Box” Obfuscation). We say that a uniform PPT machine O isa “Virtual Black-Box” Obfuscator for {C` }`∈N , if the following conditions are satisfied:• Functionality: For every ` ∈ N, every C ∈ C` , every input x to C:
Pr[(O(C))(x) 6= C(x)] ≤ negl(|C|) ,where the probability is over the coins of O.
• Polynomial Slowdown: there exist a polynomial p such that for every ` ∈ N and every C ∈ C` ,we have that |O(C)| ≤ p(|C|).
• Virtual Black-Box: for every PPT predicate A there exist a PPT simulator S, and a negligible
function µ such that for all PPT distinguishers D, for every ` ∈ N and every C ∈ C` :Pr[D(A(O(C))) = 1] − Pr[D(S C (1|C| )) = 1] ≤ µ(|C|) ,where the probabilities are over the coins of D,A,S, and O.

3.1.2

Indistinguishability Obfuscators

Given that the VBB definition is impossible in general we also consider the weaker indistinguishability based definition.
Definition 3.1.2 (Indistinguishability Obfuscator (iO)). A uniform PPT machine iO is called an
indistinguishability obfuscator for a circuit class {Cλ } if the following conditions are satisfied:20

• For all security parameters λ ∈ N, for all C ∈ Cλ , for all inputs x, we have that
Pr[C 0 (x) = C(x) : C 0 ← iO(λ, C)] = 1• For any (not necessarily uniform) PPT distinguisher D, there exists a negligible function αsuch that the following holds: For all security parameters λ ∈ N, for all pairs of circuits
C0 , C1 ∈ Cλ , we have that if C0 (x) = C1 (x) for all inputs x, thenPr D(iO(λ, C0 )) = 1 − Pr D(iO(λ, C1 )) = 1 ≤ α(λ)
Definition 3.1.3 (Indistinguishability Obfuscator for N C 1 ). A uniform PPT machine iO is called
an indistinguishability obfuscator for N C 1 if for all constants c ∈ N, the following holds: LetCλ be the class of circuits of depth at most c log λ and size at most λ. Then iO(c, ·, ·) is anindistinguishability obfuscator for the class {Cλ }.
Definition 3.1.4 (Indistinguishability Obfuscator for P/poly). A uniform PPT machine iO iscalled an indistinguishability obfuscator for P/poly if the following holds: Let Cλ be the class ofcircuits of size at most λ. Then iO is an indistinguishability obfuscator for the class {Cλ }.

3.1.3

Branching Programs

A branching program consists of a sequence of steps, where each step is defined by a pair of
permutations. In each step the the program examines one input bit, and depending on its value theprogram chooses one of the permutations. The program outputs 1 if and only if the multiplicationsof the permutations chosen in all steps is the identity permutation.
Definition 3.1.5 (Oblivious Matrix Branching Program). A branching program of width w andlength n for `-bit inputs is given by a permutation matrix Preject ∈ {0, 1}w×w such that Preject 6=
Iw×w , and by a sequence:nBP = inp(i), Bi,0 , Bi,1 i=1 ,where each Bi,b is a permutation matrix in {0, 1}w×w , and inp(i) ∈ [`] is the input bit position
examined in step i. The output of the branching program on input x ∈ {0, 1}` is as follows:Qn
1 if Qi=1 Bi,xinp(i) = Iw×w
def
BP (x) = 0 if ni=1 Bi,xinp(i) = Preject⊥ otherwise
The branching program is said to be oblivious if inp : [n] → [`] is a fixed function, independent of
the function being evaluated.
Theorem 3.1.6 ([Bar86]). For any depth-d fan-in-2 boolean circuit C, there exists an oblivious
branching program of width 5 and length at most 4d that computes the same function as the circuitC.
We present an obfuscation construction that uses a variant of branching programs that wecall dual-input branching programs. Instead of reading one input bit in every step, a dual-input
branching program inspects a pair of input bits and chooses a permutation based on the values ofboth bits.
21

Definition 3.1.7 (Dual-Input Branching Program). A Oblivious dual-input branching program ofwidth w and length n for `-bit inputs is given by a permutation matrix Preject ∈ {0, 1}w×w such that
Preject 6= Iw×w , and by a sequencenBP = inp1 (i), inp2 (i), {Bi,b1 ,b2 }b1 ,b2 ∈{0,1} i=1 ,where each Bi,b1 ,b2 is a permutation matrix in {0, 1}w×w , and inp1 (i), inp2 (i) ∈ [`] are the positionsof the input bits inspected in step i. The output of the branching program on input x ∈ {0, 1}` is
as follows:Qn
1 if Qi=1 Bi,xinp1 (i) ,xinp2 (i) = Iw×w
def
BP(x) = 0 if ni=1 Bi,xinp (i) ,xinp (i) = Preject12⊥ otherwise
As before, the dual-input branching program is said to be oblivious if both inp1 : [n] → [`] andinp2 : [n] → [`] are fixed functions, independent of the function being evaluated.
Note that any branching program can be simulated by a dual-input branching program withthe same width and length, since the dual-input branching program can always “ignore” one input
bit in each pair.

3.1.4

Straddling Set System

In this section, we define the notion of a straddling set system, and prove combinatorial properties
regarding this set system. This set system will be an ingredient in the obfusctaion construction,and the specific combinatorial properties that we establish will be essential for the security of theconstruction.
Definition 3.1.8. A straddling set system with n entries is a collection of sets Sn = {Si,b , : i ∈[n], b ∈ {0, 1}} over a universe U , such that∪i∈[n] Si,0 = ∪i∈[n] Si,1 = U
and for every distinct non-empty sets C, D ⊆ Sn we have that if:
1. (Disjoint Sets:) C contains only disjoint sets. D contains only disjoint sets.
2. (Collision:) ∪S∈C S = ∪S∈D S
Then, it must be that ∃ b ∈ {0, 1}:
C = {Sj,b }j∈[n] , D = {Sj,(1−b) }j∈[n] .
Therefore, in a straddling set system, the only exact covers of the universe U are {Sj,0 }j∈[n] and{Sj,1 }j∈[n] .
Construction. Let Sn = {Si,b , : i ∈ [n], b ∈ {0, 1}}, over the universe U = {1, 2, . . . , 2n − 1},
where:
S1,0 = {1}, S2,0 = {2, 3}, S3,0 = {4, 5}, . . . , Si,0 = {2i − 2, 2i − 1}, . . . , Sn,0 = {2n − 2, 2n − 1};and,S1,1 = {1, 2}, S2,1 = {3, 4}, . . . , Si,1 = {2i−1, 2i}, . . . , Sn−1,1 = {2n−3, 2n−2}, Sn,1 = {2n−1}.
The proof that Construction 3.1.4 satisfies the definition of a straddling set system is straightforward and is skipped.
22

3.2

Obfuscation Candidate for NC1

In this section we describe the “virtual black-box” obfuscator O for NC1 . Next we show how one
this obfuscation can be bootstrapped to obtain an obfuscation for arbitrary circuits. The securityof this candidate is argued in [BGK+ 14].
Input. The obfuscator O takes as input a circuit and transforms it into an oblivious dual-input
branching program BP of width w and length n for `-bit inputs:nBP = inp1 (i), inp2 (i), {Bi,b1 ,b2 }b1 ,b2 ∈{0,1} i=1 .
Recall that each Bi,b1 ,b2 is a permutation matrix in {0, 1}w×w , and inp1 (i), inp2 (i) ∈ [`] are thepositions of the input bits inspected in step i. Without loss of generality, we make the following
assumptions on the structure of the brunching program BP:• In every step BP inspects two different input bits; that is, for every step i ∈ [n], we haveinp1 (i) 6= inp2 (i).
• Every pair of different input bits are inspected in some step of BP; that is, for every j1 , j2 ∈ [`]such that j1 6= j2 there exists a step i ∈ [n] such that (inp1 (i), inp2 (i)) = (j1 , j2 ).
• Every bit of the input is inspected by BP exactly `0 times. More precisely, for input bit j ∈ [`],
we denote by ind(j) the set of steps that inspect the j’th bit:ind(j) = {i ∈ [n] : inp1 (i) = j} ∪ {i ∈ [n] : inp2 (i) = j} .
We assume that for every input bit j ∈ [`], |ind(j)| = `0 . Note that in every step, the j’th
input bit can be inspected at most once.
Randomizing. Next, the Obfuscator O “randomizes” the branching program BP as follows.
First, O samples a prime p of length Θ(n). Then, O samples random and independent elements asfollows:• Non-zero scalars {αi,b1 ,b2 ∈ Zp : i ∈ [n], b1 , b2 ∈ {0, 1}}.
• Pair of vectors s, t ∈ Zwp.
• n + 1 random full-rank matrices R0 , R1 , . . . , Rn ∈ Zw×w.
p
Finally, O computes the pair of vectors:s̃ = st · R0−1 ,t̃ = Rn · t ,and for every i ∈ [n] and b1 , b2 ∈ {0, 1}, O computes the matrix:B̃i,b1 ,b2 = Ri−1 · Bi,b1 ,b2 · Ri−1 .

23Initialization. For every j ∈ [`], let Sj be a straddlingset system with `0 entries over a set Uj ,Ssuch that the sets U1 , . . . , U` are disjoint. Let U = j∈[`] Uj , and let Bs and Bt be sets such thatU, Bs , Bt are disjoint. We associate the set system Sj with the j’th input bit. We index the elementsof Sj by the steps of the branching program BP that inspect the j’th input. Namely,nojSj = Sk,b: k ∈ ind(j), b ∈ {0, 1} .
For every step i ∈ [n] and bits b1 , b2 ∈ {0, 1} we denote by S(i, b1 , b2 ) the union of pairs of sets thatare indexed by i:inp (i)

S(i, b1 , b2 ) = Si,b11

inp (i)∪ Si,b22.

Note that by the way we defined the set ind(j) for input bit j ∈ [`], and by the way the elementsinp (i)inp (i)of Sj are indexed, indeed, Si,b11 ∈ Sinp1 (i) and Si,b22 ∈ Sinp2 (i) .
O generates the parameters g, z, pzt for multilinear mops. Next it interprets each of the above
terms in Zp as a small element from the corresponding coset on I = hgi. We use the asymmetricsetting of multilinear maps with the universe set U ∪ Bs ∪ Bt . Here we need to encode the following
values:(s · t, Bs ∪ Bt ),(s̃[j], Bs ), (t̃[j], Bt ) j∈[w]{(αi,b1 ,b2 , S(i, b1 , b2 ))}i∈[n],b1 ,b2 ∈{0,1}no(αi,b1 ,b2 · B̃i,b1 ,b2 [j, k], S(i, b1 , b2 ))i∈[n],b1 ,b2 ∈{0,1},j,k∈[w]

We denote the encoding of the element α at level S by [α]S . For a matrix M , [M ]S denotes
a matrix of encodings such that [M ]S [j, k] is the encoding of the element (M [j, k], S). Using thisnotation, O outputs the obfuscation as:


h
i
 
[s̃]Bs ,t̃ Bt , [s · t]Bs ∪Bt ,[αi,b1 ,b2 ]S(i,b1 ,b2 ) ,αi,b1 ,b2 · B̃i,b1 ,b2.
S(i,b1 ,b2 )Output.

i∈[n],b1 ,b2 ∈{0,1}

The obfuscator O outputs the above described encodings and the pzt parameter.

Evaluation. Given two encodings [α]S and [β]S , we can obtain the sum as [α]S + [β]S . Similarly,
given two encodings [α1 ]S1 and [α2 ]S2 such that S1 ∩ S2 = ∅, we obtain the product as [α1 ]S1 · [α2 ]S2 .
Given two matrices of encodings [M1 ]S1 , [M2 ]S2 , we define their matrix multiplication in the naturalway, and denote it by [M1 ]S1 · [M2 ]S2 .
For input x ∈ {0, 1}` to O(BP), and for every i ∈ [n] let (bi1 , bi2 ) = (xinp1 (i) , xinp2 (i) ). On inputx, O(BP) obtains the following encodings:
h = [s̃]Bs ·n hYαi,bi ,bi · B̃i,bi ,bi
1

i=1

2

1

2

i
S(i,bi1 ,bi2 ) · t̃ Bt ,h0 = [s · t]Bs ∪Bt ·n hYαi,bi ,bi
1

i=1

2

i
S(i,bi1 ,bi2 )O(BP) uses pzt to check if h0 − h is not an encoding of 0. If the zero test outputs 1 then O(BP)outputs 1, and otherwise O(BP) outputs 0.

24

Correctness. By construction we have that h0 − h is an encoding of 0 if and only if:
0 = s̃ ·=nYαi,bi ,bi · B̃i,bi ,bi · t̃ − s · t ·
1

i=1
n
Y

s̃ ·

1

2

2

=

s

αi,bi ,bi
1

2

i=1

!
B̃i,bi ,bi · t̃ − s · t
1

2

·

i=1
t

n
Y

n
Y

αi,bi ,bi
1

2

i=1

· R0−1 ·nY!
Ri−1 · Bi,b1 ,b2 · Ri−1

· Rn−1 · t − s · t

i=1= st ·

n
Y

·

n
Y

αi,bi ,bi
1

2

i=1

!
Bi,b1 ,b2 − Iw×w

·t·

i=1

n
Y

αi,bi ,bi
1

2

i=1

From the definition of the branching program we have:BP(x) = 1 ⇔nYBi,bi ,bi = Iw×w
1

2

i=1

Thus, if BP(x) = 1 then O(BP) outputs 1 with probability 1. If BP(x) = 0 then O(BP) outputs
1 with probability at most 1/p = negl(n) over the choice of s and t.
It is left to show that when multiplying two matrices of of encodings [M1 ]S1 · [M2 ]S2 , none of
the addition or multiplication calls fail as long as S1 ∩ S2 = ∅. Therefore, to show that none of theaddition or multiplication fail, it is enough to show that following sets are disjoint:
Bs , Bt , S(1, b11 , b12 ), . . . , S(n, bn1 , bn2 ) .
Their disjointness follows from the fact that U1 , . . . , U` , Bs , Bt are disjoint, together with definitionof S(i, bi1 , bi2 ) and with the fact that for every set system Sj , for every distinct i, i0 ∈ ind(j), and forjevery b ∈ {0, 1}, we have that Si,b
∩ Sij0 ,b = ∅.
Finally zero testing is possible as the encoding h−h0 corresponds to the entire universe. Namely,
we have that:
!
n
[
i i
S(i, b1 , b2 ) ∪ Bs ∪ Bt = U ∪ Bs ∪ Bt ,i=1

which follows from the following equalities:n[i=1

S(i, bi1 , bi2 ) =

n
[
i=1

inp (i)inp (i)Si,bi1 ∪ Si,bi2 =
1
2

`
[

[

j=1 k∈ind(j)

j
Sk,x
=
i

`
[

Uj = U .

j=1

We refer the reader to [BGK+ 14] for security analysis of this construction.

3.3

Amplifying to Poly-sized Circuit Indistinguishability Obfuscation

In this section we present Poly-sized Circuit Indistinguishability Obfuscation from an indistinguishability obfuscator, iONC1 , for circuits in NC1 . In addition to iO, our construction makes
use a Leveled Homomorphic Encryption. We let (SetupF HE , EncryptF HE , DecryptF HE , EvalF HE )be a leveled homomorphic encryption scheme. Furthermore, we assume the decryption algorithm
DecryptF HE can be realized by a family of circuits in NC1 and that the system has perfect correctness.
25

3.3.1

Our Construction

Consider a family of circuit classes {Cλ } for λ ∈ N where the input size, n, and the maximum
circuit size are polynomial functions of λ. Let {Uλ } be a poly-sized universal circuit family forthese circuit classes, where Uλ (C, m) = C(m) for all C ∈ {Cλ } and m ∈ {0, 1}n . Furthermore, allcircuits C ∈ {Cλ } can be encoded as an ` = `(λ) (a polynomial functions of λ) bit string as input
to U . We note that this may require some padding since circuits in the family are not required to
be all of the same size.
We show how to build an iO for such a circuit class given an indistinguishability obfuscator,
iONC1 , for circuits in NC1 .
Our construction is described by an obfuscation algorithm and an evaluation algorithm.1- Obfuscate(1λ , C ∈ Cλ ): The Obfuscate algorithm takes the security parameter λ and a circuit
C and computes
1. Generate (PK1F HE , SK1F HE ) ← SetupF HE (1λ ) and (PK2F HE , SK2F HE ) ← SetupF HE (1λ ).
The number of levels in leveled HE scheme should be set to be the depth of Uλ .
2. Encrypt g1 = EncryptF HE (PK1F HE , C) and g2 = EncryptF HE (PK2F HE , C). Here we assume
that C is encoded in a canonical form as an ` bit string for use by the universal circuit
Uλ (·, ·)1

1

3. Generate an N C 1 obfuscation for program P1(SKF HE ,g1 ,g2 ) as P = iONC1 (P1(SKF HE ,g1 ,g2 ) ).
(See Figure 3.1.)
4. The obfuscation components are output as: σ = (P, PK1F HE , PK2F HE , g1 , g2 ).
- Evaluate(σ = (P, PK1F HE , PK2F HE , g1 , g2 ), m): The Evaluate algorithm takes in the obfuscation
output σ and program input m and computes the following.
1. Compute e1 = EvalF HE (PK1F HE , Uλ (·, m), g1 ) and e2 = EvalF HE (PK2F HE , Uλ (·, m), g2 ). 2
2. Compute a low-depth proof φ that e1 and e2 were computed correctly. (Note thatverification of any computation can be done in NC1 .) We note that this statement for
which proof is being given is in P
3. Run P (m, e1 , e2 , φ) and output the result.
1

Correctness To verify correctness we first check that the size of the circuits evaluating P1(SKF HE ,g1 ,g2 )are in NC1 . Step 1 of the program is in NC1 since it involves verification of a low depth proof.
The second step of the program is also in NC1 since we use an HE scheme with decryption in NC1 .
Since both steps are in NC1 therefore the entire circuit is in NC1 .
The correctness of HE implies that the evaluated ciphertext e1 will be an encryption of thevalue U (C, m) = C(m). Next the correctness of the iONC1 implies that P implements the samefunction as P 1. These two facts together imply correctness of the obfuscation scheme.
1

Technically, we could make do with just a single obfuscation algorithm that outputs a circuit description as is theconvention given in Section 3.1. However, for the exposition of this construction we have the obfuscation algorithm
output cryptographic material that is used by the evaluation algorithm.
2
The circuit Uλ (·, m) is the universal circuit with m hardwired in as an input. This in hardwired circuit takes inan ` bit circuit description C as its input and evaluates to U (C, m).

26

P1
1

Given input (m, e1 , e2 , φ), P1(SKF HE ,g1 ,g2 ) proceeds as follows:
1. Check if φ is a valid low-depth proof for the NP-statement:^
e1 = EvalF HE (PK1F HE , Uλ (·, m), g1 )e2 = EvalF HE (PK2F HE , Uλ (·, m), g2 ).
2. If the check fails output 0; otherwise, output DecryptF HE (e1 , SK1F HE ).

Figure 3.1:
P2
2

Given input (m, e1 , e2 , φ), P2(SKF HE ,g1 ,g2 ) proceeds as follows:
1. Check if φ is a valid low-depth proof for the NP-statement:^
e1 = EvalF HE (PK1F HE , Uλ (·, m), g1 )e2 = EvalF HE (PK2F HE , Uλ (·, m), g2 ).
2. If the check fails output 0; otherwise, output DecryptF HE (e2 , SK2F HE ).

Figure 3.2:

3.3.2

Proof of Security

We prove that for all C0 , C1 ∈ Cλ such that they are functionally equivalent, there can be no
poly-time indistinguishability attacker that can distinguish between the obfuscations of C0 and C1 .
We organize our proof into a sequence of hybrids. In the first hybrid the challenger obfuscates
C0 . We then gradually change the obfuscation in multiple hybrid steps into an obfuscation of C1 .
We show that each successive hybrid experiment is indistinguishable from the last, thus showing ourobfuscator to have indistinguishability security. The proof hybrid steps themselves primarily weave
back and forth in between changing the underlying ciphertexts and the programs that are used ina two-key proof type manner. The changes program that we will use is described in Figure 3.2.
Sequence of Hybrids- Hyb0 : This hybrid corresponds to a honest execution of the Indistinguishability Obfuscation
game where C0 is obfuscated.
- Hyb1 : Same as hybrid Hyb0 except we generate g1 = EncryptF HE (PK1F HE , C0 ), g2 = EncryptF HE (PK2F HE , C1 ).
Now g1 and g2 encrypt different circuits.
Computational indistinguishability between Hyb0 and Hyb1 follows from the semantic securityof the encryption scheme.
- Hyb2 : We still generate g1 = EncryptF HE (PK1F HE , C0 ) and g2 = EncryptF HE (PK2F HE , C1 ) as2
in Hyb1 . Now P is created as P = iONC1 (P2(SKF HE ,g1 ,g2 ) ).
Computational indistinguishability between Hyb1 and Hyb2 follows from indistinguishability
obfuscation of NC1 obfuscator.
- Hyb3 : We now generate g1 = EncryptF HE (PK1F HE , C1 ) and g2 = EncryptF HE (PK2F HE , C1 ).
2
The obfuscated program P is still created as P = iONC1 (P2(SKF HE ,g1 ,g2 ) ).
27

Computational indistinguishability between Hyb2 and Hyb3 follows from the semantic securityof the encryption scheme.
- Hyb4 : We still generate g1 = EncryptF HE (PK1F HE , C1 ) and g2 = EncryptF HE (PK2F HE , C1 ) as1
in Hyb3 . Now P is created as P = iONC1 (P1(SKF HE ,g1 ,g2 ) ). Note that this hybrid corresponds
to obfuscation of C1 .
Computational indistinguishability between Hyb3 and Hyb4 follows from indistinguishability
obfuscation of NC1 obfuscator.

28

Bibliography[AGHS12]

Shweta Agrawal, Craig Gentry, Shai Halevi, and Amit Sahai. Sampling discrete gaussians efficiently and obliviously. Cryptology ePrint Archive, Report 2012/714, 2012.
http://eprint.iacr.org/.

[AGIS14]Prabhanjan Vijendra Ananth, Divya Gupta, Yuval Ishai, and Amit Sahai. Optimizing
obfuscation: Avoiding Barrington’s theorem. In Gail-Joon Ahn, Moti Yung, andNinghui Li, editors, ACM CCS 14: 21st Conference on Computer and Communications
Security, pages 646–658, Scottsdale, AZ, USA, November 3–7, 2014. ACM Press.

[AJ15]

Prabhanjan Ananth and Abhishek Jain. Indistinguishability obfuscation from compact
functional encryption. In Rosario Gennaro and Matthew J. B. Robshaw, editors,
Advances in Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in
Computer Science, pages 308–326, Santa Barbara, CA, USA, August 16–20, 2015.
Springer, Heidelberg, Germany.

[AJS15]

Prabhanjan Ananth, Abhishek Jain, and Amit Sahai. Indistinguishability obfuscation
with constant size overhead. Cryptology ePrint Archive, Report 2015/1023, 2015.
http://eprint.iacr.org/2015/1023.

[AR05]

Dorit Aharonov and Oded Regev. Lattice problems in np cap conp. J. ACM, 52(5):749–
765, 2005.

[Bar86]

D A Barrington. Bounded-width polynomial-size branching programs recognize exactly
those languages in nc1 . In STOC, 1986.

[BC10]

Nir Bitansky and Ran Canetti. On strong simulation and composable point obfuscation. In Tal Rabin, editor, Advances in Cryptology – CRYPTO 2010, volume 6223
of Lecture Notes in Computer Science, pages 520–537, Santa Barbara, CA, USA, August 15–19, 2010. Springer, Heidelberg, Germany.

[Bei11]

Amos Beimel. Secret-sharing schemes: A survey. In Yeow Meng Chee, Zhenbo Guo,
San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing,
editors, Coding and Cryptology - Third International Workshop, IWCC 2011, volume6639 of Lecture Notes in Computer Science, pages 11–46, Qingdao, China, May 30June 3 2011. Springer.

[BF11a]Dan Boneh and David Mandell Freeman. Homomorphic signatures for polynomial functions. In Kenneth G. Paterson, editor, Advances in Cryptology – EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pages 149–168,
Tallinn, Estonia, May 15–19, 2011. Springer, Heidelberg, Germany.
29

[BF11b]

Dan Boneh and David Mandell Freeman. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In Dario Catalano, Nelly Fazio,
Rosario Gennaro, and Antonio Nicolosi, editors, PKC 2011: 14th International Conference on Theory and Practice of Public Key Cryptography, volume 6571 of Lecture
Notes in Computer Science, pages 1–16, Taormina, Italy, March 6–9, 2011. Springer,
Heidelberg, Germany.

[BGI+ 01]

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P.
Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, Advances in Cryptology – CRYPTO 2001, volume 2139 of Lecture Notes
in Computer Science, pages 1–18, Santa Barbara, CA, USA, August 19–23, 2001.
Springer, Heidelberg, Germany.

[BGI+ 12]

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P.
Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. J. ACM,
59(2):6, 2012.

[BGK+ 14]

Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Protecting obfuscation against algebraic attacks. In Phong Q. Nguyen and Elisabeth
Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 221–238, Copenhagen, Denmark, May 11–15,
2014. Springer, Heidelberg, Germany.

[BMSZ15]

Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing
obfuscation: The case of evasive circuits. Cryptology ePrint Archive, Report 2015/167,
2015. http://eprint.iacr.org/2015/167.

[BPR15]

Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of findinga Nash equilibrium. In Venkatesan Guruswami, editor, 56th Annual Symposium on
Foundations of Computer Science, pages 1480–1498, Berkeley, CA, USA, October 17–
20, 2015. IEEE Computer Society Press.

[BR13]

Zvika Brakerski and Guy N. Rothblum. Obfuscating conjunctions. In Ran Canetti
and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part II, volume8043 of Lecture Notes in Computer Science, pages 416–434, Santa Barbara, CA, USA,
August 18–22, 2013. Springer, Heidelberg, Germany.

[BR14a]Zvika Brakerski and Guy N. Rothblum. Black-box obfuscation for d-CNFs. In MoniNaor, editor, ITCS 2014: 5th Innovations in Theoretical Computer Science, pages 235–
250, Princeton, NJ, USA, January 12–14, 2014. Association for Computing Machinery.

[BR14b]

Zvika Brakerski and Guy N. Rothblum. Virtual black-box obfuscation for all circuits
via generic graded encoding. In Yehuda Lindell, editor, TCC 2014: 11th Theory of
Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages
1–25, San Diego, CA, USA, February 24–26, 2014. Springer, Heidelberg, Germany.

[BS96]

Eric Bach and Jeffrey Shallit. Algorithmic Number Theory, Volume I: Efficient Algorithms. MIT Press, 1996.

[BS02]Dan Boneh and Alice Silverberg. Applications of multilinear forms to cryptography.
Cryptology ePrint Archive, Report 2002/080, 2002. http://eprint.iacr.org/2002/
080.
30

[BSW11]Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: definitions andchallenges. In TCC, pages 253–273, 2011.

[BV15]

Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation from functional encryption. In Venkatesan Guruswami, editor, 56th Annual Symposium on
Foundations of Computer Science, pages 171–190, Berkeley, CA, USA, October 17–
20, 2015. IEEE Computer Society Press.

[BVWW16] Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. Obfuscating
conjunctions under entropic ring LWE. In Madhu Sudan, editor, ITCS 2016: 7th
Innovations in Theoretical Computer Science, pages 147–156, Cambridge, MA, USA,
January 14–16, 2016. Association for Computing Machinery.
[BZ14]Dan Boneh and Mark Zhandry. Multiparty key exchange, efficient traitor tracing, andmore from indistinguishability obfuscation. In Juan A. Garay and Rosario Gennaro,
editors, Advances in Cryptology – CRYPTO 2014, Part I, volume 8616 of Lecture
Notes in Computer Science, pages 480–499, Santa Barbara, CA, USA, August 17–21,
2014. Springer, Heidelberg, Germany.

[Can97]

Ran Canetti. Towards realizing random oracles: Hash functions that hide all partial
information. In Burton S. Kaliski Jr., editor, Advances in Cryptology – CRYPTO’97,
volume 1294 of Lecture Notes in Computer Science, pages 455–469, Santa Barbara,
CA, USA, August 17–21, 1997. Springer, Heidelberg, Germany.

[CCV12]

Nishanth Chandran, Melissa Chase, and Vinod Vaikuntanathan. Functional reencryption and collusion-resistant obfuscation. In Ronald Cramer, editor, TCC 2012:
9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer
Science, pages 404–421, Taormina, Sicily, Italy, March 19–21, 2012. Springer, Heidelberg, Germany.

[CD08]Ran Canetti and Ronny Ramzi Dakdouk. Obfuscating point functions with multibit
output. In Nigel P. Smart, editor, Advances in Cryptology – EUROCRYPT 2008,
volume 4965 of Lecture Notes in Computer Science, pages 489–508, Istanbul, Turkey,
April 13–17, 2008. Springer, Heidelberg, Germany.

[CFL+ 16]

Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee, Brice Minaud, and Hansol
Ryu. Cryptanalysis of the new clt multilinear map over the integers. Cryptology
ePrint Archive, Report 2016/135, 2016. http://eprint.iacr.org/.

[CHL+ 15]

Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé.
Cryptanalysis of the multilinear map over the integers. In Elisabeth Oswald and Marc
Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part I, volume 9056
of Lecture Notes in Computer Science, pages 3–12, Sofia, Bulgaria, April 26–30, 2015.
Springer, Heidelberg, Germany.

[CIJ+ 13]

Angelo De Caro, Vincenzo Iovino, Abhishek Jain, Adam O’Neill, Omer Paneth, andGiuseppe Persiano. On the achievability of simulation-based security for functional
encryption. In CRYPTO, 2013.

[CLLT15]

Jean-Sebastien Coron, Moon Sung Lee, Tancrede Lepoint, and Mehdi Tibouchi. Cryptanalysis of GGH15 multilinear maps. Cryptology ePrint Archive, Report 2015/1037,
2015. http://eprint.iacr.org/2015/1037.
31

[CLR15]

Jung Hee Cheon, Changmin Lee, and Hansol Ryu. Cryptanalysis of the new CLT multilinear maps. Cryptology ePrint Archive, Report 2015/934, 2015. http://eprint.
iacr.org/2015/934.

[CLT13]Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear
maps over the integers. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science,
pages 476–493, Santa Barbara, CA, USA, August 18–22, 2013. Springer, Heidelberg,
Germany.

[CLT15]Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. New multilinear maps
over the integers. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advancesin Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer
Science, pages 267–286, Santa Barbara, CA, USA, August 16–20, 2015. Springer,
Heidelberg, Germany.

[CMR98]Ran Canetti, Daniele Micciancio, and Omer Reingold. Perfectly one-way probabilistic
hash functions (preliminary version). In 30th Annual ACM Symposium on Theory ofComputing, pages 131–140, Dallas, Texas, USA, May 23–26, 1998. ACM Press.

[CRV10]

Ran Canetti, Guy N. Rothblum, and Mayank Varia. Obfuscation of hyperplane membership. In Daniele Micciancio, editor, TCC 2010: 7th Theory of Cryptography Conference, volume 5978 of Lecture Notes in Computer Science, pages 72–89, Zurich,
Switzerland, February 9–11, 2010. Springer, Heidelberg, Germany.

[DH76]

Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.

[DPSZ11]

I. Damgard, V. Pastro, N.P. Smart, and S. Zakarias. Multiparty computation fromsomewhat homomorphic encryption. Cryptology ePrint Archive, Report 2011/535,
2011. http://eprint.iacr.org/.

[Gen09]Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. crypto.stanford.edu/craig.

[GGH13a]Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal
lattices. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology– EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 1–17,
Athens, Greece, May 26–30, 2013. Springer, Heidelberg, Germany.

[GGH+ 13b] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent
Waters. Candidate indistinguishability obfuscation and functional encryption for all
circuits. In 54th Annual Symposium on Foundations of Computer Science, pages 40–
49, Berkeley, CA, USA, October 26–29, 2013. IEEE Computer Society Press.
[GGH+ 13c] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent
Waters. Candidate indistinguishability obfuscation and functional encryption for all
circuits. Cryptology ePrint Archive, Report 2013/451, 2013. http://eprint.iacr.
org/.

32

[GGH15]

Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps
from lattices. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th
Theory of Cryptography Conference, Part II, volume 9015 of Lecture Notes in Computer Science, pages 498–527, Warsaw, Poland, March 23–25, 2015. Springer, Heidelberg, Germany.

[GGHR14] Sanjam Garg, Craig Gentry, Shai Halevi, and Mariana Raykova. Two-round secure
MPC from indistinguishability obfuscation. In Yehuda Lindell, editor, TCC 2014: 11th
Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages 74–94, San Diego, CA, USA, February 24–26, 2014. Springer, Heidelberg,
Germany.
[GGSW13] Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption andits applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors,
45th Annual ACM Symposium on Theory of Computing, pages 467–476, Palo Alto,
CA, USA, June 1–4, 2013. ACM Press.
[GH10]

Craig Gentry and Shai Halevi. Implementing gentry’s fully-homomorphic encryption
scheme. Cryptology ePrint Archive, Report 2010/520, 2010. http://eprint.iacr.
org/.

[GKP+ 13]

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, andNickolai Zeldovich. How to run turing machines on encrypted data. In Ran Canetti
and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part II, volume8043 of Lecture Notes in Computer Science, pages 536–553, Santa Barbara, CA, USA,
August 18–22, 2013. Springer, Heidelberg, Germany.

[GLSW15]

Craig Gentry, Allison Bishop Lewko, Amit Sahai, and Brent Waters. Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In Venkatesan
Guruswami, editor, 56th Annual Symposium on Foundations of Computer Science,
pages 151–170, Berkeley, CA, USA, October 17–20, 2015. IEEE Computer Society
Press.

[GPS15]

Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. On the exact cryptographic hardness of finding a nash equilibrium. Cryptology ePrint Archive, Report
2015/1078, 2015. http://eprint.iacr.org/2015/1078.

[GPSW06] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based encryption for fine-grained access control of encrypted data. In Ari Juels, Rebecca N.
Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 06: 13th Conference on Computer and Communications Security, pages 89–98, Alexandria, Virginia,
USA, October 30 – November 3, 2006. ACM Press. Available as Cryptology ePrint
Archive Report 2006/309.
[GPSZ16]

Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan, and Mark Zhandry. Breaking the sub-exponential barrier in obfustopia. Cryptology ePrint Archive, Report
2016/102, 2016. http://eprint.iacr.org/2016/102.

[GPV08]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices
and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, edi-

33

tors, 40th Annual ACM Symposium on Theory of Computing, pages 197–206, Victoria,
British Columbia, Canada, May 17–20, 2008. ACM Press.
[GR07]

Shafi Goldwasser and Guy N. Rothblum. On best-possible obfuscation. In Salil P.
Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of
Lecture Notes in Computer Science, pages 194–213, Amsterdam, The Netherlands,
February 21–24, 2007. Springer, Heidelberg, Germany.

[Had10]

Satoshi Hada. Secure obfuscation for encrypted signatures. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in
Computer Science, pages 92–112, French Riviera, May 30 – June 3, 2010. Springer,
Heidelberg, Germany.

[HMLS07]

Dennis Hofheinz, John Malone-Lee, and Martijn Stam. Obfuscation for cryptographic
purposes. In Salil P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, pages 214–232, Amsterdam,
The Netherlands, February 21–24, 2007. Springer, Heidelberg, Germany.

[HRsV07]

Susan Hohenberger, Guy N. Rothblum, abhi shelat, and Vinod Vaikuntanathan. Securely obfuscating re-encryption. In Salil P. Vadhan, editor, TCC 2007: 4th Theory of
Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, pages
233–252, Amsterdam, The Netherlands, February 21–24, 2007. Springer, Heidelberg,
Germany.

[Jan96]

Gerald J. Janusz. Algebraic Number Fields. American Mathematical Society, 1996.

[JHC16]

Changmin Lee Jung Hee Cheon, Jinhyuck Jeong. An algorithm for ntru problems andcryptanalysis of the ggh multilinear map without an encoding of zero. Cryptology
ePrint Archive, Report 2016/139, 2016. http://eprint.iacr.org/.

[Jou00]Antoine Joux. A one round protocol for tripartite diffie-hellman. In Algorithmic
Number Theory - ANTS’00, volume 1838 of Lecture Notes in Computer Science, pages
385–394. Springer, 2000.

[Lan90]S. Lang. Cyclotomic Fields I and II: With and Appendix by Karl Rudin. Graduate
Texts in Mathematics. Springer-Verlag, 1990.

[LM06]

Vadim Lyubashevsky and Daniele Micciancio. Generalized compact Knapsacks arecollision resistant. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo
Wegener, editors, ICALP 2006: 33rd International Colloquium on Automata, Languages and Programming, Part II, volume 4052 of Lecture Notes in Computer Science,
pages 144–155, Venice, Italy, July 10–14, 2006. Springer, Heidelberg, Germany.

[LPR10]Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learningwith errors over rings. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 1–23, French
Riviera, May 30 – June 3, 2010. Springer, Heidelberg, Germany.

[LPR12]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learningwith errors over rings. Cryptology ePrint Archive, Report 2012/230, 2012. http://eprint.iacr.org/.
34

[LPS04]

Ben Lynn, Manoj Prabhakaran, and Amit Sahai. Positive results and techniques forobfuscation. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology– EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 20–
39, Interlaken, Switzerland, May 2–6, 2004. Springer, Heidelberg, Germany.

[MA16]Lo Ducas Martin Albrecht, Shi Bai. A subfield lattice attack on overstretched ntru
assumptions: Cryptanalysis of some fhe and graded encoding schemes. Cryptology
ePrint Archive, Report 2016/127, 2016. http://eprint.iacr.org/.

[MR07]

Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on
gaussian measures. SIAM J. Computing, 37(1):267–302, 2007.

[MSW14]Eric Miles, Amit Sahai, and Mor Weiss. Protecting obfuscation against arithmetic
attacks. Cryptology ePrint Archive, Report 2014/878, 2014. http://eprint.iacr.
org/2014/878.

[MSZ16]

Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear
maps: Cryptanalysis of indistinguishability obfuscation over ggh13. Cryptology ePrint
Archive, Report 2016/147, 2016. http://eprint.iacr.org/.

[O’N10]Adam O’Neill. Definitional issues in functional encryption. Cryptology ePrint Archive,
Report 2010/556, 2010. http://eprint.iacr.org/.

[Oss08]

Brian Osserman. Algebraic Number Theory. Lecture Notes, 2008. https://www.math.
ucdavis.edu/~osserman/classes/numthy/numthybook.pdf.

[Reg04]

Oded Regev. New lattice-based cryptographic constructions. J. ACM, 51(6):899–942,
2004.

[RSA78]

Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining
digital signature and public-key cryptosystems. Communications of the Association
for Computing Machinery, 21(2):120–126, 1978.

[Rud89]

Steven Rudich. Unpublished, 1989.

[Sha84]Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley andDavid Chaum, editors, Advances in Cryptology – CRYPTO’84, volume 196 of Lecture
Notes in Computer Science, pages 47–53, Santa Barbara, CA, USA, August 19–23,
1984. Springer, Heidelberg, Germany.

[SL96]

Peter Stevenhagen and Hendrik W Lenstra. Chebotarëv and his density theorem. The
Mathematical Intelligencer, 18(2):26–37, 1996.

[SS11]

Damien Stehlé and Ron Steinfeld. Making NTRU as secure as worst-case problems
over ideal lattices. In Kenneth G. Paterson, editor, Advances in Cryptology – EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pages 27–47,
Tallinn, Estonia, May 15–19, 2011. Springer, Heidelberg, Germany.

[Ste04]

William Stein. A Brief Introduction to Classical and Adelic Algebraic Number Theory.
2004. http://modular.math.washington.edu/129/ant/ant.pdf.

[Ste10]C. L. Stewart. On divisors of lucas and lehmer numbers. 2010.
35

[SV10]Nigel P. Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Phong Q. Nguyen and David Pointcheval,
editors, PKC 2010: 13th International Conference on Theory and Practice of Public
Key Cryptography, volume 6056 of Lecture Notes in Computer Science, pages 420–443,
Paris, France, May 26–28, 2010. Springer, Heidelberg, Germany.

[SW05]

Amit Sahai and Brent R. Waters. Fuzzy identity-based encryption. In Ronald Cramer,
editor, Advances in Cryptology – EUROCRYPT 2005, volume 3494 of Lecture Notes
in Computer Science, pages 457–473, Aarhus, Denmark, May 22–26, 2005. Springer,
Heidelberg, Germany.

[SW13]

Alice Silverberg and Lawrence Washingoton, 2013. Personal Communication.

[SW14]

Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable
encryption, and more. In David B. Shmoys, editor, 46th Annual ACM Symposium on
Theory of Computing, pages 475–484, New York, NY, USA, May 31 – June 3, 2014.
ACM Press.

[Was97]

L.C. Washington. Introduction to Cyclotomic Fields. Graduate Texts in Mathematics.
Springer-Verlag, 1997.

[Wee05]

Hoeteck Wee. On obfuscating point functions. In Harold N. Gabow and Ronald
Fagin, editors, 37th Annual ACM Symposium on Theory of Computing, pages 523–
532, Baltimore, Maryland, USA, May 22–24, 2005. ACM Press.

[Wes99]Tom Weston. Algebraic Number Theory. Course Notes, 1999. https://www.math.
umass.edu/~weston/cn/notes.pdf.

36