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.

The existence of “unstructured” hard languages in NP ∩ coNP is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether P is separated from NP ∩ coNP relative to a random oracle, a question that remained open ever since. While a hard language in NP ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.

Abstract We propose F alcon , an end-to-end 3-party protocol for efficient private training and inference of large machine learning models. F alcon presents four main advantages – (i) It is highly expressive with support for high capacity networks such as VGG16 (ii) it supports batch normalization which is important for training complex networks such as AlexNet (iii) F alcon guarantees security with abort against malicious adversaries, assuming an honest majority (iv) Lastly, F alcon presents new theoretical insights for protocol design that make it highly efficient and allow it to outperform existing secure deep learning solutions. Compared to prior art for private inference, we are about 8× faster than SecureNN (PETS’19) on average and comparable to ABY 3 (CCS’18). We are about 16 − 200× more communication efficient than either of these. For private training, we are about 6× faster than SecureNN, 4.4× faster than ABY 3 and about 2−60× more communication efficient. Our experiments in the WAN setting show that over large networks and datasets, compute operations dominate the overall latency of MPC, as opposed to the communication.

We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [Kushilevitz, Ostrovsky, and Rosén, J. Comput. Syst. Sci., 58 (1999), pp. 129--136] and [Gál and Rosén, SIAM J. Comput., 31 (2002), pp. 1424--1437]. More concretely, we consider the randomness complexity of the basic Boolean function \tt and, that serves as a building block in the design of many private protocols. We show that \tt and cannot be privately computed using a single random bit, thus giving the first nontrivial lower bound on the 1-private randomness complexity of an explicit Boolean function, $f: \{0,1\}^n \rightarrow \{0,1\}$. We further show that and, on any number of inputs $n$ (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of $n=3$ players), improving the upper bound of 73 random bits implicit in [Kushilevitz, Ostrovsky, and Rosén, J. Comput. Syst. Sci., 58 (1999), pp. 129--136]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of \tt and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for \tt xor, which is 1-random, and for several degenerate functions).

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.

Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood. In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps. We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.

Motivated by applications in cryptography, we introduce and study the problem of distribution design. The goal of distribution design is to find a joint distribution on $n$ random variables that satisfies a given set of constraints on the marginal distributions. Each constraint can either require that two sequences of variables be identically distributed or, alternatively, that the two sequences have disjoint supports. We present several positive and negative results on the existence and efficiency of solutions for a given set of constraints.

We present a unified framework for studying secure multiparty computation (MPC) with arbitrarily restricted interaction patterns such as a chain, a star, a directed tree, or a directed graph. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns, such as those studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014).

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.

Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f : 2^{[n]} -> {0,...,m-1} by guaranteeing that from the point of view of each set T \subseteq [n] of parties, the secret is uniformly distributed over a set of f(T) + 1 potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n,log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X_0,...,X_n) which starts with a random secret X_0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X_0 conditioned on the value of X_t should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate.

An information-theoretic private information retrieval (PIR) protocol allows a client to retrieve the i-th bit of a database, held by two or more servers, without revealing information about i to any individual server. Information theoretic PIR protocols are closely related to locally decodable codes (LDCs), which are error correcting codes that can simultaneously offer a high level of robustness and sublinear time decoding of each bit of the encoded message. Recent breakthrough results of Yekhanin (STOC 2007) and Efremenko (STOC 2009) have led to a dramatic improvement in the asymptotic complexity of PIR and LDC. We suggest a new “cryptographic” perspective on these recent constructions, which is based on a general notion of share conversion in secret sharing schemes that may be of independent interest. Our new perspective gives rise to a clean framework which unifies previous constructions and generalizes them in several directions. In a nutshell, we use the following two-step approach: (1) apply share conversion to get a low-communication secure multiparty computation protocol P for a nontrivial class F of low-depth circuits; (2) use a lower bound on the VC dimension of F to get a good PIR protocol from P. Our framework reduces the task of designing good PIR protocols to that of finding powerful forms of share conversion which support circuit classes of a high VC dimension. Motivated by this framework, we study the general power of share conversion and obtain both positive and negative results. Our positive results improve the concrete complexity of PIR even for very feasible real-life parameters. They also lead to some improvements in the asymptotic complexity of the best previous PIR and LDC constructions. For 3-server PIR, we improve the asymptotic communication complexity from O(2146√(log n log log n)) to O(26√(log n log log n)) bits, where n is the database size. Our negative results on share conversion establish some limitations on the power of our approach.

Randomizing polynomials represent a function f(x) by a low-degree randomized mapping p(x, r) over a finite field F such that, for any input x, the output distribution of p(x, r) depends only on the value of f(x). We study the class of functions f which admit an efficient representation by constant-degree randomizing polynomials. It is known that this class contains NC1 as well as log-space classes contained in NC2. Whether it contains all polynomial-time computable functions is a wide open question. A positive answer would have major and unexpected consequences, including the existence of efficient constant-round multiparty protocols with unconditional security, and the equivalence of (polynomial-time) cryptography and cryptography in NC0.

