### Abstract

At least since the initial public proposal of public-key cryptography based on computational hardness conjectures, cryptographers have contemplated the possibility of a “one-way compiler” that translates computer programs into “incomprehensible” but equivalent forms. And yet, the search for such a “one-way compiler” remained elusive for decades. We examine a formalization of this concept with the notion of indistinguishability obfuscation (*i*𝒪). Roughly speaking, *i*𝒪 requires that the compiled versions of any two equivalent programs (with the same size and running time) be indistinguishable from any efficient adversary. Finally, we show how to construct *i*𝒪 in such a way that we can prove the security of our *i*𝒪 scheme based on well-studied computational hardness conjectures in cryptography.

## Introduction

Consider the polynomial *f*_{1}(*x,y*)ɛℤ[*x,y*] that is computed as follows:

Alternatively, contemplate the polynomial *f*_{2}(*x,y*)ɛℤ[*x,y*] that is computed via:

A calculation shows that *f*_{1} and *f*_{2} are in fact the same polynomial, computed in two different ways. Indeed, the expressions *f*_{1} and *f*_{2} above are special cases of *arithmetic circuits*, which precisely represent “ways to compute a polynomial.”

What if we wanted to hide all implementation choices made when creating such an arithmetic circuit for a particular polynomial? An easy way to do that would be to first convert our polynomial into a canonical form and then implement the canonical form as an arithmetic circuit. Indeed, the description of *f*_{2} above can be seen as a canonical representation of the polynomial as a sum of monomials with regard to a natural monomial ordering. However, as this example illustrates, canonical forms can be substantially more complex than other implementations of the same polynomial. For polynomials in *n* variables, the loss in efficiency can be exponential in *n*. This would often make computing the canonical form – or indeed, even writing it down – infeasible.

### A pseudo-canonical form

Given that computing, canonical forms can be infeasible, what is there to do? Here, following,^{7} we draw an analogy to the notion of pseudo-randomness. When truly random values are not available, we can instead aim to produce values that “look random” by means of a pseudo-random generator. That is, we require that no efficient algorithm can distinguish between truly random values and the output of our pseudo-random generator.

Now, for two arithmetic circuits *g*_{1} and *g*_{2} that compute the same underlying polynomial, a true canonical form `Canonical`

(*g*_{1}) would be identical to the canonical form of `Canonical`

(*g*_{2}). Instead, we would ask that a pseudo-canonical form `PseudoCanonical`

(*g*_{1}) would simply be indistinguishable from the pseudo-canonical form `PseudoCanonical`

(*g*_{2}), to all efficient algorithms that were given *g*_{1} and *g*_{2} as well. Observe that unless there are actual efficiently computable canonical forms for all arithmetic circuits – which we do not believe to be true – it must be that such a `PseudoCanonical`

operator is randomized, and outputs a *probability distribution* over arithmetic circuits computing the same polynomial.

### The computing lens

The classic theory of computation tells us that general computer programs can be converted into equivalent polynomials (albeit over finite fields, which we will focus on implicitly in the sequel). So the pseudo-canonicalization question posed above is equivalent to the pseudo-canonicalization question for general computer programs. Indeed, the question of hiding implementation details within a computer program has a long history, dating at least as far back as the groundbreaking 1976 work of Diffie and Hellman^{13} introducing the concept of public-key cryptography. Historically, this problem has been called “program obfuscation,” albeit it was typically discussed in an ill-defined form. Discussed in these vague terms, it was folklore that truly secure program obfuscation would have revolutionary applications to computing, especially for securing intellectual property. The work of Barak et al.^{7} gave a formal treatment of this problem and proved the impossibility of strong forms of generalpurpose program obfuscation. This work also formalized the pseudo-canonicalization problem discussed above via the notion of *indistinguishability obfuscation* (*i*𝒪). Writing now in the language of Boolean circuits, we define the problem below:

**Definition 1. (Indistinguishability Obfuscator (iO) for Circuits.**

^{7})A probabilistic polynomial-time algorithm (*i*𝒪) is called a secure indistinguishability obfuscator for polynomial-sized circuits if the following holds:

**Completeness:**For every ⋋ɛℕ every circuit*C*with input length*n*, every input*x*ɛ {0,1}^{n}we have that $Pr[\tilde{C}(x)=C(x):\tilde{C}\leftarrow iO({1}^{\lambda},C)]=1.$**Indistinguishability:**For every two ensembles ${\left\{{C}_{0,\lambda}\right\}}_{\lambda \in {Z}^{+}}$ and ${\left\{{C}_{1,\lambda}\right\}}_{\lambda \in {Z}^{+}}$ of polynomial-sized circuits that have the same size, input length, and output length, and are functionally equivalent, that is, ∀ ⋋ɛℤ^{+},*C*_{0,⋋}(*x*) =*C*_{1,⋋}(*x*) for every input*x*, the distributions*i*𝒪(1^{⋋},*C*_{0,⋋}) and are*computationally indistinguishable*, denoted as:$[iO({1}^{\lambda},{C}_{0,\lambda})\}{\approx}_{c}\{iO({1}^{\lambda},{C}_{1,\lambda})\}\mathrm{.}$

It means or every efficient polynomial-time algorithm

*D*, for every constant*c*> 0, there exists a constant ⋋_{0}ɛℤ^{+}, such that for all ⋋ > ⋋_{0}, we have: $\left|Pr\right[D(iO({1}^{\lambda},\u205f{C}_{0,\lambda}))=1]\u2013Pr[D(iO({1}^{\lambda},\u205f{C}_{1,\lambda}))=1\left]\right|\le \frac{1}{{\lambda}^{c}}$

As we discuss in Section 1.4, indeed *i*𝒪 as a formalization of pseudo-canonicalization lived up to the folklore promise of software obfuscation: there was, and still is, a large research community studying novel applications of *i*𝒪.

In contrast, demonstrating the feasibility of constructing *i*𝒪 proved far more challenging. Often one expects that theory will lag behind the practice, and given the folklore promise of software obfuscation, one might expect that over the years perhaps clever programmers had come up with heuristic approaches to software obfuscation that resisted the attack. The reality is the opposite. Indeed, in 2021 the third annual White Box Cryptography contest was held to evaluate heuristic methods for software obfuscation, and every one of the 97 submitted obfuscations was broken before the contest ended.^{1}

A large body of theoretical work, starting with the pioneering work of Garg et al.^{14} has attempted to construct *i*𝒪 using mathematical tools. However, before the result^{18} by the authors of this article, all previous mathematical approaches to constructing *i*𝒪 relied on new, unproven mathematical assumptions, many of which turned out to be false (see Jain et al.^{18} for a list of prior constructions.)

