Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-127 | 12th August 2016 16:12

The multiparty communication complexity of interleaved group products



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$

ISSN 1433-8092 | Imprint