With the gaining popularity of remote storage (e.g. in the Cloud), we consider the setting where a small, protected local machine wishes to access data on a large, untrusted remote machine. This setting was introduced in the RAM model in the context of software protection by Goldreich and Ostrovsky. A secure Oblivious RAM simulation allows for a client, with small (e.g., constant size) protected memory, to hide not only the data but also the sequence of locations it accesses (both reads and writes) in the unprotected memory of size n. Our main results are as follows: We analyze several schemes from the literature, observing a repeated design flaw that leaks information on the memory access pattern. For some of these schemes, the leakage is actually non-negligible, while for others it is negligible. On the positive side, we present a new secure oblivious RAM scheme, extending a recent scheme by Goodrich and Mitzenmacher. Our scheme uses only O(1) local memory, and its (amortized) overhead is O(log2 n/log log n), outperforming the previously-best O(log2 n) overhead (among schemes where the client only uses O(1) additional local memory). We also present a transformation of our scheme above (whose amortized overhead is O(log2 n/log log n)) into a scheme with worst-case overhead of O(log2 n/log log n).

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.

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way.

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

We investigate the question of whether the security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.

In this paper, we analyze the following communication complexity problem. It is a variant of the set-disjointness problem, denoted PDISJlog N, where each of Alice and Bob gets as an input a subset of [N] of size at most log N, with the promise that the intersection of the two subsets is of size at most 1. We provide an almost tight lower bound of ¿¿(log2N) on the deterministic communication complexity of the problem. The main motivation for studying this problem comes from the so-called "clique vs. independent-set" problem, introduced by Yannakakis (1988). Proving an ¿(log2N) lower bound on the communication complexity of the clique vs. independent-set problem for all graphs is a long standing open problem with various implications. Proving such a lower bound for random graphs is also open. In such a graph, both the cliques and the independent sets are of size O(log N) (and obviously their intersection is of size at most 1). Hence, our ¿¿(log2N) lower bound for PDISJlog Ncan be viewed as a first step in this direction. Interestingly, we note that standard lower bound techniques cannot yield the desired lower bound. Hence, we develop a novel adversary argument that may find other applications.

We consider the following question: given a two-argument boolean function f, represented as an N x N binary matrix, how hard is it to determine the (deterministic) communication complexity of f?

A zero-knowledge proof allows a prover to convince a verifier of an assertion without revealing any further information beyond the fact that the assertion is true. Secure multiparty computation allows n mutually suspicious players to jointly compute a function of their local inputs without revealing to any t corrupted players additional information beyond the output of the function. We present a new general connection between these two fundamental notions. Specifically, we present a general construction of a zero-knowledge proof for an NP relation $R(x,w)$, which makes only a black-box use of any secure protocol for a related multiparty functionality f. The latter protocol is required only to be secure against a small number of “honest but curious” players. We also present a variant of the basic construction that can leverage security against a large number of malicious players to obtain better efficiency. As an application, one can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming that one-way functions exist, we get the following types of zero-knowledge proof protocols: (1) Approaching the witness length. If C has constant depth over $\wedge,\vee,\oplus,\neg$ gates of unbounded fan-in, we get a zero-knowledge proof protocol with communication complexity $m\cdot{poly}(k)\cdot{polylog}(s)$, where k is a security parameter. (2) “Constant-rate” zero-knowledge. For an arbitrary circuit C of size s and a bounded fan-in, we get a zero-knowledge protocol with communication complexity $O(s)+{poly}(k,\log s)$. Thus, for large circuits, the ratio between the communication complexity and the circuit size approaches a constant. This improves over the $O(ks)$ complexity of the best previous protocols.

Current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. We explore the possibility of implementing basic cryptographic primitives, such as encryption, authentication, signatures, and secure two-party computation, while incurring only a constant computational overhead compared to insecure implementations of the same tasks. Here we make the usual security requirement that the advantage of any polynomial-time attacker must be negligible in the input length.

Current constructions of efficient argument systems combine a short (polynomial size) PCP with a cryptographic hashing technique. We suggest an alternative approach for this problem that allows to simplify the underlying PCP machinery using a stronger cryptographic technique. More concretely, we present a direct method for compiling an exponentially long PCP which is succinctly described by a linear oracle function \pi : F^n \to F into an argument system in which the verifier sends to the prover O(n) encrypted field elements and receives O(1) encryptions in return. This compiler can be based on an arbitrary homomorphic encryption scheme. Applying our general compiler to the exponential size Hadamard code based PCP of Arora et al. (JACM 1998) yields a simple argument system for NP in which the communication from the prover to the verifier only includes a constant number of short encryptions. The main tool we use is a new cryptographic primitive which allows to efficiently commit to a linear function and later open the output of the function on an arbitrary vector. Our efficient implementation of this primitive is independently motivated by cryptographic applications.

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small number of "honest but curious" players. As an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols.

We consider the problem of distribution-free property-testing of functions. In this setting of property-testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain. The testing algorithms are given oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, but no distribution-free property-testing algorithm was known for any (non-trivial) property. We present the first such distribution-free property-testing algorithms for two of the central problems in this field. The testers are obtained by extending some known results (from “standard,” uniform distribution, property-testing): (1) A distribution-free testing algorithm for low-degree multivariate polynomials with query complexity $O(d^2 + d \cdot \epsilon^{-1})$, where d is the total degree of the polynomial. The same approach that is taken for the distribution-free testing of low-degree polynomials is shown to apply also to several other problems; (2) a distribution-free monotonicity testing algorithm for functions $f:[n]^d \rightarrow A$ for low dimensions (e.g., when d is a constant) with query complexity similar to the one achieved in the uniform setting. On the negative side, we prove an exponential gap between the query complexity required for uniform and distribution-free monotonicity testing in the high-dimensional case.

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. middot Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, broadcast, and general multi-party protocols that remain unconditionally secure as long as less than half of the players are maliciously corrupted. middot Efficiency. We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to both communication and computation

