## CryptoDB

### Ashish Choudhary

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Communication Efficient Perfectly Secure VSS and MPC in Asynchronous Networks with Optimal Resilience
Abstract

Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power.
It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n \geq 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n=4t+1 as optimally resilient VSS (MPC) protocol.
A secret is d-shared among the parties if there exists a random degree-d polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS) protocol that can generate d-sharing of secret for any d, where t \leq d \leq 2t. This is the first optimally resilient, perfectly secure AVSS of its kind in the literature. Specifically, our AVSS can generate d-sharing of \ell \geq 1 secrets from F concurrently, with a communication cost of O(\ell n^2 \log{|F|}) bits, where F is a finite field. Communication complexity wise, the best known optimally resilient, perfectly secure AVSS is reported in [BH07]. The protocol of [BH07] can generate t-sharing of \ell secrets concurrently, with the same communication complexity as our AVSS. However, the AVSS of [BH07] and [BCG93]
(the only known optimally resilient perfectly secure AVSS, other than [BH07]) does not generate d-sharing, for any d > t.
Interpreting in a different way, we may also say that our AVSS shares \ell(d+1 -t) secrets simultaneously with a communication cost of O(\ell n^2 \log{|F|}) bits. Putting d=2t (the maximum value of d), we notice that the amortized cost of sharing a single secret using our AVSS is only O(n \log{|F|}) bits. This is a clear improvement over the AVSS of [BH07] whose amortized cost of sharing a single secret is O(n^2 \log{|F|}) bits.
As an interesting application of our AVSS, we propose a new optimally resilient, perfectly secure Asynchronous Multiparty Computation (AMPC) protocol that communicates O(n^2 \log|F|) bits per multiplication gate. The best known optimally resilient perfectly secure AMPC is due to [BH07], which communicates O(n^3 \log|F|) bits per multiplication gate. Thus our AMPC improves the communication complexity of the best known AMPC of [BH07] by a factor of \Omega(n).

2010

EPRINT

Protocols for Reliable and Secure Message Transmission
Abstract

Consider the following problem: a sender S and a receiver R are part of an unreliable, connected, distributed network. The distrust in the network is modelled by an entity called adversary, who has unbounded
computing power and who can corrupt some of the nodes of the network (excluding S and R)in a variety of ways. S wishes to send to R a message m that consists of \ell elements, where \ell \geq 1, selected uniformly from a finite field F. The challenge is to design a protocol, such that after interacting with S as per the protocol, R should output m without any error (perfect reliability). Moreover, this hold irrespective of the disruptive actions done by the adversary. This problem is called reliable message transmission or RMT in short. The problem of secure message transmission or SMT in short requires an additional constraint that the adversary should not get any information about the message what so ever in information theoretic sense (perfect secrecy). Security against an adversary with infinite computing power is also known as non-cryptographic or information theoretic or Shannon security and this is the strongest notion of security. Notice that since the adversary has unbounded computing power, we cannot solve RMT and SMT problem by using classical cryptographic primitives such as public key cryptography, digital signatures, authentication schemes, etc as the security of all these primitives holds good only against an adversary having polynomially bounded computing power.
RMT and SMT problem can be studied in various network models and adversarial settings. We may use the following parameters to describe
different settings/models for studying RMT/SMT:
\begin{enumerate}
\item Type of Underlying Network --- Undirected Graph, Directed Graph, Hypergraph.
\item Type of Communication --- Synchronous, Asynchronous.
\item Adversary capacity --- Threshold Static, Threshold Mobile, Non-threshold Static, Non-threshold Mobile.
\item Type of Faults --- Fail-stop, Passive, Byzantine, Mixed.
\end{enumerate}
Irrespective of the settings in which RMT/SMT is studied, the following issues are common:
\begin{enumerate}
\item Possibility: What are the necessary and sufficient structural conditions to be satisfied by the underlying network for the existence of any RMT/SMT protocol, tolerating a given type of adversary?
\item Feasibility: Once the existence of a RMT/SMT protocol in a network is ascertained, the next natural question is, does there exist an efficient protocol on the given network?
\item Optimality: Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any RMT/SMT protocol to transmit the message and how to design a polynomial time RMT/SMT protocol whose total communication complexity matches the lower bound on the communication complexity (optimal protocol)?
\end{enumerate}
In this dissertation, we look into the above issues in several network models and adversarial settings. This thesis reports several new/improved/efficient/optimal solutions, gives affirmative/negative answers to several significant open problems and last but not the least, provides first solutions to several newly formulated problems.