We would like to build *i*𝒪 whose security rests upon cryptographic hardness assumptions that have stood the test of time, have a long history of study, and are widely believed to be true. The main result of our works^{18}^{,}^{19} is the construction of an *i*𝒪 scheme from three well-studied assumptions. We discuss this in more detail next.

**Theorem 1**

Under the following assumptions^{18}^{,}^{19}^{,}^{a}:

*the Learning Parity with Noise*(`LPN`

)*assumption over general prime fields ℤ*_{p}with polynomially many`LPN`

*samples and error rate*1/*k*^{δ}, where k is the dimension of the`LPN`

*secret, and δ > 0 is any constant;**the existence of a Boolean Pseudo-Random Generator (*PRG*) in*NC^{0}*with stretch n*^{1+τ, where n is the length of the PRG seed, and τ > 0 is any constant;}*the Decision Linear (*DLIN*) assumption on symmetric bilinear groups of prime order*.

*Indistinguishability obfuscation for all polynomial-size circuits exists*.

The three assumptions above (discussed further in Section 1.3) are based on computational problems with a long history of study, rooted in complexity, coding, and number theory. Further, they were introduced for building basic cryptographic primitives (such as public key encryption), and have been used for realizing a variety of cryptographic goals that have nothing to do with *i*𝒪.

### Assumptions in more detail

We now describe each of the assumptions we need in more detail and briefly survey their history.

**The**`DLIN`

**Assumption:** The Decisional Linear assumption (DLIN) is stated as follows: For an appropriate *⋋*-bit prime *p*, two groups 𝔾 and 𝔾* _{T}* are chosen of order

*p*such that there exists an efficiently computable nontrivial symmetric bilinear map

*e*:𝔾×𝔾→𝔾

_{T}. A canonical generator

*g*for 𝔾 is also computed. Following the tradition of cryptography, we describe the groups above using multiplicative notation, even though they are cyclic. The

`DLIN`

assumption requires that the following computational indistinguishability holds:This assumption was first introduced in the 2004 work of Boneh et al.^{10} and instantiated using appropriate elliptic curves. Since then DLIN and assumptions implied by DLIN have seen extensive use in a wide variety of applications throughout cryptography, such as Identity-Based Encryption, Attribute-Based Encryption, Functional Encryption for degree 2 polynomials, Non-Interactive Zero-Knowledge, etc.

**The Existence of**`PRG`

**s in**`NC`

^{0}: The assumption of the existence of a Boolean Pseudo-Random Generator PRG in NC^{0} states that there exists a Boolean function **G**:{0,1}^{n}→{0,1}^{m} where *m* = *n*^{1+τ} for some constant *τ* > 0, and where each output bit computed by G depends on a constant number of input bits, such that the following computational indistinguishability holds:

Pseudorandom generators are a fundamental primitive in their own right and have vast applications throughout cryptography. PRGs in NC^{0} are tightly connected to the fundamental topic of Constraint Satisfaction Problems (CSPs) in complexity theory and were first proposed for cryptographic use by Goldreich^{16} 20 years ago. The complexity theory and cryptography communities have jointly developed a rich body of literature on the cryptanalysis and theory of constant-locality Boolean PRGs.

`LPN`

**over large fields:** The Learning Parity with Noise `LPN`

assumption over finite fields ℤ_{p} is a decoding problem. The standard `LPN`

assumption with respect to subexponential size modulus *p*, dimension ℓ, sample complexity *n*, and a noise rate *r* = 1/ℓ^{δ} for some *δ*ɛ(0,1), states that the following computational indistinguishability holds:

Above e ← 𝒟* _{r}* is a generalized Bernoulli distribution,

*i.e. e*is sampled randomly from ℤ

*with probability 1/ℓ*

_{p}^{δ}and set to be 0 with probability 1 − 1/ℓ

^{δ}. We consider polynomial sample complexity

*n*(ℓ), and the modulus

*p*is an arbitrary subexponential function in ℓ.

The origins of the `LPN`

assumption date all the way back to the 1950s (e.g. Gilbert^{15}): it has long been known that random linear codes possessed remarkably strong minimum distance properties. However, since then, very little progress has been made inefficiently decoding random linear codes under random errors. The `LPN`

over fields assumption above formalizes this, and was introduced over ℤ_{2} for cryptographic uses in 1994,^{9} and formally defined for general finite fields and parameters in 2009,^{17} under the name “Assumption 2.”

While in Ishai et al.^{17} the assumption was used when the error rate was assumed to be a constant, in fact, polynomially low error (in fact δ= 1/2) has an even longer history in the `LPN`

literature: it was used by Alekhnovitch^{2} to construct public-key encryption with the field ℤ_{2}, and used to build public-key encryption over ℤ* _{p}* in 2015.

^{5}The exact parameter settings that we describe above, with both general fields and inverse polynomial error rate corresponding to an arbitrarily small constant δ > 0 was explicitly posed by Boyle,

^{11}in the context of building efficient secure two-party and multi-party protocols for arithmetic computations.

Recently, the LPN assumption has led to a wide variety of applications. A comprehensive review of known attacks on `LPN`

over large fields, for the parameter settings we are interested in, was given in Boyle.^{11}^{,}^{12} For our parameter setting, the running time of all known attacks is $\Omega \left({{2}^{\ell}}^{1-\delta}\right)$, for any choice of the constant δɛ(0,1) and for any polynomial number of samples *n*(ℓ).

Finally, we mention that except for the `DLIN`

assumption, the other two assumptions, `LPN`

and `PRG`

in `NC`

^{0}, have search-to-decision reductions.

*i*𝒪

Applications of The notion of *i*𝒪 occupies an intriguing and influential position in complexity theory and cryptography. Interestingly, if **NP** ⊆ **BPP** then *i*𝒪 exists for the class of all polynomial size circuits, because if **NP** ⊆ **BPP**, then it is possible to efficiently compute a canonical form for any function computable by a polynomial-size circuit. This is in contrast to most powerful cryptographic objects, which typically imply the existence of one-way functions. A large body of work has shown that *i*𝒪 plus one-way functions imply a vast array of cryptographic objects, so much so that *iO* has been conjectured to be a “central hub”^{24} for cryptography. In addition, an impressive list of fascinating new cryptographic objects is only known under *i*𝒪 or related objects.

We highlight a small subset of these implications (see Jain et al.^{18} and the references therein): *multiparty non-interactive key exchange* in the plain model, *zero-knowledge succinct noninteractive arguments* (ZK-SNARGs) for any NP language, *multilinear maps* with bounded polynomial multilinear degrees, *witness encryption* for any NP language, *functional encryption* supporting all polynomial-sized circuits, and *fully homomorphic encryption schemes* (FHE) for unbounded-depth polynomial-size circuits.

### Open problems

Our workplaces *i*𝒪 on firm foundations with respect to the assumptions is based on, thereby answering the main feasibility question for the primitive (until we resolve the P vs. NP question). However, there are many important open questions that remain to be answered. One of the main questions is whether there is a construction that is very simple to describe and efficient to implement in practice. Our construction is quite complex, relies on a number of steps, and is recursive in nature. As a consequence, the actual asymptotic complexity is some large polynomial. Simplifying and finding more efficient paths to building *i*𝒪 from well-studied assumptions is one of the most important problems that must be solved, toward the vision of using *i*𝒪 as a universal tool.

*i*𝒪?

Overview: How to Construct In the remaining of the article, we describe a very high level overview of the main technical ideas implying *i*𝒪. For simplicity of exposition, we choose the simplest path to *i*𝒪 that we are aware of. This overview is based on a combination of ideas from Jain et al.,^{18}^{,}^{19} which, however, would require one additional assumption to the three stated above (See Theorem 1) – namely, the Learning With Errors (LWE)^{23} assumption. Since the exact technical reasons for needing LWE is not important for this overview, and this assumption is actually unnecessary,^{19} we do not discuss it in detail here.

### Preliminaries

Let’s start with introducing some basic notation. Let size(*X*) indicates the length of the binary description of an object *X* (e.g., a string, a circuit, or truth table). Throughout, we consider Boolean functions or circuits or algorithms mapping *n*-bit binary strings to *m*-bit binary strings, for some *n, m* ɛℤ^{+}. Let time(*A, x*) denotes the running time of an algorithm (or circuit) *A* on an input *x* (in the case of a circuit *C*, time(*C, x*) is the same as size(*C*)). We say that an algorithm or circuit is efficient if its running time is bounded by a (fixed) polynomial in the length of the input, that is, time(*C, x*) = size(*x*)* ^{c}* for some positive integer

*c*ɛℤ

^{+}. When we only care about the existence of a constant and the concrete value is not important, we write

*O*(1) in place of that constant, e.g., time(

*C, x*) = size(

*x*)

^{O(1)}(following the big-O notation in complexity theory).

Restating our goal, we want to design an efficient *randomized* algorithm, called the obfuscator 𝒪, that given a Boolean circuit *C*: {0, 1}* ^{n}* → {0, 1} with size

*s*≤

*n*

^{O(1)}, referred to as the original circuit, outputs another Boolean circuit Ĉ:{0,1}

^{n}→ {0,1}, called the obfuscated circuit, such that the following three properties hold:

Correctness: the obfuscated circuit Ĉ is

*functionally equivalent*to the original circuit*C*, denoted as Ĉ ≡, meaning that for every*x*ɛ{0,1}^{n}, Ĉ(*x*) =*C(x)*Correctness must hold no matter what random coins the obfuscator 𝒪 used.Efficiency: the obfuscator is efficient, meaning 𝒪 runs in time polynomial in the size of the original circuit, namely,

**time**(𝒪,*C*)=size(*C*)^{o(1)}Security: the obfuscated circuit Ĉ hides the implementation details in the original circuit

*C*. That is, for every two,*equally-sized*and*functionally-equivalent*circuits*C*_{0}and*C*_{1}(i.e., size(*C*_{0}) = size(*C*_{1}) and*C*_{0}≡*C*_{1}), the obfuscated circuits Ĉ_{0}and Ĉ_{1}are*computationally hard to distinguish*(as defined in Definition 1; see also Jain et al.^{18}).

Next, we give an informal overview of how to construct *i*𝒪 from well-studied assumptions.

*i*𝒪

Simplifying the task of Perhaps the simplest starting point is the following: If there is no restriction on the time the obfuscator 𝒪 can take, then there is an extremely intuitive obfuscator: the obfuscated circuit is the *truth table* of the original circuit. The truth table TT* _{C}* of a Boolean circuit

*C*is an array indexed by inputs, where TT

*[*

_{C}*x*] =

*C*(

*x*). It can be computed in time 2

*·*

^{n}*s*if the input length is

*n*and the circuit size is

*s*. Perfect security comes from the fact that for any two functionally equivalent circuits

*C*

_{0}≡

*C*

_{1}, their truth tables are identical ${\text{TT}}_{{C}_{0}}={\text{TT}}_{{C}_{1}}$ and hence impossible to distinguish.

To put simply, a truth table is a *canonical form* of all circuits producing it. While outputting the truth table satisfies the correctness and security requirement of *i*𝒪, the obvious flaw with this is that the obfuscator is far from efficient: The running time of an *i*𝒪 scheme should be *s*^{O(1)}, rather than 2* ^{n}* ·

*s*. The input length

*n*of a Boolean circuit can be close to its size

*s*, and hence the time to compute a truth table is exponentially large! This inefficiency is likely inherent, as efficient methods of finding canonical forms of circuits imply the collapse of the polynomial hierarchy, which is widely conjectured to be false.

Therefore, to improve efficiency, we seek canonical forms that fool computationally limited adversaries. Naturally, we start with a more humble goal:

Can we improve efficiency slightly to, say2^{n(1−ɛ)}·s^{o(1)}for some smallɛ > 0?What does i𝒪with such non-trivial efficiency imply?

**Simplification 1: Obfuscation with non-trivial exponential efficiency.** *i*𝒪 with non-trivial efficiency was studied in Lin et al.^{21} Surprisingly, they showed that a very modest improvement on efficiency – captured in the notion of exponential-efficiency *i*𝒪 or *xi*𝒪 for short – is actually enough to construct completely efficient (polynomial time) *i*𝒪^{b}.

*xi*𝒪 is an obfuscator 𝒪 whose running time is still “trivial” (2·^{n}*s*)^{O(1)}, but outputs an obfuscated circuit Ĉ of “non-trivial” size 2^{n(1−ɛ)}·*s*^{o(1)}for some ɛ > 0.

We can think of *xi*𝒪 (as well as *i*𝒪) as a special kind of encryption method, where the obfuscated circuit Ĉ is a “ciphertext” of the original circuit *C*, also denoted as **spCT**(*C*)=Ĉ, satisfying that

the ciphertext spCT(

*C*) hides all information about*C*, except that it lets anyone with access to it learn the truth table of*C*. This is unlike normal encryption which reveals no information about the encrypted message.The size of the ciphertext spCT(

*C*) is 2^{(1−ɛ)·n}for some 0 < ɛ < 1 So it can be viewed as a (slightly) compressed version of the truth table (that reveals no other information of*C*to computationally limited adversaries).

The such special encryption scheme is known as *functional encryption*, which controls precisely which information of the encrypted message is revealed, and hides all other information. This notion is tightly connected with *xi*𝒪 and *i*𝒪, and, in fact, the implication of *xi*𝒪 to *i*𝒪 goes via the notion of functional encryption.

When viewing spCT(*C*) as a compressed version of the truth table. It becomes clear why even slight compression is powerful enough to imply *i*𝒪: The idea is keeping compressing iteratively until the size of the special ciphertext becomes polynomial. The works of Ananth and Jain,^{3} Bitansky and Vaikuntanathan,^{8} and Lin et al.^{21} turn this high-level idea into an actual proof that *xi*𝒪 implies *i*𝒪^{c} and allows us to focus on constructing *xi*𝒪, or equivalently the special encryption described above.

**Simplification 2: It suffices to obfuscate simple circuits.** Unfortunately, despite the efficiency relaxation, it is still unclear how to obfuscate general Boolean circuits, which can be complex. Naturally, we ask:

Can we obfuscate simple sub-classes of circuits? What does xi𝒪for simple circuits imply?

It turns out that it suffices to focus on an extremely simple class of circuits C = NC^{0}, where NC^{0} is the set of all circuits with constant *output locality*, meaning every output bit depends on a constant number of input bits. To do so, we will rely on two cryptographic tools, *randomized encodings* and *Pseudo-Random Generators (PRGs)*.

**Randomized encoding in NC0.** A Randomized Encoding (RE) scheme consists of two efficient algorithms (RE, Decode). It gives a way to represent a complex circuit *C*(·), by a much simpler *randomized* circuit RE* _{C}*(·; ·) := RE(

*C*, ·; ·), such that,

Correctness: for every input

*x*, the output*π*of RE(_{x}*C, x*;*r*) produced using uniformly random coins*r*encodes the correct output: In other words, there exists an efficient decoding algorithm Decode such that Decode(*π*) =*C*(*x*).Security:

*π*reveals no information of_{x}*C*beyond the output of*x*to efficient adversaries.Simplicity: RE is a simple circuit by some measure of simplicity. Classic works

^{6}^{,}^{25}showed that RE can be simply a NC^{0}circuit, when assuming the existence of PRGs in NC^{0}like we are.

The correctness and security of the randomized encoding suggest that, instead of directly obfuscating a general circuit *C*, we can alternatively obfuscate a circuit *D* that on input *x* outputs an encoding *π _{x}*, which reveals only

*C*(

*x*). The potential benefit is that

*D*depending on RE and

*C*should be simply NC

^{0}circuit. Hence, it would suffice to construct

*xi*𝒪 for simple NC

^{0}circuits!

To make the above idea goes through, there are, however, a few wrinkles to be ironed out. The issue is that the security of randomized encoding only holds if an encoding *π _{x}* is generated using fresh random coins. There are concrete attacks that learn information of

*C*beyond the outputs, when

*π*is generated using non-uniform random coins, or when two encoding

_{x}*π*and

_{x}*π*are generated using correlated random coins. If the truth table of the circuit

_{x′}*D*contains an encoding

*π*for every input

_{x}*x*(i.e., TT

*[*

_{D}*x*] =

*π*) the random coins for generating these encodings must be embedded in

_{x}*D*, that is,

Such a circuit *D* has size at least 2* ^{n}*. In particular, we cannot hope to “compress” the random coins

*r*

_{1},

*r*

_{2}, …,

*r*

_{2}into 2

^{n(1−ɛ)}space, which is the target size of the obfuscated circuit. To resolve this problem, we will use a Pseudo-Random Generator.

**Pseudo-random generator in NC0.** Recall that a pseudo-random generator is a Boolean function PRG: {0, 1}* ^{n}* → {0, 1}

*that takes as input a uniformly random seed*

^{m}**sd**ɛ{0,1}

^{n}, and produces a polynomially longer output

*r*ɛ{0,1}

^{m}, where

*m*= n

^{1+ρ}for some constant

*ρ*> 0, such that,

*r*is indistinguishable to a uniformly random

*m*-bit string to computationally limited adversaries. There are several proposals of pseudo-random generators that can be computed by an NC

^{0}function.

Equipped with a pseudo-random generator in NC^{0}, we can replace uniformly random coins ${r}_{1},{r}_{2},\cdot \cdot \cdot ,{r}_{{2}^{n}}$ with pseudorandom coins expanded from a much shorter seed sd of length roughly ${2}^{n/(1+\rho )}={2}^{n(1-\u03f5\prime )}$ for some ε′ɛ(0,1)^{d}. This gives a variant of the circuit *D* above:

where PRG(sd) expands to output ${r}_{1},\cdot \cdot \cdot ,{r}_{{2}^{n}}$ and *r _{x}* = PRG

*(sd) is the*

_{x}*x*‘th chunk of the output. Thanks to the fact that both PRG and RE are in NC

^{0}, so is

*D′*.

Moving forward, it suffices to devise a way to encrypt *C*, sd into a ciphertext spCT(*C*, sd), from which we can expand out the truth table of *D′*, while hiding all other information of *C* and sd.

Note that the special encryption only needs to hide (*C*, sd), instead of the entire description of circuit *D′* since RE and PRG are public algorithms. Moreover, the truth table of *D′* can be computed from (*C*, sd) via a function *G*_{RE, PRG} in NC^{0}.

^{0} mappings

Special encryption for NCIn our works,^{18}^{,}^{19} we constructed the needed special encryption for general NC^{0} mappings *G*: {0, 1}* ^{l}* → {0, 1}

*, where ciphertext spCT(*

^{m}*X*) reveals the output of

*G*on

*X*while hiding all other information of

*X*, such that size(spCT(

*X*)) ~ size(

*X*) +

*m*

^{1−δ}for some δ > 0. In this subsection, we describe the first half of the ideas behind our construction, which connects the special encryption with bilinear pairing groups and a new object called a structured-seed pseudo-random generator. The second half of the ideas are explained in Section 2.5, describing the construction of a structured-seed pseudorandom generator.

**Connection with bilinear pairing groups.** As a starting point, suppose that the function *G* is really simple: Simple enough so that it can be computed by a degree-2 polynomial mapping $Q:{Z}_{p}^{l}\to {Z}_{p}^{m}$ over the finite field ℤ_{p} for some prime modulus *p*. Namely,

Then, the special encryption can be implemented using bilinear pairing groups, as shown in Ananth and Sahai,^{4} and Lin.^{20}

**Bilinear pairing groups.** At a high-level, pairing groups allows for computing quadratic polynomials over secret encoded values, and reveal only whether the output is zero or not. More specifically, it consists of cyclic groups 𝔾_{1}, 𝔾_{2}, and 𝔾* _{T}* with generators

*g*

_{1},

*g*

_{2}, and

*g*respectively, and all of order

_{T,}*p*. 𝔾

_{1}and 𝔾

_{2}are referred to as the source groups and

*𝔾T*the target group. (In some instantiations, the two source groups are the same group, which is called symmetric pairing groups.) They support the following operations:

Encode: For every group 𝔾

, one can compute ${g}_{i}^{x}$ for_{i}*x*ɛℤ_{p}. The group element ${g}_{i}^{x}$ is viewed as an*encoding*of*x*in the group 𝔾._{i}Group Operation: In each group 𝔾

, one can perform the group operation to get ${g}_{i}^{{x}_{1}}\circ {g}_{i}^{{x}_{2}}={g}_{i}^{{x}_{1}+{x}_{2}}$, corresponding to “homomorphic” addition modulo_{i}*p*in the exponent. Following the tradition of cryptography, we write the group operation multiplicatively.Bilinear Pairing: Given two source group elements ${g}^{{x}_{1}}$ and ${g}^{{x}_{2}}$, one can efficiently compute a target group element ${g}_{T}^{{x}_{1}\cdot {x}_{2}}$, using the so-called pairing operation $e({g}_{1}^{{x}_{1}},{g}_{2}^{{x}_{2}})={g}_{T}^{{x}_{1}\cdot {x}_{2}}$. This corresponds to “homomorphic” multiplication modulo

*p*in the exponent. However, after multiplication, we obtain an element in the target group that cannot be paired anymore.Zero Testing: Given a group element ${g}_{i}^{x}$, one can always tell if the encoded value is

*x*= 0, by comparing the group element with the identity in*G*. Similarly, one can do equality testing to see if ${g}_{i}^{x}={g}_{i}^{c}$ for any_{i}*c*.

Combining the above abilities gives a “rudimentary” special encryption scheme that supports the evaluation of degree-2 polynomials. A ciphertext of $X\in {Z}_{p}^{l}$ includes encodings of every element *X _{l}* in both source groups, $(({g}_{1}^{{x}_{1}},\cdot \cdot \cdot ,{g}_{1}^{{x}_{l}}),({g}_{2}^{{x}_{1}},\cdot \cdot \cdot ,{g}_{2}^{{x}_{l}}\left)\right)$. Given these, one can “homomorphically” compute a quadratic mapping

*Q*to obtain encoding of the output

*y*=

*Q*(

*X*) in the target group $({g}_{T}^{{y}_{1}},\cdot \cdot \cdot ,{g}_{T}^{{y}_{m}})$ (without knowing the encoded input

*X*at all); finally, if the output

*y*is a

*bit string*, one can learn

*y*in the clear via zerotesting. In summary,

This fulfills the correctness of the special encryption. What about security? The ciphertext must hide all information about *X* beyond what’s revealed by *Q*(*x*), for which we resort to the security of pairing groups. For simplicity of this overview, let’s gain some security intuition by assuming the strongest hardness assumptions pertaining to the pairing groups, known as the generic group model. Think of encoding as black boxes and the only way of extracting information (of the encoded values) is by performing (a combination of) the above four operations. In this model, given *g ^{x}* for a secret and random

*x*ɛℤ

_{p}no efficient adversary can learn

*x*. Extending further, if

*X*were random (in ℤ

_{p}) subject to

*Q*(

*X*) =

*y*, then the encoding would reveal only

*y*and hide all other information of

*X*. The only issue is that

*X*in our example is not random – it is binary. Nevertheless, the works of Ananth and Sahai,

^{4}and Lin

^{20}designed clever ways of

*randomizing*an arbitrary input

*X*, to a random input

*X¯*subject to the only condition that an appropriate quadratic mapping

*Q¯*reveals the right output

*Q¯*(

*X¯*)=

*Q¯(X)*. Hence, security is attained. We refer the reader to Ananth and Sahai,

^{4}and Lin

^{20}for details about how such randomization works.

**Challenges beyond Degree 2.** Unfortunately, the mapping *G*_{RE,PRG} we care about can only be computed by polynomials of a degree much larger than 2. It is known that a Boolean function with output locality *l* can be computed by a multilinear degree *l* polynomial over ℤ_{p}. However, the locality of Boolean PRG we need is at least 5,^{22} and known randomized encodings have locality at least 4.^{6}

**Key idea: The preprocessing model.** To overcome this challenge, our first idea is to use preprocessing of inputs to help reduce the degree of computation. Instead of directly computing *G*(*X*) in one shot, we separate it into two steps: First, the input is preprocessed *X′* = pre(*X*; *r*) in a randomized way using fresh random coins *r*, then the output is computed from the preprocessed input *y* = *Q*(*X′*). The idea is that the preprocessing can perform complex transformations on the input in order to help the computation later. The only constraint is that the preprocessing should not increase the size of its input too much, that is, size(*X′*) ~ size(*X*)+*m*^{1−δ}, for some *δ* > 0. As such, it suffices to encrypt the preprocessed input spCT(*X′*), from which one can recover the desired output *y* = *G*(*X*), by evaluating a (hopefully) simpler function *Q*. Unfortunately, because of the restriction on the size of *X′*, it is unclear how preprocessing alone can help.

Our second idea is to further relax the preprocessing model to allow the preprocessed input to contain a public part and a secret part *X′* = (*P, S*). Importantly, the public part *P* should reveal no information about *X* to computationally limited adversaries. (In contrast, *P, S* together reveals *X* completely.) Moreover, we allow the second stage computation *Q*(*P, S*) to have an arbitrary constant degree in *P* and only restricts its degree on *S* to 2, that is,

where *α _{j, k}*,

*β*,

_{k}*γ*are constant degree polynomials over ℤ

_{p}. It turns out that the techniques alluded to above for special encryption for degree 2 computations can be extended, so that given ciphertext spCT(

*S*) and

*P*in the clear, one can homomorphically compute

*Q*and thereby learn the output

*G*(

*X*).

In Jain et al.^{18}^{,}^{19} we show how to compute any NC^{0} Boolean function *G* in such a preprocessing model, assuming the Learning Parity with Noises assumption over general fields, which completes the puzzle of *i*𝒪. When applied to specific cryptographic tools, our techniques give interesting new objects. For instance, it converts any PRG in NC^{0} into what we call structured-seed PRG. Given a preprocessed seed (*P, S*) = PRG(sd; *r′*), the structured-seed PRG expands out a polynomially longer output *r* = sPRG(*P, S*), where the computation has only degree-2 in the private seed *S*, and the output *r* is pseudo-random given the public seed *P*. In the next section, we describe how to do preprocessing in the context of constructing structured-seed PRG. The same ideas can be extended to handle general NC^{0} functions.

### Definition of structured-seed PRG

**Definition 2. (Syntax of Structured-Seed Pseudo-Random Generators (sPRG).)**

Let *τ* > 1. A structured seed Boolean PRG (sPRG) with polynomial stretch *τ*, is defined by the following PPT algorithms:

IdSamp(1

,^{n}*p*): The index sampling algorithm takes as input the input length parameter*n*, and a prime*p*. It samples a function index*I*.SdSamp(

*I*) jointly samples two strings, a public seed and a private seed, sd = (*P, S*) which are both vectors of dimension ℓ_{sd}=*O*(*n*) over ℤ_{p}Eval(

*I*, sd) computes a string in {0, 1},^{m}*m*=*n*.^{τ}

Looking ahead, the prime *p*, that we choose is set to the order of the bilinear group which has a bit length of *n*^{θ(1)}.

**Definition 3. (Security of sPRG.)**

A structured-seed Boolean PRG, sPRG, satisfies security if for any constant *ρ* > 0, any function *p* : ℕ → ℤ that takes as input a number *k* ɛ ℕ and outputs a *k ^{ρ}* bit prime

*ρ*(

*k*), any

*n*ɛℕ, with probability 1 −

*o*(1) over IdSamp(1

*,*

^{n}*p*=

*p*(

*n*)) →

*I*it holds that the following distributions are computationally indistinguishable.

$\{I,P,\text{Eval}(I,P,S)\}{\approx}_{c}\{I,P,r\}$

where *I* is sampled by IdSamp(1* ^{n}*,

*p*), sd by SdSamp(

*I*), and

*sampled randomly from {0, 1}*

**r**^{m(n)}.

**Definition 4. (Complexity and degree of sPRG.)**

Let *ρ* > 0, *d*_{1}, *d*_{2} ɛ ℕ be any constant, and *p* : ℕ → ℤ be any function that maps an integer *k* into a *k ^{ρ}* bit prime

*p*(

*k*). An sPRG has degree

*d*

_{1}in public seed

*P*and degree

*d*

_{2}in

*S*over ℤ

_{p}, denoted as,

**sPRG**ɛ(deg

*d*

_{1}, deg

*d*

_{2}), if for every

*I*in the support of IdSamp(1

*,*

^{n}*p*=

*p*(

*n*)), there exists efficiently generatable polynomials

*g*

_{I,1}, …,

*g*over ℤ

_{I,m}_{p}such that:

Eval(

*I*, (*P, S*)) = (*g*_{I,1}(*P, S*), …,*g*(_{I,m}*P, S*)), and,The maximum degree of each

*g*over_{I,j}*P*is*d*_{1}, and the maximum degree of*g*over_{I,j}*S*is*d*_{2}.

We remark that the above definition generalizes the standard notion of families of PRGs in two aspects: 1) the seed consists of a public part and a private part, jointly sampled and arbitrarily correlated, and 2) the seed may not be uniform. Therefore, we obtain the standard notion as a special case.

**Definition 5. (Pseudo-Random Generators, degree, and locality.)**

A (uniform-seed) Boolean PRG (PRG) is an sPRG with a seed sampling algorithm SdSamp(*I*) that outputs a public seed *P* that is an empty string and a uniformly random private seed *S* ← {0, 1}* ^{n}*. Let

*d*,

*c*ɛ ℕ. The PRG has multilinear degree

*d*if for every

*n*ɛ ℕ and

*I*in the support of IdSamp(1

*), we have that Eval(*

^{n}*I*, sd) can be written as an

*m*(

*n*)-tuple of degree-

*d*polynomials over ℤ in

*S*. It has constant locality

*c*if for every

*n*ɛℕ and

*I*in the support of IdSamp(1

*), every output bit of Eval(*

^{n}*I*, sd) depends on at most

*c*bits of

*S*.

In what follows next we will give an overview of our construction of sPRG from the

`LPN`

assumption and the existence of PRG in NC^{0}. For ease of exposition, we will actually use Goldreich’s PRG candidate^{16}which is the most wellknown conjectured PRG in NC^{0}. See Jain et al.^{18}for the construction based on any PRG in NC^{0}.

**Definition 6. (Goldreich’s PRG.)**

A Goldreich PRG of locality *c* mapping *n* bits to *m* bits is described using a predicate *f* : {0, 1}* ^{c}* → {0, 1} and a hypergraph

*H*= {

*Q*

_{1}, …,

*Q*} where each

_{m}*Q*is a randomly chosen ordered subset of [

_{i}*n*] of size

*c*. The index

*I*consists of

*f*and

*H*. Further, on input

*x*ɛ{0,1}

^{n}, PRG.Eval(

*I*,

*) =*

**x***, where*

**y***= (*

**y***y*

_{1}, …,

*y*). Here each ${y}_{i}=f({{x}_{i}}_{1},\cdot \cdot \cdot ,{{x}_{i}}_{c})$ where

_{m}*Q*= (

_{i}*i*

_{1}, …,

*i*).

_{c}### SPRG overview

We start with a Goldreich PRG PRG = (IdSamp, Eval) with stretch *τ*, associated with a *d*-local predicate *f* : {0, 1}* ^{d}* → {0, 1} and a randomly sampled hypergraph

*H*, i.e.,

*I*= (

*f, H*). Observe that on any input

**σ**ɛ{0,1}

^{n},

*= PRG.Eval(*

**y***I*,

*σ*) can be computed by degree

*d*multilinear polynomials over ℤ as

*f*is a predicate evaluated on

*d*bits. Our high-level strategy is to somehow “preprocess”

*into two vectors (*

**σ***P, S*) of small dimension (preferably

*O*(

*n*), but anything sublinear in

*m*works) such that

**y**ɛ{0,1}

^{m}can be computed in (deg

*d*, deg 2). Thereby this will have the effect of transferring the complexity of computation to the public input. To achieve this, we pre-process

*into appropriate public and private seeds (*

**σ***P, S*) and leverage the LPN assumption over ℤ

_{p}(which is the input to sPRG.IdSamp) to show that the seed is hidden.

Our first idea toward this is that we can “encrypt” the seed * σ* using

`LPN`

samples over ℤ_{p}as follows:

where ℓ is set to be the dimension for the `LPN`

samples. It is set so that ${\ell}^{\lceil \frac{d}{2}\rceil}=n\mathrm{.}{D}_{r}\left(p\right)$ is a distribution that samples randomly from *p* with probability *r*, and 0 otherwise. Finally, *r* = ℓ^{−δ}.

It follows directly from `LPN`

assumption that (* A*,

*) is pseudorandom and hides*

**b***. Furthermore, due to the sparsity of*

**σ**`LPN`

noises, the vector *+*

**σ***differs from*

**e***only at a ℓ*

**σ**^{−δ}fraction of components – thus it is a sparsely erroneous version of the seed. For

*i*ɛ[

*m*], let

*f*(

_{i}*) be the locality*

**σ***d*, degree

*d*polynomial over ℤ such that

*y*=

_{i}*f*(

_{i}*). Then, for*

**σ***i*ɛ[

*m*] consider the following polynomial:

Above we first interpret *f _{i}* over ℤ into the field ℤ

_{p}by simply reducing coefficients mod

*p*, and then compute as given. Observe that

*f*is a degree

_{i}*d*polynomial in

*and*

**b***, therefore its degree over*

**s***is*

**b***d*and over ${\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil}$ is two. Thus

*h*is a (deg

_{i}*d*, deg 2) polynomial. Observe that ${h}_{i}(b,{\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil})={f}_{i}(\sigma +e)$. The main point of this is this is that if we set the polynomial map ${G}^{\left(1\right)}=({G}_{1}^{\left(1\right)},\mathrm{\dots},{G}_{m}^{\left(1\right)})$ by letting each ${G}_{i}^{\left(1\right)}={h}_{i}$, and setting the private seed $S={\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil}$:

The reason *G*^{(1)} is interesting because * e* is sparse. With probability, $1-{2}^{-{n}^{\Omega \left(1\right)}}$, it is non-zero at

*O*(

*n*ℓ

^{−δ}) locations. As a consequence of this, for any given

*i*ɛ[

*m*],

*f*(

_{i}*) =*

**σ***f*(

_{i}*+*

**σ***) with all but*

**e***O*(ℓ

^{−δ}) probability as

*f*is a

_{i}*d*local function depending on

*d*randomly chosen inputs. Since in the hypergraph

*H*of the Goldreich PRG, each set

*Q*is chosen independently, every output is independently error-prone with probability

_{i}*O*(ℓ

^{−δ}). Because of this due to Chernoff style concentration bounds, out of

*m*outputs, with probability $1-{2}^{-{n}^{\Omega \left(1\right)}}$, all but

*T*=

*O*(

*m*ℓ

^{−δ}) outputs are error-prone.

This gives us a nice candidate for sPRG that satisfies almost all properties! The dimension of *S* and *P* is *O*(*n*) which is sublinear in *m*, and it can be computed by a degree (deg *d*, deg 2) polynomial *G*^{(1)}. We would be done if we could somehow force the output to be correct on all the *m* coordinates. For the rest of the overview, we refer to the indices *i*ɛ[*m*], such that *f _{i}*(

*) ≠*

**σ***f*(

_{i}*+*

**σ***), as bad indices/outputs.*

**e**To correct errors, we further modify the polynomial and include more pre-processed information in the private seeds. We describe a sequence of ideas that lead to the final correction method, starting with two wrong ideas that illustrate the difficulties we will overcome.

The first wrong idea is correcting by adding the difference Corr =

−**y**between the correct and erroneous outputs,**y**′= Eval**y**(_{I}) and**σ**= Eval**y**′(_{I}+**σ**); we refer to Corr as the**e***correction vector*. To obtain the correct output, evaluation can compute the polynomial map ${G}^{\left(1\right)}\left(b,\left({\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil}\right)\right)+\text{Corr}$. The problem is that Corr must be included in the seed, but it is as long as the output and would destroy expansion. Thus, we have to make use of the fact that Corr is sparse.To fix expansion, the second wrong idea is adding correction only for bad outputs, so that the seed only stores non-zero entries in Corr. Recall that, Corr is sparse with at most

*T*non-zero elements. More precisely, the*j*‘th output can be computed as ${G}_{j}^{\left(1\right)}\left(b,\left({\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil}\right)\right)+{\text{Corr}}_{j}$ if output*j*is bad and without adding Corrotherwise. This fixes expansion, but now the evaluation polynomial depends on the location of bad outputs. If these locations are included in public information, this would leak information about the location of_{j}`LPN`

noises, and jeopardize security. If on the other hand the locations are included in the private seed, then it is unclear how to maintain the requirement that the polynomial map computes only a degree two polynomial in the private seed.

These two wrong ideas illustrate the tension between the expansion and security of our sPRG. Our construction takes care of both, by *compressing* the correction vector Corr to be polynomially shorter than the output and stored in the seed, and *expanding* it back during evaluation in a way that is oblivious of the location of bad output bits. This is possible thanks to the sparsity of the correction vector and the allowed degree two computation on the private seed. We first illustrate our idea with the help of a simple case.

**Simple Case 1: Much fewer than m bad outputs.** Suppose hypothetically that the number of bad outputs is bounded by *z* which is much smaller than $\sqrt{m}$. Thus, if we convert Corr into a $\sqrt{m}\times \sqrt{m}$ matrix^{e}, it has low-rank *z*. We can then factorize Corr into two matrixes **U** and **V** of dimensions $\sqrt{m}\times z$ and $z\times \sqrt{m}$, respectively, such that Corr = **UV**, and compute the correct output as follows: ∀*j*ɛ[*m*],

where (*k _{j}*,

*l*) is the corresponding index of the output bit

_{j}*j*, in the $\sqrt{m}\times \sqrt{m}$ matrix. When $z\ll \sqrt{m}$ the matrices

**U**,

**V**have $2z\sqrt{m}$ field elements, which are polynomially smaller than

*m*=

*n*. As such,

^{τ}*G*

^{(2)}is expanding. Moreover, observe that

*G*

^{(2)}has only degree 2 in the private seed and is completely oblivious to where the bad outputs are.

While the idea above works for fewer than $\sqrt{m}$ bad outputs, it does not work for the case we are in. We have *T* = Θ(*m*ℓ^{−δ}) bad outputs. Nevertheless, we show that a similar idea works for this case.

*T* bad **outputs**. The above method however cannot handle more than $\sqrt{m}$ bad outputs, whereas the actual number of bad outputs can be up to *T* = Ω(*m*/ℓ* ^{δ}*), much larger than $\sqrt{m}$ since