It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).In this paper, we study whether such nonblack-box use is essential. We present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies security under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

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 an extension of the "standard" learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model assumes that the correct classification is given by some target function f from a class of functions cal F; most of our results discuss the ability to learn a clause (an OR function of a subset of the variables) in various settings:Offline: We are given both the function f and the distribution D that is used to generate an input x. The goal is to design a strategy to decide what attribute of x to observe next so as to minimize the expected evaluation cost of f(x). (In this setting there is no "learning" to be done but only an optimization problem to be solved; this problem to be NP-hard and hence approximation algorithms are presented.)Distributional online: We study two types of "learning" problems; one where the target function f is known to the learner but the distribution D is unknown (and the goal is to minimize the expected cost including the cost that stems from "learning" D), and the other where f is unknown (except that f∈cal F) but D is known (and the goal is to minimize the expected cost while limiting the prediction error involved in "learning" f).Adversarial online: We are given f, however the inputs are selected adversarially. The goal is to compare the learner's cost to that of the best fixed evaluation order (i.e., we analyze the learner's performance by a competitive analysis).

In this paper, we examine noisy radio (broadcast) networks in which every bit transmitted has a certain probability of being flipped. Each processor has some initial input bit, and the goal is to compute a function of these input bits. In this model, we show a protocol to compute any threshold function using only a linear number of transmissions.

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.

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket. Batch codes can be viewed as relaxing several combinatorial objects, including expanders and locally decodable codes. We initiate the study of these codes by presenting some constructions, connections with other problems, and lower bounds. We also demonstrate the usefulness of batch codes by presenting two types of applications: trading maximal load for storage in certain load-balancing scenarios, and amortizing the computational cost of private information retrieval (PIR) and related cryptographic protocols.

We study the relationship between the number of rounds needed to repeatedly perform a private computation (i.e., where there are many sets of inputs sequentially given to the players on which the players must compute a function privately) and the overall randomness needed for this task. For the XOR function we show that, by re-using the same $\ell$ random bits, we can significantly speed up the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the $\ell$ random bits between the computations. Moreover, we prove that our protocols are optimal in the amount of randomness they require.

Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic, k-server PIR protocols the database is replicated among k servers, and each server learns nothing about the item the user retrieves. The cost of such protocols is measured by the communication complexity of retrieving one out of n bits of data. For any fixed k, the complexity of the best protocols prior to our work was O(n/sup 1/2k-1/). Since then several methods were developed in an attempt to beat this bound, but all these methods yielded the same asymptotic bound. In this paper, this barrier is finally broken and the complexity of information-theoretic k-server PIR is improved to n/sup O(log log k/k log k)/. The new PIR protocols can also be used to construct k-query binary locally decodable codes of length exp(n/sup O(log log k/k log k)/), compared to exp(n/sup 1/k-1/) in previous constructions. The improvements presented in this paper apply even for small values of k: the PIR protocols are more efficient than previous ones for every k/spl ges/3, and the locally decodable codes are shorter for every k/spl ges/4.

The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Verifiable Secret Sharing (VSS) and Secure Multicast.

The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in the usual sense, but does not yield any information on x other than what can be deduced from f(x). As such, F(x) is useful for private computation of f(x) (assuming that F can be computed more efficiently than f.In this work we examine the properties and limitations of this new notion. Specifically, we show that for many NP-hard problems, the privacy requirement precludes non-trivial approximation. This is the case even for problems that otherwise admit very good approximation (e.g., problems with PTAS). On the other hand, we show that slightly relaxing the privacy requirement, by means of leaking “just a few bits of informationrdquo; about x, again permits good approximation.

Motivated by questions about secure multi-party computation, we introduce and study a new natural representation of functions by polynomials, which we term randomizing polynomials. "Standard" low-degree polynomials over a finite field are easy to compute with a small number of communication rounds in virtually any setting for secure computation. However, most Boolean functions cannot be evaluated by a polynomial whose degree is smaller than their input size. We get around this barrier by relaxing the requirement of evaluatingf into a weaker requirement of randomizing f: mapping the inputs of f along with independent random inputs into a vector of outputs, whose distribution depends only on the value of f . We show that degree-3 polynomials are sufficient to randomize any function f , relating the efficiency of such a randomization to the branching program size of f . On the other hand, by characterizing the exact class of Boolean functio...

We study the learnability of multiplicity automata in Angluin's exact learning model , and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function to the rank of its Hankel matrix. With this theorem in hand, we present a new simple algorithm for learning multiplicity automata with improved time and query complexity, and we prove the learnability of various concept classes. These include (among others): -The class of disjoint DNF, and more generally satisfy- O (1) DNF. -The class of polynomials over finite fields. -The class of bounded-degree polynomials over infinite fields. -The class of XOR of terms. -Certain classes of boxes in high dimensions. In addition, we obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2). While multiplicity automata are shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, we study the limitations of this method. We prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulas or even k -term DNF for k = ω(log n ) or satisfy- s DNF formulas for s = ω(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with super-polynomial number of states.

We define the notions of reducibility and completeness in (two-party and multiparty) private computations. Let g be an n-argument function. We say that a function f is reducible to a function g if n honest-but-curious players can compute the function fn -privately, given a black box for g (for which they secretly give inputs and get the result of operating g on these inputs). We say that g is complete (for private computations) if every function f is reducible to g. In this paper, we characterize the complete boolean functions: we show that a boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black box available). Namely, for n-argument boolean functions, the notions of completeness and n-privacy are complementary. This characterization provides a huge collection of complete functions any nonprivate boolean function!) compared to very few examples that were given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are not complementary.

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting of a set of vectors in some high dimensional Euclidean space, we want to construct a space-efficient data structure that would allow us to search, given a query vector, for the closest or nearly closest vector in the database. We also address this problem when distances are measured by the L 1 norm and in the Hamming cube. Significantly improving and extending recent results of Kleinberg, we construct data structures whose size is polynomial in the size of the database and search algorithms that run in time nearly linear or nearly quadratic in the dimension. (Depending on the case, the extra factors are polylogarithmic in the size of the database.)