2009

EPRINT

Unconditionally Secure Asynchronous Multiparty Computation with Quadratic Communication
Abstract

Secure multiparty computation (MPC) allows a set of $n$ parties to securely compute an agreed function, even if up to $t$ parties are under the control of an adversary. In this paper, we propose a new Asynchronous secure multiparty computation (AMPC) protocol that provides information theoretic security with $n = 4t+1$, where $t$ out of $n$ parties can be under the influence of a Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^2 \log|{\mathbb F}|) bits per multiplication and involves a negligible error probability of $2^{-\Omega(\kappa)}$, where $\kappa$ is the error parameter and ${\mathbb F}$ is the field over which the computation is carried out. The best known information theoretically secure AMPC with $n=4t+1$ communicates
O(n^3 \log|{\mathbb F}|) bits per multiplication and does not involve any error probability in computation. Though a negligible error probability is involved, our AMPC protocol provides the best communication complexity among all the known AMPC protocols providing information theoretic security. Moreover, the communication complexity of our AMPC is same as the communication complexity of the best known AMPC protocol with cryptographic assumptions. As a tool for our AMPC protocol, we propose a new method of efficiently generating (t,2t)-sharing of multiple secrets concurrently in asynchronous setting, which is of independent interest.

2008

EPRINT

Efficient Perfectly Reliable and Secure Communication Tolerating Mobile Adversary
Abstract

We study the problem of Perfectly Reliable Message Transmission}(PRMT) and Perfectly Secure Message Transmission (PSMT) between two nodes S and R in an undirected synchronous network, a part of which is under the influence of an all powerful mobile Byzantine adversary. In ACISP 2007 Srinathan et. al. has proved that the connectivity requirement for PSMT protocols is same for both static and mobile adversary thus showing that mobility of the adversary has no effect on the possibility of PSMT (also PRMT) protocols. Similarly in CRYPTO 2004, Srinathan et. al. has shown that the lower bound on the communication complexity of any multiphase PSMT protocol is same for static and mobile adversary. The authors have also designed a $O(t)$ phase (A phase is a send from S to R or R to S or both) protocol satisfying this bound where $t$ is the maximum number of nodes corrupted by the Byzantine adversary. In this work, we design a three phase bit optimal PSMT protocol using a novel technique, whose communication complexity
matches the lower bound proved in CRYPTO 2004 and thus significantly reducing the number of phases from $O(t)$ to three.
Further using our novel technique, we design a three phase bit optimal
PRMT protocol which achieves reliability with constant factor overhead against a mobile adversary. These are the first ever constant phase optimal PRMT and PSMT protocols against mobile Byzantine adversary.
We also characterize PSMT protocols in directed networks tolerating mobile adversary.
All the existing PRMT and PSMT protocols abstracts the paths between S and R as wires, neglecting the intermediate nodes in the paths. However, this causes significant over estimation in the communication complexity as well as round complexity (Round is different from phase. Round is a send from one node to its immediate neighbor in the network} of protocols. Here, we consider the underlying paths
as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication from S to R tolerating a mobile adversary with arbitrary roaming speed (By roaming speed we mean the speed with which the adversary changes the set of corrupted node). We show how our constant phase PRMT and PSMT protocols can be easily adapted to design round optimal and bit optimal PRMT and PSMT protocols provided the network is given as a collection of vertex disjoint paths.

2008

EPRINT

Probabilistic Verifiable Secret Sharing Tolerating Adaptive Adversary
Abstract

