We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a generic template for constructing SSL-PRGs that combines the following two ingredients: [i.] 1) noisy‑NC⁰ PRGs, computable by constant‑depth circuits fed with sparse noise, with 2) new local compression schemes for sparse vectors derived from combinatorial batch codes. Instantiating the template under the sparse Learning‑Parity‑with‑Noise (LPN) assumption yields the first SSL-PRGs with polynomial stretch and constant locality from a subquadratic‑sample search hardness assumption; a mild strengthening of sparse‑LPN gives strong SSL-PRGs of arbitrary polynomial stretch. We further show that for all standard noise distributions, noisy‑local PRGs cannot be emulated by ordinary local PRGs, thereby separating the two notions. Plugging SSL-PRGs into existing frameworks, we revisit the canonical applications of local PRGs and demonstrate that SSL-PRGs suffice for: (i) indistinguishability obfuscation, (ii) constant-overhead secure computation, (iii) compact homomorphic secret sharing, and (iv) deriving hardness results for PAC‑learning DNFs from sparse‑LPN. Our work thus broadens the landscape of low‑depth pseudorandomness and anchors several primitives to a common, well‑motivated assumption.

Let C be an error-correcting code over a large alphabet q of block length n, and assume that, a possibly corrupted, codeword c is distributively stored among n servers where the ith entry is being held by the ith server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are “consistent” with some legal codeword or “conflicted”. What type of information about c can be inferred from this consistency graph? Can we check whether errors occurred and if so, can we find the error locations and effectively decode? We initiate the study of conflict-checkable and conflict-decodable codes and prove the following main results:

A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and fully-decomposable randomized encoding (or garbling schemes). In fact, for all these primitives we do not even have super-linear lower bounds. Furthermore, it is unknown how to relate these questions to each other or to other complexity-theoretic questions.In this note, we relate all these questions to the classical topic of query/space trade-offs, lifted to the setting of interactive proof systems. Specifically, we consider the following Advisor-Verifier-Prover (AVP) game: First, a function f is given to the advisor who computes an advice a. Next, an input x is given to the verifier and to the prover who claims that $f(x) \quad =1.$ The verifier should check this claim via a single round of interaction based on the private advice a and without having any additional information on f. We focus on the case where the prover is laconic and communicates only a constant number of bits, and, mostly restrict the attention to the simplest, purely information-theoretic setting, where all parties are allowed to be computationally unbounded. The goal is to minimize the total communication complexity which is dominated by the length of the advice plus the length of the verifier’s query.As our main result, we show that a super-polynomial lower bound for AVPs implies a super-polynomial lower bound for a wide range of information-theoretic cryptographic tasks. In particular, we present a communication-efficient transformation from any of the above primitives into an AVP protocol. Interestingly, each primitive induces some additional property over the resulting protocol. Thus AVP games form a new common yardstick that highlights the differences between all the above primitives.Equipped with this view, we revisit the existing (somewhat weak) lower bounds for the above primitives, and show that many of these lower bounds can be unified by proving a single counting-based lower bound on the communication of AVPs, whereas some techniques are inherently limited to specific domains. The latter is shown by proving the first polynomial separations between the complexity of secret-sharing schemes and conditional disclosure of secrets and between the complexity of randomized encodings and conditional disclosure of secrets.

A secret-sharing scheme enables a dealer to share a secret s among n parties such that only authorized subsets of parties, specified by a monotone access structure f:{0,1}n→{0,1}, can reconstruct s from their shares. Other subsets of parties learn nothing about s.

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model.

Abstract. Suppose that you wish to sample a random graph [Formula: see text] over [Formula: see text] vertices and [Formula: see text] edges conditioned on the event that [Formula: see text] does not contain a “small” [Formula: see text]-size graph [Formula: see text] (e.g., clique) as a subgraph. Assuming that most such graphs are [Formula: see text]-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for [Formula: see text]-cliques) with an expected running time of [Formula: see text]. Is it possible to solve the problem in a running time that does not grow polynomially with [Formula: see text]? In this paper, we introduce the general problem of sampling a “random looking” graph [Formula: see text] with a given edge density that avoids some arbitrary predefined [Formula: see text]-size subgraph [Formula: see text]. As our main result, we show that the problem is solvable with respect to some specially crafted [Formula: see text]-wise independent distribution over graphs. That is, we design a sampling algorithm for [Formula: see text]-wise independent graphs that supports efficient testing for subgraph-freeness in time [Formula: see text], where [Formula: see text] is a function of [Formula: see text] and the constant [Formula: see text] in the exponent is independent of [Formula: see text]. Our solution extends to the case where both [Formula: see text] and [Formula: see text] are [Formula: see text]-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially unbalanced expander graphs whose failure probability is negligible in [Formula: see text] (i.e., [Formula: see text]). In particular, given constants [Formula: see text], we output a bipartite graph that has [Formula: see text] left nodes and [Formula: see text] right nodes with right-degree of [Formula: see text] so that any right set of size at most [Formula: see text] expands by factor of [Formula: see text]. This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings and present applications in coding theory (batch codes and low-density parity-check codes), pseudorandomness (low-bias generators and randomness extractors), and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally computable cryptographic pseudorandom generators based on Goldreich’s one-wayness assumption resolving a central open problem in the area of parallel-time cryptography (e.g., Applebaum, Ishai, and Kushilevitz [ SIAM J. Comput., 36 (2006), pp. 845–888] and Ishai et al. [ Proceedings of the 40 th Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 433–442]).

