Secure function computation has been thoroughly studied and optimized
in the past decades. We extend techniques used for secure computation
to simulate arbitrary protocols involving a mediator. The key feature
of our notion of simulation is that it is bidirectional: not only
does the simulation produce only outputs that could happen in the
original protocol, but the simulation produces all such outputs. In
asynchronous systems there are also new subtleties that arise because
the scheduler can influence the output. Thus, these requirements
cannot be achieved by the standard notion of secure computation. We
provide a construction that is secure if n > 4t, where t is the
number of malicious agents, which is provably the best possible.
We also show that our construction is secure in the universal composability model and
that it satisfies additional security properties even if 3t < n \le 4t.
more »
« less
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents
Abraham, Dolev, Geffner, and Halpern [ 1 ] proved that, in asynchronous systems, a (k, t)robust equilibrium for n players and a trusted mediator can be implemented without the mediator as long as n > 4( k+t ), where an equilibrium is ( k, t )robust if, roughly speaking, no coalition of t players can decrease the payoff of any of the other players, and no coalition of k players can increase their payoff by deviating. We prove that this bound is tight, in the sense that if n ≤ 4( k+t ) there exist ( k, t )robust equilibria with a mediator that cannot be implemented by the players alone. Even though implementing ( k, t )robust mediators seems closely related to implementing asynchronous multiparty ( k+t )secure computation [ 6 ], to the best of our knowledge there is no known straightforward reduction from one problem to another. Nevertheless, we show that there is a nontrivial reduction from a slightly weaker notion of ( k+t )secure computation, which we call ( k+t )strict secure computation , to implementing ( k, t )robust mediators. We prove the desired lower bound by showing that there are functions on n variables that cannot be ( k+t )strictly securely computed if n ≤ 4( k+t ). This also provides a simple alternative proof for the wellknown lower bound of 4 t +1 on asynchronous secure computation in the presence of up to t malicious agents [ 4 , 8 , 10 ].
more »
« less
 Award ID(s):
 1703846
 NSFPAR ID:
 10414134
 Date Published:
 Journal Name:
 Journal of the ACM
 Volume:
 70
 Issue:
 2
 ISSN:
 00045411
 Page Range / eLocation ID:
 1 to 21
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


A mediator can help noncooperative agents obtain an equilibrium that may otherwise not be possible. We study the ability of players to obtain the same equilibrium without a mediator, using only cheap talk, that is, nonbinding preplay communication. Previous work has considered this problem in a synchronous setting. Here we consider the effect of asynchrony on the problem, and provide upper bounds for implementing mediators. Considering asynchronous environments introduces new subtleties, including exactly what solution concept is most appropriate and determining what move is played if the cheap talk goes on forever. Different results are obtained depending on whether the move after such ``infinite play'' is under the control of the players or part of the description of the game.more » « less

We consider computational games, sequences of games G = (G1,G2,...) where, for all n, Gn has the same set of players. Computational games arise in electronic money systems such as Bitcoin, in cryptographic protocols, and in the study of generative adversarial networks in machine learning. Assuming that oneway functions exist, we prove that there is 2player zerosum computational game G such that, for all n, the size of the action space in Gn is polynomial in n and the utility function in Gn is computable in time polynomial in n, and yet there is no εNash equilibrium if players are restricted to using strategies computable by polynomialtime Turing machines, where we use a notion of Nash equilibrium that is tailored to computational games. We also show that an εNash equilibrium may not exist if players are constrained to perform at most T computational steps in each of the games in the sequence. On the other hand, we show that if players can use arbitrary Turing machines to compute their strategies, then every computational game has an εNash equilibrium. These results may shed light on competitive settings where the availability of more running time or faster algorithms can lead to a “computational arms race”, precluding the existence of equilibrium. They also point to inherent limitations of concepts such as “best response” and Nash equilibrium in games with resourcebounded players.more » « less

Cussens, James ; Zhang, Kun (Ed.)We investigate the problem of combinatorial multiarmed bandits with stochastic submodular (in expectation) rewards and fullbandit feedback, where no extra information other than the reward of selected action at each time step $t$ is observed. We propose a simple algorithm, ExploreThenCommit Greedy (ETCG) and prove that it achieves a $(11/e)$regret upper bound of $\mathcal{O}(n^\frac{1}{3}k^\frac{4}{3}T^\frac{2}{3}\log(T)^\frac{1}{2})$ for a horizon $T$, number of base elements $n$, and cardinality constraint $k$. We also show in experiments with synthetic and realworld data that the ETCG empirically outperforms other fullbandit methods.more » « less

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)We study the time complexity of the discrete kcenter problem and related (exact) geometric set cover problems when k or the size of the cover is small. We obtain a plethora of new results:  We give the first subquadratic algorithm for rectilinear discrete 3center in 2D, running in Õ(n^{3/2}) time.  We prove a lower bound of Ω(n^{4/3δ}) for rectilinear discrete 3center in 4D, for any constant δ > 0, under a standard hypothesis about triangle detection in sparse graphs.  Given n points and n weighted axisaligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimumweight cover of the points by 3 unit squares, running in Õ(n^{8/5}) time. We also prove a lower bound of Ω(n^{3/2δ}) for the same problem in 2D, under the wellknown APSP Hypothesis. For arbitrary axisaligned rectangles in 2D, our upper bound is Õ(n^{7/4}).  We prove a lower bound of Ω(n^{2δ}) for Euclidean discrete 2center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of Õ(n^ω), if the matrix multiplication exponent ω is equal to 2.  We similarly prove an Ω(n^{kδ}) lower bound for Euclidean discrete kcenter in O(k) dimensions for any constant k ≥ 3, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if ω = 2.  We also prove an Ω(n^{2δ}) lower bound for the problem of finding 2 boxes to cover the largest number of points, given n points and n boxes in 12D . This matches the straightforward nearquadratic upper bound.more » « less