In this work we focus on two basic secure distributed computation tasks- Probabilistic Weak Secret Sharing (PWSS) and Probabilistic Verifiable Secret Sharing (PVSS). PVSS allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret with negligible error probability. PWSS is slightly weaker version of PVSS where the dealer can choose not to disclose his secret later. Both of them are well-studied problems. While PVSS is used as a building block in every general probabilistic secure multiparty computation, PWSS can be used as a building block for PVSS protocols. Both these problems can be parameterized by the number of players ($n$) and the fault tolerance threshold ($t$) which bounds the total number of malicious (Byzantine) players having {\it unbounded computing power}. We focus on the standard {\it secure channel model}, where all players have access to secure point-to-point channels and a common broadcast medium. We show the following for PVSS: (a) 1-round PVSS is possible iff $t=1$ and $n>3$ (b) 2-round PVSS is possible if $n>3t$ (c) 4-round PVSS is possible if $n>2t$. For the PWSS we show the following: (a) 1-round PWSS is possible iff $n>3t$ and (b) 3-round PWSS is possible if $n>2t$. All our protocols are {\it efficient}. Comparing our results with the existing trade-off
results for perfect (zero error probability) VSS and WSS, we find that probabilistically relaxing the conditions of VSS/WSS helps to increase fault tolerance significantly.

2008

EPRINT

Unconditionally Reliable and Secure Message Transmission in Undirected Synchronous Networks: Possibility, Feasibility and Optimality
Abstract

We study the interplay of network connectivity and the issues related to the possibility, feasibility and optimality for {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in an undirected {\it synchronous} network, under the influence of an adaptive {\it mixed} adversary ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$, who has
{\it unbounded computing power} and can corrupt $t_b$, $t_o$, $t_f$
and $t_p$ nodes in the network in Byzantine, {\it omission}, {\it
fail-stop} and passive fashion respectively. In URMT problem, a sender {\bf S} and a receiver {\bf R} are part of a distributed network, where {\bf S} and {\bf R} are connected by intermediate nodes, of which at most $t_b, t_o, t_f$ and $t_p$ nodes can be under the control of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. {\bf S} wants to send a message $m$ which is a sequence of $\ell$ field elements from a finite field ${\mathbb F}$ to {\bf R}. The challenge is to design a protocol,
such that after interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or viceversa.} as per the protocol, {\bf R} should output $m' = m$ with probability at least $1 - \delta$, where
$0 < \delta < \frac{1}{2}$. Moreover, this should happen, irrespective of the adversary strategy of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. The USMT problem has an additional requirement that ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$ should not know anything about $m$ in {\it information theoretic} sense.
In this paper, we answer the following in context of URMT and USMT: (a) {\sc Possibility:} when is a protocol possible in a given network? (b) {\sc Feasibility:} Once the existence of a protocol is ensured then does there exists a polynomial time protocol on the given network? (c) {\sc Optimality: } Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any protocol to transmit the message and how to design a protocol whose total communication complexity matches the lower bound on the communication complexity? Finally we also show that {\it allowing a negligible error probability significantly helps in the possibility, feasibility and optimality of both reliable and secure message transmission protocols.} To design our protocols, we propose several new techniques which are of independent interest.

2008

EPRINT

On Round Complexity of Unconditionally Secure VSS
Abstract

In this work, we initiate the study of round complexity of
{\it unconditionally secure weak secret sharing} (UWSS)
and {\it unconditionally secure verifiable secret sharing}
(UVSS) \footnote{In the literature, these problems
are also called as statistical WSS and statistical
VSS \cite{GennaroVSSSTOC01} respectively.}
in the presence of an {\it all powerful} $t$-active adversary.
Specifically, we show the following for UVSS: (a) 1-round
UVSS is possible iff $t=1$ and $n>3$, (b) 2-round UVSS
is possible if $n>3t$ and (c) 5-round
{\it efficient} UVSS is possible if $n>2t$. For UWSS we show the following: (a)
1-round UWSS is possible iff $n>3t$ and
(b) 3-round UWSS is possible if $n>2t$.
Comparing our results with
existing results for trade-off between fault tolerance and round complexity of perfect (zero error)
VSS and WSS \cite{GennaroVSSSTOC01,FitziVSSTCC06,KatzVSSICALP2008},
we find that probabilistically relaxing the conditions of VSS/WSS helps to increase
fault tolerance significantly.

2008

EPRINT

Perfectly Reliable and Secure Communication Tolerating Static and Mobile Mixed Adversary
Abstract

