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.

There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes for$n$-party access structures; consistent with our current knowledge the optimal share size can be anywhere between polynomial and exponential in$n$. For linear secret-sharing schemes, the share size for almost all$n$-party access structures is exponential in$n$. We would like to study larger classes of secret-sharing schemes with two goals: 1) prove lower bounds for larger classes of secret-sharing schemes; and 2) construct efficient secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC’20) introduced a new class of secret-sharing schemes in which the shares are generated by applying degree-$d$polynomials to the secret and some random field elements. We define and study two additional classes of polynomial secret-sharing schemes: 1) schemes in which the reconstruction of the secret is done using polynomials; and 2) schemes in which both sharing and reconstruction are done by polynomials. Our main result is a construction of secret-sharing schemes and conditional disclosure of secrets protocols with quadratic sharing and reconstruction that are more efficient than linear secret-sharing schemes. To complement our results, we prove lower bounds on the share size for schemes with polynomial reconstruction. Finally, we give an evidence that schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction.

Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a valid solution to some predefined problem at any point in time; the goal is to design an algorithm in which computing a solution to the updated input is done more efficiently than computing the solution from scratch. A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis. Our results are as follows.

In his seminal work, Cleve [ Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 364--369] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. This lower bound was met for the two-party case by Moran, Naor, and Segev [ J. Cryptology, 29 (2016), pp. 491--513] and the three-party case (up to a ${polylog}$ factor) by Haitner and Tsfadia [ SIAM J. Comput., 46 (2017), pp. 479--542] and was approached for $n$-party protocols when $n< {loglog} r$ by Buchbinder et al. [ Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2580--2600]. For $n > {loglog} r$, however, the best bias for $n$-party coin-flipping protocols remains $O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch et al. [ How to implement Bracha's ${O}(\log n)$ Byzantine Agreement Algorithm, manuscript, 1985]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\varepsilon >0$, an $r^{\varepsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound and is only $n=r^{\varepsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of (``augmented'') weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [ Martingales, Collective Coin Flipping and Discrete Control Processes (Extended Abstract), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of R. Cleve and R. Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph$G=(V,E)$if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in$E$(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with$n$vertices and at most$n^{1+\beta }$edges (resp. at least$\binom {n}{2} - n^{1+\beta }$edges), for some$0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size$\tilde {O} (n^{1+\beta /2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is$\tilde {O} (n^{1/4+\beta /4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size$\Omega (n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is$\Omega (n^{1+\beta /2})$. Finally, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is$\Omega (n^{1/4+\beta /4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

Let H be a class of boolean functions and consider a composed class H’ that is derived from H using some arbitrary aggregation rule (for example, H’ may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H’ in terms of that of H. As a corollary, we derive closure properties for online learning and private PAC learning. The derived bounds on the Littlestone dimension exhibit an undesirable exponential dependence. For private learning, we prove close to optimal bounds that circumvents this suboptimal dependency. The improved bounds on the sample complexity of private learning are derived algorithmically via transforming a private learner for the original class H to a private learner for the composed class H’. Using the same ideas we show that any (proper or improper) private algorithm that learns a class of functions H in the realizable case (i.e., when the examples are labeled by some function in the class) can be transformed to a private algorithm that learns the class H in the agnostic case.

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).

In a recent paper, Chan et al. [SODA '19] proposed a relaxation of the notion of (full) memory obliviousness, which was introduced by Goldreich and Ostrovsky [J. ACM '96] and extensively researched by cryptographers. The new notion, differential obliviousness, requires that any two neighboring inputs exhibit similar memory access patterns, where the similarity requirement is that of differential privacy. Chan et al. demonstrated that differential obliviousness allows achieving improved efficiency for several algorithmic tasks, including sorting, merging of sorted lists, and range query data structures. In this work, we continue the exploration of differential obliviousness, focusing on algorithms that do not necessarily examine all their input. This choice is motivated by the fact that the existence of logarithmic overhead ORAM protocols implies that differential obliviousness can yield at most a logarithmic improvement in efficiency for computations that need to examine all their input. In particular, we explore property testing, where we show that differential obliviousness yields an almost linear improvement in overhead in the dense graph model, and at most quadratic improvement in the bounded degree model. We also explore tasks where a non-oblivious algorithm would need to explore different portions of the input, where the latter would depend on the input itself, and where we show that such a behavior can be maintained under differential obliviousness, but not under full obliviousness. Our examples suggest that there would be benefits in further exploring which class of computational tasks are amenable to differential obliviousness.

We present a private agnostic learner for halfspaces over an arbitrary finite domain $X\subset \R^d$ with sample complexity $\mathsf{poly}(d,2^{\log^*|X|})$. The building block for this learner is a differentially private algorithm for locating an approximate center point of $m>\mathsf{poly}(d,2^{\log^*|X|})$ points – a high dimensional generalization of the median function. Our construction establishes a relationship between these two problems that is reminiscent of the relation between the median and learning one-dimensional thresholds [Bun et al. FOCS ’15]. This relationship suggests that the problem of privately locating a center point may have further applications in the design of differentially private algorithms. We also provide a lower bound on the sample complexity for privately finding a point in the convex hull. For approximate differential privacy, we show a lower bound of $m=\Omega(d+\log^*|X|)$, whereas for pure differential privacy $m=\Omega(d\log|X|)$.

Kasiviswanathan et al. (FOCS 2008) defined private learning as a combination of PAC learning and differential privacy. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. left open the question of characterizing the sample complexity of private learners. We give a combinatorial characterization of the sample size sufficient and necessary to learn a class of concepts under pure differential privacy. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure $RepDim$ corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class $C$ with sample complexity $m$ implies $RepDim(C)=O(m)$, and that there exists a private learning algorithm with sample complexity $m=O(RepDim(C))$. We further demonstrate that a similar characterization holds for the database size needed for computing a large class of optimization problems under pure differential privacy, and also for the well studied problem of private data release.

In his seminal work, Cleve [STOC '86] proved that the bias of any coin-flipping protocol is inversely proportional to the number of rounds. This lower bound was met for the two-party case by Moran et al. [Journal of Cryptology '16], and the three-party case (up to a polylogarithmic factor) by Haitner and Tsfadia [SICOMP '17], and was approached for multi-party protocols by Haitner et al. [SODA '17] when the number of rounds is at least doubly exponential in the number of parties. For the complement case, however, the best bias for multi-party coin-flipping protocols is proportional to the number of parties and inversely proportional to the square root of the number of rounds. The latter bias is achieved by the majority protocol of Awerbuch et al. [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, if the number of rounds is bounded by some polynomial in the number of parties, then the bias is lower-bounded by a quantity that is inversely proportional to the square root of the number of rounds (up to a polylogarithmic factor). As far as we know, this is the first improvement of Cleve's bound, and is far from the aforementioned upper bound of Awerbuch et al. only by a factor of the number of parties. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

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.

A private learner is an algorithm that given a sample of labeled individual examples outputs a generalizing hypothesis while preserving the privacy of each individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a generic construction of private learners, in which the sample complexity is (generally) higher than what is needed for non-private learners. This gap in the sample complexity was then further studied in several followup papers, showing that (at least in some cases) this gap is unavoidable. Moreover, those papers considered ways to overcome the gap, by relaxing either the privacy or the learning guarantees of the learner. We suggest an alternative approach, inspired by the (non-private) models of semi-supervised learning and active-learning, where the focus is on the sample complexity of labeled examples whereas unlabeled examples are of a significantly lower cost. We consider private semi-supervised learners that operate on a random sample, where only a (hopefully small) portion of this sample is labeled. The learners have no control over which of the sample elements are labeled. Our main result is that the labeled sample complexity of private learners is characterized by the VC dimension. We present two generic constructions of private semi-supervised learners. The first construction is of learners where the labeled sample complexity is proportional to the VC dimension of the concept class, however, the unlabeled sample complexity of the algorithm is as big as the representation length of domain elements. Our second construction presents a new technique for decreasing the labeled sample complexity of a given private learner, while roughly maintaining its unlabeled sample complexity. In addition, we show that in some settings the labeled sample complexity does not depend on the privacy parameters of the learner.

In 2008, Kasiviswanathan el al. defined private learning as a combination of PAC learning and differential privacy [16]. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. gave a generic construction of private learners for (finite) concept classes, with sample complexity logarithmic in the size of the concept class. This sample complexity is higher than what is needed for non-private learners, hence leaving open the possibility that the sample complexity of private learning may be sometimes significantly higher than that of non-private learning. We give a combinatorial characterization of the sample size sufficient and necessary to privately learn a class of concepts. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure RepDim corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class C with sample complexity m implies RepDim(C) = O(m), and that there exists a private learning algorithm with sample complexity m = O(RepDim(C)).

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.

The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2O(n), wherenis the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz, who proved that there exist access structures withnparticipants such that the size of the share of at least one party isn/logntimes the secret size. Csirmaz's proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω(n) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. In fact, it was proved that there are infinity many independent information inequalities even in four variables. This raises the hope that these inequalities can help in improving the lower bounds beyondn. However, we show that any information inequality with four or five variables cannot prove a lower bound of ω(n) on the share size. In addition, we show that the same negative result holds for all information inequalities with more than five variables that are known to date.

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms -- efficient algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information.For functions, [Feigenbaum et al., ICALP 2001] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to search problems is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms -- applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. Although our privacy requirement seems minimal, we show that for well studied problems, as vertex cover and 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similar to [Halevi et al., STOC 2001], we define a relaxed notion of approximation algorithms that leak (little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for 3SAT that leak little information.

Weighted threshold secret sharing was introduced by Shamir in his seminal work on secret sharing. In such settings, there is a set of users where each user is assigned a positive weight. A dealer wishes to distribute a secret among those users so that a subset of users may reconstruct the secret if and only if the sum of weights of its users exceeds a certain threshold. On one hand, there are nontrivial weighted threshold access structures that have an ideal scheme—a scheme in which the size of the domain of shares of each user is the same as the size of the domain of possible secrets (this is the smallest possible size for the domain of shares). On the other hand, other weighted threshold access structures are not ideal. In this work we characterize all weighted threshold access structures that are ideal. We show that a weighted threshold access structure is ideal if and only if it is a hierarchical threshold access structure (as introduced by Simmons), or a tripartite access structure (these structures generalize the concept of bipartite access structures due to Padró and Sáez), or a composition of two ideal weighted threshold access structures that are defined on smaller sets of users. We further show that in all those cases the weighted threshold access structure may be realized by a linear ideal secret sharing scheme. The proof of our characterization relies heavily on the strong connection between ideal secret sharing schemes and matroids, as proved by Brickell and Davenport.

Secret-sharing schemes are a tool used in many cryptographic protocols. In these schemes, a dealer holding a secret string distributes shares to the parties such that only authorized subsets of participants can reconstruct the secret from their shares. The collection of authorized sets is called an access structure. An access structure is ideal if there is a secret-sharing scheme realizing it such that the shares are taken from the same domain as the secrets. Brickell and Davenport (Journal of Cryptology, 1991) have shown that ideal access structures are closely related to matroids. They give a necessary condition for an access structure to be ideal-the access structure must be induced by a matroid. Seymour (Journal of Combinatorial Theory B, 1992) has proved that the necessary condition is not sufficient: There exists an access structure induced by a matroid that does not have an ideal scheme. The research on access structures induced by matroids is continued in this work. The main result in this paper is strengthening the result of Seymour. It is shown that in any secret-sharing scheme realizing the access structure induced by the Vamos matroid with domain of the secrets of size k, the size of the domain of the shares is at least k + Omega(radic(k)). The second result considers nonideal secret-sharing schemes realizing access structures induced by matroids. It is proved that the fact that an access structure is induced by a matroid implies lower and upper bounds on the size of the domain of shares of subsets of participants even in nonideal schemes (as long as the shares are still relatively short). This generalized results of Brickell and Davenport for ideal schemes. Finally, an example of a nonideal access structure that is nearly ideal is presented.

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone. However, the naive way of computing them is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we bypass this addition step and construct a polynomial size logarithmic depth unbounded fan-in monotone circuit for every weighted threshold function, i.e., we show that weighted threshold functions are in mAC. (To the best of our knowledge, prior to our work no polynomial monotone circuits were known for weighted threshold functions). Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes. Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure. Specifically, we get: (1) information-theoretic secret sharing schemes where the size of each share is quasi-polynomial in the number of users, and (2) computational secret sharing schemes where the size of each share is polynomial in the number of users.

Monotone span programs represent a linear-algebraic model of computation. They are equivalent to linear secret sharing schemes and have various applications in cryptography and complexity. A fundamental question regarding them is how the choice of the field in which the algebraic operations are performed affects the power of the span program. In this paper we prove that the power of monotone span programs over finite fields of different characteristics is incomparable; we show a superpolynomial separation between any two fields with different characteristics, solving an open problem of Pudlák and Sgall [Algebraic models of computation and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 39, P. W. Beame and S. Buss, eds., AMS, Providence, RI, 1998, pp. 279--296]. Using this result we prove a superpolynomial lower bound for monotone span programs for a function in uniform-${\cal N}C^2$ (and therefore in ${\cal P}$), solving an open problem of Babai, Gál, and Wigderson [Combinatorica, 19 (1999), pp. 301--319]. (All previous superpolynomial lower bounds for monotone span programs were for functions not known to be in ${\cal P}$.) Finally, we show that quasi-linear secret sharing schemes, a generalization of linear secret sharing schemes introduced in Beimel and Ishai [On the power of nonlinear secret-sharing, in Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 188--202], are stronger than linear secret sharing schemes. In particular, this proves, without any assumptions, that nonlinear secret sharing schemes are more efficient than linear secret sharing schemes.

An erasure correcting scheme is rateless if it is designed to tolerate any pattern of packet loss and reveal the information sent after a certain number of packets are received. On one hand, transmission schemes that use rateless erasure correcting usually do not use the feedback channel, however they may require an additional significant amount of processing in both the sender and the receiver sides. On the other hand, automatic repeated request (ARQ) protocols use the feedback channel to assist the sender and usually do not require information processing. In this work we present a combined approach where a lean feedback channel is used to assist the sender to efficiently transmit the information. Our real-time oblivious approach minimizes the processing and memory required at the receiver, and therefore may fit a variety of receiving devices. In addition, the transmission is real-time where the expected number of original packets revealed when a packet is received is approximately the same through the entire transmission process. We may use our end-to-end scheme as a base for broadcast (and multicast) schemes. An overlay tree structure is used to convey the information to a large number of receivers. Moreover, the receivers may download the information from a number of senders or even migrate from one sender to another.

No abstract available.

Monotone span programs are a linear-algebraic model of computation. They are equivalent to linear secret sharing schemes and have various applications in cryptography and complexity. A fundamental question is how the choice of the field in which the algebraic operations are performed effects the power of the span program. In this paper we prove that the power of monotone span programs over finite fields of different characteristics is incomparable; we show a super-polynomial separation between any two fields with different characteristics, answering an open problem of Pudlak and Sgall (1998). Using this result we prove a super-polynomial lower bound for monotone span programs for a function in uniform - /spl Nscr/;/spl Cscr/;/sup 2/ (and therefore in /spl Pscr/;), answering an open problem of Babai, Wigderson, and Gal (1999). Finally, we show that quasi-linear schemes, a generalization of linear secret sharing schemes introduced in Beimel and Ishai (2001), are stronger than linear secret sharing schemes. In particular, this proves, without any assumptions, that non-linear secret sharing schemes are more efficient than linear secret sharing schemes.

Reliable communication between parties in a network is a basic requirement for executing any protocol. Dolev [4] and Dolev et al. [5] showed that reliable communication is possible if and only if the communication network is sufficiently connected. Beimel and Franklin [1] showed that the connectivity requirement can be relaxed if some pairs of parties share authentication keys. That is, costly communication links can be replaced by authentication keys.In this work, we continue this line of research. We consider the scenario where there is a speciiic sender and a specific receiver. In this case, the protocol of [1] has no(n) rounds even if there is a single Byzantine processor. We present a more efficient protocol with round complexity of (n/t)o(t), where n is the number of processors in the network and t is an upper bound on the number of Byzantine processors in the network. Specifically, our protocol is polynomial when the number of Byzantine processors is O(1), and for every t its round complexity is bounded by 2O(n). The same improvements hold for reliable and private communication. The improved protocol is obtained by analyzing the properties of a "communication and authentication graph" that characterizes reliable communication.

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.

A secret-sharing scheme enables a dealer to distribute a secret among no parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The (monotone) collection of authorized sets is called an access structure, and is freely identified with its characteristic monotone function f: {0, 1}/sup n//spl rarr/{0, 1}. A family of secret-sharing schemes is called efficient if the total length of the n shares is polynomial in n. Most previously known secret-sharing schemes belonged to a class of linear schemes, whose complexity coincides with the monotone span program size of their access structure. Prior to this work there was no evidence that nonlinear schemes can be significantly more efficient than linear schemes, and in particular there were no candidates for schemes efficiently realizing access structures which do not lie in NC. The main contribution of this work is the construction of two efficient nonlinear schemes: (1) A scheme with perfect privacy whose access structure is conjectured not to lie in NC; (2) A scheme with statistical privacy whose access structure is conjectured not to lie to P/poly. Another contribution is the study of a class of nonlinear schemes, termed quasi-linear schemes, obtained by composing linear schemes over different fields. We show that while these schemes are possibly (super-polynomially) more powerful than linear schemes, they cannot efficiently realize access structures outside NC.

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.

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

We consider the model of arithmetic branching programs, which is a generalization of modular branching programs. We show that, up to a polynomial factor in size, arithmetic branching programs are equivalent to complements of dependency programs. Using this equivalence we prove that dependency programs are closed under conjunction over every field. Furthermore, we show that span programs, an algebraic model of computation introduced by M. Karchmer and A. Wigderson (1993), are at least as strong as arithmetic programs; every arithmetic program can be simulated by a span program of size nod more than twice the size of the arithmetic program. Using the above results we give a new proof that NL/poly/spl sube//spl oplus/L/poly, first proved by A. Wigderson (1995). Our simulation of NL/poly is more efficient, and it holds for logspace counting classes over every field.

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

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.

A (g, b) key distribution scheme allows conferences of g users to generate secret keys, such that disjoint coalitions of b users cannot gain any information on the generated key (in the information-theoretic sense). We study the relationships between communication and space efficiency of key distribution schemes. We prove that communication does not help in the context of unrestricted schemes. On the other hand, we show that for restricted schemes, which are secure only when used by a limited number of conferences, communication can substantially improve the space efficiency. We also present lower bounds on the space efficiency of restricted schemes.

Span programs provide a linear algebraic model of computation. Lower Bounds for span programs imply lower bounds for formula size, symmetric branching programs and for contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a technique for proving lower bounds for monotone span programs, and prove a lower bound of Ω(m/sup 2.5/) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.

Given a set of parties {1, /spl middot//spl middot//spl middot/, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions.>