In this work we introduce and study threshold (t-out-of-n) secret sharing schemes for families of functions ${\cal F}$. Such schemes allow any set of at least t parties to compute privately the value f(s) of a (previously distributed) secret s, for any $f\in {\cal F}$. Smaller sets of players get no more information about the secret than what follows from the value f(s). The goal is to make the shares as short as possible. Results are obtained for two different settings: we study the case when the evaluation is done on a broadcast channel without interaction, and we examine what can be gained by allowing evaluations to be done interactively via private channels.

Private Information Retrieval (PIR) protocols allow a user to read information from a database without revealing to the server storing the database which information he has read.Kushilevitz and Ostrovsky [23] construct, based on the quadratic residuosity assumption, a single-server PIR protc-co1 with small communication complexity.Cachin, Micali, and Stadler [6] present a single-server PIR protocol with a smaller communication complexity, based an the (new) *hiding assumption.A major question, addressed in the present work, is what assumption is the minimal assumption necessary for the construction of single-server private information retrieval protocols with small communication complexity.We prove that if there is a (O-error) PIR protocol in which the server sends less than n bits then one-way functions exist (where n is the number of bits in the database).That is, even saving one bit compared to the naive protocol, in which the entire database is sent, already requires one-way functions.The same result holds (but requires more work) even if we allow the retrieval to fail with probability of at most 1/(8n).Moreover, similar tcomputer science

Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit database x, replicated in k servers, while keeping the value of i private from each server. A t-private PIR scheme protects the user's privacy from any collusion of up to t servers. The main cost measure for such schemes is their communication complexity. We introduce a new technique for the construction of information-theoretic (i.e., unconditionally secure) PIR schemes, providing a non-trivial linear-algebraic generalization of previous techniques. Using this technique, we improve and simplify known upper bounds on the communication complexity of PIR schemes in the information-theoretic setting. In the case of 1-private PIR, we give a simple k-server scheme with complexity O(k 3 n 1=(2k\\Gamma1) ), improving the best known construction whose complexity also grows linearly in n 1=(2k\\Gamma1) for any fixed k, but depends exponentially on k. Our improvements are more significant for t-pri...

Article The query complexity of finding local minima in the lattice Share on Authors: Amos Beimel Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MA Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MAView Profile , Felix Geller Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Eyal Kushilevitz Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 294–302https://doi.org/10.1145/279943.280000Online:24 July 1998Publication History 1citation200DownloadsMetricsTotal Citations1Total Downloads200Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

IntroductionWe study the relationship between the number of rounds needed to repeatedly perform a private computation (i.e., where there are many sets of inputs sequentially given to the players on which the players must compute a function privately) and the overall randomness needed for this task.For the XOR function, we show that for k sets of inputs, if instead of using totally fresh (i.e., independent) random bits for each of these k sets of inputs, we re-use the same f! random bits then we can significantly speedup the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the fJ random bits between the k computations.

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems: path selection and congestion resolution along the selected paths. However, this conceptual separation has a serious drawback: each packet’s path is fixed at the source and cannot be modified adaptively en-route. The problem is especially severe when packet injections are modeled by an adversary, whose goal is to cause “traffic-jams”. In this paper, we consider this adversarial setting, motivated by the “adversarial queuing theory ” model of Borodin et al. [BKR+]. More precisely, we consider an adversary who injects packets, with only their destinations specified, into network nodes in a continuous manner subject to certain limitations on the injection rate. The question whether it is possible to deal with such an adversary and to design protocols that would “discover ” routes which avoid “traffic jams ” so that nodes only store a bounded number of packets, was left as an open problem by Andrews et al. [AAF+] (who deal with the “non-adaptive ” case where the adversary provides routes for the packets). In the present paper, we resolve this open problem. In particular, we present a simple, deterministic, local-control protocol that applies to any network topology. Our protocol guarantees that, for any injection sequence generated by the adversary, the buffers at the nodes are polynomially-bounded and that each packet has a polynomiallybounded delivery time.