In the conditional disclosure of secrets (CDS) problem (Gertner et al. in J Comput Syst Sci, 2000) Alice and Bob, who hold n-bit inputs x and y respectively, wish to release a common secret z to Carol, who knows both x and y, if and only if the input (x, y) satisfies some predefined predicate f. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security. Despite the growing interest in this model, very few lower-bounds are known. In this paper, we relate the CDS complexity of a predicate f to its communication complexity under various communication games. For several basic predicates our results yield tight, or almost tight, lower-bounds of $$\Omega (n)$$ or $$\Omega (n^{1-\epsilon })$$ , providing an exponential improvement over previous logarithmic lower-bounds. We also define new communication complexity classes that correspond to different variants of the CDS model and study the relations between them and their complements. Notably, we show that allowing for imperfect correctness can significantly reduce communication—a seemingly new phenomenon in the context of information-theoretic cryptography. Finally, our results show that proving explicit super-logarithmic lower-bounds for imperfect CDS protocols is a necessary step towards proving explicit lower-bounds against the communication complexity class $$\text {AM}^{\text {cc}}$$ , or even $$\text {AM}^{\text {cc}}\cap \text {co-AM}^{\text {cc}}$$ —a well known open problem in the theory of communication complexity. Thus imperfect CDS forms a new minimal class which is placed just beyond the boundaries of the “civilized” part of the communication complexity world for which explicit lower-bounds are known.

In the conditional disclosure of secrets (CDS) problem [Gertner et al., J. Comput. System Sci., 60 (2000), pp. 592--629] Alice and Bob, who hold inputs $x$ and $y$, respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies some predefined predicate $f$. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some joint randomness and the goal is to minimize the communication complexity while providing information-theoretic security. In this work, we initiate the study of CDS manipulation techniques and derive the following positive and negative results: (Closure) A CDS for $f$ can be turned into a CDS for its complement $\bar{f}$ with only a minor blow-up in complexity. More generally, for a (possibly nonmonotone) predicate $h$, we obtain a CDS for $h(f_1,\ldots,f_m)$ whose cost is essentially linear in the formula size of $h$ and polynomial in the CDS complexity of $f_i$. (Amplification) It is possible to reduce the privacy and correctness error of a CDS from constant to $2^{-k}$ with a multiplicative overhead of $O(k)$. Moreover, this overhead can be amortized over $k$-bit secrets. (Amortization) Every predicate $f$ over $n$-bit inputs admits a CDS for multibit secrets whose amortized communication complexity per secret bit grows linearly with the input length $n$ for sufficiently long secrets. In contrast, the best known upper-bound for single-bit secrets is exponential in $n$. (Lower-bounds) There exists a (nonexplicit) predicate $f$ over $n$-bit inputs for which any perfect (single-bit) CDS requires communication of at least $\Omega(n)$. This is an exponential improvement over the previously known $\Omega(\log n)$ lower-bound. (Separations) There exists an (explicit) predicate whose CDS complexity is exponentially smaller than its randomized communication complexity. This matches a lower-bound of Gay, Kerenidis, and Wee [ Advances in Cryptology, Lecture Notes in Comput. Sci. 9216, Springer, New York, 2015, pp. 485--502] and, combined with another result of theirs, yields an exponential separation between the communication complexity of linear CDS and non-linear CDS. This is the first provable gap between the communication complexity of linear CDS (which captures most known protocols) and nonlinear CDS.