*δ*is an arbitrarily small constant. Consider another hypothetical case where the bad outputs are evenly spread in the following sense: suppose that if we divide the matrix Corr into

*m*/ℓ

*blocks, each of dimension ℓ*

^{δ}^{δ/2}× ℓ

^{δ/2}, there are at most ℓ

*bad outputs in each block where*

^{ρ}*ρ*> 0 is a really small constant (say

*δ*/10). In this case, we can “compress” each block of Corr separately using the idea from case 1. More specifically, for every block

*i*ɛ[

*/ℓ*

**m**^{δ}] we factor it into

**U**

_{i}**V**

*, with dimensions ℓ*

_{i}^{d/2}× ℓ

^{ρ}and ℓ

*× ℓ*

^{ρ}^{δ/2}, respectively, and correct bad outputs as follows: ∀

*j*ɛ[

*m*],

where *i _{j}* is the block that output

*j*belongs to, and (

*k*,

_{j}*l*) ɛ [ℓ

_{j}^{δ/2}]×[ℓ

^{δ/2}] is its index within this block. We observe that

*G*

^{(2)}is expanding, since each matrix

**U**

*or*

_{i}**V**

*has ℓ*

_{i}^{δ/2+ρ}field elements, and the total number of elements is ${\ell}^{\delta /2+\rho}\cdot \frac{m}{{\ell}^{\delta}}$ which is polynomially smaller than