Abotract'An (;)-OT protocol (also denoted "all or nothing discloxwc of secrets") allows Bob to secretly choose one of n occret bits held hy Alice, in a way that at the end of the protocol Bob learnn only a oinglo bit of his choice, and Alice learns nothing about Bob% choice.

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors.More specifically, given a database consisting of a set of vectors in some high dimensional Euclidean space, we want to construct a space-efficient data struct,ure t,hat would allow us to search, given a query vector, for t.he closest or nearly closest vector in the database.We also address t.hii problem when distances are measured by the L1 norm, and in t.he Hamming cube.Sign%cant.lyimproving and extending recent results of Kleinberg, we const,ruct data structures whose size is polynomial in the size of t,he database, and search algorithms t,hat run in time nearly linear or nearly quadratic in the dimension (depending on the case; the extra factors are polylogarit.hmicin the size of the database).

Publicly accessible databases are an indispensable resource for retrieving up-to-date information. But they also pose a significant risk to the privacy of the user, since a curious database operator can follow the user's queries and infer what the user is after. Indeed, in cases where the users' intentions are to be kept secret, users are often cautious about accessing the database. It can be shown that when accessing a single database, to completely guarantee the privacy of the user, the whole database should be down-loaded; namely n bits should be communicated (where n is the number of bits in the database). In this work, we investigate whether by replicating the database, more efficient solutions to the private retrieval problem can be obtained. We describe schemes that enable a user to access k replicated copies of a database ( k ≥2) and privately retrieve information stored in the database. This means that each individual server (holding a replicated copy of the database) gets no information on the identity of the item retrieved by the user. Our schemes use the replication to gain substantial saving. In particular, we present a two-server scheme with communication complexity O(n 1/3 ).

We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for $k\cdot j=O({\log n\over\log\log n})$, where n is the number of input variables.

We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a message is $\Omega(D\log (N/D))$, where D is the diameter of the network and N is the number of nodes. This implies a tight lower bound of $\Omega(D\log N)$ for any $D \le N^{1-\varepsilon}$, where $\varepsilon > 0$ is any constant.

We establish, for the first time, lower bounds for randomized mutual exclusion algorithms (with a read-modify-write operation). Our main result is that a constant-size shared variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of $\Omega (\log\log n)$ bits on the size of the shared variable, which is also tight. We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared variable. Our lower bounds rely on an analysis of Markov chains that may be of interest on its own and may have applications elsewhere.

Communication between processors is the essence of distributed computing: clearly, without communication, distributed computation is impossible. However, as networks become larger and larger, the frequency of link failures increases. The end-to-end communication problem asks how to efficiently carry out fault-free communication between two processors over a network, in spite of such frequent link failures. The sole minimum assumption is that the two processors that are trying to communicate are not permanently disconnected (i.e., the communication should proceed even when there does not (ever) simultaneously exist an operational path between the two processors that are trying to communicate). We present a protocol to solve the end-to-end problem with logarithmic-space and polynomial communication at the same time. This is an exponential memory improvement to all previous polynomial communication solutions. That is, all previous polynomial communication solutions needed at least linear (in n, the size of the network) amount of memory per link. Our protocol transfers packets over the network, maintains a simple-to-compute O(log n)-bits potential function at each link in order to perform routing, and uses a novel technique of packet canceling which allows us to keep only one packet per link. The computations of both our potential function and our packet-canceling policy are totally local in nature.

We study the role of randomness in multiparty private computations. In particular, we give several results that prove the existence of a randomness-rounds tradeoff in multiparty private computation of $\fxor$. We show that with a single random bit, $\Theta(n)$ rounds are necessary and sufficient to privately compute $\fxor$ of n input bits. With $d\ge 2$ random bits, $\Omega(\log n/ d)$ rounds are necessary, and $O(\log n/ \log d)$ are sufficient. More generally, we show that the private computation of a boolean function f, using $d\ge 2 $ random bits, requires $\Omega(\log S(f)/ d)$ rounds, where S(f) is the sensitivity of f. Using a single random bit, $\Omega(S(f))$ rounds are necessary.

We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.

We investigate the relations between the fault tolemnce (or resilience) and the mndornnea requirements of multiparty protocols.Fault-tolerance is measured in terms of the maximum number of colluding faulty players, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honeat players).Randomness is measured in terms of the total number of random bits needed by the players in order to execute the protocol.Previously, the upper bound on the amount of randomncm needed for securely computing any non-trivial function ~was polynomial both in n, the total number of parties, and the circuit-size C(f).This was the state of knowledge even for the special case t = 1 (i.e., when there is at most one malicious player).In this paper, we show that for any linear-size circuit, and for any value t < n/2, O(poly(t) .log n) randomness is srtflicient.More generally, we show that for any function j with circuit-size C(~), we need only O (poiy(t) .log n + polg(t) .~) randomness in order to withstrmd any coalition of size at most t.Moreover, in our prot~ CO1 only t + 1 players flip coins and the rest of the players are deterministic.Our results generalize to the case of adaptive adversaries as well.

This paper solves the open problem of exact learning geometric objects bounded by hyperplanes (and more generally by any constant degree algebraic surfaces) in the constant dimensional space from equivalence queries only (i.e., in the on-line learning model). We present a novel approach that allows, under certain conditions, the composition of learning algorithms for simple classes into an algorithm for a more complicated class. Informally speaking, it shows that if a class of concepts C is learnable in time t using a small space then C ? , the class of all functions of the form f(g 1 ; : : : ; g m ) with g 1 ; : : : ; gm 2 C and any f , is learnable in polynomial time in t and m. We then show that the class of halfspaces in a fixed dimension space is learnable with a small space. 1 Introduction Littlestone's on-line learning model [L88, L89] is one of the major models of learning. Learnability in this model implies learnability in Valiant's PAC model [Val84], and is equivalent to l...