In the problem of perfectly reliable message transmission} (PRMT), a sender {\bf S} and a receiver {\bf R} are connected by $n$ bidirectional synchronous channels. A mixed adversary
${\mathcal A}_{(t_b,t_f,t_p)}$ with {\it infinite computing power} controls $t_b, t_f$ and $t_p$ channels in Byzantine, fail-stop and passive fashion respectively. Inspite of the presence of ${\mathcal A}_{(t_b,t_f,t_p)}$, {\bf S} wants to reliably send a message $m$ to {\bf R}, using some protocol, without sharing any key with {\bf R} beforehand. After interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or vice-versa} as per the protocol, {\bf R} should output $m' = m$, without any error. In the problem of {\it perfectly secure message transmission} (PSMT), there is an
additional constraint that ${\mathcal A}_{(t_b,t_f,t_p)}$ should not know {\it any} information about $m$ in {\it information theoretic} sense. The adversary can be either static\footnote{A static adversary corrupts the same set of channels in each phase of the protocol. The choice of the channel to corrupt is decided before the beginning of the protocol.} or mobile.\footnote{A mobile adversary can corrupt different set of channels in different phases of the protocol.}
The {\it connectivity requirement}, {\it phase complexity} and {\it communication complexity} are three important parameters of any interactive PRMT/PSMT protocol and are well studied in the literature when the channels are controlled by a static/mobile Byzantine adversary. However, when the channels are controlled by mixed adversary ${\mathcal A}_{(t_b,t_f,t_p)}$ , we encounter several surprising consequences. In this paper, we study the problem of PRMT and PSMT tolerating "static/mobile mixed adversary". We prove that even though the connectivity requirement for PRMT is same against both static and mobile mixed adversary, the lower bound on communication complexity for PRMT tolerating mobile mixed adversary
is more than its static mixed counterpart. This is interesting because against only "Byzantine adversary", the connectivity requirement and the lower bound on the communication complexity of PRMT protocols are same for both static and mobile case. Thus our result shows that
for PRMT, mobile mixed adversary is more powerful than its static counterpart. As our second contribution, we design a four phase communication optimal PSMT protocol tolerating "static mixed adversary". Comparing this with the existing three phase communication
optimal PSMT protocol against "static Byzantine adversary", we find that additional one phase is enough to design communication optimal protocol against static mixed adversary. Finally, we show that the connectivity requirement and lower bound on communication complexity
of any PSMT protocol is same against both static and mobile mixed adversary, thus proving that mobility of the adversary has no effect in PSMT. To show that our bound is tight, we also present a worst case nine phase communication optimal PSMT protocol tolerating mobile mixed adversary which is first of it's kind. This also shows that the mobility of the adversary does not hinder to design constant phase communication optimal PSMT protocol. In our protocols, we have used new techniques which can be effectively used against both static and mobile mixed adversary and are of independent interest.

2008

EPRINT

Unconditionally Reliable and Secure Message Transmission in Directed Networks Revisited
Abstract