*m*as long as

*δ*is positive and

*m*is polynomially related to ℓ. Moreover,

*G*

^{(2)}is oblivious to the location of bad outputs just as in case 1.

This completely solves our problem except that we need to ensure that the bad outputs are well spread out in the manner described above. Our main observation here is that this is ensured due to the fact that in a Goldreich’s PRG candidate the input dependence hypergraph *Q*_{1}, …, *Q _{m}* is randomly chosen. Therefore, once we fix the location of the non-zero errors inside

*(where with high probability*

**e***O*(

*n*ℓ

^{−δ}) locations are non-zero), in every block of ℓ

*output bits, each entry*

^{δ}*j*is independently non-zero with probability

*O*(ℓ

^{−δ}). Thus, in expectation, each block has a constant number of bad output bits. More so, due to the Chernoff bound, it can be seen that with probability $1-{{2}^{-\ell}}^{\Omega \left(1\right)}$, each has at most ℓ

^{ρ}, non-zero elements. Thus, our construction can be summarized as follows:

**Step 1: Assign outputs**. We partition the outputs into*B*buckets, via a mapping*ø*_{bkt}: [*m*] → [*B*]. The number of buckets is set to*B*=*m*/ℓand the number of elements in each bucket is set to be ℓ^{δ}so that they exactly form a partition of^{δ}*m*. The mapping*ø*_{bkt}simply divides*m*by*B*, and outputs the remainder. Since the erroris chosen to be from the**e**`LPN`

