TR16-127 Authors: Timothy Gowers, Emanuele Viola

Publication: 12th August 2016 16:13

Downloads: 404

Keywords:

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on

its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of

elements from the group $G=\text{SL}(2,q)$. The parties

are promised that the interleaved product $a_{11}\dots

a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is

equal either to the identity $e$ or to some other fixed

element $g\in G$. Their goal is to determine which of $e$

and $g$ the interleaved product is equal to, using the

least amount of communication.

We show that for all fixed $k$ and all sufficiently large

$t$ the communication is $\Omega(t \log |G|)$, which is

tight. As an application, we establish the security of

the leakage-resilient circuits studied by Miles and Viola

(STOC 2013) in the ``only computation leaks'' model. Our

main technical contribution is of independent interest.

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.