Interleaved group products
share
Let G be the special linear group SL(2,q). We show that if (a_1,...,a_t) and (b_1,...,b_t) are sampled uniformly from large subsets A and B of G^t then their interleaved product a_1 b_1 a_2 b_2 ... a_t b_t is nearly uniform over G. This extends a result of the first author, which corresponds to the independent case where A and B are product sets. We obtain a number of other results. For example, we show that if X is a probability distribution on G^m such that any two coordinates are uniform in G^2, then a pointwise product of s independent copies of X is nearly uniform in G^m, where s depends on m only. Extensions to other groups are also discussed. We obtain closely related results in communication complexity, which is the setting where some of these questions were first asked by Miles and Viola. For example, suppose party A_i of k parties A_1,...,A_k receives on its forehead a t-tuple (a_i1,...,a_it) of elements from G. The parties are promised that the interleaved product a_11... a_k1a_12... a_k2... a_1t... a_kt is equal either to the identity e or to some other fixed element g∈ G, and their goal is to determine which of the two the product is equal to. We show that for all fixed k and all sufficiently large t the communication is Ω(t |G|), which is tight. Even for k=2 the previous best lower bound was Ω(t). As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola in the "only computation leaks" model.
READ FULL TEXT