In this paper, we re-visit the problem of {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al \cite{Desmedt}
have given the necessary and sufficient condition for the existence of URMT and USMT protocols in directed networks. Though their protocols are efficient, they are not communication optimal. In this paper, we prove for the first time the lower bound on the communication complexity of URMT and USMT protocols in directed networks. Moreover, we show that our bounds are tight by giving efficient communication optimal URMT and USMT protocols, whose communication complexity satisfies our proven lower bounds.

2008

EPRINT

Unconditionally Reliable Message Transmission in Directed Hypergraphs
Abstract

We study the problem of unconditionally reliable message transmission (URMT), where two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed hypergraph, a part of which may be under the influence of an adversary having unbounded computing power. S intends to transmit a message $m$ to R, such that R should correctly obtain S's message with probability at least $(1-\delta)$ for arbitrarily small $\delta > 0$. However, unlike most of the literature on this problem, we assume the adversary modeling the faults is threshold mixed, and can corrupt different set of nodes in Byzantine, passive and fail-stop fashion simultaneously. The main contribution of this work is the complete characterization of URMT in directed hypergraph tolerating such an adversary. Working out a direct characterization of URMT over directed hypergraphs tolerating threshold mixed adversary is highly un-intuitive. So we first propose a novel technique, which takes as input a directed hypergraph and a threshold mixed adversary on that hypergraph and outputs a corresponding digraph, along with a non-threshold mixed adversary, such that URMT over the hypergraph tolerating the threshold mixed adversary is possible iff a special type of URMT is possible over the obtained digraph, tolerating the corresponding non-threshold mixed adversary}. Thus characterization of URMT over directed hypergraph tolerating threshold mixed adversary reduces to characterizing special type of a URMT over arbitrary digraph tolerating non-threshold mixed adversary. We then characterize URMT in arbitrary digraphs tolerating non-threshold mixed adversary
and modify it to obtain the characterization for special type of URMT over digraphs tolerating non-threshold mixed adversary. This completes the characterization of URMT over the original hypergraph.
Surprisingly, our results indicate that even passive corruption, in
collusion with active faults, substantially affects the reliability of URMT protocols! This is interesting because it is a general belief that passive corruption (eavesdropping) does not affect reliable communication.

2008

EPRINT

Efficient Asynchronous Multiparty Computation with Optimal Resilience
Abstract

We propose an efficient information theoretic secure asynchronous multiparty computation (AMPC) protocol with optimal fault tolerance; i.e., with $n = 3t+1$, where $n$ is the total number of parties and $t$ is the number of parties that can be under the influence of a Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^5 \kappa)$ bits per multiplication and involves a negligible error probability
of $2^{- O(\kappa)}$, where $\kappa$ is the error parameter. As
far as our knowledge is concerned, the only known AMPC protocol with $n = 3t+1$ providing information theoretic security with negligible error probability is due to \cite{BenOrPODC94AsynchronousMPC}, which communicates $\Omega(n^{11} \kappa^4)$ bits and A-Casts $\Omega(n^{11} \kappa^2 \log(n))$ bits per multiplication. Here A-Cast is an asynchronous broadcast primitive, which allows a party to send the same information to all other parties identically. Thus our AMPC protocol shows significant improvement in communication complexity over the AMPC protocol of \cite{BenOrPODC94AsynchronousMPC}. As a tool for our AMPC protocol, we introduce a new asynchronous primitive called Asynchronous Complete Verifiable Secret Sharing (ACVSS), which is first of its kind and is of independent interest. For designing our ACVSS, we employ a new asynchronous verifiable secret sharing (AVSS) protocol which is better than all known communication-efficient AVSS protocols with $n=3t+1$.

2008

EPRINT

On Communication Complexity of Perfectly Reliable and Secure Communication in Directed Networks
Abstract