We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The protocol is efficient for ${NC}^1$ functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality $g$ is an encoding of the functionality $f$, then for any (permitted) coalition of players, their respective outputs and inputs in $g$ allow them to simulate their respective inputs and outputs in $f$, without learning anything else, including the other outputs of $f$. We further introduce a new notion of effective degree, and show that the round complexity of a functionality $f$ is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to n/3 of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.

We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing a round preserving reduction to the task of secure 2-party computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use of the underlying OT protocol. The question remained whether this can be done by only making black-box use of 2-round OT. This is of theoretical and potentially also practical value as black-box use of primitives tends to lead to more efficient constructions. Our main result proves that such a black-box construction is impossible, namely that non-black-box use of OT is necessary. As a corollary, a similar separation holds when starting with any 2-party functionality other than OT. As a secondary contribution, we prove several additional results that further clarify the landscape of black-box MPC with minimal interaction. In particular, we complement the separation from 2-party functionalities by presenting a complete 4-party functionality, give evidence for the difficulty of ruling out a complete 3-party functionality and for the difficulty of ruling out black-box constructions of 3-round MPC from 2-round OT, and separate a relaxed "non-compact" variant of 2-party homomorphic secret sharing from 2-round OT.

A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2 n−o(n) and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 20.994n+o(n), which was later improved to 20.892n+o(n) by Applebaum et al. (EUROCRYPT 2019).

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a “small" t-size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of nO(t). Is it possible to solve the problem in running time that does not grow polynomially with nt? In this paper, we introduce the general problem of sampling a “random looking'' graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t) · ncwhere f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially-unbalanced expander graphs whose failure probability is negligible in n (i.e., n-ω(1)). In particular, given constants d>c, we output a bipartite graph that has n left nodes, ncright nodes with right-degree of d so that any right set of size at most nΩ(1)expands by factor of Ω(d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings, and present applications in coding theory (batch codes and LDPC codes), pseudorandomness (low-bias generators and randomness extractors) and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally-computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in parallel-cryptography (cf., Applebaum-Ishai-Kushilevitz, FOCS 2004; and Ishai-Kushilevitz-Ostrovsky-Sahai, STOC 2008).

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial regime of $m=n^s$, $s>1$, the only known solution, originating from [Goldreich, Electronic Colloquium on Computational Complexity (ECCC), 2000], is based on random local functions: Compute $y_i$ by applying some fixed (public) $d$-ary predicate $P$ to a random (public) tuple of distinct input indices $(x_{i_1},\ldots,x_{i_d})$. Our goal in this paper is to understand, for any value of $s$, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results: (1) We show that pseudorandomness against $\mathbb{F}_2$-linear adversaries (i.e., the distribution $y$ has small bias) is achieved if the predicate is (a) $k=\Omega(s)$-resilient, i.e., uncorrelated with any $k$-subset of its inputs, and (b) has algebraic degree of $\Omega(s)$ even after fixing $\Omega(s)$ of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a $d$-local small-biased generator can have output length of $n^{\Omega(d)}$, answering an open question of Mossel, Shpilka, and Trevisan [ Proceedings of FOCS, 2003]. Our negative result shows that a candidate for a pseudorandom generator proposed by Applebaum [ Comput. Complexity, 25 (2016), pp. 667--722] and by O'Donnell and Witmer [ Proceedings of CCC 2014] is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins, and Vempala [ Proceedings of STOC 2015] regarding the hardness of planted constraint satisfaction problems. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the polynomial calculus proof system. We show that algebraic attacks succeed if and only if the predicate $P$ has rational degree $e=\Theta(s)$, where the rational degree of a predicate $P$ is the smallest integer $e$ for which there exist degree $e$ polynomials $Q,R$, not both zero, such that $PQ=R$. As a corollary, we obtain the first example of a predicate $P$ for which the generated sequence $y$ passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by Applebaum [ Comput. Complexity, 25 (2016), pp. 667--722].

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for smooth 3-CNFs. Here smoothness means that the number of satisfying assignments is not much smaller than the number of almost-satisfying assignments. We further show that the latter (smooth-ETH) assumption follows from the exponential hardness of solving constraint satisfaction problems over well-studied distributions, and, more generally, from the existence of any exponentially-hard locally-computable one-way function. This confirms a conjecture of Dinur (ECCC 2016). We also prove an analogous result in the cryptographic setting. Namely, we show that the existence of exponentially-hard locally-computable pseudorandom generator with linear stretch (el-PRG) follows from the existence of an exponentially-hard locally-computable almost regular one-way functions.None of the above assumptions (gap-ETH and el-PRG) was previously known to follow from the hardness of a search problem. Our results are based on a new construction of general (GL-type) hardcore functions that, for any exponentially-hard one-way function, output linearly many hardcore bits, can be locally computed, and consume only a linear amount of random bits. We also show that such hardcore functions have several other useful applications in cryptography and complexity theory.

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output.

