Varsha Dani
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Varsha Dani has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Jared Saia
University of New Mexico
7 shared publications - Mahnush Movahedi
University of New Mexico
5 shared publications - Thomas P. Hayes
Department of Computer Science University of New Mexico
5 shared publications - Alexander Russell
University of Connecticut, USA
2 shared publications - Cristopher Moore
Santa Fe Institute
2 shared publications - Maxwell Young
Department of Computer Science and Engineering Mississippi State University 39762 MS USA
2 shared publications
Latest Publications
- 1 August 2018
- Published by Elsevier in Information and Computation
- Vol. 261, 464-486
Interactive communication with unknown noise rate
- 1 August 2018
- Published by Elsevier in Information and Computation
- Vol. 261, 464-486
Interactive communication with unknown noise rate
- Open Access
Distributed Computing with Channel Noise
A group of $n$ users want to run a distributed protocol $\pi$ over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows $\pi$, is able to maliciously flip bits on the channels. Can we efficiently simulate $\pi$ in the presence of such an adversary? We show that this is possible, even when $L$, the number of bits sent in $\pi$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $\pi$ that 1) fails with probability at most $\delta$, for any $\delta>0$; and 2) sends $\tilde{O}(L + T)$ bits, where the $\tilde{O}$ notation hides a $\log (nL/ \delta)$ term multiplying $L$. Additionally, we show how to improve this result when the average message size $\alpha$ is not constant. In particular, we give an algorithm that sends $O( L (1 + (1/\alpha) \log (n L/\delta) + T)$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $\alpha$. We note that if $\alpha$ is $\Omega\left( \log (n L/\delta) \right)$, then this improved algorithm sends only $O(L+T)$ bits, and is therefore within a constant factor of optimal.Open AccessDistributed Computing with Channel Noise
A group of $n$ users want to run a distributed protocol $\pi$ over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows $\pi$, is able to maliciously flip bits on the channels. Can we efficiently simulate $\pi$ in the presence of such an adversary? We show that this is possible, even when $L$, the number of bits sent in $\pi$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $\pi$ that 1) fails with probability at most $\delta$, for any $\delta>0$; and 2) sends $\tilde{O}(L + T)$ bits, where the $\tilde{O}$ notation hides a $\log (nL/ \delta)$ term multiplying $L$. Additionally, we show how to improve this result when the average message size $\alpha$ is not constant. In particular, we give an algorithm that sends $O( L (1 + (1/\alpha) \log (n L/\delta) + T)$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $\alpha$. We note that if $\alpha$ is $\Omega\left( \log (n L/\delta) \right)$, then this improved algorithm sends only $O(L+T)$ bits, and is therefore within a constant factor of optimal. - 19 October 2016
- Published by Wiley in Random Structures & Algorithms
- Vol. 49 (4) , 742-765
Codes, lower bounds, and phase transitions in the symmetric rendezvous problem
- 19 October 2016
- Published by Wiley in Random Structures & Algorithms
- Vol. 49 (4) , 742-765
Codes, lower bounds, and phase transitions in the symmetric rendezvous problem
- 26 September 2016
- Published by Springer Nature in Distributed Computing
- Vol. 30 (3) , 193-229
Secure multi-party computation in large networks
- 26 September 2016
- Published by Springer Nature in Distributed Computing
- Vol. 30 (3) , 193-229
Secure multi-party computation in large networks
- Open Access
Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem
In the rendezvous problem, two parties with different labelings of the vertices of a complete graph are trying to meet at some vertex at the same time. It is well-known that if the parties have predetermined roles, then the strategy where one of them waits at one vertex, while the other visits all $n$ vertices in random order is optimal, taking at most $n$ steps and averaging about $n/2$. Anderson and Weber considered the symmetric rendezvous problem, where both parties must use the same randomized strategy. They analyzed strategies where the parties repeatedly play the optimal asymmetric strategy, determining their role independently each time by a biased coin-flip. By tuning the bias, Anderson and Weber achieved an expected meeting time of about $0.829 n$, which they conjectured to be asymptotically optimal. We change perspective slightly: instead of minimizing the expected meeting time, we seek to maximize the probability of meeting within a specified time $T$. The Anderson-Weber strategy, which fails with constant probability when $T= \Theta(n)$, is not asymptotically optimal for large $T$ in this setting. Specifically, we exhibit a symmetric strategy that succeeds with probability $1-o(1)$ in $T=4n$ steps. This is tight: for any $\alpha < 4$, any symmetric strategy with $T = \alpha n$ fails with constant probability. Our strategy uses a new combinatorial object that we dub a "rendezvous code," which may be of independent interest. When $T \le n$, we show that the probability of meeting within $T$ steps is indeed asymptotically maximized by the Anderson-Weber strategy. Our results imply new lower bounds, showing that the best symmetric strategy takes at least $0.638 n$ steps in expectation. We also present some partial results for the symmetric rendezvous problem on other vertex-transitive graphs.Open AccessCodes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem
In the rendezvous problem, two parties with different labelings of the vertices of a complete graph are trying to meet at some vertex at the same time. It is well-known that if the parties have predetermined roles, then the strategy where one of them waits at one vertex, while the other visits all $n$ vertices in random order is optimal, taking at most $n$ steps and averaging about $n/2$. Anderson and Weber considered the symmetric rendezvous problem, where both parties must use the same randomized strategy. They analyzed strategies where the parties repeatedly play the optimal asymmetric strategy, determining their role independently each time by a biased coin-flip. By tuning the bias, Anderson and Weber achieved an expected meeting time of about $0.829 n$, which they conjectured to be asymptotically optimal. We change perspective slightly: instead of minimizing the expected meeting time, we seek to maximize the probability of meeting within a specified time $T$. The Anderson-Weber strategy, which fails with constant probability when $T= \Theta(n)$, is not asymptotically optimal for large $T$ in this setting. Specifically, we exhibit a symmetric strategy that succeeds with probability $1-o(1)$ in $T=4n$ steps. This is tight: for any $\alpha < 4$, any symmetric strategy with $T = \alpha n$ fails with constant probability. Our strategy uses a new combinatorial object that we dub a "rendezvous code," which may be of independent interest. When $T \le n$, we show that the probability of meeting within $T$ steps is indeed asymptotically maximized by the Anderson-Weber strategy. Our results imply new lower bounds, showing that the best symmetric strategy takes at least $0.638 n$ steps in expectation. We also present some partial results for the symmetric rendezvous problem on other vertex-transitive graphs. - Open Access
Secure Multi-Party Computation in Large Networks
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a $1/8$ fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide perfect and universally-composable security. To achieve our asynchronous MPC result, we define the \emph{threshold counting problem} and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model.Open AccessSecure Multi-Party Computation in Large Networks
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a $1/8$ fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide perfect and universally-composable security. To achieve our asynchronous MPC result, we define the \emph{threshold counting problem} and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model. - Open Access
Interactive Communication with Unknown Noise Rate
Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring $L$ bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires $a \ priori$ knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips $T$ bits, our algorithm sends $L + O\left(\sqrt{L(T+1)\log L} + T\right)$ bits in expectation and succeeds with high probability in $L$. It does so without any $a \ priori$ knowledge of $T$. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.Open AccessInteractive Communication with Unknown Noise Rate
Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring $L$ bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires $a \ priori$ knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips $T$ bits, our algorithm sends $L + O\left(\sqrt{L(T+1)\log L} + T\right)$ bits in expectation and succeeds with high probability in $L$. It does so without any $a \ priori$ knowledge of $T$. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown. - 13 November 2014
- Published by Springer Nature in Distributed Computing
- Vol. 28 (3) , 171-187
Scalable mechanisms for rational secret sharing
- 13 November 2014
- Published by Springer Nature in Distributed Computing
- Vol. 28 (3) , 171-187
Scalable mechanisms for rational secret sharing
- Open Access
Scalable Mechanisms for Rational Secret Sharing
We consider the classical secret sharing problem in the case where all agents are selfish but rational. In recent work, Kol and Naor show that, when there are two players, in the non-simultaneous communication model, i.e. when rushing is possible, there is no Nash equilibrium that ensures both players learn the secret. However, they describe a mechanism for this problem, for any number of players, that is an epsilon-Nash equilibrium, in that no player can gain more than epsilon utility by deviating from it. Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send O(n) messages in expectation, where n is the number of agents. This may be problematic for some applications of rational secret sharing such as secure multi-party computation and simulation of a mediator. We address this issue by describing mechanisms for rational secret sharing that are designed for large n. Both of our results hold for n > 2, and are Nash equilbria, rather than just epsilon-Nash equilbria. Our first result is a mechanism for n-out-of-n rational secret sharing that is scalable in the sense that it requires each agent to send only an expected O(log n) bits. Moreover, the latency of this mechanism is O(log n) in expectation, compared to O(n) expected latency for the Kol and Naor result. Our second result is a mechanism for a relaxed variant of rational m-out-of-n secret sharing where m = Theta(n). It requires each processor to send O(log n) bits and has O(log n) latency. Both of our mechanisms are non-cryptographic, and are not susceptible to backwards induction.
Open AccessScalable Mechanisms for Rational Secret Sharing
We consider the classical secret sharing problem in the case where all agents are selfish but rational. In recent work, Kol and Naor show that, when there are two players, in the non-simultaneous communication model, i.e. when rushing is possible, there is no Nash equilibrium that ensures both players learn the secret. However, they describe a mechanism for this problem, for any number of players, that is an epsilon-Nash equilibrium, in that no player can gain more than epsilon utility by deviating from it. Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send O(n) messages in expectation, where n is the number of agents. This may be problematic for some applications of rational secret sharing such as secure multi-party computation and simulation of a mediator. We address this issue by describing mechanisms for rational secret sharing that are designed for large n. Both of our results hold for n > 2, and are Nash equilbria, rather than just epsilon-Nash equilbria. Our first result is a mechanism for n-out-of-n rational secret sharing that is scalable in the sense that it requires each agent to send only an expected O(log n) bits. Moreover, the latency of this mechanism is O(log n) in expectation, compared to O(n) expected latency for the Kol and Naor result. Our second result is a mechanism for a relaxed variant of rational m-out-of-n secret sharing where m = Theta(n). It requires each processor to send O(log n) bits and has O(log n) latency. Both of our mechanisms are non-cryptographic, and are not susceptible to backwards induction.