We consider the amount of randomness used in private distributed computations. Specifically, we show how n players can compute the exclusive-or (xor) of n boolean inputs t-privately, using only O(t2 log (n/t)) random bits (the best known upper bound is O(tn)). We accompany this result by a lower bound on the number of random bits required to carry out this task; we show that any protocol solving this problem requires at least t random bits (again, this significantly improves over the known lower bounds). For the upper bound, we show how, given m subsets of {1,...,n}, to construct in (deterministic) polynomial time a probability distribution of n random variables (i.e., a probability distribution over {0,1}n) such that (1) the parity of random variables in each of these m subsets is 0 or 1 with equal probability, and (2) the support of the distribution is of size at most 2m. This construction generalizes previously considered types of sample spaces (such as k-wise independent spaces and Schulman's spaces [Sample spaces uniform on neighborhoods, in Proc. of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 17--25]). We believe that this construction is of independent interest and may have various applications.

Article Free Access Share on A simple algorithm for learning O(log n)-term DNF Author: Eyal Kushilevitz Department of Computer Science, Technion Institute of Technology, Haifa, Israel Department of Computer Science, Technion Institute of Technology, Haifa, IsraelView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 266–269https://doi.org/10.1145/238061.238115Online:01 January 1996Publication History 8citation189DownloadsMetricsTotal Citations8Total Downloads189Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The learnability of multiplicity automata has attracted a lot of attention, mainly because of its implications on the learnability of several classes of DNF formulae. The authors further study the learnability of multiplicity automata. The starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function f to the rank of a certain matrix F. With this theorem in hand they obtain the following results: a new simple algorithm for learning multiplicity automata with a better query complexity. As a result, they improve the complexity for all classes that use the algorithms of Bergadano and Varricchio (1994) and Ohnishi et al. (1994) and also obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2). They prove the learnability of some new classes that were not known to be learnable before. Most notably, the class of polynomials over finite fields, the class of bounded-degree polynomials over infinite fields, the class of XOR of terms, and a certain class of decision trees. While multiplicity automata were shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, they study the limitations of this method. They prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulae or even K-term DNF for k=/spl omega/ (log n) or satisfy-s DNF formulae for s=/spl omega/(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with superpolynomial number of states.

We consider the amount of randomness used in private distributed computations.Specifically, we show how n players can compute the exclusive-or (xor) of n boolean inputs t-privately, using only C)(tz log(n/t)) random bits (the best known upper bound is O(i!n)).We accompany this result by a lower bound on the number of random bits required to carry out this task; we show that any protocol solving this problem requires at least t random bits (again, this significantly improves over the known lower bounds).For the upper bound, we show how, given m subsets Of {l,... , n}, to construct in (deterministic) polynomial time a probability distribution of n random variables such that ( 1 ) the parity of random-variables in each of these m subsets is O or 1 with equal probability; and (2) the support of the distribution is of size at most 2m.This construction generalizes previously considered types of sample spaces (such as k-wise independent spaces and Schulman's spaces [S92]).We believe that this construction is of independent interest and may have various applications.1

A linear array network consists of k + 1 processors P 0 ; P 1 ; : : : ; P k with links only between P i and P i+1 (0 i ! k). It is required to compute some boolean function f(x; y) in this network, where initially x is stored at P 0 and y is stored at P k . Let D k (f) be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, D k (f) k \\Delta D(f ), where D(f) is the standard two-party communication complexity of f . Tiwari proved that for almost all functions D k (f) k(D(f) \\Gamma O(1)) and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite family of functions for which D k (f) is essentially at most 3 4 k \\Delta D(f ). Our construction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, given the least number of monochromatic rectangles in any partition of the input space. How tight are suc...

erms of PrivacyAdi Ros&$ constant-random protocol, might be difficult.In this paper we prove a perhaps unexpected relationship between the complexity class of linear size circuits, and n-part y private protocols.Specifically, let ~: {O, I}n ~{O, 1} be a boolean function.We show that ~has a linear size circuit if and only if j has a l-private n-part y protocol in which the total number of random bits used by all players is constant.From the point of view of complexity theory, our result gives a characterization of the class of linear size circuits in terms of another class of a very different nature.From the point of view of privacy, this result provides l-private protocols that use a constant number of random bits, for many important functions for which no such protocol was known.On the other hand, our result suggests that proving, for any lV.P function, that it has no l-private

We study several issues concerning the selfdmected model of learning [G RS93, GS94).In of queries it has to go through.

We describe schemes that enable a user to access k replicated copies of a database (k/spl ges/2) and privately retrieve information stored in the database. This means that each individual database gets no information on the identity of the item retrieved by the user. For a single database, achieving this type of privacy requires communicating the whole database, or n bits (where n is the number of bits in the database). Our schemes use the replication to gain substantial saving. In particular, we have: A two database scheme with communication complexity of O(n/sup 1/3/). A scheme for a constant number, k, of databases with communication complexity O(n/sup 1/k/). A scheme for 1/3 log/sub 2/ n databases with polylogarithmic (in n) communication complexity.

Article Log-space polynomial end-to-end communication Share on Authors: Eyal Kushilevitz Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile , Rafail Ostrovsky Computer Science Division, University of California at Berkeley and International Computer Science Institute, Berkeley, CA Computer Science Division, University of California at Berkeley and International Computer Science Institute, Berkeley, CAView Profile , Adi Rosén Dept of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel Dept of Computer Science, Tel-Aviv University, Tel-Aviv 69978, IsraelView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 559–568https://doi.org/10.1145/225058.225273Online:29 May 1995Publication History 9citation202DownloadsMetricsTotal Citations9Total Downloads202Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The subject of this work is the possibility of private distributed computations of n-argument functions defined over the integers. A function f is t-private if there exists a protocol for computing f, so that no coalition of at most t participants can infer any additional information from the execution of the protocol. It is known that over finite domains every function can be computed $\lfloor (n - 1)/2 \rfloor $-privately. Some functions, like addition, are even n-private. We prove that this result cannot be extended to infinite domains. The possibility of privately computing f is shown to be closely related to the communication complexity of f. By using this relation, we show, for example, that n-argument addition is $\lfloor (n - 1)/2 \rfloor $-private over the nonnegative integers, but not even 1-private over all the integers. Finally, a complete characterization of t-private Boolean functions over countable domains is given. A Boolean function is 1-private if and only if its communication complexity is bounded. This characterization enables us to prove that every Boolean function falls into one of the following three categories: It is either n-private, $\lfloor (n - 1)/2 \rfloor $-private but not $\lceil n/2 \rceil$-private, or not 1-private.

In this work we study the direct-sum problem with respect to communication complexity: Consider a relation f defined over $\{0,1\}^{n} \times \{0,1\}^{n}$. Can the communication complexity of simultaneously computing f on $\ell $ instances $(x_{1}, y_{1}), \dotsc , (x_{\ell}, y_{\ell})$ be smaller than the communication complexity of separately computing f on the $\ell $ instances? Let the amortized communication complexity of f be the communication complexity of simultaneously computing f on $\ell $ instances divided by $\ell $. We study the properties of the amortized communication complexity. We show that the amortized communication complexity of a relation can be smaller than its communication complexity. More precisely, we present a partial function whose (deterministic) communication complexity is $\Theta (\log n)$ and amortized (deterministic) communication complexity is $O(1)$. Similarly, for randomized protocols we present a function whose randomized communication complexity is $\Theta (\log n)$ and amortized randomized communication complexity is $O(1)$. We also give a general lower bound on the amortized communication complexity of any functionf in terms of its communication complexity $C(f)$: for every function f the amortized communication complexity of f is $\Omega (\sqrt{C(f)} - \log n)$.

It is possible to view communication complexity as the minimum solution of an integer programming problem. This integer programming problem is relaxed to a linear programming problem and from it information regarding the original communication complexity question is deduced. A particularly appealing avenue this opens is the possibility of proving lower bounds on the communication complexity (which is a minimization problem) by exhibiting upper bounds on the maximization problem defined by the dual of the linear program. This approach works very neatly in the case of nondeterministic communication complexity. In this case a special case of Lovász’s fractional cover measure is obtained. Through it the amortized nondeterministic communication complexity is completely characterized. The power of the approach is also illustrated by proving lower and upper bounds on the nondeterministic communication complexity of various functions. In the case of deterministic complexity the situation is more complicated. Two attempts are discussed and some results using each of them are obtaied. The main result regarding the first attempt is negative: one cannot use this method for proving superpolynomial lower bounds for formula size. The main result regarding the second attempt is a “direct-sum” theorem for two-round communication complexity.

Lotteries with the unique maximum property and the unique winner property are considered. Tight lower bounds are proven on the domain size of such lotteries.

We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k•j=O(logn/loglogn). Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size > 2W(n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

We define the notions of reducibility and completeness in multi-party private computations. Let g be an n-argument function. We say that a function f is reducible to g if n honest-but-curious players can compute the function f n-privately, given a black-box for g (for which they secretly give inputs and get the result of operating g on these inputs). We say that g is complete (for multi-party private computations) if every function f is reducible to g. In this paper, we characterize the complete Boolean functions: we show that a Boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black-box available). Namely, for Boolean functions, the notions of completeness and n-privacy are complementary. This characterization gives a huge collection of complete functions (any non-private Boolean function!) compared to very few examples given (implicitly) in previous work. On the other hand, for non-Boolean functions, we show that these two notions are not complementary. Our results can be viewed as a generalization (for multi-party protocols and for (n/spl ges/2)-argument functions) of the two-party case, where it was known that Oblivious Transfer protocol (and its variants) are complete.>

We consider the problem of learning visual concepts in the mistake-bound and the PAC models.We develop an approach that is shown to be useful also for the problem of learning DNF formulae in these models.As a result, we extend the class of learnable DNF (and CNF) formulae.The classes shown to be learnable are not limited in the number of terms or in the number of variables per term, and they contain the classes of k-DNF and kterm-DNF (and the corresponding classes of CNF) as special cases.We discuss some of the limitations of this approach and a number of applications.

We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a message is Q(ll log(N/11)), where D is the diameter of the network and N is the number of nodes.This implies a tight lower bound of Q( D log N) for all D S N1-e, where s >0 is any constant.

We establish, for the first time, lower bounds for randomized mutual-exclusion algorithms (with a read-modify-write operation). Our main result is that a constant size shared-variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of\\Omega\\Gamma/46 log n) bits on the size of the shared-variable, which is also tight. We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared-variable. Our lower bounds rely on an analysis of Markovchains, that may be of interest on its own and may have applications elsewhere. Keywords: Mutual Exclusion, Randomized Distributed Algorithms, Markov-Chains, Lower-Bounds. 1 Introduction Randomization has played an important role in the design and understanding of distributed algorithms. It is a natural tool which is usual...

