We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least Ω(log n) random bits are necessary for the t-private computation of the function xor by n players, for any t ≥ 2. In view of the upper bound of O(t2log(n/t))[19], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give stronger lower bounds of Ω(t log (n/t)). We note that all known randomness efficient private protocols designed specifically for xor belong to this class. All our lower bounds hold for the "trusted dealer" model as well, and the Ω(t log (n/t)) lower bound for restricted protocols is tight, up to constant factors, for any t ≥ 2 in this model.In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 ≤ t = o(log n). Our results also show that already for t = 2, Ω(log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players.Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.
We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least Ω(log n) random bits are necessary for the t-private computation of the function xor by n players, for any t ≥ 2. In view of the upper bound of O(t2log(n/t))[19], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give stronger lower bounds of Ω(t log (n/t)). We note that all known randomness efficient private protocols designed specifically for xor belong to this class. All our lower bounds hold for the "trusted dealer" model as well, and the Ω(t log (n/t)) lower bound for restricted protocols is tight, up to constant factors, for any t ≥ 2 in this model.In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 ≤ t = o(log n). Our results also show that already for t = 2, Ω(log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players.Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.
We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least Ω(log n) random bits are necessary for the t-private computation of the function xor by n players, for any t ≥ 2. In view of the upper bound of O(t2log(n/t))[19], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give stronger lower bounds of Ω(t log (n/t)). We note that all known randomness efficient private protocols designed specifically for xor belong to this class. All our lower bounds hold for the "trusted dealer" model as well, and the Ω(t log (n/t)) lower bound for restricted protocols is tight, up to constant factors, for any t ≥ 2 in this model.In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 ≤ t = o(log n). Our results also show that already for t = 2, Ω(log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players.Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.
In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of 1-private computation of n-party AND, the exact complexity is unknown. We study two settings. First, we consider the model of Goyal, Ishai, and Song (Crypto '22) where helper parties without any inputs are allowed to assist in the computation. In this setting, we show that two random bits always suffice to compute an arbitrary Boolean circuit C 1-privately: a single designated inputless helper flips the two bits and privately distributes the derived one-time bits to the other helper parties and the input parties as they are needed. We give an explicit construction using seven helper parties per AND gate and three helper parties per XOR gate (plus the single global randomness dealer). Moreover, two random bits are necessary already for the AND functionality (by a reduction to the standard no-helper model together with the lower bound of Kushilevitz, Ostrovsky, Prouff, Rosén, Thillard and Vergnaud (TCC '19), and therefore the worst-case helper-party randomness complexity is exactly 2 bits. Second, in the setting without helper parties, we improve the upper bound from Couteau and Rosén (Asiacrypt '22) on the (asymptotic) randomness complexity of n-party AND from 6 to 5 bits. That is, we give a 1-private protocol for computing the AND of n parties' inputs requiring 5 bits of randomness, for all n ≥ 6. Our construction, like that of Couteau and Rosén, uses a single party to flip the 5 bits and distribute the required derived values during the execution. Our approach to both problems is built around a more systematic exploration of techniques for recycling randomness across sub-computations. As part of resolving the second problem, we isolate an exact local-independence combinatorial object called a Sliding-Window Independence Generator, or a SWIG. A (k,m)-SWIG is a linear generator from a k-bit seed to m ≥ k output bits, where every cyclic length-k sliding window chosen from m output bits is perfectly uniform. We give an explicit (k,m)-SWIG for every k ≥ 1 and every m ≥ k and use a (5,n-1)-SWIG in our no-helper AND protocol.
We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k -party, n -bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is Ω ( n ).
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 ℓ 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 ℓ random bits between the computations. Moreover, we prove that our protocols are optimal in the amount of randomness they require.
In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.
We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation in the standard model with n = 2t+1 parties of which t are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn or not learn the output. Specifically, we show that there is a function H^* such that for any protocol that evaluates y_i = b_i ⋅ f(x₁,...,x_n) with perfect passive security (where b_i is a private boolean input), the total communication must be at least 1/2 ∑_{i = 1}ⁿ H_f^*(x_i) bits of information. The second lower bound applies to the perfect maliciously secure setting with n = 3t+1 parties. We show that for any n and all large enough S, there exists a reactive functionality F_S taking an S-bit string as input (and with short output) such that any protocol implementing F_S with perfect malicious security must communicate Ω(nS) bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any n and all large enough g ∈ ℕ there exists a reactive functionality F_C doing computation specified by a Boolean circuit C with g gates, where any perfectly secure protocol implementing F_C must communicate Ω(n g) bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lg n off for Boolean circuits). Both results also extend to the case where the threshold t is suboptimal. Namely if n = kt+s the bound is weakened by a factor O(s), which corresponds to known optimizations via packed secret-sharing.