We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F . In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits that make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under coding-related intractability assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, additively homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field $\F$. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions.

A rateless code encodes a finite length information word into an infinitely long codeword such that longer prefixes of the codeword can tolerate a larger fraction of errors. A rateless code achieves capacity for a family of channels if, for every channel in the family, reliable communication is obtained by a prefix of the code whose rate is arbitrarily close to the channel's capacity. As a result, a universal encoder can communicate over all channels in the family while simultaneously achieving optimal communication overhead.

Randomized encodings of functions can be used to replace a “complex” function $f(x)$ by a “simpler” randomized mapping $\hat{f}(x;r)$ whose output distribution on an input $x$ encodes the value of $f(x)$ and hides any other information about $x$. One desirable feature of randomized encodings is low online complexity. That is, the goal is to obtain a randomized encoding $\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\hat{x}$, where the online complexity of computing $\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part $\hat{x}$ consists of $n$ encryption keys of length $\kappa$ each, where $n=|x|$ and $\kappa$ is a security parameter. Thus, the online rate $|\hat{x}|/|x|$ of this encoding is proportional to the security parameter $\kappa$. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\{0,1\}^n\to\{0,1\}^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie--Hellman (DDH) assumption, the learning with errors (LWE) assumption, or the RSA assumption. We also present a variant of this result which applies to arithmetic formulas, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for noninteractive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as noninteractive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation.

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a “garbled circuit” $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \mathbb{Z}^n\to\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors problem.

We continue the study of locally-computable pseudorandom generators (PRG) G:{0,1}n -> {0,1}m that each of their outputs depend on a small number of d input bits. While it is known that such generators are likely to exist for the case of small sub-linear stretch m=n+n1-δ, it is less clear whether achieving larger stretch such as m=n+Ω(n), or even m=n1+δ is possible. The existence of such PRGs, which was posed as an open question in previous works, has recently gained an additional motivation due to several interesting applications. We make progress towards resolving this question by obtaining several local constructions based on the one-wayness of "random" local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Specifically, we construct collections of PRGs with the following parameters: 1. Linear stretch m=n+Ω(n) and constant locality d=O(1). 2. Polynomial stretch m=n1+δ and any (arbitrarily slowly growing) super-constant locality d=ω(1), e.g., log*n. 3. Polynomial stretch m=n1+δ, constant locality d=O(1), and inverse polynomial distinguishing advantage (as opposed to the standard case of n-ω(1)).

Yao's garbled circuit construction transforms a boolean circuit C : {0, 1}n→ {0, 1}minto a "garbled circuit" Ĉ along with n pairs of k-bit keys, one for each input bit, such that Ĉ together with the n keys corresponding to an input x reveal C(x) and no additional information about x. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C : ℤn→ ℤmover integers from a bounded (but possibly exponential) range into a garbled circuit Ĉ along with n affine functions Li: ℤ → ℤksuch that Ĉ together with the n integer vectors Li(xi) reveal C(x) and no additional information about x. The security of our construction relies on the intractability of the learning with errors (LWE) problem.

This paper attempts to broaden the foundations of public-key cryptography. We construct new public-key encryption schemes based on new hardness-on-average assumptions for natural combinatorial NP-hard optimization problems. We consider the following assumptions: It is infeasible to solve a random set of sparse linear equations mod 2, of which a small fraction is noisy. It is infeasible to distinguish between a random unbalanced bipartite graph, and such a graph in which we "plant" at random in the large side a set S with only |S|/3 neighbors. There is a pseudorandom generator in NCz where every output depends on a random constant-size subset of the inputs.

We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.

Randomizing polynomials allow representing a function f(x) by a low-degree randomized mapping $$\hat{f}(x, r)$$ whose output distribution on an input x is a randomized encoding of f(x). It is known that any function f in uniform $$\bigoplus$$ L/poly (and in particular in NC1) can be efficiently represented by degree-3 randomizing polynomials. Such a degree-3 representation gives rise to an NC 4 0 representation, in which every bit of the output depends on only four bits of the input. In this paper, we study the relaxed notion of computationally private randomizing polynomials, where the output distribution of $$\hat{f}(x, r)$$ should only be computationally indistinguishable from a randomized encoding of f(x). We construct degree-3 randomizing polynomials of this type for every polynomial-time computable function, assuming the existence of a cryptographic pseudorandom generator (PRG) in uniform $$\bigoplus$$ L/poly. (The latter assumption is implied by most standard intractability assumptions used in cryptography.) This result is obtained by combining a variant of Yao’s garbled circuit technique with previous “information-theoretic” constructions of randomizing polynomials. We present several applications of computationally private randomizing polynomials in cryptography. In particular, we relax the sufficient assumptions for parallel constructions of cryptographic primitives, obtain new parallel reductions between primitives, and simplify the design of constant-round protocols for multiparty computation.