This work gives a polynomial time algorithm for learning decision trees with respect to the uniform distribution. (This algorithm uses membership queries.) The decision tree model that is considered is an extension of the traditional boolean decision tree model that allows linear operations in each node (i.e., summation of a subset of the input variables over $GF(2)$). This paper shows how to learn in polynomial time any function that can be approximated (in norm $L_2 $) by a polynomially sparse function (i.e., a function with only polynomially many nonzero Fourier coefficients). The authors demonstrate that any function f whose $L_1 $-norm (i.e., the sum of absolute value of the Fourier coefficients) is polynomial can be approximated by a polynomially sparse function, and prove that boolean decision trees with linear operations are a subset of this class of functions. Moreover, it is shown that the functions with polynomial $L_1 $-norm can be learned deterministically. The algorithm can also exactly identify a decision tree of depth d in time polynomial in $2^d $ and n. This result implies that trees of logarithmic depth can be identified in polynomial time.

Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation.>

In [4] a randomized algorithm for mutual exclusion with bounded waiting, employing a logarithmic sized shared variable, was given. Saias and Lynch [5] pointed out that the adversary scheduler postulated in the above paper can observe the behavior of processes in the interval between an opening of the critical section and the next closing of the critical section. it can then draw conclusions about values of their local variables as well as the value of the randomized round number component of the shared variable, and arrange the schedule so as to discriminate against a chosen process. This invalidates the claimed properties of the algorithm.

Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of $f( x,y )$. That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value $f ( x,y )$, and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every $1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)$ there are functions that can be privately computed with $g( n )$-rounds of communication, but not with $( g ( n ) - 1 )$-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.