error distribution and the hypergraph*H*of the PRG is randomly chosen, by a Chernoffstyle argument, we can show that in each bucket out of*ℓ*output bits, at most^{δ}*t*of them are bad, except with probability $1-{{2}^{-t}}^{\Omega \left(1\right)}$. We will set*t*= ℓfor a tiny constant^{δ}*ρ*> 0.**Step 2: Compress the buckets**. Next, we organize each bucket*i*into a matrix**M**of dimension ℓ_{i}^{d/2}× ℓ^{d/2}and then compute its factorization**M**=_{i}**U**_{i}**V**, where_{i}**U**,_{i}**V**are matrices of dimensions ℓ_{i}^{δ/2}×*t*and*t*× ℓ^{δ/2}, respectively. To form matrix**M**, we use another mapping_{i}*ø*_{ind}: [*m*] → [ℓ^{δ/2}] × [ℓ^{δ/2}] to assign each output bit*j*to an index (*k*,_{j}*l*) in the matrix of the bucket_{j}*i*it is assigned to. This assignment must guarantee that no two output bits in the same bucket (assigned according to_{j}*ø*_{bkt}) have the same index. One such way to compute*ø*_{ind}(*j*) is to divide*j*ɛ[*m*] by*B*. The remainder is set as*ø*_{bkt}(*j*), and the quotient is divided further by ℓ^{δ/2}. The quotient and the remainder from this division are set as the resulting indices (*k*,_{j}*l*). Once we have this, ${\left({M}_{i}\right)}_{k,l}$ is set to Corr_{j}if there is_{j}*j*such that*ø*_{bkt}(*j*) =*i*and*ø*_{ind}(*j*) = (*k, l*). Since every matrix**M**has at most_{i}*t*non-zero entries, we can factor them and compute the correct output as: ∀*j*ɛ [*m*],${G}_{j}^{\left(2\right)}(b,\u205f\underset{S}{\underbrace{({\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil},\u205f{({U}_{i},{V}_{i})}_{i\in \left[\frac{m}{{\ell}^{\delta}}\right]})}})={G}_{j}^{\left(1\right)}(b,\u205f({\overline{s}}^{\otimes \lceil \frac{d}{2}\rceil}))+({U}_{{\phi}_{\text{bkt}}\left(j\right)}{V}_{{\phi}_{\text{bkt}}\left(j\right)}{)}_{{\phi}_{\text{ind}}\left(j\right)},$