We study the parallel time‐complexity of basic cryptographic primitives such as one‐way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of implementing instances of these primitives by $NC^0$ functions, namely, by functions in which each output bit depends on a constant number of input bits. Despite previous efforts in this direction, there has been no convincing theoretical evidence supporting this possibility, which was posed as an open question in several previous works. We essentially settle this question by providing strong positive evidence for the possibility of cryptography in $NC^0$. Our main result is that every “moderately easy” OWF (resp., PRG), say computable in $NC^1$, can be compiled into a corresponding OWF (resp., “low‐stretch” PRG) in which each output bit depends on at most 4 input bits. The existence of OWFs and PRGs in $NC^1$ is a relatively mild assumption, implied by most number‐theoretic or algebraic intractability assumptions commonly used in cryptography. A similar compiler can also be obtained for other cryptographic primitives such as one‐way permutations, encryption, signatures, commitment, and collision‐resistant hashing. Our techniques can also be applied to obtain (unconditional) constructions of “noncryptographic” PRGs. In particular, we obtain ε‐biased generators and a PRG for space‐bounded computation in which each output bit depends on only 3 input bits. Our results make use of the machinery of randomizing polynomials [Y. Ishai and E. Kushilevitz, Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2000, pp. 294–304], which was originally motivated by questions in the domain of information‐theoretic secure multiparty computation.

Randomizing polynomials allow to represent a function f(x) by a low-degree randomized mapping f/spl circ/(x, r) whose output distribution on an input x is a randomized encoding of f(x). It is known that any function f in /spl oplus/L/poly (and in particular in NC/sup 1/) can be efficiently represented by degree-3 randomizing polynomials. Such a degree-3 representation gives rise to an NC/sub 4//sup 0/ representation, in which every bit of the output depends on only 4 bits of the input. In this paper, we study the relaxed notion of computationally private randomizing polynomials, where the output distribution of f/spl circ/(x, r) should only be computationally indistinguishable from a randomized encoding of f(x). We construct degree-3 randomizing polynomials of this type for every polynomial-time computable function, assuming the existence of a cryptographic pseudorandom generator (PRG) in /spl oplus/L/poly. (The latter assumption is implied by most standard intractability assumptions used in cryptography.) This result is obtained by combining a variant of Yao's garbled circuit technique with previous "information-theoretic" constructions of randomizing polynomials.

We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of computing instances of these primitives by NC/sup 0/ circuits, in which each output bit depends on a constant number of input bits. Despite previous efforts in this direction, there has been no significant theoretical evidence supporting this possibility, which was posed as an open question in several previous works. We essentially settle this question by providing overwhelming positive evidence for the possibility of cryptography in NC/sup 0/. Our main result is that every "moderately easy" OWF (resp., PRG), say computable in NC/sup 1/, can be compiled into a corresponding OWF (resp., low-stretch PRG) in NC/sub 4//sup 0/, i.e. whose output bits each depend on at most 4 input bits. The existence of OWF and PRG in NC/sup 1/ is a relatively mild assumption, implied by most number-theoretic or algebraic intractability assumptions commonly used in cryptography. Hence, the existence of OWF and PRG in NC/sup 0/ follows from a variety of standard assumptions. A similar compiler can also be obtained for other cryptographic primitives such as one-way permutations, encryption, commitment, and collision-resistant flashing. The above results leave a small gap between the possibility of cryptography in NC/sub 4//sup 0/, and the known impossibility of implementing even OWF in NC/sub 2//sup 0/. We partially close this gap by providing evidence for the existence of OWF in NC/sub 3//sup 0/. Finally, our techniques can also be applied to obtain unconditionally provable constructions of non-cryptographic PRGs. In particular, we obtain e-biased generators in NC/sub 3//sup 0/, resolving an open question posed by Mossel et al. (2003), as well as a PRG for logspace in NC/sup 0/. Our results make use of the machinery of randomizing polynomials which was originally motivated by questions in the domain of information-theoretic secure multiparty computation.