The authors study the direct sum problem with respect to communication complexity: Consider a function f: D to (0, 1), where D contained in (0, 1)/sup n/*(0, 1)/sup n/. The amortized communication complexity of f, i.e. the communication complexity of simultaneously computing f on l instances, divided by l is studied. The authors present, both in the deterministic and the randomized model, functions with communication complexity Theta (log n) and amortized communication complexity O(1). They also give a general lower bound on the amortized communication complexity of any function f in terms of its communication complexity C(f).>

This work gives a polynomial time algcmithm for learning decision trees with respect tc~the uniform distribution.(This algorithm uses memb- ership queries.)

A Boolean function $f:A_1 \times A_2 \times \cdots \times A_n \to \{ 0,1 \}$ is t-private if there exists a protocol for computing f so that no coalition of size $\leqq t$ can infer any additional information from the execution, other than the value of the function. It is shown that f is $\lceil n/2 \rceil $-private if and only if it can be represented as \[ f ( x_1 ,x_2 , \cdots ,x_n ) = f_1 ( x_1 ) \oplus f_2 ( x_2 ) \oplus \cdots \oplus f_n ( x_n ), \] where the $f_i $ are arbitrary Boolean functions. It follows that if f is $\lceil n/2 \rceil $-private, then it is also n-private. Combining this with a result of Ben-Or, Goldwasser, and Wigderson, and of Chaum, Crepeau, and Damgard, [Proc. 20th Symposium on Theory of Computing, 1988, pp. 1–10 and pp. 11–19] an interesting “zero-one” law for private distributed computation of Boolean functions is derived: every Boolean function defined over a finite domain is either n-private, or it is $\lfloor ( n - 1 )/2 \rfloor $-private but not $\lceil n/2 \rceil $-private. A weaker notion of privacy is also investigated, where (a) coalitions are allowed to infer a limited amount of additional information, and (b) there is a probability of error in the final output of the protocol. It is shown that the same characterization of $\lceil n/2 \rceil $-private Boolean functions holds, even under these weaker requirements.In particular, this implies that for Boolean functions, the strong and the weak notions of privacy are equivalent.

The possibility of private distributed computations of n-argument functions defined over the integers is considered. A function f is t-private if there exists a protocol for computing f so that no coalition of>

Each of two parties P/sub 1/ and P/sub 2/ holds an n-bit input, x and y, respectively. They wish to compute privately the value of f(x,y). Two questions are considered: (1) Which functions can be privately computed? (2) What is the communication complexity of protocols that privately compute a function f (in the case in which such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1>

A Boolean function ƒ: A1 X A2 X … X An → {0,1} is t - private if there exists a protocol for computing ƒ so that no coalition of size ≤ t can infer any additional information from the execution, other than the value of the function. We show that ƒ is ⌈n/2⌉ - private if and only if it can be represented as ƒ (x1, x2, …, xn) = ƒ (x1) ⊕ ƒ2(x2) ⊕ … ⊕ ƒn (xn, where the ƒi are arbitrary Boolean functions. It follows that if ƒ is ⌈n/2⌉ - private, then it is also n - private. Combining this with a result of Ben-Or, Goldwasser, and Wigderson, we derive an interesting “zero-one” law for private distributed computation of Boolean functions: Every Boolean function defined over a finite domain is either n - private, or it is ⌈n-1/2⌉ - private but not ⌈n/2⌉ - private.