We consider the "and" communication mechanism that inputs messages from two players and outputs the public signal "yes" if both messages are "yes", and outputs "no" otherwise. We prove that no correlation can securely be implemented through finite or infinite repetition of this mechanism.
One-sided output secure function evaluation is a cryptographic primitive where the two mutually distrustful players, Alice and Bob, both have a private input to a bivariate function. Bob obtains the value of the function for the given inputs, while Alice receives no output. It is known that this primitive cannot be securely implemented if the two players only have access to noiseless classical and quantum communication. In this work, we first show that Bob can extract the function values for all his possible inputs from any implementation of a non-trivial function that is correct and preserves the privacy of Bob's input. Our result holds in the non-asymptotic setting where the players have finite resources and the error is a constant. Then we consider protocols for secure function evaluation in a setup where the two players have access to trusted distributed randomness as a resource. Building upon the first result, we prove a bound on the efficiency of such cryptographic reductions for any non-trivial function in terms of the conditional entropies of the trusted randomness. From this result, we can derive lower bounds on the number of instances of different variants of OT needed to securely implement a given function.
We present two parallel repetition theorems for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our first theorem shows that for a k-player free game G with entangled value val∗(G)=1−ε, the n-fold repetition of G has entangled value val∗(G⊗n) at most (1−ε3/2)Ω(n/sk4), where s is the answer length of any player. In contrast, the best known parallel repetition theorem for the classical value of two-player free games is val(G⊗n)≤(1−ε2)Ω(n/s), due to Barak, et al. (RANDOM 2009). This suggests the possibility of a separation between the behavior of entangled and classical free games under parallel repetition. Our second theorem handles the broader class of free games G where the players can output (possibly entangled) quantum states. For such games, the repeated entangled value is upper bounded by (1−ε2)Ω(n/sk2). We also show that the dependence of the exponent on k is necessary: we exhibit a k-player free game G and n≥1 such that val∗(G⊗n)≥val∗(G)n/k. Our analysis exploits the novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa (ICALP 2014). We demonstrate that better communication protocols yield better parallel repetition theorems: our first theorem crucially uses a quantum search protocol by Aaronson and Ambainis, which gives a quadratic speed-up for distributed search problems. Finally, our results apply to a broader class of games than were previously considered before; in particular, we obtain the first parallel repetition theorem for entangled games involving more than two players, and for games involving quantum outputs.
We present a strong parallel repetition theorem for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our result is the first parallel repetition theorem for entangled games involving more than two players. Furthermore, our theorem applies to games where the players are allowed to output (possibly entangled) quantum states as answers. More specifically, let G be a k-player free game, with entangled value val∗(G)=1−ε. We show that the entangled value of the n-fold repetition of G, val∗(G⊗n), is at most (1−ε)Ω(n/k2). In the traditional setting of k=2 players, our parallel repetition theorem is optimal in terms of its dependence on ε and n. For an arbitrary number of players, our result is nearly optimal: for all k, we exhibit a k-player free game G and n>1 such that val∗(G⊗n)≥val∗(G)n/k. Hence, exponent of the repeated game value cannot be improved beyond Ω(n/k). Our parallel repetition theorem improves on the prior results of [Jain, et al. 2014] and [Chailloux, Scarpa 2014] in a number of ways: (1) our theorem applies to a larger class of games (arbitrary number of players, quantum outputs); (2) we demonstrate that strong parallel repetition holds for the entangled value of free games: i.e., the base of the repeated game value is 1−ε, rather than 1−ε2; and (3) there is no dependence of the repeated game value on the input and output alphabets of G. In contrast, it is known that the repeated game value of classical free games must depend on the output size. Thus our results demonstrate a seperation between the behavior of entangled games and classical games.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement.
We first introduce XOR Equality, a total Boolean function in which each of k players receives an unrestricted string xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) on total communication and Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/4. For n=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(n) qubits, whereas two public-coin bits per player suffice.
We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a k-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(logn), giving exponential separations in both regimes. The implicit constants are independent of k, and both quantum lower bounds become linear when k≥clogn for any fixed c>0.