In this paper, we re-visit the problem of {\it perfectly reliable message transmission} (PRMT) and {\it perfectly secure message transmission}(PSMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al have given the necessary and sufficient condition for the existence of PSMT protocols in directed networks. In this paper, we first show that the necessary and sufficient condition (characterization) given by Desmedt et.al does not hold for two phase\footnote{A phase is a send from sender to receiver or vice-versa.} PSMT protocols. Hence we provide a different necessary and sufficient condition for two phase PSMT in directed networks. We also derive the lower bound on communication complexity of two phase PSMT and show that our lower bound is {\it asymptotically tight} by designing a two phase PSMT protocol whose
communication complexity satisfies the lower bound. Though the characterization for three or more phase PSMT is resolved by the result of Desmedt et. al, the lower bound on communication
complexity for the same has not been investigated yet. Here we derive the lower bound on the communication complexity of three or more phase PSMT in directed networks and show that our lower bound is {\it asymptotically tight} by designing {\it communication optimal} PSMT protocols. Finally, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. By communication optimal PRMT
or PRMT with constant factor overhead, we mean that the PRMT protocol is able to send $\ell$ field elements by communicating $O(\ell)$ field elements from a finite field $\mathbb F$.
To design our protocols, we use several techniques, which are of independent interest.

2008

EPRINT

Unconditionally Secure Message Transmission in Arbitrary Directed Synchronous Networks Tolerating Generalized Mixed Adversary
Abstract

In this paper, we re-visit the problem of {\it unconditionally secure message transmission} (USMT) from a sender {\bf S} to a receiver {\bf R}, who are part of a distributed synchronous network, modeled as an {\it arbitrary} directed graph. Some of the intermediate nodes between {\bf S} and {\bf R} can be under the control of the adversary having {\it unbounded} computing power. Desmedt and Wang \cite{Desmedt} have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between {\bf S} and {\bf R}, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al \cite{Desmedt} does not hold good for {\it arbitrary} directed networks, where the intermediate nodes perform some computation, beside acting as message forwarding nodes.
We then give the {\it true} characterization of USMT in arbitrary directed networks. As far our knowledge
is concerned, this is the first ever {\it true} characterization of USMT in arbitrary directed networks.

2008

EPRINT

Simple and Efficient Asynchronous Byzantine Agreement with Optimal Resilience
Abstract

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t < n / 3 parties in Byzantine fashion. In these settings, we say that \pi is a $t$-resilient, $(1-\epsilon)$-terminating Asynchronous Byzantine Agreement (ABA) protocol, if $\pi$ satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating A_t and terminates (i.e every honest party terminates $\pi$) with probability at least $(1-\epsilon)$. In this work, we present a
new $t$-resilient, $(1-\epsilon)$-terminating ABA protocol which privately communicates O(C n^{5} \kappa) bits
and A-casts O(C n^{5} \kappa) bits, where $\epsilon = 2^{-O(\kappa)$ and C is the expected running time of the protocol.
Here A-Cast is a primitive in asynchronous world, allowing a party to send the same value to all the other parties. Hence A-Cast in asynchronous world is the parallel notion of broadcast in synchronous world. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time; i.e., C = O(1). Our ABA protocol is to be compared with the only known $t$-resilient, $(1-\epsilon)$-terminating ABA protocol of \cite{CanettiSTOC93} in the same settings, which privately communicates O(C n^{11} \kappa^{4}) bits and A-casts O(C n^{11} \kappa^2 \log(n)) bits, where
$\epsilon = 2^{-O(\kappa)} and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of \cite{CanettiSTOC93}, while keeping all other properties in place. In another landmark work, in PODC 2008,
Abraham et. al \cite{DolevAsynchronousBAPODC2008} proposed a $t$-resilient, $1$-terminating (called as almost-surely terminating in \cite{DolevAsynchronousBAPODC2008}) ABA protocol which communicates O(C n^{6} \log{n}) bits and A-casts O(C n^{6} \log{n}) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n^2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any \kappa < n^3 \log{n}, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in constant expected time (the constant is independent of n, t and \kappa), whereas ABA of Abraham et. al. takes polynomial expected time. However, it should be noted that our ABA is only $(1-\epsilon)$-terminating whereas ABA of Abraham et al. is almost-surely terminating. Summing up, in a practical scenario where a faster and communication efficient ABA protocol is required, our ABA fits the bill better than ABA protocols of \cite{CanettiSTOC93,DolevAsynchronousBAPODC2008}.
For designing our ABA protocol, we present a novel and simple asynchronous verifiable secret sharing (AVSS) protocol which significantly improves the communication complexity of the only known AVSS protocol of \cite{CanettiSTOC93} in the same settings. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest.

2008

EPRINT

Unconditionally Secure Multiparty Set Intersection Re-Visited
Abstract

In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model.
Li et.al \cite{LiSetMPCACNS07} have proposed a protocol
for $n$-party set intersection problem, which provides unconditional security when $t < \frac{n}{3}$ players are corrupted by an active adversary having {\it unbounded computing power}. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of ${\cal O}(n^4m^2)$, where each player has a set of size $m$. However, we show that the round complexity and communication complexity of the protocol in \cite{LiSetMPCACNS07} is much more than what is claimed
in \cite{LiSetMPCACNS07}. We then propose a {\it novel} unconditionally secure protocol for multiparty set intersection problem with $n > 3t$ players, which significantly improves the "actual" round and communication complexity (as shown in this paper) of the protocol given in \cite{LiSetMPCACNS07}. To design our protocol, we use several tools which are of independent interest.

#### Program Committees

- Asiacrypt 2014

#### Coauthors

- AshwinKumar B.V (3)
- Madhu Gayatri (1)
- Jake Loftus (1)
- Emmanuela Orsini (2)
- Arpita Patra (19)
- Tal Rabin (1)
- C. Pandu Rangan (16)
- Nigel P. Smart (3)
- Kannan Srinathan (5)