G

^{(2)}is expanding, because the number of field elements in**U**‘s and_{i}**V**‘s are much smaller than_{i}*m*, namely: 2*tℓ*^{δ/2}*B*=*O*(*mℓ*^{−δ/2+ρ})≪*m*. We set*I′*= (*I*,,**A***ø*_{bkt},*ø*_{ind}).**Step 3: Zeroize if uneven buckets**. Finally, to deal with the low probability event that some bucket contains more than*t*bad outputs, we introduce a new variable called flag. If this occurs, our sPRG sets*P*and*S*as all zero vectors. In this case, the evaluation always outputs 0. This gives us our candidate sPRG. For security, observe that the polynomial map*G*^{(2)}is independent of the location of`LPN`

noises. With probability $1-{2}^{-{n}^{\Omega \left(1\right)}}$, the evaluation results in output. Therefore, by the**y**`LPN`

over ℤassumption, the seed_{p}of PRG is hidden and the security of PRG ensures that the output is pseudorandom when it is not all zero (which occurs with a subexponentially small probability). We now proceed to the formal construction and proof.**σ**

This completes the overview of our construction of structured seed PRG, as well as *i*𝒪; see Jain et al.^{18}^{,}^{19} for the formal constructions and security proofs. In conclusion, *i*𝒪 is an extremely powerful cryptographic tool and our works have established its feasibility based on well-studied assumptions.

## Join the Discussion (0)

## Become a Member or Sign In to Post a Comment